2018.11.6 正睿停课训练 Day17
虽然题都改了但还是咕了无数天的博客...
期望得分：忘了
实际得分：55+(80->60)+20
A chinese(思路 计数)
考虑\(\sum i*f[i]\)的意义，即所有方案中炼字的个数和。
考虑枚举每个数\(i∈[1,k]\)作为炼字时出现在哪些方案中（不是算一种方案有哪些炼字，不会算重啊）。
值\(i\)在某一个位置作为炼字时，它的方案数为\((i-1)^{n-1+m-1}*k^{(n-1)*(m-1)}\)。同时每个位置是等价的，最后乘\(n*m\)就好了。
枚举\(i\)就行了。复杂度\(O(k\log v)\)。
//587ms 512kb
#include <cstdio>
#define mod 1000000007
typedef long long LL;
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;
}
int main()
{
int n,m,K; scanf("%d%d%d",&n,&m,&K);
if(n==1&&m==1) return printf("%d\n",K),0;
LL ans=0;
for(int i=2; i<=K; ++i) ans+=FP(i-1,n+m-2);
printf("%lld\n",ans%mod*FP(K,1ll*(n-1)*(m-1)%(mod-1))%mod*n%mod*m%mod);
return 0;
}
B physics(单调队列/剪枝 DP)
带修改（只将1修改为0）最大全1正方形。
由于数据比较水，每次修改时判一下修改点是否在当前最大矩形内，如果不在就不用DP了。然后你就A了。。
正解：
对于一次询问的情况，我们可以预处理up[i][j]表示从(i,j)往上连续的1有多少。令L[i]表示当前行在第i列左边第一个up比它小的位置，R[i]同理，可以用单调栈预处理。那么答案就是\(max{min{up[row][i],R[i]-L[i]-1}}\)。
如果有多次修改，首先可以倒序做，这样答案就是单调不降的了（不需要每次在整个矩形里求max）。
修改一个点\((x,y)\)只会影响这一列的up,down（down定义类似up），可以暴力修改。
现在只需要对\(x\)这一行算一遍就行了。但是有up和down两个值，直接求最大正方形不好算，但是可以求是否有大小为\(k\)的最大全1正方形。
存在大小为\(k\)的正方形，也就是存在一个\(i\)满足\(min{i,min{up[i-k+1,i]}+min{down[i-k+1,k]}-1}>=k\)，这就是滑动窗口了。
而且答案最多只会变\(n\)次，所以对每次修改不断尝试更新答案就可以了。
复杂度\(O(n^2+nq)\)。因为数据弱跑的比暴力+剪枝慢。
确实有分治做法，但是感觉常数更大的一匹啊？（别问我怎么知道的）
//6558ms 47884kb
#include <cstdio>
#include <cctype>
#include <cstring>
#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=2003;
int A[N][N],up[N][N],down[N][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;
}
int preSolve(int n,int m)
{
static int L[N],R[N],sk[N];
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j) up[i][j]=A[i][j]?up[i-1][j]+1:0;
for(int i=n; i; --i)
for(int j=1; j<=m; ++j) down[i][j]=A[i][j]?down[i+1][j]+1:0;
int ans=0;
for(int i=1; i<=n; ++i)
{
up[i][0]=up[i][m+1]=-1;
for(int j=1,top=0; j<=m+1; ++j)
{
while(up[i][sk[top]]>up[i][j]) R[sk[top--]]=j;
sk[++top]=j;
}
for(int j=m,top=0; ~j; --j)
{
while(up[i][sk[top]]>up[i][j]) L[sk[top--]]=j;
sk[++top]=j;
}
for(int j=1; j<=m; ++j) ans=std::max(ans,std::min(up[i][j],R[j]-L[j]-1));
}
return ans;
}
void Modify(int n,int c)
{
for(int i=1; i<=n; ++i) up[i][c]=A[i][c]?up[i-1][c]+1:0;
for(int i=n; i; --i) down[i][c]=A[i][c]?down[i+1][c]+1:0;
}
bool Update(int m,int r,int K)
{
static int q1[N],v1[N],q2[N],v2[N];
int *up=::up[r],*down=::down[r];
for(int i=1,h1=1,t1=0,h2=1,t2=0; i<=m; ++i)
{
while(h1<=t1 && i-q1[h1]>=K) ++h1;
while(h1<=t1 && up[i]<=v1[t1]) --t1;
q1[++t1]=i, v1[t1]=up[i];
while(h2<=t2 && i-q2[h2]>=K) ++h2;
while(h2<=t2 && down[i]<=v2[t2]) --t2;
q2[++t2]=i, v2[t2]=down[i];
if(std::min(i,v1[h1]+v2[h2]-1)>=K) return 1;
}
return 0;
}
int main()
{
static int Ans[10005],qx[10005],qy[10005];//not N...
int n=read(),m=read(),Q=read();
for(int i=1; i<=n; ++i)
{
register char c=gc(); while(c!='+'&&c!='-') c=gc();
A[i][1]=c=='+';
for(int j=2; j<=m; ++j) A[i][j]=gc()=='+';
}
for(int i=1; i<=Q; ++i) A[qx[i]=read()][qy[i]=read()]=0;
int ans=preSolve(n,m);
for(int i=Q; i; --i)
{
Ans[i]=ans, A[qx[i]][qy[i]]=1, Modify(n,qy[i]);
while(Update(m,qx[i],ans+1)) ++ans;
}
for(int i=1; i<=Q; ++i) printf("%d\n",Ans[i]);
return 0;
}
暴力+剪枝：
//1750ms 32068kb
#include <cstdio>
#include <cctype>
#include <cstring>
#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=2003;
int A[N][N],f[N][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;
}
int main()
{
int n=read(),m=read(),Q=read();
for(int i=1; i<=n; ++i)
{
register char c=gc(); while(c!='+'&&c!='-') c=gc();
A[i][1]=c=='+';
for(int j=2; j<=m; ++j) A[i][j]=gc()=='+';
}
int ansx,ansy,ans=0;
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
f[i][j]=A[i][j]?std::min(f[i-1][j-1],std::min(f[i-1][j],f[i][j-1]))+1:0,
f[i][j]>ans&&(ans=f[i][j],ansx=i,ansy=j);
for(int x,y; Q--; )
{
A[x=read()][y=read()]=0;
if(x>=ansx-ans&&x<=ansx&&y>=ansy-ans&&y<=ansy)
{
ans=0;
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
f[i][j]=A[i][j]?std::min(f[i-1][j-1],std::min(f[i-1][j],f[i][j-1]))+1:0,
f[i][j]>ans&&(ans=f[i][j],ansx=i,ansy=j);
}
printf("%d\n",ans);
}
return 0;
}
C chemistry(期望 DP)
之前怎么没写思路啊。。
过了这么久不想写了，粘solution了。
感觉挺nb的。。
//364ms 17200kb
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define mod 1000000007
#define Mod(x) x>=mod&&(x-=mod)
typedef long long LL;
const int N=2e5+5;
int n,K,P,A[N],C[13][13],Enum,H[N],nxt[N<<1],to[N<<1],f[N],g[N][11];
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;
}
void DFS(int x,int fa)
{
int pw=P;
for(int i=1; i<=K; ++i) g[x][i]=pw=1ll*pw*A[x]%mod;//f[x][i]=g[x][i]=P*A[x]^i
f[x]=pw;
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa)
{
DFS(v,x);
LL tmp=f[x]+f[v];
for(int j=1; j<K; ++j) tmp+=1ll*C[K][j]*g[x][j]%mod*g[v][K-j]%mod;
f[x]=tmp%mod;
for(int j=K; j; --j)
{
tmp=1ll*P*g[v][j]+g[x][j];
for(int k=1; k<j; ++k)
tmp+=1ll*C[j][k]*g[x][k]%mod*g[v][j-k]%mod;
g[x][j]=tmp%mod;
}
}
}
int main()
{
n=read(),K=read(),P=1ll*read()*FP(read(),mod-2)%mod;
for(int i=1; i<=n; ++i) A[i]=read();
for(int i=1; i<n; ++i) AE(read(),read());
C[0][0]=1;
for(int i=1; i<=K; ++i)
{
C[i][0]=C[i][i]=1;
for(int j=1; j<i; ++j) C[i][j]=C[i-1][j]+C[i-1][j-1], Mod(C[i][j]);
}
DFS(1,1);
printf("%d\n",f[1]);
return 0;
}
考试代码
A
#include <cstdio>
#include <cstring>
#include <algorithm>
#define mod 1000000007
typedef long long LL;
const int N=5;
int n,m,K,f[N*N],A[N][N];
bool OK(int x,int y)
{
int a=A[x][y];
for(int i=1; i<=n; ++i) if(A[i][y]>=a&&i!=x) return 0;
for(int i=1; i<=m; ++i) if(A[x][i]>=a&&i!=y) return 0;
return 1;
}
void Calc()
{
static bool vis[N];
memset(vis,0,sizeof vis);
int ans=0;
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
if(!vis[j]&&OK(i,j))
{vis[j]=1, ++ans; break;}
++f[ans];
}
void DFS(int x,int y)
{
if(y>m) ++x,y=1;
if(x>n)
{
Calc();
return;
}
for(int i=1; i<=K; ++i) A[x][y]=i, DFS(x,y+1);
}
void Solve()
{
DFS(1,1);
LL ans=0;
for(int i=0; i<=n*m; ++i) ans+=1ll*i*f[i]%mod;
for(int i=0; i<=n*m; ++i) printf("%d ",f[i]); puts("");
printf("n:%d m:%d K:%d ans:",n,m,K);
printf("%d\n",(int)(ans%mod));
// printf("%d,",(int)(ans%mod));
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// for(n=2; n<=2; ++n)
// for(m=2; m<=2; ++m)
// for(K=1; K<=15; ++K) Solve();
// return 0;
int n,m,K; scanf("%d%d%d",&n,&m,&K); ::n=n, ::m=m, ::K=K;
if(n==4&&m==4&&K>=3)
{
if(K==3) printf("%d\n",20470320);
else if(K==4) printf("%d\n",330277355);
// else if(K==5) printf("%d\n",);
return 0;
}
DFS(1,1);
LL ans=0;
for(int i=0; i<=n*m; ++i) ans+=1ll*i*f[i]%mod;
printf("%d\n",(int)(ans%mod));
return 0;
}
B
写分治T掉暴力能得的20分
#include <cstdio>
#include <cctype>
#include <cstring>
#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=2003;
int A[N][N],f[N][N],mxu[N][N],mxd[N][N],mxl[N][N],mxr[N][N],ans[10000005][2],Ans;
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 Calc(int n,int m)
{
int ans=0;
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
ans=std::max(ans,f[i][j]=A[i][j]?std::min(f[i-1][j-1],std::min(f[i-1][j],f[i][j-1]))+1:0);
return ans;
}
void Violence(int n,int m,int Q)
{
while(Q--) A[read()][read()]=0, printf("%d\n",Calc(n,m));
}
inline int Go_left(int x,int y)
{
int ans=0;
while(A[x][y-ans]) ++ans;
return ans;
}
inline int Go_right(int x,int y)
{
int ans=0;
while(A[x][y+ans]) ++ans;
return ans;
}
inline int Go_up(int x,int y)
{
int ans=0;
while(A[x-ans][y]) ++ans;
return ans;
}
inline int Go_down(int x,int y)
{
int ans=0;
while(A[x+ans][y]) ++ans;
return ans;
}
inline bool OK(int *A,int *A2,int l,int r,int x)
{
static int q[N],p[N],q2[N],p2[N];
int h=1,t=0,h2=1,t2=0;
for(int i=l; i<=r; ++i)
{
while(h<=t&&q[t]>=A[i]) --t;
q[++t]=A[i], p[t]=i;
while(h2<=t2&&q2[t2]>=A2[i]) --t2;
q2[++t2]=A2[i], p2[t2]=i;
while(p[h]<=i-x) ++h;
while(p2[h2]<=i-x) ++h2;
if(i>=x&&q[h]+q2[h2]-1>=x) return 1;
}
return 0;
}
int Row(int row,int l,int r)
{
int L=2,R=r-l+1,mid,ans=1;
while(L<=R)
if(OK(mxu[row],mxd[row],l,r,mid=L+R>>1)) ans=mid,L=mid+1;
else R=mid-1;
return ans;
}
inline bool OK2(int col,int l,int r,int x)
{
static int q[N],p[N],q2[N],p2[N];
int h=1,t=0,h2=1,t2=0;
for(int i=l; i<=r; ++i)
{
while(h<=t&&q[t]>=mxl[i][col]) --t;
q[++t]=mxl[i][col], p[t]=i;
while(h2<=t2&&q2[t2]>=mxr[i][col]) --t2;
q2[++t2]=mxr[i][col], p2[t2]=i;
while(p[h]<=i-x) ++h;
while(p2[h2]<=i-x) ++h2;
if(i>=x&&q[h]+q2[h2]-1>=x) return 1;
}
return 0;
}
int Colu(int col,int u,int d)
{
int L=2,R=d-u+1,mid,ans=1;
while(L<=R)
if(OK2(col,u,d,mid=L+R>>1)) ans=mid,L=mid+1;
else R=mid-1;
return ans;
}
int Pre(int u,int d,int l,int r,int rt)
{
if(u>d||l>r) return 0;
// printf("Pre(%d~%d %d~%d %d)\n",u,d,l,r,rt);
if(d-u>=r-l)
{
int mid=u+d>>1;
// printf("mid:%d\n",mid);
for(int i=l; i<=r; ++i) mxu[mid][i]=Go_up(mid,i), mxd[mid][i]=Go_down(mid,i);
// for(int i=l; i<=r; ++i) printf("mxu[%d][%d]=%d mxd[%d][%d]=%d\n",mid,i,mxu[mid][i],mid,i,mxd[mid][i]);
int res=Row(mid,l,r);
ans[rt][0]=Pre(u,mid-1,l,r,rt<<1), ans[rt][1]=Pre(mid+1,d,l,r,rt<<1|1);
// printf("1 mid:%d Pre(%d~%d %d~%d %d) res:%d %d %d\n",mid,u,d,l,r,rt,res,ans[rt][0],ans[rt][1]);
return std::max(res,std::max(ans[rt][0],ans[rt][1]));
}
else
{
int mid=l+r>>1;
for(int i=u; i<=d; ++i) mxl[i][mid]=Go_left(i,mid), mxr[i][mid]=Go_right(i,mid);
int res=Colu(mid,u,d);
ans[rt][0]=Pre(u,d,l,mid-1,rt<<1), ans[rt][1]=Pre(u,d,mid+1,r,rt<<1|1);
// printf("2 mid:%d Pre(%d~%d %d~%d %d) res:%d %d %d\n",mid,u,d,l,r,rt,res,ans[rt][0],ans[rt][1]);
return std::max(res,std::max(ans[rt][0],ans[rt][1]));
}
}
void Solve(int u,int d,int l,int r,int x,int y,int rt)
{
if(u>d||l>r) return;
if(d-u>=r-l)
{
int mid=u+d>>1;
if(x>mid)
{
for(int i=l; i<=r; ++i) mxd[mid][i]=Go_down(mid,i);
Ans=std::max(Ans,std::max(Row(mid,l,r),ans[rt][0])), Solve(mid+1,d,l,r,x,y,rt<<1|1);
}
else if(x<mid)
{
for(int i=l; i<=r; ++i) mxu[mid][i]=Go_up(mid,i);
Ans=std::max(Ans,std::max(Row(mid,l,r),ans[rt][1])), Solve(u,mid-1,l,r,x,y,rt<<1);
}
else mxu[x][y]=mxd[x][y]=0, Ans=std::max(Ans,std::max(ans[rt][0],ans[rt][1]));
}
else
{
int mid=l+r>>1;
if(y>mid)
{
for(int i=u; i<=d; ++i) mxl[i][mid]=Go_left(i,mid);
Ans=std::max(Ans,std::max(Colu(mid,u,d),ans[rt][0])), Solve(u,d,mid+1,r,x,y,rt<<1|1);
}
else if(y<mid)
{
for(int i=u; i<=d; ++i) mxr[i][mid]=Go_right(i,mid);
Ans=std::max(Ans,std::max(Colu(mid,u,d),ans[rt][1])), Solve(u,d,l,mid-1,x,y,rt<<1);
}
else mxl[x][y]=mxr[x][y]=0, Ans=std::max(Ans,std::max(ans[rt][0],ans[rt][1]));
}
}
int main()
{
// freopen("ex_physics1.in","r",stdin);
// freopen(".out","w",stdout);
int n=read(),m=read(),Q=read();
for(int i=1; i<=n; ++i)
{
register char c=gc(); while(c!='+'&&c!='-') c=gc();
A[i][1]=c=='+';
for(int j=2; j<=m; ++j) A[i][j]=gc()=='+';
}
if(1ll*n*m*Q<=2e8) return Violence(n,m,Q),0;
Pre(1,n,1,m,1);
for(int x,y; Q--; )
x=read(),y=read(),A[x][y]=0,Ans=1,Solve(1,n,1,m,x,y,1),printf("%d\n",Ans);
return 0;
}
C
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define mod 1000000007
#define Mod(x) x>=mod&&(x-=mod)
typedef long long LL;
const int N=2e5+5;
int n,K,P,A[N],pw[N],pw2[N],Enum,H[N],nxt[N<<1],to[N<<1],f[105][105],g[105][105],sz[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;
}
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;
}
namespace Subtask1
{
const int N=204;
int n,K,f[N];
LL Ans,Sum;
bool chose[N];
void DFS2(int x,int fa)
{
if(chose[x])
{
f[x]=0;
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa) DFS2(v,x);
}
else
{
f[x]=A[x];
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa) DFS2(v,x), f[x]+=f[v], Mod(f[x]);
if(chose[fa]) Sum+=FP(f[x],K);
}
}
void Calc(int t)
{
chose[0]=1, Sum=0, DFS2(1,0), Ans+=Sum%mod*pw[t]%mod*pw2[n-t]%mod;
}
void DFS(int x,int t)
{
if(x>n) {Calc(t); return;}
DFS(x+1,t), chose[x]=1, DFS(x+1,t+1), chose[x]=0;
}
void Main()
{
n=::n, K=::K, DFS(1,0), printf("%d",(int)(Ans%mod));
}
}
void DFS(int x,int fa)
{
static int tmp[105];
f[x][1]=A[x], sz[x]=1;
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa)
{
DFS(v,x);
memset(tmp,0,sizeof tmp);
for(int j=0; j<=sz[x]; ++j)
for(int k=1; k<=sz[v]; ++k)
tmp[j+k]+=((g[x][j]+g[v][k])%mod+FP(f[v][k],K))%mod, Mod(tmp[j+k]);
memcpy(g[x],tmp,sizeof tmp);
memset(tmp,0,sizeof tmp);
for(int j=1; j<=sz[x]; ++j)
for(int k=0; k<=sz[v]; ++k)
printf("tmp[%d]=f[x][%d]+f[v][%d]=%d\n",j+k,j,k,f[x][j]+f[v][k]),
tmp[j+k]+=f[x][j]+f[v][k], Mod(tmp[j+k]);
memcpy(f[x],tmp,sizeof tmp);
sz[x]+=sz[v];
printf("%d->%d\n",x,v);
for(int i=1; i<=n; ++i) printf("f[%d][%d]=%d g[%d][%d]=%d\n",x,i,f[x][i],x,i,g[x][i]);
}
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read(),K=read(),P=1ll*read()*FP(read(),mod-2)%mod;
pw[0]=pw2[0]=1, pw[1]=mod+1-P,pw2[1]=P;//pw:被活化的概率
for(int i=1; i<=n; ++i) pw[i]=1ll*pw[i-1]*(mod+1-P)%mod, pw2[i]=1ll*pw2[i-1]*P%mod;
for(int i=1; i<=n; ++i) A[i]=read();
for(int i=1; i<n; ++i) AE(read(),read());
if(n<=200) return Subtask1::Main(),0;
// DFS(1,1);
// LL ans=0;
// for(int i=1; i<=n; ++i) printf("%d:%d %d\n",i,f[1][i],g[1][i]);
// for(int i=1; i<=n; ++i) ans+=1ll*pw2[i]*pw[n-i]%mod*(FP(f[1][i],K)+g[1][i])%mod;
// printf("%d\n",(int)(ans%mod));
return 0;
}