广州二中NOI2018模拟赛（三十七）
A.贪婪人
考虑一个DP
设dp[i][j][k]表示前i行j列中，a[i][j]=k时的方案数
转移也非常简单。如果某个格子左边的数是k，它本身是k+r，那么如果要从左边过来，它左下方那个格子就有r+1种取值，再下面那些格子可以任意取，因此有(s+1)^(H-i-1)种取值，于是dp[i][j][k]对dp[i][j+1][k+r]的贡献就是dp[i][j][k]*(r+1)*(s+1)^(H-i-1)
对下面那个格子的贡献也类似，具体看代码
时间复杂度O(HWS²)，能拿70分
#include<bits/stdc++.h>
#define ha 10007
using namespace std;
const int N=110;
int gao[N][N][N];
int pw[N];
inline void add(int &x,const int &y){x=(x+y>=ha)?(x+y-ha):(x+y);}
int main()
{
int n,m,s;
scanf("%d%d%d",&m,&n,&s);
gao[1][1][0]=1;pw[0]=1;
for(int i=1;i<N;i++)
pw[i]=pw[i-1]*(s+1)%ha;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
for(int k=0;k<=s;k++)
for(int l=0;l+k<=s;l++)
{
if(j<n)
{
if(i<m) add(gao[i][j+1][k+l],1ll*gao[i][j][k]*(l+1)*pw[m-i-1]%ha);
else add(gao[i][j+1][k+l],gao[i][j][k]);
}
if(i<m)
{
if(j<n) add(gao[i+1][j][k+l],1ll*gao[i][j][k]*l*pw[n-j-1]%ha);
else add(gao[i+1][j][k+l],gao[i][j][k]);
}
}
printf("%d\n",gao[m][n][s]);
return 0;
}
发现在非边缘每次向下走，路径权值最少增加1，于是可以不用做那么多的DP，只要做到第S+1行就够了
然后DP的时候用前缀和优化一下，就可以达到O(WS²)的复杂度了！
最后统计答案还要再跑一个O(HS)的DP，这个很简单，看代码就好了
#include<bits/stdc++.h>
#define ha 10007
using namespace std;
int gao[110][2510][110];
int pw[2510],f[2510][110];
int s1[5+2510],s2[5+2510];
inline void add(int &x,const int &y){x=(x+y>=ha)?(x+y-ha):(x+y);}
inline int Add(const int &x,const int &y){return (x+y>=ha)?(x+y-ha):(x+y);}
inline int dev(const int &x,const int &y){return (x-y<0)?(x-y+ha):(x-y);}
int main()
{
int m,n,s;
scanf("%d%d%d",&m,&n,&s);
gao[1][1][0]=pw[0]=1;
for(int i=1;i<=2500;i++)
pw[i]=pw[i-1]*(s+1)%ha;
for(int i=1;i<=m&&i<=s+1;i++)
for(int j=1;j<=n;j++)
{
s1[5+0]=s2[5+0]=gao[i][j][s];
for(int k=1;k<=s;k++)
s1[5+k]=(s1[5+k-1]+gao[i][j][s-k]*(k+1))%ha,
s2[5+k]=Add(s2[5+k-1],gao[i][j][s-k]);
for(int k=0;k<=s;k++)
if(i<m) add(gao[i][j+1][k],((s1[5+s]-s1[5+s-k-1]-(s2[5+s]-s2[5+s-k-1])*(s-k))%ha+ha)*pw[m-i-1]%ha);
else if(j<n) add(gao[i][j+1][k],dev(s2[5+s],s2[5+s-k-1]));
s1[5+0]=0;
for(int k=1;k<=s;k++)
s1[5+k]=(s1[5+k-1]+gao[i][j][s-k]*k)%ha;
if(i==m) continue;
for(int k=0;k<=s;k++)
{
if(j<n) add(gao[i+1][j][k],((s1[5+s]-s1[5+s-k-1]-(s2[5+s]-s2[5+s-k-1])*(s-k))%ha+ha)*pw[n-j-1]%ha);
else add(gao[i+1][j][k],dev(s2[5+s],s2[5+s-k-1]));
}
}
if(m<=s+1){printf("%d\n",gao[m][n][s]);return 0;}
for(int i=s+1;i<m;i++)
{
for(int k=0;k<=s;k++)
s2[5+k]=Add(s2[5+k-1],(i==s+1)?gao[i][n][s-k]:f[i][s-k]);
for(int k=0;k<=s;k++)
add(f[i+1][k],dev(s2[5+s],s2[5+s-k-1]));
}
printf("%d\n",f[m][s]);
return 0;
}
B.社会人
场上脑残，没想到70分做法，写了个爆搜，本以为70分的数据会有梯度，没想到直接爆0
贴一下爆搜程序，对拍用
#include<bits/stdc++.h>
using namespace std;
struct Edge{int u,v,next;bool tag;} e[60];
int h[30],tot,n,m,T;
double k;
bool vis[30];
double ans=0;
inline int get(int i,int j){return (i-1)*n+j;}
void AddEdge(int u,int v)
{
e[++tot].u=u;
e[tot].v=v;
e[tot].next=h[u];
e[tot].tag=0;
h[u]=tot;
}
void add_edge(int u,int v)
{
AddEdge(u,v);
AddEdge(v,u);
}
bool gao()
{
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(get(1,1));
while(!q.empty())
{
int u=q.front();vis[u]=1;q.pop();
for(int tmp=h[u];tmp;tmp=e[tmp].next)
if(e[tmp].tag&&(!vis[e[tmp].v]))
q.push(e[tmp].v);
}
return vis[get(m,n)];
}
void gao(int now,double p)
{
if(now>tot)
{
if(gao()) ans+=p;
return;
}
gao(now+2,p*k);
e[now].tag=e[now+1].tag=1;
gao(now+2,p*(1-k));
e[now].tag=e[now+1].tag=0;
}
int main()
{
for(scanf("%d",&T);T;T--)
{
scanf("%d%d%lf",&n,&m,&k);
ans=0;tot=0;
memset(h,0,sizeof(h));
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(j<n) add_edge(get(i,j),get(i,j+1));
if(i<m) add_edge(get(i,j),get(i+1,j));
}
gao(1,1);
printf("%.7lf\n",ans);
}
return 0;
}
试想，假如我们知道了在一个m*n的网格图中，连接k条边，使得(1,1)与(m,n)联通的方案数（这个方案数记作gao[m][n][k]），我们就可以搞出答案
设tot为m*n网格图的总边数（即tot=n*(m-1)+m*(n-1)），那么连接某k条边，其它的边不连的概率就是(1-p)^k*p^(tot-k)
于是连接k条边时，对答案的贡献就是gao[m][n][k]*(1-p)^k*p^(tot-k)
那么只要得到了这个gao数组，我们就可以在O(tot)的时间内求出答案
gao数组可以打表弄出来。打表程序跑了30s……不过这不是问题，反正是本地的时间
打表程序源码：
#include<bits/stdc++.h>
using namespace std;
struct Edge{int u,v,next;bool tag;} e[60];
int h[30],tot,n,m,T,fuck;
double k;
bool vis[30];
int ans;
inline int get(int i,int j){return (i-1)*n+j;}
void AddEdge(int u,int v)
{
e[++tot].u=u;
e[tot].v=v;
e[tot].next=h[u];
e[tot].tag=0;
h[u]=tot;
}
void add_edge(int u,int v)
{
AddEdge(u,v);
AddEdge(v,u);
}
bool gao()
{
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(get(1,1));
while(!q.empty())
{
int u=q.front();vis[u]=1;q.pop();
for(int tmp=h[u];tmp;tmp=e[tmp].next)
if(e[tmp].tag&&(!vis[e[tmp].v]))
q.push(e[tmp].v);
}
return vis[get(m,n)];
}
void gao(int now,int g)
{
if(g>=fuck)
{
if(gao()) ans++;
return;
}
if(now>tot) return;
gao(now+2,g);
e[now].tag=e[now+1].tag=1;
gao(now+2,g+1);
e[now].tag=e[now+1].tag=0;
}
int main()
{
freopen("gao.out","w",stdout);
for(m=1;m<=4;m++)
for(n=1;n<=4;n++)
{
tot=0;
memset(h,0,sizeof(h));
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(j<n) add_edge(get(i,j),get(i,j+1));
if(i<m) add_edge(get(i,j),get(i+1,j));
}
for(fuck=0;fuck<=tot/2;fuck++)
{
ans=0;
gao(1,0);
printf("gao[%d][%d][%d]=%d;\n",m,n,fuck,ans);
}
//printf("%.7lf\n",ans);
}
return 0;
}
70分代码：
#include<bits/stdc++.h>
using namespace std;
double gao[7][7][30];
double p1[30],p2[30];
void gaogao()
{
gao[1][1][0]=1;
gao[1][2][0]=0;
gao[1][2][1]=1;
gao[1][3][0]=0;
gao[1][3][1]=0;
gao[1][3][2]=1;
gao[1][4][0]=0;
gao[1][4][1]=0;
gao[1][4][2]=0;
gao[1][4][3]=1;
gao[2][1][0]=0;
gao[2][1][1]=1;
gao[2][2][0]=0;
gao[2][2][1]=0;
gao[2][2][2]=2;
gao[2][2][3]=4;
gao[2][2][4]=1;
gao[2][3][0]=0;
gao[2][3][1]=0;
gao[2][3][2]=0;
gao[2][3][3]=3;
gao[2][3][4]=12;
gao[2][3][5]=17;
gao[2][3][6]=7;
gao[2][3][7]=1;
gao[2][4][0]=0;
gao[2][4][1]=0;
gao[2][4][2]=0;
gao[2][4][3]=0;
gao[2][4][4]=4;
gao[2][4][5]=24;
gao[2][4][6]=61;
gao[2][4][7]=76;
gao[2][4][8]=40;
gao[2][4][9]=10;
gao[2][4][10]=1;
gao[3][1][0]=0;
gao[3][1][1]=0;
gao[3][1][2]=1;
gao[3][2][0]=0;
gao[3][2][1]=0;
gao[3][2][2]=0;
gao[3][2][3]=3;
gao[3][2][4]=12;
gao[3][2][5]=17;
gao[3][2][6]=7;
gao[3][2][7]=1;
gao[3][3][0]=0;
gao[3][3][1]=0;
gao[3][3][2]=0;
gao[3][3][3]=0;
gao[3][3][4]=6;
gao[3][3][5]=48;
gao[3][3][6]=166;
gao[3][3][7]=312;
gao[3][3][8]=334;
gao[3][3][9]=192;
gao[3][3][10]=64;
gao[3][3][11]=12;
gao[3][3][12]=1;
gao[3][4][0]=0;
gao[3][4][1]=0;
gao[3][4][2]=0;
gao[3][4][3]=0;
gao[3][4][4]=0;
gao[3][4][5]=10;
gao[3][4][6]=120;
gao[3][4][7]=661;
gao[3][4][8]=2179;
gao[3][4][9]=4718;
gao[3][4][10]=6929;
gao[3][4][11]=6897;
gao[3][4][12]=4568;
gao[3][4][13]=2065;
gao[3][4][14]=643;
gao[3][4][15]=134;
gao[3][4][16]=17;
gao[3][4][17]=1;
gao[4][1][0]=0;
gao[4][1][1]=0;
gao[4][1][2]=0;
gao[4][1][3]=1;
gao[4][2][0]=0;
gao[4][2][1]=0;
gao[4][2][2]=0;
gao[4][2][3]=0;
gao[4][2][4]=4;
gao[4][2][5]=24;
gao[4][2][6]=61;
gao[4][2][7]=76;
gao[4][2][8]=40;
gao[4][2][9]=10;
gao[4][2][10]=1;
gao[4][3][0]=0;
gao[4][3][1]=0;
gao[4][3][2]=0;
gao[4][3][3]=0;
gao[4][3][4]=0;
gao[4][3][5]=10;
gao[4][3][6]=120;
gao[4][3][7]=661;
gao[4][3][8]=2179;
gao[4][3][9]=4718;
gao[4][3][10]=6929;
gao[4][3][11]=6897;
gao[4][3][12]=4568;
gao[4][3][13]=2065;
gao[4][3][14]=643;
gao[4][3][15]=134;
gao[4][3][16]=17;
gao[4][3][17]=1;
gao[4][4][0]=0;
gao[4][4][1]=0;
gao[4][4][2]=0;
gao[4][4][3]=0;
gao[4][4][4]=0;
gao[4][4][5]=0;
gao[4][4][6]=20;
gao[4][4][7]=360;
gao[4][4][8]=3066;
gao[4][4][9]=16332;
gao[4][4][10]=60670;
gao[4][4][11]=165956;
gao[4][4][12]=344033;
gao[4][4][13]=547944;
gao[4][4][14]=672928;
gao[4][4][15]=635632;
gao[4][4][16]=460680;
gao[4][4][17]=258144;
gao[4][4][18]=112742;
gao[4][4][19]=38392;
gao[4][4][20]=10071;
gao[4][4][21]=1976;
gao[4][4][22]=274;
gao[4][4][23]=24;
gao[4][4][24]=1;
}
int main()
{
gaogao();
int T,m,n;
double p;
for(scanf("%d",&T);T;T--)
{
scanf("%d%d%lf",&m,&n,&p);
if(n==1&&m==1){puts("1");continue;}
int tot=n*(m-1)+m*(n-1);
p1[0]=p2[0]=1;
for(int i=1;i<=tot;i++)
p1[i]=p1[i-1]*(1-p),p2[i]=p2[i-1]*p;
double ans=0;
for(int i=1;i<=tot;i++)
ans+=gao[m][n][i]*p1[i]*p2[tot-i];
printf("%.7lf\n",ans);
}
return 0;
}
你问我100分做法？那你自己去学插头DP吧，反正我不会
C.周树人
显然是一道乱搞题
如何用36行代码得到39分？
太简单了！只要默认这棵树是一条链，然后枚举每一个点，贪心地选取与自己距离近的点为儿子就好了！当然需要并查集来维护一下，以确保不会选择已经在树上的点
#include<bits/stdc++.h>
using namespace std;
const int N=410;
struct Point{int x,y;} p[N];
int fa[N],son[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int dist(Point a,Point b){return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);}
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=n;i++)
{
int mx=0x7fffffff;
for(int j=1;j<=n;j++)
{
if(i==j) continue;
int f1=find(i),f2=find(j);
if(f1==f2) continue;
int dis=dist(p[i],p[j]);
if(dis<mx) son[i]=j,mx=dis;
}
if(son[i]) fa[find(son[i])]=fa[find(i)];
}
for(int i=1;i<=n;i++)
if(son[i]) printf("%d %d\n",i,son[i]);
}
return 0;
}
如何用47行代码得到65分？
太简单了！只要先把所有点两两之间连好边，边权设为距离，然后跑一遍最小生成树就可以了！
卧槽这么随便就拿了65分？？？为什么我场上没想到啊呜……
#include<bits/stdc++.h>
using namespace std;
struct Edge{int u,v,c;} e[160010];
struct Point{int x,y;} p[410];
int h[410],sum,fa[410];
bool operator < (const Edge &a,const Edge &b){return a.c<b.c;}
int dist(const Point &a,const Point &b){return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void gao(int n)
{
sort(e+1,e+1+sum);
int cnt=1;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=sum;i++)
{
int u=e[i].u,v=e[i].v;
int fu=find(u),fv=find(v);
if(fu==fv) continue;
fa[fv]=fu;cnt++;
printf("%d %d\n",u,v);
if(cnt==n) break;
}
}
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
memset(h,0,sizeof(h));sum=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j)
{
e[++sum].u=i;
e[sum].v=j;
e[sum].c=dist(p[i],p[j]);
}
gao(n);
}
return 0;
}
什么？你问我怎么拿100分？醒醒吧，zjt都还没搞出100分做法！