Problem - A - Codeforces
思路：如果领先方互换，那么“NO”，否则“YES”。
void solve(){ A
int x1,y1; cin>>x1>>y1;
int x2,y2; cin>>x2>>y2;
if(x1>y1&&x2>y2||x1<y1&&x2<y2) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}Problem - B - Codeforces
思路：找现在的X还差多少可以被Y整除，即need=y-x%y;如此一直模拟即可。但是要注意的是，当X==1之后，是一直在循环的，每y-1次循环回到X==1.所以k%=(y-1)。因为y>=2，所以这样模拟的话，X会递减非常快，只要k足够大，X很快就递减到1，不会TLE。
void solve(){ B
int x,y,k; cin>>x>>y>>k;
int need=y-x%y;
while(k>=need){
x+=need,k-=need;
while(x%y==0) x/=y;
need=y-x%y;
if(x==1) k%=(y-1); key!!!!!!!!!!!!!!
}
cout<<x+k<<endl;
}Problem - C - Codeforces
思路：滑动窗口+贪心。
int arr[100005];
void solve(){ C 第一发写的太急了,应该是滑动窗口 写拉了，wa了3发。。
int n,l,r; cin>>n>>l>>r;
for(int i=1;i<=n;i++) cin>>arr[i];
int idxl=1,idxr=1,ans=0,sum=0;
while(idxr<=n){
sum+=arr[idxr];
if(sum>=l&&sum<=r||arr[idxr]>=l&&arr[idxr]<=r) ans++,sum=0,idxl=idxr+1;
else if(sum>r){
while(sum>r){ rr和r搞混了。。这里应该是sum>r 不是sum>rr。。。 这都能过样例。。 取名应该区分一点。。不然把自己搞混了
sum-=arr[idxl];
idxl++;
}
if(sum>=l&&sum<=r||arr[idxr]>=l&&arr[idxr]<=r) ans++,sum=0,idxl=idxr+1; 刚才复制的..这里忘了删rr++..
}
idxr++;
}
cout<<ans<<endl;
}Problem - D - Codeforces
思路：一开始山峰的高度差dif是可知的，那么需要弥补这个dif。因为是固定了修改k*k的矩形，那么可以初始化，在每一个这样的k*k矩形中，存在的R山和B山各有几个，它们之间的差difrb就是可以作为弥补dif的值。那么计算出所有的difrb,题目就变成了判断是否存在c1a1+c2a2+...+cnan==dif.
要满足这个条件，那么dif%gcd(a1,a2,...,an)==0即可。初始化的话，我这里先是计算了每一个k*1的矩形的R,B各有几个，利于后面k*k矩阵的遍历移动(滑动窗口一样,只不过这里是长条的移动)。
int n,m,k;
int arr[550][550];
char mark[550][550];
pair<int,int> cnt[550][550];
void solve(){ D..
cin>>n>>m>>k;
int red=0,blue=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>arr[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mark[i][j];
if(mark[i][j]=='0') red+=arr[i][j];
else if(mark[i][j]=='1') blue+=arr[i][j];
}
}
bool check=false;
int dif=red-blue;
if(k==1||dif==0) check=true;
for(int i=1;i<=n-k+1;i++){ o(1e8) 初始化
for(int j=1;j<=m;j++){
int r=0,b=0;
for(int f=i;f<=i+k-1;f++){
if(mark[f][j]=='0') r++;
else if(mark[f][j]=='1') b++;
}
cnt[i][j]={r,b};
}
}
set<int> st; st最大是500...st中存在的是因子，需要判断能否通过使用这些因子的倍数组合，组合出dif----多重背包？--不可能，非常庞大X^500次方的级别,X为每个因子最多可以取的次数
for(int i=1;i<=n-k+1;i++){
int r=0,b=0;
for(int j=1;j<=m+1;j++){
if(j<=k) r+=cnt[i][j].first,b+=cnt[i][j].second;
else{
int difrb=abs(r-b);
if(difrb!=0&&dif%difrb==0) check=true;
if(difrb!=0) st.insert(difrb);
if(j!=m+1){
r-=cnt[i][j-k].first,b-=cnt[i][j-k].second;
r+=cnt[i][j].first,b+=cnt[i][j].second;
}
}
}
}
我想知道怎么判断，能否通过使用n个不同的数字a1,a2...an的倍数组合出数字X.即判断是否存在?a1+?a2+...+?an==X,其中?代表系数(可以为0).
int gcd0=*st.begin();
for(auto s:st) gcd0=gcd(gcd0,s);
if(gcd0!=0&&dif%gcd0==0) check=true;
这个st可以省去，直接计算gcd0
if(check) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}