A. Card Game
题意:
有T组样例:
对于每组样例:共有n张牌,其中A有k1张,B有k2张,每张牌标号i互不相同,游戏规则:每次两人各出一牌,牌号大的一方会得到这两张牌,直到其中一方无牌, 最后有牌的一方获胜。
思路:找最大的数即可,等于是大王无限赢然后赢完之后还能用.
#include<bits/stdc++.h> using namespace std; int main() { int n,i,j,t; cin>>t; while(t--){ int d1,d2,d3; cin>>d1>>d2>>d3; int f1=0; for(i=0;i<d2;i++){ cin>>j; if(j==d1) f1=1; } for(i=0;i<d3;i++) cin>>j; if(f1==1) { scYES; } else scNO; } return 0; }
B. Interesting Subarray
题意:给出一个数列,要求找出一段连续的子数列满足这个子数列的最大值与最小值之差不小于其元素个数(子数列可以是原数列).
思路:只要这两个元素的差不小于2即为可行,因此我们在输入的同时比较相邻的元素判断是否可行即可。其实可以倒推一下
(ps:刚刚看有人敲了线段树调了一小时没搞出来orz)
#include<bits/stdc++.h> using namespace std; int main() { int n,m,t,j,i; cin>>t; while(t--){ cin>>n; int mm,ff=0,ans; for(i=0;i<n;i++){ cin>>j; if(i==0){ mm=j; } else { if(abs(j-mm)>1){ ans=i; ff=1; mm=j; } else { mm=j; } } } if(ff==1){ scYES; cout<<ans<<" "<<ans+1<<endl; } else { scNO; } } }
C. Make Good
题意:给你一串数字,让你在其中插入最多3个数字(可以不插入),使得这些数字的总和等于异或的2倍,只要给出任何一种方案即可。
思路:
先说模拟时自己的思路:当时对着样例模了一会列了几个例子,像12,24,36,48这种数如果左边求和是这些数中的sum1,假定为A类。
那过程就是先求出左边的和ans1,再求出右边的异或结果ans2,然后左边的最多能加的数是need1=sum1-ans1
然后把那个数/2再异或,就是need2=sum1/2^ans2 就是我右边要求的值
那么直接判断右边加的值 need2>=need1,need%2==0(一定成立)
所以我need2=需要加的两个值,第一个值就是直接加need2,然后sum1-=need2,这个时候得到的值一定是偶数,所以另外两个加相同的数,异或结果不变,然后暴力枚举sum1就过了,好像没人和我一样= =
#include<bits/stdc++.h> using namespace std; #define int long long signed main() { int t,i,j,n; cin>>t; while(t--){ int z1=0,y1=0; cin>>n; for(i=0;i<n;i++){ cin>>j; z1+=j; y1^=j; } if(z1==y1*2){ cout<<0<<endl<<endl; } else { int mm=12,cnt1; for(i=0;;mm*=2) { cnt1=mm; int yy=cnt1/2; yy^=y1; cnt1-=yy; cnt1-=z1; if(cnt1<0) continue; else if(cnt1==0){ cout<<1<<endl<<yy<<endl; break; } else { cout<<3<<endl<<yy<<" "; cout<<cnt1/2<<" "<<cnt1/2<<endl; break; } } } } return 0; }