苏州企业建设网站价格,seo排名怎么看,泰安房产网新楼盘,广州做公司网站的公司有哪些688 div2 C Balanced Bitstring
思路#xff1a;首先对于区间问题 #xff0c; 我们可以先思考让它滑动滑动。对于[l,r],向后滑动一位后 #xff0c;[l1 , r1],因为两次的区间中 #xff0c; [l1 ,r]中所有数都是相同的 #xff0c; 所以 可以得到s[l] s[r1] #xff0…688 div2 C Balanced Bitstring
思路首先对于区间问题 我们可以先思考让它滑动滑动。对于[l,r],向后滑动一位后 [l1 , r1],因为两次的区间中 [l1 ,r]中所有数都是相同的 所以 可以得到s[l] s[r1] 那么再向后滑动 就有 l1 r2 , 一次类推 在1 ~ k中 每个数每次 k s[x] s[xk]的。那么我们就可以对于每个k的区间来进行处理 观察它们是否相同。但是对于 的话 我们可以先不管他,最后看 1和0的个数是否都 k/2 就行了
void solve(){cinnk;string s;cins;s # s;for(int i 1;ik;i)str[i] 0;for(int i1;ik;i){for(int j i;jn;j k){if(s[j] ?)continue;if(str[i] 0)str[i] s[j];else if(str[i] ! s[j]){coutNOendl;return;}}}int cnt1 0 , cnt0 0;for(int i 1;ik;i){if(str[i] 1)cnt1;else if(str[i] 0)cnt0;}if(cnt1 k/2 cnt0 k/2){coutYESendl;return;}coutNOendl;
}
688 div2 D Tree Tag
思路首先如果一开始 a和b的距离小于 da 那么爱丽丝赢 。 如果b被追到了死角 那么必须db 2*da 。 最后需要树有一段很长的距离足够b来躲掉a也就是树的直径 2abob才有可能赢
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(){cinnabdadb;for(int i 1;in;i)g[i].clear();for(int i 1;in;i){int u ,v;cinuv;g[u].push_back(v);g[v].push_back(u); }for(int i 1;in;i)vis[i] 0 , dis[i] 0;dis[a] 0;dfs(a , 0);if(dis[b] da){coutAliceendl;return;}int ma -1 , Q 0;for(int i 1;in;i){if(dis[i] ma)ma dis[i] , Q i;}for(int i 1;in;i)vis[i] 0 , dis[i] 0;dfs(Q , 0);ma -1;for(int i 1;in;i){if(dis[i] ma)ma dis[i];}if(2 * da db){coutAliceendl;return;}coutBobendl;}
962 div3 E Decode
思路 还是区间01的问题 我们可以把0当作-1 1当作 1如果区间中0和1的数量相等 那么就说明区间和为 0 对于一个区间为0的区间我们思考它对答案的贡献。
假设区间为[l,r]的这样一段区间它对答案的贡献是多少 首先左边的贡献是 l , 右边的贡献是 n-r1 , 根据乘法原理 贡献为l*(n-r1)。
如何找区间 根据前缀和思想 pre[r] - pre[l-1] 0 - pre[l-1] pre[r]。那么接下来可以用一个map进行优化 时间复杂度就应该是 Onlogn
void solve(){cins;int n s.size();s # s;for(int i 1;in;i)pre[i] pre[i-1] (s[i]1 ?1 : -1 );mapint,intmp;int ans 0;mp[0] 1;for(int i 1;in;i){ans (mp[pre[i]])*(n-i1);mp[pre[i]] (i1); mp[pre[i]]% mod;ans % mod;}coutansendl;
}
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(){cinnk;for(int i 1;in;i)cina[i];for(int i 1;in;i)cinb[i];auto check [](int x){int cnt 0;for(int i 1;in;i){if(a[i] x){cnt (a[i]-x)/b[i] 1;}}return cnt k;};int l0 ,r 2e10;while(l r){int mid (lr1)1;if(check(mid))l mid;else r mid -1;}int cnt 0;int sum 0;for(int i 1;in;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;}}coutsum l*(k - cnt)endl;
}
很细节的一道题 多多思考。
