CF 训练2
688 div2 C Balanced Bitstring
思路：首先对于区间问题 ， 我们可以先思考让它滑动滑动。对于[l,r],向后滑动一位后 ，[l+1 , r+1],因为两次的区间中 ， [l+1 ,r]中所有数都是相同的 ， 所以 可以得到s[l] = s[r+1] ， 那么再向后滑动 ， 就有 l+1 = r+2 , 一次类推 ， 在1 ~ k中 ， 每个数每次 +k ， s[x] = s[x+k]的。那么我们就可以对于每个k的区间来进行处理 ， 观察它们是否相同。但是对于 ？ 的话 ，我们可以先不管他,最后看
1和0的个数是否都 <= k/2 就行了
void solve(){ cin>>n>>k; string s;cin>>s; s = '#' + s; for(int i =1;i<=k;++i)str[i] = 0; for(int i=1;i<=k;++i){ for(int j =i;j<=n;j +=k){ if(s[j] == '?')continue; if(str[i] == 0)str[i] = s[j]; else if(str[i] != s[j]){ cout<<"NO"<688 div2 D Tree Tag
思路：首先如果一开始 a和b的距离小于 da ， 那么爱丽丝赢 。 如果b被追到了死角 ， 那么必须db > 2*da 。 最后需要树有一段很长的距离，足够b来躲掉a，也就是树的直径 > 2a，bob才有可能赢
void dfs(int u , int fa){ for(auto to : g[u]){ if(vis[to] || to == fa)continue; dis[to] = dis[u] + 1; vis[to] = 1; dfs(to , u); } } void solve(){ cin>>n>>a>>b>>da>>db; for(int i =1;i<=n;++i)g[i].clear(); for(int i =1;i>u>>v; g[u].push_back(v); g[v].push_back(u); } for(int i =1;i<=n;++i)vis[i] = 0 , dis[i] = 0; dis[a] = 0; dfs(a , 0); if(dis[b] <= da){ cout<<"Alice"< ma)ma = dis[i] , Q =i; } for(int i =1;i<=n;++i)vis[i] = 0 , dis[i] = 0; dfs(Q , 0); ma = -1; for(int i =1;i<=n;++i){ if(dis[i] > ma)ma = dis[i]; } if(2 * da >= db){ cout<<"Alice"< 962 div3 E Decode
思路 ：还是区间01的问题 ， 我们可以把0当作-1 ， 1当作 1，如果区间中0和1的数量相等 ， 那么就说明区间和为 0 ，对于一个区间为0的区间，我们思考它对答案的贡献。
假设区间为[l,r]的这样一段区间，它对答案的贡献是多少 ， 首先左边的贡献是 l , 右边的贡献是 n-r+1 , 根据乘法原理 ， 贡献为l*(n-r+1)。
如何找区间 ，根据前缀和思想 ， pre[r] - pre[l-1] = 0 -> pre[l-1] = pre[r]。那么接下来，可以用一个map进行优化 ， 时间复杂度就应该是 Onlogn
void solve(){ cin>>s; int n = s.size(); s = '#' + s; for(int i =1;i<=n;++i)pre[i] = pre[i-1] + (s[i]=='1' ?1 : -1 ); mapmp; int ans = 0; mp[0] =1; for(int i =1;i<=n;++i){ ans +=(mp[pre[i]])*(n-i+1); mp[pre[i]] += (i+1); mp[pre[i]]%= mod; ans %= mod; } cout< 962 div3 F Bomb
思路： 观察到数据非常大 ， k 是1e9 , 那么k次的优先队列询问肯定是不行了。这题其实是个很典的题，我们可以二分出来最后每个数的最大值，也就是说，每个数最后肯定会减到 那个最大值或者大于最大值。
那么对于如何二分，我们思考到 ， 二分出来的x 越大 ，我们所需要减少的次数cnt 就越少,cnt <= k的话，x就有一个最小值 ， 所以是在分界线的右边 ,当我们的cnt >= k 的话就需要 l = mid , 否则
r = mid -1;
对于每个数可以用掉的次数为 cnt = (ai - x) / bi + 1，那么构成一个等差数列，其中的和也很容易算出来。
还有一个细节就是最后我们用掉的次数可能小于k ，那么多出来的这几次 直接×二分出来的x即可
void solve(){ cin>>n>>k; for(int i =1;i<=n;++i)cin>>a[i]; for(int i =1;i<=n;++i)cin>>b[i]; auto check =[&](int x){ int cnt = 0; for(int i =1;i<=n;++i){ if(a[i] >= x){ cnt += (a[i]-x)/b[i] + 1; } } return cnt >= k; }; int l=0 ,r = 2e10; while(l < r){ int mid = (l+r+1)>>1; if(check(mid))l =mid; else r = mid -1; } int cnt = 0; int sum = 0; for(int i= 1;i<=n;++i){ if(a[i] >= l){ int m =(a[i]-l)/b[i] + 1; sum += a[i]*m - m*(m-1)*b[i]/2; cnt += m; } } cout<很细节的一道题 ， 多多思考🤔。