2018.10.24 正睿停课训练 Day8 AM
期望得分：70+21+xjbDP(好像昨天我也写了一个?->people in despair什么都能写...)
实际得分：75+10+0
A 棒棒糖(组合)
倍增LCA的第二部分是没有问题的。第一部分的目的是利用深度差让\(u,v\)跳到同一深度上，但是\(dep[u]\)与\(dep[v]\)可能会改变。但只要让深度差在变化前后不变就能保证正确。
\(w=LCA(u,v)\)以上的部分是公共的，不需要考虑。记\(d_u=dep[u]-dep[w],d_v=de[v]-dep[w]\)，且设\(d_u\leq d_v,\ \Delta d=d_v-d_u\)。我们枚举\(d_u\)变成了多少，则\(d_v\)也应该变成\(d_u+\Delta d\)。
\(d_u\)变成\(x\)的概率是\(\frac{C_{d_u}^{x}}{2^{d_u}}\)。所以\(Ans=\frac{1}{2^{d_u+d_v}}\sum_{i=0}^{\min(d_u,d_v-\Delta d)}C_{du}^iC_{dv}^{i+\Delta d}\)。
直接这样是\(O(nq)\)的。考虑怎么化简。
把\(\Delta d\)拆开，\(Ans=\frac{1}{2^{d_u+d_v}}\sum_{i=0}^{d_u}C_{du}^iC_{dv}^{d_u-i}\)（或者，直接枚举\(u,v\)上面有多少条边消失了也可以得到这个式子）。
\[\sum_{i=0}^{d_u}C_{du}^iC_{dv}^{d_u-i}
\]
\]
考虑这个东西的意义，就是枚举从\(d_u\)中选多少个，然后再从\(d_v\)中补若干个，使得选出的数总共有\(d_u\)个的所有方案。也就是\(C_{d_u+d_v}^{d_u}\)。
然后就可以\(O(1)\)计算了。复杂度\(O(q)\)。
上面的式子可以扩展到任意多个的情况，即：范德蒙德卷积。
我就记得有这样的式子。。但是看到T2T3直接弃疗了，还有具体数学不在手上。
//621ms 18032kb
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 200000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define mod 998244353
#define Mod(x) x>=mod&&(x-=mod)
#define C(n,m) (1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod)
typedef long long LL;
const int N=2e5+5;
int n,Enum,H[N],nxt[N<<1],to[N<<1],fa[N],dep[N],sz[N],son[N],top[N];
int fac[N<<1],ifac[N<<1],pw[N<<1],ipw[N<<1];
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline int FP(int x,int k)
{
int t=1;
for(; k; k>>=1,x=1ll*x*x%mod)
if(k&1) t=1ll*t*x%mod;
return t;
}
inline void AE(int u,int v)
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
}
inline int LCA(int u,int v)
{
while(top[u]!=top[v]) dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];
return dep[u]<dep[v]?u:v;
}
void DFS1(int x)
{
int mx=0; sz[x]=1;
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa[x])
{
fa[v]=x, dep[v]=dep[x]+1, DFS1(v), sz[x]+=sz[v];
if(sz[v]>mx) mx=sz[v], son[x]=v;
}
}
void DFS2(int x,int tp)
{
top[x]=tp;
if(son[x])
{
DFS2(son[x],tp);
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa[x]&&v!=son[x]) DFS2(v,v);
}
}
int main()
{
n=read();
for(int i=1; i<n; ++i) AE(read(),read());
fac[0]=fac[1]=1, pw[0]=1, pw[1]=2;
for(int i=2; i<=n; ++i) fac[i]=1ll*fac[i-1]*i%mod;
for(int i=2; i<=n<<1; ++i) pw[i]=pw[i-1]<<1, Mod(pw[i]);
ifac[n]=FP(fac[n],mod-2);
for(int i=n; i; --i) ifac[i-1]=1ll*ifac[i]*i%mod;
ipw[n<<1]=FP(pw[n<<1],mod-2);
for(int i=n<<1; i; --i) ipw[i-1]=ipw[i]<<1, Mod(ipw[i-1]);
DFS1(1), DFS2(1,1);
for(int Q=read(),u,v,w; Q--; )
{
w=LCA(u=read(),v=read());
int du=dep[u]-dep[w],dv=dep[v]-dep[w];
printf("%d\n",(int)(1ll*C(du+dv,du)*ipw[du+dv]%mod));
}
return 0;
}
B 彩虹糖(思路 博弈)
因为集合\(A,B\)不相交，所以每个人的操作顺序可以是任意的（能由他操作的堆不会由另一个人去操作）。所以我们只需要计算每一堆的贡献（或者说一堆中有\(x\)个时的贡献）。
对于先手能操作的一堆糖果，设有\(x\)个，把它分成两堆可能会给先手增加操作次数，也可能会给后手更多操作机会。而先手要最大化 \(它能操作的次数-后手能操作的次数\)。
记\(f(x)\)表示一堆中有\(x\)个糖果时（对应情况的）\(先手可操作次数-后手可操作次数\)。直接\(O(m)\)枚举把\(x\)分成\(i\)和\(x-i\)，对于先手，求\(\max_{i=1}^{x-1}\{f(i)+f(i-x)\}\)就可以了。先手也可以不选，所以要对\(0\)取\(\max\)。
后手同理，不过是对于它能选的\(x\)，要最小化\(f(x)\)的值（同样要与\(0\)取\(\min\)）。
\(O(m^2)\)求出所有\(f(i)\)，然后判一下\(\sum_{x=1}^nf(P[x])\)是否\(>0\)就行了。
ps：因为\(A,B\)集合不相交，所以这是平等博弈，大多可以用SG函数解决；
如果\(A,B\)集合可以相交，则是不平等博弈问题，要用超现实数解决。（见dls课件？反正我见了也没什么用）
其实也不难啊，怎么就是想不到啊。
//649ms 804kb
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1e6+5,M=1e4+5;
int f[M];
bool okA[M],okB[M];
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
int n=read(),m=read();
for(int totA=read(); totA--; okA[read()]=1);
for(int totB=read(); totB--; okB[read()]=1);
for(int i=2; i<=m; ++i)
if(okA[i])
for(int j=1; j<=i>>1; ++j)
f[i]=std::max(f[i],f[j]+f[i-j]+1);//0
else if(okB[i])
for(int j=1; j<=i>>1; ++j)
f[i]=std::min(f[i],f[j]+f[i-j]-1);//0
int ans=0;
for(int i=1,p; i<=n; ++i)
if((p=read())<=m) ans+=f[p];
puts(ans>0?"Pomegranate":"Orange");
return 0;
}
C 泡泡糖(DP)
神仙dp优化？
dls：这题太难了我们咕了吧。
咕了
考试代码
A
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 200000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define mod 998244353
#define Mod(x) x>=mod&&(x-=mod)
typedef long long LL;
const int N=2e5+5;
int n,Enum,H[N],nxt[N<<1],to[N<<1],fa[N],dep[N],sz[N],son[N],top[N],dfn[N],Index,out[N];
int fac[N<<1],ifac[N<<1],pw[N<<1],ipw[N<<1];
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline int FP(int x,int k)
{
int t=1;
for(; k; k>>=1,x=1ll*x*x%mod)
if(k&1) t=1ll*t*x%mod;
return t;
}
inline void AE(int u,int v)
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
}
inline int LCA(int u,int v)
{
while(top[u]!=top[v]) dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];
return dep[u]<dep[v]?u:v;
}
void DFS1(int x)
{
int mx=0; sz[x]=1;
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa[x])
{
fa[v]=x, dep[v]=dep[x]+1, DFS1(v), sz[x]+=sz[v];
if(sz[v]>mx) mx=sz[v], son[x]=v;
}
}
void DFS2(int x,int tp)
{
dfn[x]=++Index, top[x]=tp;
if(son[x])
{
DFS2(son[x],tp);
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa[x]&&v!=son[x]) DFS2(v,v);
}
out[x]=Index;
}
int main()
{
// freopen("ex_BBT2.in","r",stdin);
// freopen(".out","w",stdout);
n=read();
for(int i=1; i<n; ++i) AE(read(),read());
fac[0]=fac[1]=1, pw[0]=1, pw[1]=2;
for(int i=2; i<=n; ++i) fac[i]=1ll*fac[i-1]*i%mod;
for(int i=2; i<=n<<1; ++i) pw[i]=pw[i-1]<<1, Mod(pw[i]);
ifac[n]=FP(fac[n],mod-2);
for(int i=n; i; --i) ifac[i-1]=1ll*ifac[i]*i%mod;
ipw[n<<1]=FP(pw[n<<1],mod-2);
for(int i=n<<1; i; --i) ipw[i-1]=ipw[i]<<1, Mod(ipw[i-1]);
// for(int i=1; i<=n; ++i) printf("Inv(%d)=%d\n",i,ipw[i]);
DFS1(1), DFS2(1,1);
for(int Q=read(),u,v,w; Q--; )
{
u=read(), v=read(), w=LCA(u,v); if(dep[u]>dep[v]) std::swap(u,v);
LL ans=0;
int du=dep[u]-dep[w],dv=dep[v]-dep[w],delta=dv-du,lim=std::min(du,dv-delta);
for(int i=0; i<=lim; ++i) ans+=1ll*ifac[i]*ifac[du-i]%mod*ifac[i+delta]%mod*ifac[dv-i-delta]%mod;
ans=ans%mod*fac[du]%mod*fac[dv]%mod*ipw[du+dv]%mod;
printf("%d\n",(int)ans);
}
return 0;
}
B
没有暴力分的原因：把飞飞侠想傻了。。
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <algorithm>
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1e6+5;
int n,m,P[N],totA,A[N],totB,B[N],sg[2][N];
bool okA[N],okB[N];
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
namespace Subtask1
{
void DFS(int now)
{
bool f=0;
for(int i=1; i<=n; ++i)
if(!now)
{
if(!okA[P[i]]||P[i]<=1) continue;
f=1;
for(int x=1; x<P[i]; ++x)
P[i]-=x, P[++n]=x, DFS(now^1), P[i]+=x, --n;
}
else
{
if(!okB[P[i]]||P[i]<=1) continue;
f=1;
for(int x=1; x<P[i]; ++x)
P[i]-=x, P[++n]=x, DFS(now^1), P[i]+=x, --n;
}
if(!f)
{
if(!now) return;
else {puts("Pomegranate"); exit(0);}
}
}
void Main()
{
DFS(0), puts("Orange");
}
}
void Init()
{
static int vis[10005],A[2][N];
int Time=0,mx=0,tot[2]={totA,totB};
for(int i=1; i<=n; ++i) mx=std::max(mx,P[i]);
for(int i=1; i<=totA; ++i) A[0][i]=::A[i];
for(int i=1; i<=totB; ++i) A[1][i]=::B[i];
A[0][totA+1]=A[1][totB+1]=1e9;
for(int i=1; i<=mx; ++i)
for(int now=0; now<2; ++now)
{
++Time;
for(int j=1; A[now][j]<=i; ++j)
vis[sg[now^1][i-A[now][j]]]=Time;
for(int j=0; ; ++j)
if(vis[j]!=Time) {sg[now][i]=j; break;}
}
}
int main()
{
// freopen("B3.in","r",stdin);
// freopen(".out","w",stdout);
n=read(),m=read(),totA=read();
for(int i=1; i<=totA; ++i) okA[A[i]=read()]=1;
totB=read();
for(int i=1; i<=totB; ++i) okB[B[i]=read()]=1;
int cnt=0;
for(int i=1,p; i<=n; ++i) if((p=read())<=m&&p>1) P[++cnt]=p;
n=cnt;
bool f=0;
for(int i=1; i<=n; ++i) if(okA[P[i]]&&P[i]>1) {f=1; break;}
if(!f) return puts("Orange"),0;
//Pomegranate Orange
if(!totA) return puts("Orange"),0;
if(!totB) return puts("Pomegranate"),0;
if(n<=8||1) return Subtask1::Main(),0;
std::sort(A+1,A+1+totA), std::sort(B+1,B+1+totB);
Init();
int sum=0;
for(int i=1; i<=n; ++i) sum^=sg[0][P[i]];
puts(sum?"Pomegranate":"Orange");
return 0;
}
C
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define MAXIN 200000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=5e4+5,INF=2e9;
int n,m,L[6][N],R[6][N],row[6][N],col[6][N];
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
namespace Subtask4
{
int f[2][10005];
void Main()
{
int n=::n,m=::m,now=0,las=1;
for(int j=2; j<=m; ++j)
for(int a=L[1][j]; a<=R[1][j]; ++a)
{
int tmp=INF;
for(int k=L[1][j-1]; k<=R[1][j-1]; ++k)
tmp=std::min(tmp,f[las][k]+std::abs(a-k)*row[1][j-1]);
f[now][a]=tmp;
}
int ans=INF;
for(int i=L[n][m]; i<=R[n][m]; ++i) ans=std::min(ans,f[now][i]);
printf("%d\n",ans);
}
}
namespace Subtask5
{
int f[6][N][2];
void Main()
{
int n=::n,m=::m;
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
for(int a=L[i][j]; a<=R[i][j]; ++a)
{
int tmp=INF;
for(int k=L[i][j-1]; k<=R[i][j-1]; ++k)
for(int l=L[i-1][j]; l<=R[i-1][j]; ++l)
tmp=std::min(tmp,f[i][j-1][k]+std::abs(a-k)*row[i][j-1]+f[i-1][j][l]+std::abs(a-l)*col[i-1][j]);
f[i][j][a]=tmp;
}
int ans=INF;
for(int i=L[n][m]; i<=R[n][m]; ++i) ans=std::min(ans,f[n][m][i]);
printf("%d\n",ans);
}
}/*
3 1
2 2 3 5 5 5
4 4
*/
int main()
{
// freopen("C1.in","r",stdin);
// freopen(".out","w",stdout);
m=read(),n=read();//n行m列
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j) L[i][j]=read(),R[i][j]=read();
for(int i=1; i<=n; ++i)
for(int j=1; j<m; ++j) row[i][j]=read();
for(int i=1; i<n; ++i)
for(int j=1; j<=m; ++j) col[i][j]=read();
if(n==1) return Subtask4::Main(),0;
return Subtask5::Main(),0;
return 0;
}