这场比赛除了E题涉及到了一点前缀和以外，其他的应该都是思维题，难度不大，但是想不到的话做起来还是比较吃力。（忽略我菜）
题目大意：给两个整数n,k，问n能否由k个整数相加而来，且这k个整数%2的结果相等。
这个题一开始想歪了，其实只要根据奇数+奇数=偶数，偶数+偶数=偶数，奇数+偶数=奇数，这个原则来思考就行，因为这k个整数要么全是奇数，要么全是偶数
所以我们只需要对n和k的奇偶性进行判断
当n为奇数的话，只能是全为奇数才能满足，并且k也要是奇数
n为偶数的话，因为最小的偶数是2，所以当n>2k时，一定满足n可以由k个偶数相加而成
当n<2k时，只能是k个奇数构成，这是也要对k进行奇偶校验。
具体看代码
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <algorithm> 5 #include <queue> 6 #include <stack> 7 #include <stdio.h> 8 #include <cmath> 9 #include <string.h> 10 11 using namespace std; 12 #define ll long long 13 static const int WHITE=0; 14 static const int GRAY=1; 15 static const int BLACK=2; 16 static const int INF=0x3f3f3f3f; 17 int gcd(int a,int b){return b == 0 ? a : gcd(b,a%b);} 18 int lcm(int a,int b){return a*b/gcd(a,b);} 19 ll Pow(ll a,ll b,ll mod){if(b==0) return 1%mod; ll sum=1; a=a%mod; while(b>0) { if(b%2==1) sum=(sum*a)%mod; b/=2; a=(a*a)%mod;}return sum;} 20 21 int main() 22 { 23 //freopen("C:\Users\16599\Desktop\in.txt","r",stdin); 24 int T; 25 cin>>T; 26 while(T--) 27 { 28 ll n,k; 29 cin>>n>>k; 30 if(n<k) 31 { 32 cout<<"NO"<<endl; 33 continue; 34 } 35 if(n%2==1) 36 { 37 if(k%2!=1) 38 { 39 cout<<"NO"<<endl; 40 continue; 41 } 42 else 43 { 44 cout<<"YES"<<endl; 45 for(int i=1;i<=k-1;i++) 46 cout<<"1"<<" "; 47 cout<<n-(k-1)<<endl; 48 } 49 50 } 51 else 52 { 53 if(n>=2*k) 54 { 55 cout<<"YES"<<endl; 56 for(int i=1;i<=k-1;i++) 57 cout<<"2"<<" "; 58 cout<<n-2*(k-1)<<endl; 59 } 60 else 61 { 62 if(k%2==0) 63 { 64 cout<<"YES"<<endl; 65 for(int i=1;i<=k-1;i++) 66 cout<<"1"<<" "; 67 cout<<n-(k-1)<<endl; 68 } 69 else 70 cout<<"NO"<<endl; 71 } 72 } 73 } 74 return 0; 75 }
题目大意，给定一个长度为n的数列，问数列中有多少个元素可以是数列的任意连续子序列的和
只需要求前缀和，将所有可能的连续子序列的和求出来标记，再遍历一遍数列统计个数
需要注意的是这题的内存只有64，所以要根据ai<=n这个条件来进行优化，及如果连续子序列的和都大于n的话，就不需要标记了，一定不存在。
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <algorithm> 5 #include <queue> 6 #include <stack> 7 #include <stdio.h> 8 #include <cmath> 9 #include <string.h> 10 11 using namespace std; 12 #define ll long long 13 static const int WHITE=0; 14 static const int GRAY=1; 15 static const int BLACK=2; 16 static const int INF=0x3f3f3f3f; 17 int gcd(int a,int b){return b == 0 ? a : gcd(b,a%b);} 18 int lcm(int a,int b){return a*b/gcd(a,b);} 19 ll Pow(ll a,ll b,ll mod){if(b==0) return 1%mod; ll sum=1; a=a%mod; while(b>0) { if(b%2==1) sum=(sum*a)%mod; b/=2; a=(a*a)%mod;}return sum;} 20 int a[8010],sum[8010]; 21 bool v[8010]; 22 int main() 23 { 24 //freopen("C:\Users\16599\Desktop\in.txt","r",stdin); 25 int T; 26 cin>>T; 27 while(T--) 28 { 29 int n; 30 cin>>n; 31 for(int i=1;i<=n;i++) 32 { 33 cin>>a[i]; 34 sum[i]=sum[i-1]+a[i]; 35 } 36 for(int i=0;i<=n;i++) 37 { 38 for(int j=i+2;j<=n;j++) 39 { 40 if(sum[j]-sum[i]<=n) 41 v[sum[j]-sum[i]]=true; 42 } 43 } 44 int cnt=0; 45 for(int i=1;i<=n;i++) 46 if(v[a[i]]) 47 cnt++; 48 cout<<cnt<<endl; 49 memset(v,false,sizeof(v)); 50 } 51 return 0; 52 }
F. Binary String Reconstruction
这一题我个人认为是最难想且坑点最多的题了，我也是看了别人的思路才会写的
题目大意，给定三个数n0,n1,n2，构造一个01串，并且这个串满足有n0个"00"，n1个"01"或"10"，n2个"11"。
构造方法 由于n0和n2只有0和1所以如果他们同时存在，则必有一个n1，所以先判断n1是否存在
n1若存在，则通过11110000这种先1后0的形式处理完n0和n2，最后只要在后面加01即可
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <algorithm> 5 #include <queue> 6 #include <stack> 7 #include <stdio.h> 8 #include <cmath> 9 #include <string.h> 10 11 using namespace std; 12 #define ll long long 13 static const int WHITE=0; 14 static const int GRAY=1; 15 static const int BLACK=2; 16 static const int INF=0x3f3f3f3f; 17 int gcd(int a,int b){return b == 0 ? a : gcd(b,a%b);} 18 int lcm(int a,int b){return a*b/gcd(a,b);} 19 ll Pow(ll a,ll b,ll mod){if(b==0) return 1%mod; ll sum=1; a=a%mod; while(b>0) { if(b%2==1) sum=(sum*a)%mod; b/=2; a=(a*a)%mod;}return sum;} 20 21 int main() 22 { 23 //freopen("C:\Users\16599\Desktop\in.txt","r",stdin); 24 int T; 25 cin>>T; 26 while(T--) 27 { 28 int n1,n2,n3; 29 cin>>n1>>n2>>n3; 30 if(n2==0) 31 { 32 if(n1!=0) 33 for(int i=0;i<=n1;i++) 34 cout<<"0"; 35 if(n3!=0) 36 for(int i=0;i<=n3;i++) 37 cout<<"1"; 38 cout<<endl; 39 continue; 40 } 41 n2--; 42 for(int i=0;i<=n3;i++) 43 cout<<"1"; 44 for(int i=0;i<=n1;i++) 45 cout<<"0"; 46 int now=1; 47 while(n2--) 48 { 49 cout<<now; 50 now^=1; 51 } 52 cout<<endl; 53 } 54 return 0; 55 }
这题也是一个构造题
题目大意，给定一个整数n，你需要把1-n的n个整数重新排列，使得到的这个数列相邻两个数的差的绝对值在2-4之间。
由于奇数之间相差为2，偶数之间相差为2，所以分奇偶，从两边同时向中间构造即可，以10为例
10 8 6 4 2 1 3 5 7 9
注意在1和2之间不满足题意，所以在处理这一步的时候只要把2和4换个位置，然后n==2,n==3时特判即可
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <algorithm> 5 #include <queue> 6 #include <stack> 7 #include <stdio.h> 8 #include <cmath> 9 #include <string.h> 10 11 using namespace std; 12 #define ll long long 13 static const int WHITE=0; 14 static const int GRAY=1; 15 static const int BLACK=2; 16 static const int INF=0x3f3f3f3f; 17 int gcd(int a,int b){return b == 0 ? a : gcd(b,a%b);} 18 int lcm(int a,int b){return a*b/gcd(a,b);} 19 ll Pow(ll a,ll b,ll mod){if(b==0) return 1%mod; ll sum=1; a=a%mod; while(b>0) { if(b%2==1) sum=(sum*a)%mod; b/=2; a=(a*a)%mod;}return sum;} 20 21 int main() 22 { 23 //freopen("C:\Users\16599\Desktop\in.txt","r",stdin); 24 int T; 25 cin>>T; 26 while(T--) 27 { 28 int a; 29 cin>>a; 30 if(a==2||a==3) 31 { 32 cout<<"-1"<<endl; 33 continue; 34 } 35 if(a%2==1) 36 { 37 for(int i=a;i>=1;i-=2) 38 cout<<i<<" "; 39 cout<<"4 "<<"2 "; 40 for(int i=6;i<=a;i+=2) 41 cout<<i<<" "; 42 } 43 else 44 { 45 for(int i=a-1;i>=1;i-=2) 46 cout<<i<<" "; 47 cout<<"4 "<<"2 "; 48 for(int i=6;i<=a;i+=2) 49 cout<<i<<" "; 50 } 51 cout<<endl; 52 } 53 return 0; 54 }