A. Red and Blue Beans
题意： 你有红色球n个，蓝色球m个，假设你可以用无数个背包，每个背包里最少放一个红球和篮球，求背包中红色球和蓝色球相差最大个数的最小值。
思路：模拟着放，每个包都尽量按比例放n/m，然后判断差是否在K以内。
#include<bits/stdc++.h> using namespace std; int main() { int t,i,j,n; cin>>t; while(t--){ int a,b,c; cin>>a>>b>>c; int ans=max(a,b)%min(a,b)==0?max(a,b)/min(a,b):max(a,b)/min(a,b)+1; if(ans-1<=c){scYES;} else scNO; } return 0; }
B. The Cake Is a Lie
题意：起点是（1,1），有两种走法，一种是向右走，需要和横坐标一样大的花费，一种是向下走，需要和纵坐标一样大的花费，求最后的花费是否为k。
思路：其实一开始就觉得它的花费是定值，然后推花费的时候推错了，其实既然怎么走都是一样的花费，那我就走一条路求花费就行了，看别人的式子那么简单就一行就我模拟跑的
#include<bits/stdc++.h> using namespace std; int main() { int t,i,j; cin>>t; while(t--){ int n,m,k; cin>>n>>m>>k; int ans1=0; for(i=1;i<=n-1;i++){ ans1+=1; } for(j=1;j<=m-1;j++){ ans1+=i; } if(ans1==k){ scYES; } else { scNO; } } return 0; }
C. Berland Regional
题意：有n位同学，分别来自不同的学校，有不同的编程水平，每个学校可以派出n个队，求当每个队人数为k时，每个学校派出的队伍的编程水平总和。
思路：首先开个结构体先按照学校排序再按分数排，观察规律，不难发现如果学校的人数%每个队的人数=0时，即可全员出动，那么ans【k】就等于学校总人数的和，否则，每个队都会剩下一部分人无法组队，然后按照学校遍历，再按照人数遍历对答案有贡献的值即可(就是能派出的队伍)，估摸着复杂度不会t，还可以用前缀和优化一下。
#include<bits/stdc++.h> using namespace std; #define int long long const int maxn=2*1e5+100000; struct node { int u; int s; }mo[maxn]; int u[maxn]; int ans[maxn]; int sum[maxn]; bool cmp(node a,node b){ if(a.u==b.u){ return a.s>b.s; } else { return a.u<b.u; } } signed main() { int t,i,j,n,q; scanf("%lld",&t); while(t--){ memset(ans,0,sizeof(ans)); map<int ,int >m1; scanf("%lld",&n); for(i=0;i<n;i++){ scanf("%lld",&u[i]); mo[i].u=u[i]; m1[u[i]]++; } for(i=0;i<n;i++){ scanf("%lld",&mo[i].s); } sort(mo,mo+n,cmp); int cnt=1; for(i=0;i<n;){ int js=m1[cnt++]; sum[0]=0; for(int d1=0;d1<js;d1++) { sum[d1+1]=sum[d1]+mo[i+d1].s; } for(int k=1;k<=js;k++){ if(js%k==0) ans[k]+=sum[js]; else ans[k]+=sum[(js/k)*k]; } i+=js; } for( q=1;q<=n-1;q++){ printf("%lld ",ans[q]); } printf("%lld\n",ans[q]); } return 0; }
D. Maximum Sum of Products
题意：给你两个数组a和b，它的总价值是相同位置相乘的和(a1×b1+a2×b2…这样)，然后可以操作一次，翻转a数列的一个子区间，问翻转哪段子区间可以得到最大的价值。
思路：大佬说像区间dp，其实有点类似之前校赛做过的一道题，其实就是先选定一个点，然后扩大他们的左区间和右区间长度，那么他的翻转其实只有最外面的改变了
#include<bits/stdc++.h> using namespace std; #define int long long const int maxn=5005; signed main() { int n,i,j,k,a[maxn],b[maxn],sum=0; cin>>n; for(i=0;i<n;i++) cin>>a[i]; for(i=0;i<n;i++) cin>>b[i]; for(i=0;i<n;i++) sum+=a[i]*b[i]; int ans=sum; for(i=0;i<n;i++){ int m1=sum; for(j=i-1,k=i+1; (j<n&&j>=0)&&(k<n&&k>=0); j--,k++){ m1-=a[j]*b[j]+a[k]*b[k]; m1+=a[j]*b[k]+a[k]*b[j]; ans=max(ans,m1); } m1=sum; for( j = i, k = i + 1; (j<n&&j>=0)&&(k<n&&k>=0); j--, k++){ m1 -= a[j] * b[j] + a[k] * b[k]; m1 += a[j] * b[k] + a[k] * b[j]; ans = max(ans, m1); } } cout<<ans<<endl; return 0; }
