)
传送门
说在前面的话：
两年多了。现在高考结束，学上了计算机专业，重拾C++。一边学学知识，一边做做题目，参加这些比赛吧。CF的Div2难度有点高啊对于我来说，力争能赛时做出ABC吧。
这次比赛，英文题面真难懂啊，幸亏有豆包翻译（hhhhh
A
A题就是一个贪心，要想有一个数能打败其他所有数，首先它肯定得是最大的数，不然比他大的书中肯定有跟他互质的，就会输了。所以只要判断最大的那个数（n+1）是不是质数即可。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int t;
bool isPrime(int n){if(n<=2)return 1;for(int i=2;i*i<=n;i++){if(n%i==0)return 0;}return 1;
}
int main(){cin>>t;while(t--){int k;cin>>k;if(isPrime(k+1))cout<<"yes"<<endl;else cout<<"no"<<endl;}system("pause");return 0;
}
B
首先，假设我们不考虑交换这个步骤，要使得结果符合要求，就是把所有连续的数字都删到只剩下一个，假设此时答案是m。再考虑这个交换，其实从样例1 1 2 3 3 2 2 1中可以看出来，一次交换最多可以“拯救”两个数字，也不难知道不可能救三个。于是，答案只可能是m,m+1,m+2。具体就是去考虑到底是哪一个情况就行了。
我于是把所有重复的数字加个标记。至于判断也很简单了，首先如果某一个连续数字超过两个，就当作两个处理，否则一个交换下来肯定还是会有两个相连的。然后我们观察交换+2的，都是原来XXYY型，所以只要有两个标记数相连，就是m+2。至于m+1，则是XXYZ格式的，注意不能是XXYX，否则交换完还有，简单判断。但是这里有个特例，就是比如1 1 2这种，显然是可以的，这种边界单独考虑即可。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2*1e5+10;
int main()
{int TestsNumT;cin >> TestsNumT;while (TestsNumT--){int n;cin>>n;vector<int> a(n);for(int i=0;i<n;i++)cin>>a[i];vector<int> s;vector<int> cnt;for(int i=0;i<n;i++){if(s.empty()||a[i]!=s.back()){s.push_back(a[i]);cnt.push_back(1);}else{cnt.back()++;}}int m=s.size();if(m==1){cout<<1<<endl;continue;}bool ispair=0;for(int i=0;i<=m-2;i++){if(cnt[i]>=2&&cnt[i+1]>=2){ispair=1;break;}}if(ispair){cout<<m+2<<endl;continue;}bool f=0;for(int i=0;i<m-1;i++){if(cnt[i]>=2&&s[i+2]!=s[i] || cnt[i]>=2&&i+2>=m){f=1;break;}}for(int i=1;i<m;i++){if(cnt[i]>=2&&s[i-2]!=s[i] || cnt[i]>=2&&i-2<0){f=1;break;}}if(f){cout<<m+1<<endl;continue;}cout<<m<<endl;continue;}system("pause");return 0;
}
C
这题比赛没看出来，后面问了问豆包，还是挺给力的。首先还是一个贪心，由于存在覆盖这个机制，所以，行或者列二者肯定有一个取不了，也就是说就两种可能 行n-1，列m 或者 行n，列m-1。所以，两个情况比较就好。至于取什么数，那就是从大往小取呗，但是注意，会有重复数字，就是行列都有的数，所以这个要单独提出来，当其中的数被取到时，可以灵活地算为行或列。这个“灵活”如何实现，其实也就是在算和时也要同时进行行列的比较，让整体都是从大到小的加入。
这里就用到了双指针，也是第一次见，学到了。其实原理还是挺简单的，代码一看就懂了。就是这个i，j经常搞错啊，写成b[j]了，呃呃。还有这题会卡long long ，1e10了好像。最搞笑的是，看自己以前的题解说以及用上signed了，结果...好的，现在就把源代码改了。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+10;
ll n,m,x,y,t,a[N],b[N];
ll min(ll x,ll y){return x<y?x:y;
}
ll solve(ll R,ll C,vector<ll> onlyA,vector<ll> onlyB,vector<ll> sumC,ll len){ll RA=min(R,onlyA.size());ll RB=min(C,onlyB.size());ll i=0,j=0;vector<ll> f;f.push_back(0);ll s=0;while(i<RA && j<RB){if(onlyA[i]>=onlyB[j]){s+=onlyA[i];i++;}else{s+=onlyB[j];j++;}f.push_back(s);}while(i<RA){s+=onlyA[i];i++;f.push_back(s);}while(j<RB){s+=onlyB[j];j++;f.push_back(s);}ll maxkc=min(len,R+C);ll ans=0;for(ll i=0; i<=maxkc; i++){ll T=min(R+C-i,f.size()-1);ans=max(ans,sumC[i]+f[T]);}return ans;
}
int main(){cin>>t;while(t--){cin>>n>>m>>x>>y;vector<ll> a(x);vector<ll> b(y);for(ll i=0; i<x; i++)cin>>a[i];for(ll i=0; i<y; i++)cin>>b[i];vector<ll> onlyA, onlyB, common;ll i=x-1,j=y-1;while(i>=0 && j>=0){if(a[i]==b[j]){common.push_back(a[i]);i--;j--;}else if(a[i]>b[j]){onlyA.push_back(a[i]);i--;}else{onlyB.push_back(b[j]);j--;}}while(i>=0){onlyA.push_back(a[i]);i--;}while(j>=0){onlyB.push_back(b[j]);j--;}vector<ll> sumC;sumC.push_back(0);ll s=0;for(ll i=0; i<common.size(); i++){s+=common[i];sumC.push_back(s);}ll len=common.size();ll ans1=solve(n,m-1,onlyA,onlyB,sumC,len);ll ans2=solve(n-1,m,onlyA,onlyB,sumC,len);cout<<max(ans1,ans2)<<endl;}system("pause");return 0;
}