-
暑期多校赛
牛客Day1
I-Chiitoitsu
题目描述
一副日本麻将，总共有34种花色，每种花色有4张牌。起初你有13张牌，之后每次你都从剩下的牌库中随机取出一张牌，然后判断当前手中的14张牌能否构成七个不同的对子。如果可以那么游戏结束，否则你从14张牌中选择一张牌把它放在一旁（注意这个牌并不放回牌库）。问：当你选取最优策略时期望需要多少回合可以结束游戏。
题目分析
首先先来分析一下如何是最优策略。考虑贪心。加入当前我有一对对子了，那么这两张牌我一定不会动，并且如果有多余的那我一定会踢出去。然后如果我当前手中有一张单牌，他还没有成对，那么我不会踢掉他，只会等下一张相同的牌。因为在随机的情况下，我等现有的一张牌成对一定比等两张相同的牌优。主要难点在于状态的定义。注意到对我有用的信息只有当前手中的单牌数量以及成对的数量以及牌库剩余的数量。先考虑概率dp。令f[i][j][k]表示当前手里有i个单牌，j对不同的对子，牌库剩余k张牌时的概率。转移很明显。需要注意的点：有可能最开始i很大，是大于7的。那当我们遇到一个成对时，应该再随机删掉一个。也有可能i很小，i+j小于7，这时候我们遇到一张单牌应该加入i里。但是还有一个问题是，概率dp复杂度是 m a x i ∗ m a x j ∗ m a x k maxi*maxj*maxk maxi∗maxj∗maxk，k最大是34*4，i最大是14，j最大是7。所以整体复杂度是 O ( 34 ∗ 4 ∗ 14 ∗ 7 ∗ t ) O(34*4*14*7*t) O(34∗4∗14∗7∗t)，t是1e5，显然会tle。那我们只好写个记忆化搜索，而为了记忆化搜索，就需要写期望dp。因为概率dp跟起点有关系，所以每一组数据都必须跑一遍才行。
代码
#includeusing namespace std; #define ll long long #define N 200010 inline ll read(){ ll Num=0,F=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')F=-1;ch=getchar();} while(isdigit(ch)){Num=(Num<<3)+(Num<<1)+(ch^48);ch=getchar();} return Num*F; } const int mod=1e9+7; int t,n; char s[N]; ll dp[35][35][34*4+10]; ll inv(ll x){ ll res=1; ll b=mod-2; for(;b;b>>=1){ if(b&1){ res=res*x%mod; } x=x*x%mod; } return res; } ll dfs(int i,int j,int k){ ll y=inv(k); if(i==0&&j==7){ return 0; } if(dp[i][j][k]!=-1){ return dp[i][j][k]; } if(i+j<=7){ dp[i][j][k]=1; //抽到一张单牌 ll tmp=(34-i-j)*4%mod*y%mod; if(i+j<7&&k>0){ dp[i][j][k]=(dp[i][j][k]+dfs(i+1,j,k-1)*tmp%mod)%mod; }else if(k>0) { dp[i][j][k]=(dp[i][j][k]+dfs(i,j,k-1)*tmp%mod)%mod; } tmp=3*i%mod*y%mod; if(i>1&&k>0){ dp[i][j][k]=(dp[i][j][k]+dfs(i-1,j+1,k-1)*tmp%mod)%mod; } tmp=(k-3*i-(34-i-j)*4)%mod*y%mod; if(k>0) dp[i][j][k]=(dp[i][j][k]+dfs(i,j,k-1)*tmp%mod)%mod; dp[i][j][k]=(dp[i][j][k]+mod)%mod; return dp[i][j][k]; }else{ dp[i][j][k]=1; ll tmp=3*i%mod*y%mod; if(i>=2&&k>0){ dp[i][j][k]=(dp[i][j][k]+dfs(i-2,j+1,k-1)*tmp%mod)%mod; } tmp=(34-i-j)*4%mod*y%mod; if(k>0) dp[i][j][k]=(dp[i][j][k]+dfs(i,j,k-1)*tmp%mod)%mod; tmp=(k-3*i-(34-i-j)*4)%mod*y%mod; if(k>0) dp[i][j][k]=(dp[i][j][k]+dfs(i,j,k-1)*tmp%mod)%mod; dp[i][j][k]=(dp[i][j][k]+mod)%mod; return dp[i][j][k]; } } int main(){ cin>>t; memset(dp,-1,sizeof(dp)); for(int p = 1;p<=t;++p){ scanf("%s",s+1); n=strlen(s+1); int f[101]={}; for(int i=1;i<=n;i+=2){ int num=s[i]-'0'; if(s[i+1]=='m') num+=10; else if(s[i+1]=='p') num+=20; else if(s[i+1]=='s') num+=30; else if(s[i+1]=='z') num+=40; f[num]++; } int g[5]={}; for(int i=10;i<50;i++) g[f[i]]++; g[0]-=6; if(dp[g[1]][g[2]+g[3]+g[4]][34*4-g[2]*2-g[1]-g[3]*3-g[4]*4]==-1){ dp[g[1]][g[2]+g[3]+g[4]][34*4-g[2]*2-g[1]-g[3]*3-g[4]*4]=dfs(g[1],g[2]+g[3]+g[4],34*4-g[2]*2-g[1]-g[3]*3-g[4]*4); } //memset(dp,0,sizeof(dp)); //dp[g[1]][g[2]+g[3]+g[4]][34 * 4 - g[2] * 2 - g[1] - g[3] * 3 - g[4] * 4] = 1; /*ll ans = 0; for(int k=34*4;k>=0;--k) { for(int i=14;i>=0;i--) { for(int j=7;j>=0;j--) { int y = inv(k); if (i == 1 && j == 6) { dp[i] }ans = (ans + dp[i][j][k] * (34*4 - 13 - k + 1) %mod * 3 * y%mod)%mod; if (dp[i][j][k] == 0) continue; if (!k) continue; if (i >= 1 && i + j*2 < 13) { (dp[i-1][j+1][k-1]+=(dp[i][j][k]*i*3%mod*y)%mod)%=mod; } if (i >= 2) { (dp[i-2][j+1][k-1]+=(dp[i][j][k]*i*3%mod*y)%mod)%=mod; } dp[i][j][k-1]=(dp[i][j][k-1]+dp[i][j][k]*(k-i*3)%mod*y)%mod; } }*/ //} cout<<"Case #"<< p <<": "<<dp[g[1]][g[2]+g[3]+g[4]][34*4-g[2]*2-g[1]-g[3]*3-g[4]*4]<<endl; } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
杭电Day1
1012
题目描述
Alice和Bob玩游戏，起初有m个整数，数的范围是[0,n]。每回合Alice将数分为两个集合，Bob任选一个集合将这个集合全部删除。若删完以后没有数字了，那么Bob赢。否则剩下的那个集合全部减1。若集合中出现0，Alice获胜。
题目分析
假如集合中有0，Alice直接获胜。假如有1的话，那么Alice将1分散开，Bob删除任意一个集合后，另一个集合全部减1后一定会出现0。简单分析以后，发现最优策略下，Alice一定是想让游戏尽可能多进行几个回合，并且尽可能让小的数被减。而Bob一定是先尽可能让游戏早一点结束。因此最优策略一定是Alice每次都将相同数值的数字平分到两个集合中。Bob一定是把当前最小的数个数多的那个集合删掉。那么Alice想要获胜，就需要至少1个0，或者至少2个1，或者至少4个2。。。也就是说0的贡献是1,1的贡献是2,2的贡献是4。我们对所有数值求一下贡献并相加，如果小于1，那么Bob胜，否则Alice。
代码
#include#define MAXN 1000010 using namespace std; int T; int n,a[MAXN]; int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0;i<=n;i++) { scanf("%d",&a[i]); } for(int i=n;i>=1;i--) { if(a[i]>=2) { a[i-1]+=(a[i]/2); a[i]=0; } } if(a[0]!=0) { printf("Alice\n"); } else { printf("Alice\n"); } } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
1002
题目描述
一个方格，坐标从(0,0)到(n,m)，有k堵墙。起点是(xs+0.5,ys+0,5)，终点是(xt+0.5,yt+0.5)。问你最少需要翻过几堵墙才可以到达终点。注意，如果把墙当做线段，那么端点也是不可以到达的。
题目分析
样例2说明人是可以不在直线上走的。比如可以从(xs+0.5,ys+0.5)走到(xs+1.5,ys+0.5)。这样的话直接写dfs不是很好写。可以将所有的坐标全部放大一倍，这样的话不会存在小数值坐标。k很小，直接爆搜所有的情况，然后dfs判断是否可以到达就行。
代码
#include#define ll long long using namespace std; const int N=1025; int t,n,m,k,x[2][16],y[2][16],xs,ys,xt,yt,a[32][32],f[16],vis[32][32]; int ans; int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; void Dfs(int tx,int ty){ if(a[tx][ty]==-1) return; for(int i=0;i<4;i++){ int nx=tx+dx[i]; int ny=ty+dy[i]; if(nx<0||nx>n*2||ny<0||ny>m*2) continue; if(!vis[nx][ny]&&a[nx][ny]!=-1){ vis[nx][ny]=1; Dfs(nx,ny); } } } void dfs(int I,int num){ if(I==k+1){ memset(vis,0,sizeof(vis)); memset(a,0,sizeof(a)); //if(num==0){ // for(int i=1;i<=2;i++) cout< - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
1003
题目描述
背包问题，容量为m，有n件物品，每个物品有一个体积vi和价值wi。问恰好把背包装满的情况下，所有物品价值的xor值最大是多少。
题目分析
对于最简单的背包问题，可以直接令f[i]表示容量为i时的最大价值，然后先枚举物品从1到n，再依次更新f[i]从m到0。复杂度是O(n*m)。
但是本题要求的是xor的最大值。因为xor具有后效性，所以我们需要把状态都保存下来。令f[i][k]表示当前容量为i时xor值为k是否存在。那么递推复杂度应该是 n ∗ m ∗ m a x x o r n*m*maxxor n∗m∗maxxor。之前对于这种存储状态的问题，一般用bitset来优化。复杂度会降到 n ∗ m ∗ m a x x o r / 32 n*m*maxxor/32 n∗m∗maxxor/32。但是对于当前这个状态定义，因为从f[i]到f[i-v[i]]，需要做出的是把xor的值先与wi进行xor，再把状态变成0/1串。如果这样写bitset是无法实现的。
考虑bitset的方便之处：比如一个0/1串：00110，它代表0，3，4不存在，1和2存在。然后如果我们状态的更迭是平移的话，也就是整体做加法，那么bitset就很方便，只需要将二进制串整体左移就可以。因此将状态定义换一下，f[i][j]表示当前xor值为i，容量为j是否存在。这样我们用当前物品更新状态时，就很方便。
f [ i ] ∣ = f [ i x o r w ] < < v f[i]|=f[i\ xor\ w]<f[i]∣=f[i xor w]<<v 代码
#includeusing namespace std; #define ll long long bitset<1025>f[1025]; int t,n,m,w[1025],v[1025]; int main(){ scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=0;i<=1024;i++) f[i].reset(); f[0][0]=1; for(int i=1;i<=n;i++){ scanf("%d%d",&v[i],&w[i]); } for(int i=1;i<=n;i++){ for(int j=0;j<=1024;j++){ if((j^w[i])<=1024) f[j]|=f[j^w[i]]<<v[i]; } } bool flag=0; for(int i=1024;i>=1;i--){ if(f[i][m]){ printf("%d\n",i); flag=1; break; } } if(!flag) printf("-1\n"); } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
-
相关阅读:
注册的业务、登录业务、个人中心、nginx配置【VUE项目】
字节面试题——数据库， linux
[Power Query] 日期和时间处理
【halcon知识】重要的9个元组操作
FME&ArcGIS版本兼容性
git 给分支添加描述
FlexRay通信协议概述
社交网络用户行为分析,各类社交软件用户分析
ubuntu_24.04 Noble LTS安装docker desktop启动无窗口及引擎启动失败的解决方法
Leetcode-1408 数组中的字符串匹配
- 原文地址：https://blog.csdn.net/qq_39759315/article/details/125889970
