Codeforces Round #706 A~C

A:给了一个比较复杂的定义，但是仔细读了之后就会发现问的就是字符串s的回文长度是否大于等于k，例如abqewba的回文长度是2.

 1 #include<algorithm>
 2 #include<iostream>
 3 using namespace std;
 4  
 5 int main(void){
 6     int t;
 7     cin>>t;
 8     while(t--){
 9         int n,k;
10         cin>>n>>k;
11         string s;
12         cin>>s;
13         int i=0,j=n-1;
14         while(i<j-1){
15             if(s[i]==s[j]) i++,j--;
16             else break;
17         }
18         if(i>=k) cout<<"YES"<<endl;
19         else cout<<"NO"<<endl;
20     }
21     return 0;
22 }

B:分析如下。

 1 #include<cstring>
 2 #include<algorithm>
 3 #include<iostream>
 4 using namespace std;
 5 const int N=1e5+10;
 6 int a[N];
 7 int get_mex(int n){
 8     if(a[0]!=0) return 0;
 9     for(int i=1;i<n;i++){
10         if(a[i]!=a[i-1]+1){
11             return a[i-1]+1;
12         }
13     }
14     return a[n-1]+1;
15 }
16 bool exist(int x,int n){
17     int l=0,r=n-1;
18     while(l<r){
19         int mid=(l+r)>>1;
20         if(a[mid]>=x) r=mid;
21         else l=mid+1;
22     }
23     if(a[l]==x)
24         return true;
25     else
26         return false;
27 }
28 int main(void){
29     int t;
30     cin>>t;
31     while(t--){
32         int n,k;
33         cin>>n>>k;
34         for(int i=0;i<n;i++) cin>>a[i];
35         sort(a,a+n);
36         int b=get_mex(n);
37         int c=a[n-1];
38         if(k==0) cout<<n<<endl;
39         else if((b+c)%2==1){
40             if(b-1==c){
41                 cout<<n+k<<endl;
42             }else{
43                 if(exist(((b+c+1)/2),n)){
44                     cout<<n<<endl;
45                 }else{
46                     cout<<n+1<<endl;
47                 }
48             }
49         }else{
50             if(exist(((b+c+1)/2),n)){
51                     cout<<n<<endl;
52             }else{
53                 cout<<n+1<<endl;
54             }
55         }
56     }
57     return 0;
58 }

C:第三题今早差点给我气炸了，我忘记换行了0.0.

　可以发现这个和正负没有关系，所以全部取正就好了。

 1 #include<cstring>
 2 #include<algorithm>
 3 #include<iostream>
 4 using namespace std;
 5 int n1,n2;
 6 const int N=1e5+10;
 7 double a[N],b[N];
 8 int main(void){
 9     int t;
10     cin>>t;
11     while(t--){
12         n1=0,n2=0;
13         int n;
14         cin>>n;
15         for(int i=0;i<2*n;i++){
16             int t1,t2;
17             cin>>t1>>t2;
18             if(t1==0){
19                 a[n1++]=abs(t2);
20             }else if(t2==0){
21                 b[n2++]=abs(t1);
22             }
23         }
24         sort(a,a+n1);
25         sort(b,b+n2);
26         double res=0;
27         for(int i=0;i<n;i++){
28             res+=sqrt(a[i]*a[i]+b[i]*b[i]);
29         }
30         printf("%.10f
",res);
31     }
32     return 0;
33 }