D1T1：水题
D1T2：
D1T3：换教室
D2T1：组合数问题
题解：
杨辉三角基础应用+二维差分
#include <cstdio> using namespace std; int c[2005][2005],g[2005][2005]; int main() { int T,i,j,k; scanf("%d%d",&T,&k); for (i=0;i<=2000;i++) c[i][0]=1; for (i=1;i<=2000;i++) { for (j=1;j<=i;j++) { c[i][j]=(c[i-1][j]+c[i-1][j-1])%k; if (c[i][j]==0) g[i][j]=1; g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1]; } g[i][i+1]=g[i][i];//求前缀和中必不可少的哦 } while (T--) { int n,m; scanf("%d%d",&n,&m); if(m>n) m=n; printf("%d\n",g[n][m]); } }D2T2：蚯蚓
很简单的75送分，用自带的priority_queue，但是这样会T
我们可以发现，如果自己建立三个单调队列，q1未切割的蚯蚓长度，q2切割后较长的蚯蚓长度，q3切割后较短的蚯蚓长度
只要把读入的数据排个序就可以发现这三个都是单调队列
那每次在队首取max，然后弹出。
#include <cstdio> #include <queue> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> #define N 7050005 #define INF 1e9 using namespace std; double p; int q1[N],q2[N],q3[N],h1,t1,h2,t2,h3,t3,qq,a[100005]; void pts75() { priority_queue<int>q; int n,m,qq,u,v,t,x=1,i; scanf("%d%d%d%d%d%d",&n,&m,&qq,&u,&v,&t); p=(double)u/(double)v; for (i=1;i<=n;i++) { int a; scanf("%d",&a); q.push(a); } for(i=1;i<=m;i++) { int now=q.top(); q.pop(); int noww=now+(i-1)*qq; if (i==x*t) { x++;printf("%d ",noww); } int a1=floor((int)noww*p),a2=noww-a1; q.push(a1-i*qq); q.push(a2-i*qq); } printf("\n"); i=1;x=1; while (!q.empty()) { int now=q.top(); q.pop(); if (i==x*t) {x++;printf("%d ",now+m*qq);} i++; } } int findmax(int i) { int a1,a2,a3; if (h1<=t1) a1=q1[h1];else a1=-INF; if (h2<=t2) a2=q2[h2];else a2=-INF; if (h3<=t3) a3=q3[h3];else a3=-INF; if (a1>=a2 && a1>=a3){h1++;return a1+i*qq;} if (a2>=a1 && a2>=a3){h2++;return a2+i*qq;} h3++; return a3+i*qq; } int main() { int n,m,u,v,t,x=1,i; scanf("%d%d%d%d%d%d",&n,&m,&qq,&u,&v,&t); p=(double)u/(double)v; for (i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); for (i=n;i>=1;i--) q1[++t1]=a[i]; h1=1;h2=1;h3=1; for(i=1;i<=m;i++) { int noww=findmax(i-1); if (i==x*t){x++;printf("%d ",noww);} int a1=floor((int)noww*p),a2=noww-a1; q2[++t2]=max(a1,a2)-i*qq; q3[++t3]=min(a1,a2)-i*qq; } printf("\n"); x=1; for (i=1;i<=n+m;i++) { int noww=findmax(m); if (i==x*t) {x++;printf("%d ",noww);} } } D2T3： 愤怒的小鸟