题意：有r轮游戏，每轮每张卡p[i]概率发动技能造成d[i]伤害，发动技能后该卡片作废且进行下一轮游戏，求期望伤害。
f[i][j]表示游戏还剩j轮时，前i张卡还未被打出的概率。
那么对于第i+1张牌，若成功打出，则有f[i+1][j]=f[i][j]*(1-p[i+1])j；若未成功打出，则有f[i+1][j-1]=f[i][j]*(1-(1-p[i+1])j)。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define maxn 225 #define maxm 135 using namespace std; double pw[maxn][maxm],f[maxn][maxm],p[maxn],d[maxn]; int main() { int T,i,j,n,m; double ans; scanf("%d",&T); while (T--) { memset(f,0,sizeof(f)); scanf("%d%d",&n,&m); for (i=1;i<=n;i++) scanf("%lf%lf",&p[i],&d[i]); for (i=1;i<=n;i++) { pw[i][0]=1; for (j=1;j<=m;j++) pw[i][j]=(1-p[i])*pw[i][j-1]; } f[0][m]=1;ans=0; for (i=0;i<n;i++) for (j=0;j<=m;j++) { f[i+1][j]+=f[i][j]*pw[i+1][j]; if (j>=1) { f[i+1][j-1]+=f[i][j]*(1-pw[i+1][j]); ans+=f[i][j]*(1-pw[i+1][j])*d[i+1]; } } printf("%.10lf ",ans); } return 0; }
题意：多次询问一棵树上一段路径（x->y）上所有节点深度的k次方和。
树上前缀和+lca。维护一个树上前缀和数组dis[i][k]，表示从根节点1至节点i所有节点深度的k次方和。
易知，ans=dis[x][k]+dis[y][k]-dis[lca(x,y)][k]-dis[fa[lca(x,y)]][k]。
取模时注意考虑负数的情况。
（为啥这种题我会写不出来呢。。）
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define maxn 300002 #define mod 998244353 using namespace std; typedef long long ll; int fa[maxn][20],dep[maxn],vis[maxn]; ll dis[maxn][51]; int num,last[maxn],n; struct edge { int to,nxt; }e[maxn<<1]; void add(int x,int y) { e[++num].to=y; e[num].nxt=last[x]; last[x]=num; } void dfs(int u,int pre) { int i,v; ll tmp=1; dep[u]=dep[pre]+1; fa[u][0]=pre; for (i=1;i<=50;i++) { tmp=tmp*dep[u]%mod; dis[u][i]=(dis[pre][i]+tmp+mod)%mod; } for (i=1;i<=19;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for (i=last[u];i;i=e[i].nxt) { v=e[i].to; if (v!=pre) dfs(v,u); } } int lca(int x,int y) { int i,ans=0; if (dep[x]>dep[y]) { i=x;x=y;y=i; } for (i=19;i>=0;i--) { if (dep[fa[y][i]]>=dep[x]) y=fa[y][i]; } if (x==y) return x; for (i=19;i>=0;i--) { if (fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } } return fa[x][0]; } int main() { int i,j,k,x,y,z,q; ll ans; scanf("%d",&n); for (i=1;i<n;i++) { scanf("%d%d",&x,&y); add(x,y);add(y,x); } dep[1]=-1; dfs(1,1); scanf("%d",&q); while (q--) { scanf("%d%d%d",&x,&y,&k); z=lca(x,y); ans=(dis[x][k]+dis[y][k])%mod; ans=(ans+2*mod-dis[z][k]-dis[fa[z][0]][k])%mod; printf("%lld ",ans); } return 0; }
题意：一棵树，每个节点存在c[i]权值和son[i]个儿子，要求满足c[i]+son[i]<=m的条件下删掉尽量多的节点。
贪心。从叶子节点开始向上合并，从c值最小的点开始，能合并的就合并。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define maxn 2000005 using namespace std; int num,to[maxn],nxt[maxn],last[maxn]; int n,m,c[maxn],b[maxn],ans; void add(int x,int y) { to[++num]=y; nxt[num]=last[x]; last[x]=num; } void dfs(int u) { int i,cnt=0; for (i=last[u];i;i=nxt[i]) dfs(to[i]); for (i=last[u];i;i=nxt[i]) b[++cnt]=c[to[i]]; sort(b+1,b+cnt+1); for (i=1;i<=cnt;i++) { if (c[u]+b[i]-1>m) break; ans++; c[u]+=b[i]-1; } } int main() { int i,x,k; scanf("%d%d",&n,&m); for (i=0;i<n;i++) scanf("%d",&c[i]); for (i=0;i<n;i++) { scanf("%d",&k); c[i]+=k; while (k--) { scanf("%d",&x); add(i,x); } } dfs(0); printf("%d ",ans); return 0; }
哈希+DP。题解见洛谷
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define base 131 #define maxn 100005 #define mod 1000000007 using namespace std; typedef long long ll; ll pos[maxn],hastr[maxn],has[maxn]; int dp[12][maxn],q[maxn],l; char str[maxn],s[maxn]; int main() { int i,j,k,len,lens,n; pos[0]=1; for (i=1;i<=100000;i++) pos[i]=pos[i-1]*base%mod; scanf("%s%d",str+1,&n); len=strlen(str+1); str[++len]='?'; for (i=1;i<=len;i++) { if (str[i]=='?' || str[i]=='*') q[++l]=i; hastr[i]=(hastr[i-1]*base+str[i])%mod; } while (n--) { scanf("%s",s+1); lens=strlen(s+1); s[++lens]='&'; for (i=1;i<=lens;i++) has[i]=(has[i-1]*base+s[i])%mod; memset(dp,0,sizeof(dp)); dp[0][0]=1; for (i=0;i<=l;i++) { if (str[q[i]]=='*') { for (j=1;j<=lens;j++) if (dp[i][j-1]) dp[i][j]=1; } for (j=0;j<=lens;j++) { k=q[i+1]-q[i]-1; if (k<0 || i+k>lens) continue; if (dp[i][j] && (hastr[q[i]+k]-hastr[q[i]]*pos[k]%mod+mod)%mod==(has[j+k]-has[j]*pos[k]%mod+mod)%mod) { if (str[q[i+1]]=='?') dp[i+1][j+k+1]=1; else dp[i+1][j+k]=1; } } } if (dp[l][lens]) printf("YES "); else printf("NO "); } return 0; }