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"<<endl;return;}}}int cnt1 = 0 , cnt0 = 0;for(int i =1;i<=k;++i){if(str[i] == '1')cnt1++;else if(str[i] == '0')cnt0++;}if(cnt1 <=k/2 && cnt0 <= k/2){cout<<"YES"<<endl;return;}cout<<"NO"<<endl;
}

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<n;++i){int u ,v;cin>>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"<<endl;return;}int ma = -1 , Q = 0;for(int i =1;i<=n;++i){if(dis[i] > 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"<<endl;return;}cout<<"Bob"<<endl;}

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 );map<int,int>mp;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<<ans<<endl;
}

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<<sum + l*(k - cnt)<<endl;
}

很细节的一道题 ， 多多思考🤔。