CODEFORCES 每日五题A.不同字符的划分根据题意 是把一个字符串分成两段 求前半段以及后半段的字母的种类之和由于我们不知道是从哪里分开的 所以肯定要暴力一下 选择一个地方分开那么我们只需要求前半段的种类数加上后半段的种类数之和即可。此时思考 如果我们每次分开以后都遍历前半段和后半段 时间复杂度为ON^2)那么我们可以想办法来进行优化 比如我们可以利用前缀和的思想让pre[i] 表示从1到i的种类数 suf[i] 表示从 i 到 n的种类数 值得注意的是在计算pre时从前往后遍历 在计算suf时从后往前遍历即可#include iostream #include string using namespace std; int main(){ int t; cin t; while(t--){ int n ; cin n; string s; cin s; s s; vectorint pre(n1); vectorint suf(n2); int h1[26] {0}; int h2[26] {0}; for(int i 1 ; i n ; i){ h1[s[i] - 0]; if(h1[s[i] - 0] 1) pre[i] pre[i-1] 1; else pre[i] pre[i-1]; } for(int i n ; i 1 ; i--){ h2[s[i] - 0]; if(h2[s[i] - 0] 1) suf[n] suf[n1] 1; else suf[n] suf[n1]; } int ans 0; for(int i 1 ; i n ; i){ ans max(ans, pre[i]suf[i1]); } cout ans endl; } return 0; }B. 相似数对相似数对的含义 奇偶性相同 或者相差1Target: 判断数组A能否把所有元素全部分成相似数对 A的大小为偶数分析如果偶数的数量为偶数 那么由于n为偶数 奇数的数量也肯定为偶数因此一定可以分成相似数对如果偶数的数量为奇数那么奇数的数量肯定也为奇数此时我们只要找到一对相差1的相似数对即可把这一种情况转化为上面那一种情况也就可以分成相似数对了思路 先遍历找evennum判断是否时偶数 同时用hash记录每个元素出现的次数如果不是偶数从第一个数开始遍历 看hash[a[i] - 1] 或者hash[a[i]1] 是否存在如果存在则cout YES else cout NO;#include iostream #include vector using namespace std; int main(){ int t; cin t; while(t--){ int hash1[102] {0}; int n; cin n; vectorint a(n1); int evennum 0; for(int i 1 ; i n ; i) { cin a[i]; hash1[a[i]]; if(a[i] % 2 0); evennum; } if(evennum 0) cout YES endl; else{ int flag 1; for(int i 1 ; i n ; i){ if(h[a[i]-1] || h[a[i]1]){ cout YES endl; flag 0; break; } } if(flag) cout NO endl; } } return 0; }C.对比值首先我们要考虑的是如何让对比值不变① 当删除的在两端时 由于少了这一组对于大量的测试案例 一定对减少 无法保证不变②对于中间的 当连续的三个数 a1 a2 a3 是升序或者降序排列时那么这一定是可以删除的而且删除后的对比值也保持不变。details:我们可以遍历 i 2 到 i n-1这一段找符合条件的同时为了避免每次都往前找可以用last来记录上个位置如果上一次没有删除 让last i 对于下一个元素它左边的元素就是last 了同时考虑一个问题 当所有值都是恒定的时候我们可以把中间的元素删完 此时ans 2 BUT 真实答案应当是 1 因为一个数的对比值也是0 因此对于此情况需要特判我采取的方案是哈希记录出现的次数 等于n的话最后让ans 1;#include iostream #include unordered_map #include vector using namespace std; int main(){ int t; cin t; while(t--){ unordered_mapint,int h; int n; cin n; vectorint a(n1); for(int i 1 ; i n ; i){ cin a[i]; h[a[i]]; } int ans n , last 1; for(int i 2 ; i n-1 ; i){ if((a[i] a[last] a[i] a[i1]) || (a[i] a[last] a[i] a[i1])) ans--; else last i; } if(h[a[0]] n) ans 1; cout ans endl; } return 0; }D.翻转游戏题意为让我们翻转一段连续的子序列 0 - 1 1 - 0Think : 对于此题而言 子序列中的0 会让 最后 1的个数1 子序列的1会让最后 1 的个数 -1思路我们完全可以把0看成1 把 1 看成 -1 求一段子序列的最大和即可一般求子序列我们都会想会不会是用滑动窗口 但是这道题没有单调性我们可以考虑动态规划dp[i]表示以i位置为结尾时的sum的最大值#include iostream #include vector using namespace std; int main(){ int n; cin n; vectorint a(n1); int sum 0; for(int i 1 ; i n ; i){ cin a[i]; sum a[i]; if(a[i] 0) a[i] 1; else a[i] -1; } int ans 0; vectorint dp(n1); dp[1] a[1]; for(int i 2 ; i n ; i) { dp[i] max(a[i],dp[n-1] a[i]); ans max(ans,dp[i]); } sum ans; cout sum endl; return 0; }C.数对的数量要找的是两个整数的和在l 与 r之间暴力查找 ON^2)如果我们先固定一个 再取另一个区间二分查找可行区间 O(nlogn)#include iostream #include vector #include algorithm using namespace std; int main(){ int t ; cin t; while(t--){ int n , l , r; cin n l r; vectorint a(n1); int ans 0; for(int i 1 ; i n ; i) cin a[i]; sort(a.begin()1,a.end()); for(int i 1 ; i n-1 ; i){ int num1 a[i] , l1 l - a[i] , r1 r - a[i]; int L i 1 , R n; while(L R){ int mid L (R - L ) / 2; if(a[mid] l1) R mid; else L mid 1; } int t1 L; L i 1 , R n; while(L R){ int mid L (R - L 1) / 2; if(a[mid] r1) L mid; else R mid - 1; } int t2 L; if(a[t1] l1 a[t2] r1) ans t2 - t1 1; } cout ans endl; } return 0; }