Educational Codeforces Round 81 (Rated for Div. 2)
QAQ：
A. Display The Number
思路：
题目说了液晶屏最多有998244353位数，观察所有数字的液晶显示，只有1所用的线段最少，即使我们每一位都放1，最多也只有1e5/2位数，那么题目就变得简单了，我们优先凑一来增加所得数的位数，假如最后还剩下一根线段，我们可以把最高位变成7。
代码：
#include <bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); int d = n/2; if(n%2==1) printf("7"); else printf("1"); for(int i = 1;i<d;++i) printf("1"); printf(" "); } return 0; }
B. Infinite Prefixes
思路：
假设一个前缀i的balance值为pre[i]，它的值可以表示为k*c+pre[i%n](其中c为一个串总的balance)，对结果进行分类讨论。
如果c是0的话
假如在一个s串中有值能达到x，则结果显然是无限的，否则，答案就是0
如果c不是零的话，则可以枚举一个s的每个位置i，计算一下x = k*c+pre[i]是否存在整数k使方程成立，如果存在，则ans++。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long li; int n, x; string s; inline bool read() { if(!(cin >> n >> x >> s)) return false; return true; } inline void solve() { int ans = 0; bool infAns = false; int cntZeros = (int)count(s.begin(), s.end(), '0'); int total = cntZeros - (n - cntZeros); int bal = 0; for(int i = 0; i < n; i++) { if(total == 0) { if(bal == x) infAns = true; } else if(abs(x - bal) % abs(total) == 0) { if((x - bal) / total >= 0) ans++; } if(s[i] == '0') bal++; else bal--; } if(infAns) ans = -1; cout << ans << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); cout << fixed << setprecision(15); int tc; cin >> tc; while(tc--) { read(); solve(); } return 0; }
C. Obtain The String
思路：
用一个set数组去存储s串每个字母出现的位置，从头遍历t串，另外用一个数记录下当前选用来构成z串所用字母的位置，假如在当前这次已经没有办法去找到符合条件的字母，那就代表需要在找一个s串来继续z串的填充，ans++，最后输出答案即可。
代码：
#include <bits/stdc++.h> using namespace std; typedef long long LL; set<int> st[30]; int main() { int T; scanf("%d",&T); while(T--) { for(int i =0; i<26; i++) st[i].clear(); //memset(tmp,0,sizeof(tmp)); string s,t; cin >> s >> t; int len = s.size(); for(int i = 0; i<len; ++i) { st[s[i]-'a'].insert(i); } len =t.size(); bool flag = false; LL ans =1; int tmp = 0; for(int i = 0; i<len; ++i) { int d = t[i]-'a'; if(st[d].size()==0) { flag = true; break; } else { set<int>::iterator it = st[d].lower_bound(tmp); //cout << d << endl; //cout << *it <<" " << tmp << endl; if(it!=st[d].end()) { tmp = (*it)+1; } else { ++ans; tmp = 0; --i; } //cout << "**" << ans << endl; } } if(flag) { printf("-1 "); } else cout << ans << " "; } return 0; }
D. Same GCDs
思路：
设 g = gcd(a,m)
D题的答案就是Eular(m/g);证明如下，
同时，因为
所以变换之后a+x的取值区间就变成了[0,m)
那么(a+x)/g的区间就是[0,m/g)
整个式子就是求[0,m/g)中与m/g互素的数的个数，就是Eular(m/g)的值。
代码：
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL Eular(LL n) { LL ans = n; for(LL i = 2;i*i<=n;++i) { if(n%i==0) { ans-=(ans/i); while(n%i==0) n/=i; } } if(n>1) ans-=ans/n; return ans; } int main() { int T; cin >> T; while(T--) { LL a,b; cin >>a >> b; LL g = __gcd(a,b); cout << Eular(b/g) << endl; } return 0; }
E. Permutation Separation
思路：
首先我们先假设分割的位置为i，长度为x，那么最终答案是多少？我们需要把1-x放进左边的集合，x+1-n放到右面的集合，所以总花费可以这样计算，令pos = 数x在原排列中的位置，对于i<=pos的部分来说，只要它的值比x大，它就需要移到右边，花费就需要加上这个数的权值。同样，对于i>pos的数来说，只要它的值比x小，他就需要移到左边，花费就需要加上它的权值。
接下来我们考虑优化一下当前的算法。我们先求出前缀和pre，从x = 1.i = 1开始枚举，外层循环枚举x，内层循环枚举i,我们发现对于每个i<pos(x)，答案都是pre[i]+a[pos(x)]，而对于i>=pos(x)，答案就变成了pre[i]-a[pos(x)]，在x为1的情况下就是上面两个式子所有取值的最小值。接下来x = 2，也是同样的道理，可以发现，事实上假如我们把前缀和作为节点的值建一棵线段树，上面的内层循环就变成的区间加上一个数以及求最小值。这样复杂度就由O(n^2)到了O(nlogn)。题目可解。
代码：
#include <bits/stdc++.h> using namespace std; #define MAXN 200000+10 #define LL long long int n; int p[MAXN]; int rp[MAXN]; int a[MAXN]; LL b[MAXN]; long long t[4*MAXN]; LL add[4*MAXN]; void build(int v,int l,int r) { if(r-l==1) { t[v] = b[l]; return ; } int mid = (l+r)/2; build(v*2+1,l,mid); build(v*2+2,mid,r); t[v] = min(t[v*2+1],t[v*2+2]); return ; } void push(int v,int l,int r) { if(add[v]!=0) { if(r-l>1) { for(int i = 2*v+1;i<2*v+3;++i) { add[i]+=add[v]; t[i]+=add[v]; } } add[v] = 0; } } void upd(int v,int l,int r,int L,int R,int x) { if(L>=R) return ; if(l==L&&r==R) { add[v]+=x; t[v]+=x; push(v,l,r); return ; } push(v,l,r); int mid = (l+r)/2; upd(v*2+1,l,mid,L,min(mid,R),x); upd(v*2+2,mid,r,max(L,mid),R,x); t[v] = min(t[v*2+1],t[v*2+2]); } void upd(int l,int r,int x) { upd(0,0,n,l,r,x); } LL get(int v,int l,int r,int L,int R) { if(L>=R) return 1e18; push(v,l,r); if(l==L&&r==R) return t[v]; int mid = (l+r)/2; return min(get(v * 2 + 1, l, mid, L, min(R, mid)), get(v * 2 + 2, mid, r, max(L, mid), R)); } LL get(int l,int r) { return get(0,0,n,l,r); } int main() { scanf("%d",&n); for(int i = 0;i<n;++i) { scanf("%d",p+i); --p[i]; rp[p[i]] = i; } for(int i = 0;i<n;++i) scanf("%d",a+i); b[0] = a[0]; for(int i = 1;i<n;++i) b[i] = a[i]+b[i-1]; build(0,0,n); LL res = get(0,n-1); for(int i = 0;i<n;++i) { int pos = rp[i]; upd(pos,n,-a[pos]); upd(0,pos,a[pos]); res = min(res,get(0,n-1)); } cout <<res <<endl; return 0; }