题意：有n个数，21 , 22 , 23…2n(n保证为偶数).将这n个数平均分成两组，求怎么分才能使这两组的差的绝对值最小。
由等比数列求和可得前n-1项的和为2n-2 大于第n项2n ，其中一组为2n加上前n/2-1项，前n/2-1项的和为2n/2-2
则另外一组为前n项的和减这一组，使两组相减差的绝对值最小
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int main(){ int t,n; cin>>t; while(t--){ cin>>n; int sum1=0,sum2=0; sum1=pow(2,n)+pow(2,n/2)-2; sum2=pow(2,n+1)-2-sum1; cout<<abs(sum1-sum2)<<endl; } return 0; }
题意：给序列长n的数组和k。完美数组的定义是数组中每一个连续k项的子段和为定值，在数组中插入一些数使其变成完美数组，
如果可以构成输出完美数组，否则输出-1。数组中数的种类大于k时，不可能构造出完美数列。反之用原数组中出现的数
开始构造一个连续k项的子段，不足k用其他的数补。
#include<iostream> #include<cstdio> #include<cmath> #include<string> #include<cstring> #include<set> using namespace std; #define maxn 100010 int a[maxn],b[maxn],flag[maxn]; int main(){ int t,i,j; cin>>t; while(t--){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(flag,0,sizeof(flag)); int n,k,num=1; cin>>n>>k; for(i=1;i<=n;i++){ cin>>a[i]; if(flag[a[i]]==0){ flag[a[i]]=1; b[num++]=a[i]; } } if(num-1>k){ cout<<"-1"<<endl; }else{ for(i=1;i<=100;i++){ if(flag[i]==0){ b[num]=i; if(num==k) break; num++; } } cout<<n*k<<endl; for(i=1;i<=n;i++){ for(j=1;j<=k;j++){ cout<<b[j]<<" "; } } cout<<endl; } } return 0; }
题意：给a,b；花a元可以使x或y加一或减一，花b元可以使x和y同时加一或减一，求使x=y=0时，花费的最少钱数
因为无论是怎么算都得先使x和y相等，即先计算他们之间的差值
所以出现了两种算法 1.|x-y|*a+min（x，y）*b
2.|x-y|*a+min（x，y）*2*a；
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> using namespace std; int main(){ int t; cin>>t; while(t--){ long long x,y,a,b; long long sum1=0,sum2=0; cin>>x>>y>>a>>b; sum1=abs(x-y)*a+min(x,y)*b; sum2=abs(x-y)*a+min(x,y)*2*a; cout<<min(sum1,sum2)<<endl; } return 0; }
题意：给一个只由0和1构成的字符串s，求一个字符串t，使s是t的字串，且t的长度小于等于s长度的两倍，且循环节长度尽量小。
t是s的子序列，t可以通过删除零个或多个元素而不改变其余元素的顺序从而生成s
如果字符串全是1或者全是0，直接输出字符串本身。若即含有0也含有1，就01或10循环输出
#include<iostream> #include<algorithm> #include<cstdio> #include<string> #include<cmath> using namespace std; int main(){ int t; cin>>t; while(t--){ int flag1=0,flag2=0; string s; cin>>s; for(int i=0;i<s.length();i++){ if(s[i]==‘0‘){ flag1=1; }else{ flag2=1; } } if(flag1&&flag2){ for(int j=1;j<=s.length();j++){ cout<<"10"; } cout<<endl; }else{ cout<<s<<endl; } } return 0; }
题意：给n个数a-b<=x<=a+b,y=n*x c-d<=y<=c+d;
若（a+b）*n<c+d，或者（a-b）*n>c+d 则输出“No”，反之输出“Yes”
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> using namespace std; int main(){ int t; cin>>t; while(t--){ int a,b,c,d,n; cin>>n>>a>>b>>c>>d; if(n*(a-b)>c+d||n*(a+b)<c-d){ cout<<"No"<<endl; }else{ cout<<"Yes"<<endl; } } return 0; }
题意：把一个很长门扔到连着的n座山上，门如果掉到山峰上就会变成成两半。某座山的高度比左右两座山
都高的叫做山峰给n座山的高度a[i],求门最多可以断成几节（山峰数加1）和此时门的最左边在第几座
山上。即在区间k上尽可能的找到最多的山峰
记录每个点前面的山峰数，然后求每k段里面山峰的数，找到山峰数最多的
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; #define maxn 200010 int a[maxn],b[maxn]; int main(){ int t; cin>>t; while(t--){ int n,k,sum1=0,sum2=0; int max=0,flag=1; cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ if(a[i]>a[i-1]&&a[i]>a[i+1]){ sum1++; } b[i]=sum1; } for(int i=1;i<=n-k+1;i++){ sum2=b[i+k-2]-b[i]; if(sum2>max){ max=sum2; flag=i; } } cout<<max+1<<" "<<flag<<endl; } return 0; }
原文：https://www.cnblogs.com/yy0826/p/12933839.html
