1.一个数初始为0，先+a，再-b...重复上面操作，总共操作了k次，问最后的数是多少。
#include<bitsstdc++.h> using namespace std; int t; long long a,b,k,ans; int main() { scanf("%d",&t); while(t--) { scanf("%I64d%I64d%I64d",&a,&b,&k); ans=(a-b)*(k/2); if(k%2==1) ans+=a; printf("%I64d ",ans); } }
2.给出一个长度为n的01串，使其不出现101的情况，问最少修改的次数
#include<bitsstdc++.h> using namespace std; int t,n; int ans=0,a[10100]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=3;i<=n;i++) if(a[i-2]==1&&a[i-1]==0&&a[i]==1) { ans++; a[i]=0; } printf("%d ",ans); }
3.给你一个长度为n的序列，删除其中一个数，问你剩下的数中是否存在一个数是其余所有数字的和。（当只有两个数字的时候答案为0）
#include<bitsstdc++.h> using namespace std; int t,n,l=0; int ans=0; struct node{ int c,id; }a[301010]; int p[301000]; long long sum=0; bool cmp(node a,node b) { return a.c<b.c; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i].c),a[i].id=i,sum+=a[i].c; if(n==2) { printf("0 "); return 0; } sort(a+1,a+1+n,cmp); if(sum-a[n].c==2ll*a[n-1].c) p[++l]=a[n].id; for(int i=1;i<n;i++) { if(sum-a[i].c==2ll*a[n].c) { p[++l]=a[i].id; } } printf("%d ",l); for(int i=1;i<=l;i++) printf("%d ",p[i]); }
4.有一个长度为n的序列，从中选出k个数，使其在序列中出现的次数最多。（不能重叠，但可以无序）
7 3
1,2,3,2,4,3,1
那就是1 2 3 出现了两次
算法：按照每个数出现的次数多少进行排序，然后二分答案（次数）
#include<bitsstdc++.h> using namespace std; struct node{ int c,id; }a[301000]; int n,m,x,p,q=0; bool cmp(node a,node b) { return a.c>b.c; } bool check(int x) { int ans=0; for(int i=1;i<=p;i++) { if(a[i].c/x==0) return 0; ans+=a[i].c/x; if(ans>=m) return 1; } } int main() { scanf("%d%d",&n,&m);p=2e5+5; for(int i=1;i<=n;i++) { scanf("%d",&x); a[x].c++;a[x].id=x; } sort(a+1,a+1+p,cmp); int l=1,r=n,ans=1; while(l<=r) { int mid=(l+r)/2; if(check(mid)){ans=mid;l=mid+1;} else r=mid-1; } for(int i=1;i<=p;i++) for(int j=1;j<=a[i].c/ans;j++) { q++; if(q>m) return 0; printf("%d ",a[i].id); } }
5.有一个长度为n的序列，想从中选出最多的数，使其满足：每天选出的数字必须相同，且出现的次数是前一天的两倍，第一天没有限制
算法：枚举第一天选的数字次数，判断是否符合条件（二分判断），算出答案取个max
#include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<map> using namespace std; map <int,int > b; int a[301010],p[301010],l=0,n,ans=0,x,m=0; int main() { scanf("%d",&n);b.clear(); for(int i=1;i<=n;i++) { scanf("%d",&x); if(b[x]==0) b[x]=++l; a[b[x]]++; } sort(a+1,a+1+l); ans=a[l]; for(int i=1;i<=a[l];i++) { int sum=0,k=0,j=0; while(1) { int L=j+1,r=l,an=l+1; while(L<=r) { int mid=(L+r)/2; if(a[mid]>=i*(1<<k)){an=mid;r=mid-1;} else L=mid+1; } j=an; if(j>l) break; sum+=i*(1<<k);k++; } ans=max(ans,sum); } printf("%d ",ans); }
6-7 给出n个数选出其中的x个，使其和最大（而且必须相邻的k个数必须取一个）
算法：动态规划，f[i][j]表示选了i个数选到第j个数了获得的最大价值，转移是k，但可以用单调队列优化
#include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<cmath> #include<map> using namespace std; struct node{ long long c,id; }q[5010]; int n,k,x,a[5110]; long long f[5110][5110]; int main() { scanf("%d%d%d",&n,&k,&x); for(int i=1;i<=n;i++) scanf("%d",&a[i]); memset(f,-1,sizeof(f)); for(int i=1;i<=k;i++) f[1][i]=a[i]; for(int i=2;i<=x;i++) { int l=1,r=1; q[1].id=1;q[1].c=f[i-1][1]; for(int j=2;j<=n;j++) { while(q[l].id+k<j&&l<=r) l++; if(l<=r&&q[l].c!=-1) f[i][j]=max(f[i][j],q[l].c+1ll*a[j]); while(q[r].c<=f[i-1][j]&&l<=r) r--; q[++r].c=f[i-1][j];q[r].id=j; } } long long ans=-1; for(int i=n-k+1;i<=n;i++) ans=max(ans,f[x][i]); printf("%I64d ",ans); }