2019-5-23 杂题选讲

T1 [PKUSC2018]最大前缀和

给定一个长为$n$的整数序列，求全排列的最大前缀和（必须包含第一个数）之和。 $1\le n\le 20,1\le {\sum }_{i=1}^n|a[i]|\le 10^9$

正解

考虑序列的一个子集$S$对答案的贡献，也就是考虑一个子集$S$的所有元素之和能成为多少个排列的最大前缀和。

一个子集的排列$T$能成为最大和前缀的充要条件是：1，它的最大前缀和是自己；2，除 $T$外后面那段的最大前缀和小于等于零

于是定义$f[S]$表示子集$S$能组成最大前缀和是自己的排列数，定义$g[S]$表示子集$S$能组成的最大前缀和小于等于零的排列数

至于$f$和$g$的更新方式是由它们的性质决定，$f$的性质在于“除本身外的每个后缀和都大于零”，$g$的性质在于“每个前缀和都小于等于零”,于是就可以考虑$g$的状态由$sum[S]<=0$的转移而来（并且加入一个元素后和任然非正），而$f$的状态则可以由$sum[S]>0$的状态加入一个元素来转移（加入后的和的正负不关心）。

答案 ${\sum }_{S}sum[S]\ast f[S]\ast f[全集-S]$

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=50; const int M=5e6+5; const int MOD=998244353; int n,tot; ll a[N],sum[M],f[M],g[M],Ans=0; int lowbit(int x) { return x&-x; } int main() { scanf("%d",&n); tot=1<<n; for (int i=1;i<=n;i++) scanf("%lld",&a[i]),sum[1<<(i-1)]=a[i]; for (int i=1;i<tot;i++) sum[i]=sum[i^(lowbit(i))]+sum[lowbit(i)]; g[0]=1; for (int i=1;i<=n;i++) f[1<<(i-1)]=1; for (int i=1;i<tot;i++) { if (sum[i]>=0) { for (int j=1;j<=n;j++) if (!((i>>(j-1))&1)) f[i|(1<<(j-1))]=(f[i|(1<<(j-1))]+f[i])%MOD; } else { for (int j=1;j<=n;j++) if ((i>>(j-1))&1) g[i]=(g[i]+g[i^(1<<(j-1))])%MOD; } } for (int i=0;i<tot;i++) Ans=(Ans+(sum[i]+MOD)%MOD*f[i]%MOD*g[(tot-1)^i]%MOD)%MOD; printf("%lld\n",Ans); return 0; }

T2 CF1163D Mysterious Code

有三个字符串 $c,s,t$，其中$c$只包含小写字母和星号，$s,t$只包含小写字母。 现在你可以把$c$中每一个星号替换成一个小写 字母（不同的星号可以替换成不同的字母），使得$s$在$c$中出现次数减去$t$在$c$中出现次数最大。求出这个最大值。 $1\le |c|\le 1000,1\le |s|,|t|\le 50$。

正解

定义$dp[i][j][k]$为$c$串匹配到第$i$位时$s$和$t$分别已经匹配了$j$和$k$位时的最大答案。 如果$c[i]$为$\ast$就枚举字符全集取最大的一个做答案转移，否则直接转移，其中并不是所有状态都能转移到，用$vis$记录，并且第一次拓展到某个状态时不能直接取$max$，因为答案可以小于零。

#include<bits/stdc++.h> using namespace std; const int N=1e3+5; char c[N],s[N],t[N]; int l1,l2,l3,nxt1[N],nxt2[N],p,dp[N][60][60],vis[N][60][60]; int Ans=-1e9; int main() { // freopen("testdata.in","r",stdin); scanf("%s",c+1),l1=strlen(c+1); scanf("%s",s+1),l2=strlen(s+1); scanf("%s",t+1),l3=strlen(t+1); p=0; for (int i=2;i<=l2;i++) { while (p&&s[p+1]!=s[i]) p=nxt1[p]; if (s[p+1]==s[i]) p++; nxt1[i]=p; } p=0; for (int i=2;i<=l3;i++) { while (p&&t[p+1]!=t[i]) p=nxt2[p]; if (t[p+1]==t[i]) p++; nxt2[i]=p; } dp[0][0][0]=0; vis[0][0][0]=1; for (int i=1;i<=l1;i++) for (int j=0;j<l2;j++) for (int k=0;k<l3;k++) { int L='a',R='z'; if (c[i]!='*') L=R=c[i]; for (int cc=L;cc<=R;cc++) { int tmp=0; char ch=cc; if (!vis[i-1][j][k]) continue; int p1=j,p2=k; while (p1&&s[p1+1]!=ch) p1=nxt1[p1]; if (s[p1+1]==ch) p1++; while (p2&&t[p2+1]!=ch) p2=nxt2[p2]; if (t[p2+1]==ch) p2++; if (p1==l2) p1=nxt1[p1],tmp++; if (p2==l3) p2=nxt2[p2],tmp--; if (!vis[i][p1][p2]) dp[i][p1][p2]=dp[i-1][j][k]+tmp; else dp[i][p1][p2]=max(dp[i][p1][p2],dp[i-1][j][k]+tmp); vis[i][p1][p2]=1; if (i==l1) Ans=max(Ans,dp[i][p1][p2]); } } printf("%d\n",Ans); return 0; }

T3 CF1139E Maximize Mex

一个学校有$n$个人$m$个社团。一开始每人都恰好在一个社团里。第$i$人有能力值$p[i]$。接下来有$d$天，在第$i$天，第$k[i]$个人离开他所在的社团。 每天人离开之后，就会从每个社团中选出一个人（已经没人的社团不管）。对于每一天，求出这些人的能力值$mex$的最大值。($mex$是没出现过的最小非负整数） 输入的所有数是非负整数且$\le 5000$ 。

正解

匈牙利求二分图最大匹配，左部点是能力值，右部点是社团，由于能力值要求总零开始连续，符合匈牙利的思想，删边按套路倒过来加边。

#include<bits/stdc++.h> using namespace std; const int N=1e6+5; int n,m,p[N],c[N],d,k[N]; int tag[N]; int tot=0,f[N],nxt[N<<1]; int Ans[N],dxx=0,dfn[N],match[N]; struct Edge { int u,v; }e[N<<1]; int read() { int x=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();} return f*x; } void Add(int u,int v) { tot++; nxt[tot]=f[u]; f[u]=tot; e[tot]=(Edge){u,v}; return; } int DFS(int x) { for (int j=f[x];j!=-1;j=nxt[j]) { int v=e[j].v; if (dfn[v]==dxx) continue; dfn[v]=dxx; if ((!match[v])||DFS(match[v])) { match[v]=x; return 1; } } return 0; } int main() { memset(f,-1,sizeof(f)); n=read(),m=read(); for (int i=1;i<=n;i++) p[i]=read(),p[i]++; for (int i=1;i<=n;i++) c[i]=read(); d=read(); for (int i=1;i<=d;i++) k[i]=read(),tag[k[i]]=-1; for (int i=1;i<=n;i++) if (tag[i]!=-1) Add(p[i],10000+c[i]); for (int i=d;i>=1;i--) { dxx++; Ans[i]=Ans[i+1]; for (int j=Ans[i]+1;j<=m;j++) { dxx++; if (DFS(j)) Ans[i]++; else break; } Add(p[k[i]],10000+c[k[i]]); } for (int i=1;i<=d;i++) printf("%d\n",Ans[i]); return 0; }

T4[HNOI2015]亚瑟王

你有$n$张牌，有$r$个回合。每张牌有$p[i]$和$d[i]$ 对于每个回合，从编号为$1$到编号为$n$的牌轮流考虑 对于每张牌：

若此牌已发动过，跳过；（如果本牌是最后一张牌，结束本回合）若此牌没发动，将有$p[i]$的概率发动它，并造成$d[i]$的伤害。（如果发动，本回合结束） 求造成伤害的期望。（有T组数据） $1\le T\le 144,1\le n\le 220,0\le r\le 132,0<p[i]<1,0\le d[i]\le 1000$

正解

由题面可知，每张卡片在整个$r$轮游戏中要么发动一次要么不发动。 假设第$i$张牌被发动的概率为$f[i]$那么答案就是${\sum }_{i=1}^{n}f[i]\ast d[i]$

明显地，这个$f[i]$不等于$p[i]$，因为每回合如果发动一张牌成功就会立马结束该回合，这导致了决定$f[i]$的因素不仅有$p[i]$，还有$r$的大小以及卡牌的顺序（越在后面发动概率消减越多）。

定义$dp[i][j]$表示，在$r$轮游戏中，前i张卡牌当中有$j$张被发动的概率，定义有些奇怪但是能把决定$f[i]$的因素都囊括。 于是就有$f[i]={\sum }_{j=0}^{r}dp[i-1][j]\ast (1-(1-p[i]{)}^{r-j})$ 对于每次循环，由于我们知道了$i$前面有$j$张卡牌已发动，所以有$r-j$轮第i张卡牌是否发动与前$i-1$张无关，只要别每次都发动不了就行了

$dp$数组的求法： $dp[i][j]$从$dp[i][j-1]$和$dp[i-1][j-1]$转移而来，思想类似 $dp[i][j]=dp[i-1][j-1]\ast (1-(1-p[i]{)}^{r-j+1})+dp[i-1][j]\ast (1-p[i]{)}^{r-j}$

#include<bits/stdc++.h> using namespace std; const int N=300; int T,n,r; double p[N],d[N],qpow[N][N],f[N],dp[N][N],Ans; int main() { scanf("%d",&T); while (T--) { Ans=0; memset(f,0,sizeof(f)); memset(dp,0,sizeof(dp)); scanf("%d%d",&n,&r); for (int i=1;i<=n;i++) scanf("%lf%lf",&p[i],&d[i]),qpow[i][0]=1; for (int i=1;i<=n;i++) for (int j=1;j<=r;j++) qpow[i][j]=qpow[i][j-1]*(1-p[i]); f[1]=1-qpow[1][r]; dp[1][0]=qpow[1][r]; dp[1][1]=1-qpow[1][r]; for (int i=2;i<=n;i++) for (int j=0;j<=min(i,r);j++) { dp[i][j]+=dp[i-1][j]*qpow[i][r-j]; if (j>0) dp[i][j]+=dp[i-1][j-1]*(1-qpow[i][r-j+1]); } for (int i=1;i<=n;i++) for (int j=0;j<=r;j++) f[i]+=dp[i-1][j]*(1-qpow[i][r-j]); for (int i=1;i<=n;i++) Ans+=f[i]*d[i]; printf("%.9lf\n",Ans); } return 0; }

T5 [THUPC2019]过河卒二

题意见链接

正解

1，当没有障碍时，$(1,1)->(n,m)$出界的答案等于$(1,1)->(n+1,m+1)$右上角的答案，是这题的关键。因为当出界后想走到$(n+1,m+1)$只有一种走法，一一对应。该方案数的求法，则是枚举斜着走有多少步，再乘上剩下正常走的方案数。

2，当有障碍时，容斥定理即可。设状态压缩后障碍物的状态为$state$的方案数为$sum[state]$,那么它的求法就是，把这些障碍物（加上起点和终点）从左下到右上排序，每个阶段的方案数累乘起来。设$cnt$为$state$中的障碍数，若$cnt$偶数则加上，否则减去。

3，预处理两两障碍物之间（包括起点和终点）的方案数，$O(k^{2}M)$,求解复杂度$O(2^{k}k)$。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int K=30; const int MOD=59393; int n,m,k,tpp,point[K]; ll dis[K][K]; ll pre[MOD],inv[MOD]; ll Ans=0; struct data { int x,y; }p[K]; bool cmp(const data a,const data b) { if (a.x==b.x) return a.y<b.y; return a.x<b.x; } ll qpow(ll x,ll y) { ll ret=1; while (y) { if (y&1) ret=ret*x%MOD; y>>=1; x=x*x%MOD; } return ret; } void Init() { pre[0]=1; for (int i=1;i<MOD;i++) pre[i]=pre[i-1]*i%MOD; inv[MOD-1]=qpow(pre[MOD-1],MOD-2); for (int i=MOD-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%MOD; return; } ll C(ll nn,ll mm) { if (nn<0||mm<0||nn<mm) return 0; ll ret; ret=pre[nn]*inv[mm]%MOD*inv[nn-mm]%MOD; return ret; } ll Lucas(ll nn,ll mm) { if (nn<MOD) return C(nn,mm); ll ret=Lucas(nn/MOD,mm/MOD)*Lucas(nn%MOD,mm%MOD)%MOD; return ret; } ll Caldis(int st,int end) { int a1=p[st].x,a2=p[end].x,b1=p[st].y,b2=p[end].y; if (b1>b2) return -1; ll nn=a2-a1,mm=b2-b1; ll ret=0; for (int i=0;i<=min(nn,mm);i++) ret=(ret+Lucas(nn+mm-i,i)*Lucas(nn+mm-2*i,nn-i)%MOD)%MOD; return ret; } int Cnt(int state) { int ret=0; tpp=0; point[++tpp]=1; for (int i=1;i<=k;i++) point[i]=1; for (int i=0;i<k;i++) if ((1<<i)&state) ret++,point[++tpp]=i+2; point[++tpp]=k+2; return ret; } int main() { // freopen("1.in","r",stdin); Init(); scanf("%d%d%d",&n,&m,&k); for (int i=1;i<=k;i++) scanf("%d%d",&p[i].x,&p[i].y); p[k+1]=(data){1,1}; p[k+2]=(data){n+1,m+1}; sort(p+1,p+k+3,cmp); for (int i=1;i<=k+1;i++) for (int j=i+1;j<=k+2;j++) dis[i][j]=Caldis(i,j); for (int i=0;i<(1<<k);i++) { int cnt=Cnt(i); ll tmp=1; for (int j=1;j<tpp;j++) { ll tmp2=dis[point[j]][point[j+1]]; if (tmp2==-1) { tmp=0; break; } else tmp=tmp*tmp2%MOD; } if (cnt&1) Ans=(Ans-tmp+MOD)%MOD; else Ans=(Ans+tmp)%MOD; } printf("%lld\n",Ans); return 0; }