CODEFORCES 每日五题-港品优选

CODEFORCES 每日五题

A.不同字符的划分

根据题意是把一个字符串分成两段求前半段以及后半段的字母的种类之和

由于我们不知道是从哪里分开的，所以肯定要暴力一下，选择一个地方分开，那么我们只需要求前半段的种类数加上后半段的种类数之和即可。

此时思考如果我们每次分开以后都遍历前半段和后半段时间复杂度为O（N^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; vector<int> pre(n+1); vector<int> suf(n+2); 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[n+1] + 1; else suf[n] = suf[n+1]; } int ans = 0; for(int i = 1 ; i < n ; i++){ ans = max(ans, pre[i]+suf[i+1]); } cout << ans << endl; } return 0; }

B. 相似数对

相似数对的含义：奇偶性相同或者相差1

Target: 判断数组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; vector<int> a(n+1); 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_map<int,int> h; int n; cin >>n; vector<int> a(n+1); 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[i+1]) || (a[i] <= a[last] && a[i] >= a[i+1])) ans--; else last = i; } if(h[a[0]] == n) ans = 1; cout << ans << endl; } return 0; }

D.翻转游戏

题意为让我们翻转一段连续的子序列 0 -> 1 1 -> 0

Think : 对于此题而言，子序列中的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; vector<int> a(n+1); 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; vector<int> dp(n+1); 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之间

暴力查找 O（N^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; vector<int> a(n+1); 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; }

企业官网建设流程全解析