\(T1：\) 选彩笔（rgb）
思路：
签到题 （但是没签上），二分答案，在写一个三维前缀和\(check\)一下就搞定了。如果忘记三维前缀和的话，请看这里
代码：
$code$
#include<iostream>
using namespace std;
const int N=1e4+5;
int n,m,b,g,r,x,y,z,ans,num,maxn,sum[260][260][260],cnt[260][260][260];
inline bool check(int mid){for(int i=1;i+mid<=maxn;i++){for(int j=1;j+mid<=maxn;j++){for(int k=1;k+mid<=maxn;k++){x=i+mid;y=j+mid;z=k+mid;num=sum[x][y][z]-sum[i-1][y][z]-sum[x][j-1][z]-sum[x][y][k-1]+sum[i-1][j-1][z]+sum[i-1][y][k-1]+sum[x][j-1][k-1]-sum[i-1][j-1][k-1];//三位差分 if(num>=m) return 1;//如果这里的笔数大于等于题目要求的话 可以成为答案 }}}return 0;
}
signed main(){
// freopen("rgb.in","r",stdin);
// freopen("rgb.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>m;for(int x=1;x<=n;x++){cin>>r>>g>>b;cnt[++r][++g][++b]++;//统计每个点出现的笔的个数 maxn=max(maxn,max(g,max(r,b)));//最大值 }for(int i=1;i<=maxn;i++){for(int j=1;j<=maxn;j++){for(int k=1;k<=maxn;k++){sum[i][j][k]=cnt[i][j][k]+sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1]-sum[i-1][j-1][k]-sum[i][j-1][k-1]-sum[i-1][j][k-1]+sum[i-1][j-1][k-1];//三位前缀和 }}}int l=1,r=maxn;ans=maxn;while(l<=r){//二分答案 int mid=(l+r)>>1;if(check(mid)) ans=mid,r=mid-1;else l=mid+1;}cout<<ans<<endl;return 0;
}
\(T2：\) 兵蚁排序（sort）
思路：
这道题非常友好的一点在于只要随便输出一种方案就行，不需要求最小方案。因此，我们观察大样例可得，这个方案跟冒泡排序相似，次数呢跟逆序对个数一样。就没啦。
代码：
$code$
#include<iostream>
using namespace std;
const int N=1e6+10;
int T,n,cnt,l,r,a[N],b[N];pair<int,int> p[N];
int main(){freopen("sort.in","r",stdin);freopen("sort.out","w",stdout);ios::sync_with_stdio(false);cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];cnt=0;l=1;r=n;while(a[l]==b[l]) l++;while(a[r]==b[r]) r--;//一样的就不用管了 if(r<l){cout<<"0\n0\n";continue;}//a与b完全一样 那还指挥啥 for(int i=l;i<=r;i++){if(a[i]==b[i]) continue;//同16 int id=-1;for(int j=i+1;j<=r;j++){if(a[j]==b[i]){id=j;break;}//记录下对应的位置 }for(int j=id;j>i;j--){if(a[j]<a[j-1]) swap(a[j],a[j-1]),p[++cnt]={j-1,j};//冒泡排序 else break;}if(a[i]!=b[i]){//排不过去 不符合题意 cout<<"-1\n";cnt=0;break;}}if(!cnt) continue;//已经输出-1了 cout<<"0\n"<<cnt<<'\n';//输出方案数 for(int i=1;i<=cnt;i++) cout<<p[i].first<<" "<<p[i].second<<'\n';//输出操作 }return 0;
}
\(T3：\)人口局 DBA（dba）
思路：
借鉴自大佬
一道式子超级难推的数位\(DP\)。（其实可能也没有那么难推）
先推式子。设\(h(l,sum)\)表示长度为\(l\)总和为\(sum\)的方案数。难点在于每一位上的数必须小于\(m\)。然后考虑用二项式繁衍反演进行容斥。设\(f(x)\)表示恰有\(i\)个位置不满足的方案数，\(g(x)\)表示至少有\(i\)个不满足的方案数（注意这里是「选择类问题」里的至少，不是「钦定类问题」，详情见这里），然后我们先把二项式反演的式子列出来$$g(x)=\sum_{i-x}^l\tbinom{i}{x}f(i)$$
先考虑求解\(g(x)\)，我们知道总和为\(sum\)，先忽略限制的话由插板法可得方案数为\(\tbinom{sum+l-1}{l-1}\)。这里可以理解为：原来有\(x\)个球，后来又放进去\(y-1\)个，然后选出\(y-1\)个球涂色作为板子将原来的东西分为\(y\)个部分。假设现在有\(x\)个位置的值大于\(m\)，那就让这\(x\)个值先为\(m\)，可以得出剩下值的和为\(sum-x*m\)，方案数就为\(\tbinom{sum-x*m+l-1}{l-1}\)。所以，我们可得最后方案数为\(g(x)=\tbinom{l}{x}\tbinom{sum-xm+l-1}{l-1}\)
然后反演求\(f(x)\)
\(h(l,sum)\)的值即为对应\(l,sum\)下的\(f(0)\)，所以可得
然后考虑数位\(dp\)，设第\(i\)位的贡献为\(ans_i\)，则\(ans_i=\sum_{i=0}^{a[i]-1}h(l-1,sum-i)\).然后推式子$$ans_k=\sum_{i=0}^{a[k]-1}h(l-1,sum-i)$$
然后考虑优化最后的那个\(\sum\)，把它跟杨辉三角联系起来优化。
如图，我们想求\(1+2+3\)的话只需要求出\(10-4\)即可。
同理，把组合数放到杨辉三角上，可得\(\sum_{i=0}^{x}\tbinom{a+b-i}{a}=\tbinom{a+b+1}{a+1}+\tbinom{a+b-x}{a+1}\)
于是，上述式子可以化简为
最后遍历一下每个位置，把贡献求和就行了。
\(ps：\) 终于写完了！！！！这堆式子差点累死我！！我感觉我快要瞎了！！！这题解比这题都难写！！
代码：
$code$
#include<iostream>
#define int long long
using namespace std;
const int N=2050,mod=1e9+7;
int m,l,sum,ans,num,op,a[N],fac[4000004],inv[4000004];
inline int qpow(int x,int y){int res=1;while(y){if(y&1) res=(res*x)%mod;x=(x*x)%mod;y>>=1;}return res;
}//快速幂
inline int C(int n,int m){if(n<m) return 0;return fac[n]*inv[n-m]%mod*inv[m]%mod;
}//组合数
signed main(){
// freopen("dba.in","r",stdin);
// freopen("dba.out","w",stdout);ios::sync_with_stdio(false);cin>>m>>l;for(int i=l;i>=1;i--) cin>>a[i],sum+=a[i];//数位DP常规倒序输入 fac[0]=inv[0]=1;for(int i=1;i<=m*l;i++){fac[i]=fac[i-1]*i%mod;inv[i]=qpow(fac[i],mod-2);}//组合数 for(int i=l;i>=1;i--){//同23 遍历每个位置 int css=0;for(int j=0;j<i;j++){op=(j&1)?(-1):1;//(-1)^j num=(C(i-1,j)*((C(sum-m*j+i-1,i-1)-C(sum-a[i]-m*j+i-1,i-1)+mod)%mod))%mod;//式子 css=(css+op*num+mod)%mod;//求和 }ans=(ans+css)%mod;//统计每一位的答案 sum-=a[i];//倒序遍历减掉后面的值 }cout<<ans;//输出答案 return 0;
}