A.Split it!
题意：判断一个字符串是否能使得这条件：s=a1+a2+…+ak+ak+1+R(ak)+R(ak−1)+…+R(a1).成立,并且R(abcd)=dcba。
思路：只需要从两头看，把中间看做a（k+1），所以只要两头相同的字符个数大于等于k即可。
#include<bits/stdc++.h> using namespace std; int main() { int t,i,j,n,k; string s1; cin>>t; while(t--){ cin>>n>>k>>s1; // cout<<s1.length()<<endl; if(k==0){ cout<<"YES"<<endl; } else if(k+k+1>n){ cout<<"NO"<<endl; } else { int cnt=0; for(i=0;i<s1.length()/2;i++){ if(s1[i]==s1[s1.length()-1-i]){ cnt++; } else { break; } } if(cnt>=k){ cout<<"YES"<<endl; } else { cout<<"NO"<<endl; } } } }
B. Max and Mex
题意：有k次操作，每次操作将从0开始数第一个没出现的数字加上数组里出现最大的一个数相加除以2。
思路：乱搞一下能找到规律，因为数组里都是不重复的数，所以如果是一个从0开始的全排列，那么最后数就有n+1个，否则就判断（max+mex）/2所放入的新值有没有出现过并且要判断操作次数要有一次才行。
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+1000; int a[maxn]; int main() { int t,i,j,n,k; cin>>t; while(t--){ cin>>n>>k; map<int ,int >mo; for(i=0;i<n;i++){ cin>>a[i]; mo[a[i]]=1; } sort(a,a+n); int d1=0,max1=a[n-1]; for(i=0;i<n;i++){ if(d1==a[i]){ d1++; continue; } else { break; } } //cout<<d1<<" "<<max1<<endl; if(d1==max1+1){ cout<<n+k<<endl; } else { int m1=(max1+d1)%2==0?(max1+d1)/2:(max1+d1)/2+1; if(mo[m1]==0&&k>=1){ cout<<n+1<<endl; } else { cout<<n<<endl; } } } }
C. Diamond Miner
题意：分别给你x轴上n个点和y轴上n个点，求两两相连所构成的三角形的斜边和最小。
思路：直接排序既可。
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+1000; double x[maxn],y[maxn]; bool cmp(double x1,double y1){ return x1>y1; } int main() { int t,i,j,n; scanf("%d",&t); while(t--){ scanf("%d",&n); double sum=0; int cnt1=0,cnt2=0,x1,y1; for(i=0;i<2*n;i++){ scanf("%d%d",&x1,&y1); if(x1==0) y[cnt1++]=abs(y1); if(y1==0) x[cnt2++]=abs(x1); } sort(y,y+n); sort(x,x+n); int zs1=0,zs2=n-1,ys1=0,ys2=n-1; for(i=0;i<n;i++){ sum+=sqrt(x[i]*x[i]+y[i]*y[i]); } printf("%.16lf\n",sum); } }
