Educational Codeforces Round 81 題解

Educational Codeforces Round 81 題解

A - Display The Number

肯定是1越多越好，因?yàn)槲粩?shù)越大越大，所以當(dāng)n是2的倍數(shù)的時(shí)候，全是1

但是n可能不是n的倍數(shù)，此時(shí)應(yīng)該有<svg xmlns:xlink="http://www.w3.org/1999/xlink" width="11.452ex" height="2.811ex" viewBox="0 -906.7 4930.7 1210.2" role="img" focusable="false" style="vertical-align: -0.705ex;" class="in-text-selection"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><text font-family="STIXGeneral,'Arial Unicode MS',serif" stroke="none" transform="scale(50.259) matrix(1 0 0 -1 0 0)">（</text><g transform="translate(3126,0)"><text font-family="STIXGeneral,'Arial Unicode MS',serif" stroke="none" transform="scale(50.259) matrix(1 0 0 -1 0 0)">）</text></g></g></svg>個(gè)和個(gè)，并且7在前面

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="cpp" cid="n5" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> #include <bits/stdc++.h>
using namespace std;

define ll long long

const int maxn = 2e5 + 10;
int main(){
ios_base::sync_with_stdio(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int cnt = n >> 1;
if(n & 1){
cout << 7;
cnt--;
}
while(cnt--){
cout << 1;
}
cout << endl;
}
return 0;
}</pre>

B - Infinite Prefixes

本題有幾點(diǎn)需要注意

1.如果所給是0，要特判空字符串情況，也就是初始為1，其他為0

2.循環(huán)的題目第一看循環(huán)節(jié)，我們知道題目不是求在哪個(gè)位置相等，而是求個(gè)數(shù)，所以只需要考慮第一節(jié)

3.分兩種情況，因?yàn)橐懦裏o窮的情況，假如一個(gè)循環(huán)節(jié)內(nèi)1的個(gè)數(shù)和0的相等，那么我們就需要遍歷一下這個(gè)循環(huán)節(jié)，如果存在滿足x的，那么一定有無窮個(gè)，否則是0個(gè)。

4.個(gè)數(shù)不相同的情況，那么我們可以想到，假設(shè)一個(gè)循環(huán)節(jié)差，滿足條件的情況肯定時(shí)t的倍數(shù)加上最后一個(gè)循環(huán)節(jié)中的部分差等于x

也就是說 ，找到一個(gè)這樣的情況 ，但是要注意的是，兩者必須是同號的，因?yàn)槟?shù)為0兩者不一定同號，如果不同號則沒有意義，是相反的。

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="cpp" cid="n16" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> #include <bits/stdc++.h>
using namespace std;

define ll long long

const int maxn = 2e5 + 10;
bool judge(int cur, int delta){
if(delta < 0){
delta = -delta;
cur = -cur;
}
if(cur < 0)
return false;
return cur % delta == 0;
}
void solve(){
int n, x;
cin >> n >> x;
string s;
cin >> s;
int delta = 0;
for (int i = 0; i < n; i++){
if(s[i] == '0')
delta++;
else
delta--;
}
int cur = 0, ans = 0;

for (int i = 0; i < n; i++){
if(delta == 0 && cur == x){
cout << -1 << endl;
return;
}
if(delta != 0 && judge(x-cur, delta))
ans++;
if(s[i]=='0')
cur++;
else
cur--;
}
cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(0);
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}</pre>

C - Obtain The String

本題是暴力題，思路很好想，只需要設(shè)計(jì)一個(gè)指針遍歷t字符串，答案不存在只有可能是t中字符串s中沒有

然后不停映射s就行，如果t中連續(xù)的子串不是s中的遞增的，那么就要ans++；

問題是實(shí)現(xiàn)方法，要是純暴力的搜，一定會(huì)TLE，所以要想一個(gè)巧妙的解法：

設(shè)置數(shù)組，代表字符串在當(dāng)前的字符位上下一個(gè)字符在字符串的向后最早出現(xiàn)的位置是什么。

具體看代碼：

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="cpp" cid="n27" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> #include <bits/stdc++.h>
using namespace std;

define ll long long

const int maxn = 2e5 + 10;
?
int nxt[maxn][26];
void solve(){
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
int vis[26];
memset(vis, 0, sizeof(vis));
for (int i = 0; i < m; i++){
vis[t[i] - 'a'] = 1;
}
for (int i = 0; i < n; i++){
vis[s[i] - 'a'] = 0;
}
for (int i = 0; i < 26; i++){
if(vis[i]){
cout << -1 << endl;
return;
}
}
?
//initial
for (int i = 0; i < 26; i++)
nxt[n][i] = -1;
for (int i = n - 1; i >= 0; i--){
for (int c = 0; c < 26; c++){
nxt[i][c] = nxt[i + 1][c]; //向前回溯
}
nxt[i][s[i] - 'a'] = i; //字符串s中從第i個(gè)字符處開始往后找，第s[i]-'a'字符最早出現(xiàn)的位置是i
}
int cur = 0, ans = 1;
for (int i = 0; i < m; i++){
cur = nxt[cur][t[i] - 'a'];
if(cur == -1){
ans++;
cur = 0;
i--;
}
else{
cur++;
}
}
cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(0);
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}</pre>

D - Same GCDs

題意很明顯要求出當(dāng)時(shí)，滿足的的個(gè)數(shù)，由歐拉函數(shù)可以轉(zhuǎn)換為，和肯定是的倍數(shù)，那么假設(shè)，令，那么的取值范圍為，那么最終要求的東西就是當(dāng)時(shí)，滿足的的個(gè)數(shù)。

把，分成兩個(gè)區(qū)域和

先討論時(shí)，由歐幾里得定理可以得出，再由可以化簡所求東西為求時(shí)，滿足的的個(gè)數(shù)，而我們把這個(gè)區(qū)間與進(jìn)行合并，就可以發(fā)現(xiàn)，我們要求的就是時(shí)滿足的個(gè)數(shù)，即與互質(zhì)，可以發(fā)現(xiàn)求的就是的歐拉函數(shù)值。

代碼：

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="cpp" cid="n36" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> #include <bits/stdc++.h>
using namespace std;

define ll long long

const int maxn = 2e5 + 10;
ll phi(ll x){
ll ans = x;
for (ll i = 2; i * i <= x; i++){
if(x % i == 0){
ans -= ans / i;
while(x % i == 0)
x /= i;
}
}
if(x > 1)
ans -= ans / x;
return ans;
}
void solve(){
ll a, m;
cin >> a >> m;
cout << phi(m / __gcd(a, m)) << endl;
}
int main(){
ios_base::sync_with_stdio(0);
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}</pre>

歐拉函數(shù)

歐拉函數(shù)：

歐拉函數(shù)，即，表示的是小于等于和互質(zhì)的數(shù)的個(gè)數(shù)。

比如。

利用唯一分解定理，我們可以把一個(gè)整數(shù)唯一地分解為質(zhì)數(shù)冪次的乘積，

設(shè)

，其中是質(zhì)數(shù)，那么

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="cpp" cid="n50" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit;"> int phi(int n){
int ans = n;
for(int i = 2; i * i <= n; ++i){
if(n % i == 0){
ans -= ans * i;
while(n % i == 0)
n /= i;
}
}
if( n > 1 )
ans -= ans * i;
return ans;
}</pre>

歐拉函數(shù)的性質(zhì)：

①歐拉函數(shù)是積性函數(shù)：

如果有，那么

特別的，當(dāng)為奇數(shù)時(shí)，

②

即表示，的所有因子的歐拉函數(shù)的值加起來為

③如果, 那么

④設(shè)為 的 的個(gè)數(shù)，那么

⑤若，其中為質(zhì)數(shù)，那么

E - Permutation Separation

在區(qū)間枚舉切割位置 (從 右邊切開，不取是因?yàn)橐ＷC兩部分初始非空) ，時(shí)間復(fù)雜度

那么我們知道所有 位置后面的小于等于 的數(shù)都要移動(dòng)到左邊， 位置即前面的大于 的數(shù)都要移動(dòng)到右邊。

我們尚若可以 時(shí)間內(nèi)得到上面移動(dòng)操作的就可以維護(hù)出最小值。

想到了線段樹。

首先對 做一個(gè)前綴和 數(shù)組 ，代表將1~i的數(shù)都移動(dòng)到右邊需要的cost。

以數(shù)組建立區(qū)間修改，區(qū)間查詢最小值的線段樹。

然后從到枚舉割切位置，

對于第個(gè)位置，我們將找到在中的位置 id ,將區(qū)間減去 ，區(qū)間 加上

意義為：在切割位置大于等于i 的時(shí)候，不需要將數(shù)字i移動(dòng)到右邊部分，又結(jié)合線段樹維護(hù)的是前綴和數(shù)組，

那么對于每一個(gè)位置i 用線段樹的根節(jié)點(diǎn)維護(hù)的最小值去更新答案ans即可。

<pre mdtype="fences" cid="n87" lang="cpp" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> #include <bits/stdc++.h>
using namespace std;

define ll long long

const int maxn = 3e5 + 10;
?
struct node{
int l, r;
ll laze, val;
} segment_tree[maxn << 2];
?
int n, p[maxn], id[maxn];
ll a[maxn], sum[maxn];
?
void push_Up(int rt){
segment_tree[rt].val = min(segment_tree[rt << 1].val, segment_tree[rt << 1 | 1].val);
}
?
void build(int rt, int l, int r){
segment_tree[rt].l = l;
segment_tree[rt].r = r;
if (l == r){
segment_tree[rt].val = sum[l];
segment_tree[rt].laze = 0ll;
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
push_Up(rt);
}
?
void push_Down(int rt){
segment_tree[rt << 1 | 1].val += segment_tree[rt].laze;
segment_tree[rt << 1 | 1].laze += segment_tree[rt].laze;
segment_tree[rt << 1].val += segment_tree[rt].laze;
segment_tree[rt << 1].laze += segment_tree[rt].laze;
segment_tree[rt].laze = 0;
}
?
void update(int rt, int l, int r, int num){
if(segment_tree[rt].laze && l != r)
push_Down(rt);
if(segment_tree[rt].l >= l && segment_tree[rt].r <= r){
segment_tree[rt].val += num;
segment_tree[rt].laze += num;
return;
}
int mid = segment_tree[rt].l + segment_tree[rt].r >> 1;
if(r > mid){
update(rt << 1 | 1, l, r, num);
}
if(l <= mid){
update(rt << 1, l, r, num);
}
push_Up(rt);
}
?
int main(){
ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++){
cin >> p[i];
id[p[i]] = i;
}
for (int i = 1; i <= n; i++){
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
?
ll ans = a[n];
build(1, 1, n - 1);
ans = min(ans, segment_tree[1].val);
int x;
for (int i = 1; i <= n; i++){
x = id[i];
if(x != n){
update(1, x, n - 1, -a[x]);
}
if(x != 1){
update(1, 1, x - 1, a[x]);
}
ans = min(ans, segment_tree[1].val);
//cout << ans << " ";
}
cout << ans << endl;
return 0;
}</pre>

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • Educational Codeforces Round 80 比賽鏈接： Educational Codefor...
    frans4x閱讀 264評論 0贊 0
  • "use strict";function _classCallCheck(e,t){if(!(e instanc...
    久些閱讀 2,142評論 0贊 2
  • 在C語言中,五種基本數(shù)據(jù)類型存儲空間長度的排列順序是: A)char B)char=int<=float C)ch...
    夏天再來閱讀 4,008評論 0贊 2
  • 線段樹 (Segement Tree) 線段樹是用二叉樹來表示一段區(qū)間的一種數(shù)據(jù)結(jié)構(gòu)。 將區(qū)間分割成若干個(gè)單元區(qū)間...
    Sprendd閱讀 418評論 0贊 2
  • created by Dejavu(不斷更新中) 概念 線段樹，類似區(qū)間樹，是一個(gè)完全二叉樹，它在各個(gè)節(jié)點(diǎn)保存一條...
    ericdejavu閱讀 1,395評論 0贊 0

友情鏈接更多精彩內(nèi)容