题目链接：http://codeforces.com/contest/1348
A
思路：分成两部分，一部分里面的和先置为最大的2^n，然后另一部分置为2^(n-1),然后将1~n-2拆分，前一半分到2^n那部分去，剩余的另一半分给2^(n-1)那部分
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <list> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; typedef double db; typedef long long ll; ll qmi(int m, int k) { int res = 1, t = m; while (k) { if (k&1) res = res * t; t = t * t; k >>= 1; } return res; } int main() { #ifdef ONLINE_JUDGE #else freopen("in.txt","r",stdin); #endif int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); if(n==2) { printf("2 "); continue; } ll a[50],b=0,c=0; for(int i=1;i<=n;i++) { a[i]=qmi(2, i); } b=a[n]; c=a[n-1]; for(int i=1;i<=(n-2)/2;i++) { b+=a[i]; } for(int i=(n-2)/2+1;i<=(n-2);i++) { c+=a[i]; } printf("%lld ",abs(b-c)); } return 0; }
B
思路：既然要求每k个子序列的和都一致，那么先求出不同数的个数，如果比k大，那么肯定不存在输出“-1”,存在的话找出k个数输出n遍即可，如果不同数的个数小于k，记不同数的数组为b，长度为len ,那么在后面添加k-len个b[0]即可，输出n遍
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <list> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; typedef double db; typedef long long ll; const int maxn=2e5+10; int main() { #ifdef ONLINE_JUDGE #else freopen("in.txt","r",stdin); #endif int t; scanf("%d",&t); while(t--) { int n,k; scanf("%d%d",&n,&k); int a[105]; for(int i=0;i<n;i++) scanf("%d",a+i); map<int,int>m; for(int i=0;i<n;i++) m[a[i]]++; if(k<m.size()) printf("-1 "); else{ printf("%d ",n*k); int b[maxn]; int ops=0; for(auto ss:m){ b[ops++]=ss.first; } int num=ops; for(int i=0;i<k-num;i++) { b[ops++]=b[0]; } for(int i=0;i<=n-2;i++) { for(int j=0;j<ops;j++) { printf("%d ",b[j]); } } for(int j=0;j<ops;j++) { if(j==ops-1) printf("%d ",b[j]); else printf("%d ",b[j]); } } } return 0; }
C
思路：将一个字符串分成k份，至少个数为1，求分成后的字符串字典序最大的最小字符串。排序后我们先分前k个，当str[0]和str[k-1]不相等的时候，那么答案就是str[k-1]了，其余的都分给其他部分，字典序都比str[k-1]小，同时满足最大的字符串的最小值。然后当str[0]和str[k-1]相等的时候，那么目标字符串的第一个元素就是str[0]，这时候再看k到n的字符串一样不一样，如果依旧一样，那么先把排序后的字符串的第一个元素给目标串，然后剩余的(n-1)/k这样分配，输出即可。这段区间有不相同的字符时，直接把这段区间的字符串放在排序后第一个元素后面即可。
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <list> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; typedef double db; typedef long long ll; const int maxn=2e5+10; int main() { #ifdef ONLINE_JUDGE #else freopen("in.txt","r",stdin); #endif int t; scanf("%d",&t); while(t--) { int n,k; string str; scanf("%d%d",&n,&k); cin>>str; sort(str.begin(),str.end()); if(str[0]!=str[k-1]) { cout<<str[k-1]<<endl; continue; } cout<<str[0]; if(str[k]!=str[n-1]) { for(int i=k;i<n;i++)cout<<str[i]; //s+=str[k]; } else { for(int i=0;i<(n-1)/k;i++)cout<<str[k]; // s+=str[i]; } cout<<endl; } return 0; }