CSP-S模拟测试 88 题解

T1 queue：

考场写出dp柿子后觉得很斜率优化，然后因为理解错了题觉得斜率优化完全不可做，只打了暴力。

实际上他是可以乱序的，所以直接sort，正确性比较显然，贪心可证，然后就是个sb斜率优化dp了

T2:

究极大模拟，懒得打，鸽了

T3:

蒟蒻博主用的是记忆化搜索的方法，其实和抵制克苏恩那题思路很像，因为他的小球个数很少，颜色种数也很少，所以这是可行的，记搜时我们只需记录还有多少个1个的，2个的，3个的，和上一个选取的是剩几个的，然后这一次可能选剩1个的，2个的，3个的，如果这次选的和上次选的有可能一样就减掉一种可能，然后直接记搜就好了，数据范围需要高精，然而我没脸用int128水过。

 #include<bits/stdc++.h>

 using namespace std;

 signed k[],cnt[];

 #define int __int128

 int f[][][][];

 int dfs(int i,int j,int k,int x){

     if(!i&&!j&&!k) return ;

     if(f[i][j][k][x]) return f[i][j][k][x];

     int res=;

     if(i) res+=(i-(x==))*dfs(i-,j,k,);

     if(j) res+=(j-(x==))*dfs(i+,j-,k,);

     if(k) res+=(k-(x==))*dfs(i,j+,k-,);

     return f[i][j][k][x]=res;

 }

 void print(int x){

     if(!x)return ;

     print(x/);

     putchar(x%+'');

 }

 signed main(){

     signed n,sum=;

     scanf("%d",&n);

     for(int i=;i<=n;++i) scanf("%d",&k[i]),cnt[k[i]]++,sum+=k[i];

     print(dfs(cnt[],cnt[],cnt[],));

 }

color

巴特西

CSP-S模拟测试 88 题解

最新文章

热门文章