注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

NOI2009算法总结  

2009-08-23 15:35:26|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

NOI2009算法总结

北京 范浩强

今年OI可谓是盛况空前,大牛云集,精彩纷呈。在题目及算法上,都有了更多的趣味。

Day1

【第一题:变换序列】

题目意思:每个位置上都有两个或一个可行的值,求字典序最小的可行的0~N-1全排列。

一看就是二分图。左边为0~N-1的位置,右边为0~N-1的数字。如果第x个位置可以填y,则连一条线。题目所求为最大匹配。

这个匹配的求法,我使用的是Dinic,成功AC。题目比较恶心的是要输出字典序最小。我用的方法:Dinic初始解,从前往后扫描每个位置,尝试填字典序更小的那个数字,看是否可以在网络中找到一个“交错环”,如果有则增广之。

北京的何行舟同学写的也是Dinic,结果最后一个点TLE了。看来,使用Dinic是有技巧的。张放大牛使用的“一通乱搞”,即,利用图的极端稀疏性,把问题转化为图中找环的问题,dfs之。

题目给的数据很仁慈,实际复杂度未知的Dinic和线性的dfs都过了。

【第二题:诗人小G

题目意思:给一个文章排版,使每行多出或少的字母数的K次方之和最小。

这是一个经典的dp

dp[i]表示前i个次放在整行中的最小代价。

dp[i]=min{dp[j]+Abs(lenth(j+1,i)-L)^k}

有人说这个符合四边形法则,于是用单调队列优化就行了。(我感到怀疑)。有人用蒙分:每次选j=i-2000i-1,得出的最优解即为答案,也有人把0...i-1分成若干份,每份里用三分搜索。总之,他们都AC了。

我其实想到了单调队列的方法,只不过有一个细节不知道怎么写:题目要求如果差>1000000000000000000就输出“Too hard to arrange”,而这个范围超出了纯long long的计算范围。还是张放大牛说的好:每次乘法前用double试乘一下,如果超long long直接忽略。

最后,我只把第一个点搞掉了。

【第三题:二叉查找树】

题目意思:修改treap中若干个点的权值,使得修改代价+最后的访问代价最小。

又是一个dp

先用key排一遍序(某个大牛坚持要对70个数使用快排,以避免超时)。

最开始的想法:设dp(i,j)表示从ij的区间构成的子树最优的代价。

dp(i,j)=min{

dp(i,k-1)+dp(k+1,j)

k的权值为i~j间最小的

dp(i,k-1)+dp(k+1,j)+K

k的权值不是最小的,K为修改代价。

|k=i..j

}+sum(i,j)

不过,悲惨的是,我这么做wa10个点(出题的说应该对3个点)。为什么wa了?因为:没有考虑一个点权值向大调整的可能!

正解如何?

dp(i,j,k)=min{

dp(i,l-1,Weight(l))+dp(l+1,j,Weight(l))

l的权值,Weight(l),大于k

dp(i,l-1,k)+dp(l+1,j,k)+K

l的权值,Weight(l),小于k

|k=i..j

}+sum(i,j)

就是这么一个小小的改动,由wa变成了AC

北京的何博硕试图用随机化蒙分,结果,光荣的挂了。

代码如下:

#include <cstdio>

#define NMax 70

using namespace std;

int dp[NMax][NMax][NMax];

int rank[NMax],key[NMax],V[NMax],weight[NMax],ss[NMax+1];

int N,K;

int dfs(int b,int e,int k){

if (b>e)return 0;

if (dp[b][e][k]!=-1)return dp[b][e][k];

dp[b][e][k]=2100000000;

int tmp;

for (int i=b;i<=e;i++){

//case 1 : free the node

tmp=dfs(b,i-1,k)+dfs(i+1,e,k)+ss[e+1]-ss[b]+K;

if (tmp<dp[b][e][k])dp[b][e][k]=tmp;

//case 2 : stil the same

if (rank[i]>=k){

tmp=dfs(b,i-1,rank[i])+dfs(i+1,e,rank[i])+

ss[e+1]-ss[b];

if (tmp<dp[b][e][k])dp[b][e][k]=tmp;

}

}

return dp[b][e][k];

}

int main()

{

int t;

FILE *fin=fopen("treapmod.in","r"),

*fout=fopen("treapmod.out","w");

fscanf(fin,"%d %d",&N,&K);

for (int i=0;i<N;i++)fscanf(fin,"%d",key+i);

for (int i=0;i<N;i++)fscanf(fin,"%d",weight+i);

for (int i=0;i<N;i++)fscanf(fin,"%d",V+i);

for (int i=0;i<N;i++)for (int j=i+1;j<N;j++)if (key[i]>key[j]){

t=key[i];key[i]=key[j];key[j]=t;

t=V[i];V[i]=V[j];V[j]=t;

t=weight[i];weight[i]=weight[j];weight[j]=t;

}

for (int i=0;i<N;i++)for (int j=rank[i]=0;j<N;j++)

rank[i]+=(weight[j]<weight[i]);

for (int i=ss[0]=0;i<N;i++)ss[i+1]=ss[i]+V[i];

for (int i=0;i<N;i++)for (int j=0;j<N;j++)

for (int k=0;k<N;k++)dp[i][j][k]=-1;

fprintf(fout,"%d\n",dfs(0,N-1,0));

fclose(fin);fclose(fout);

return 0;

}

可以看出,今年day1的题目较去年简单了些,不过依然和我的水平有距离。

Day2

【第一题:植物大战僵尸】

题目意思:一个矩阵,每次可以取走每行最右边的数,但是有些元素必须在他依赖的元素都取走后才能取。试图最大化取的元素和。

有个大牛说这是经典的最大权封闭子图问题,可以转换为最小割。

而我是在考试结束的那一刹那想出了那个网络流解法。

有点像最大获利问题,构图的思路:先假设我们把正权的点都搞到了。令所有我们选择的点和源点在割的同一边,反之亦然。这样,每个正权点和源连一个变,流量是权值,负权和汇连一个边,流量是权值的相反数。如果x依赖y,则从xy连一条无穷大的边。

图很小,跑Dinic应该就过了。另外有一个特判:如果出现“依赖环”的情况,那么环中的点统统删,所有依赖删去的点的点统统删。

出题的大牛说用搜索可以得80分,但要强剪枝。我考试的时候用启发式搜索+掐时得到了50分。

代码:

#include <cstdio>

#define NMax 600

using namespace std;

char map[NMax][NMax],used[NMax];

int N,R,C;

int V[NMax],ord[NMax],nc;

void dfs1(int id){//拓扑排序

used[id]=1;

for (int i=0;i<N;i++)if (map[id][i] && !used[i])

dfs1(i);

ord[nc++]=id;

}

void dfs2(int id){//污染强联通分量

used[id]=0;

for (int i=0;i<N;i++)if (map[id][i] && used[i]==1)

dfs2(i);

}

int S,T,f[NMax+2][NMax+2],n;

int Level[NMax+2],queue[NMax+2];

int makeLevel(){

int qbot,x;

for (int i=0;i<n;i++)Level[i]=-1;

Level[S]=0;queue[0]=S;qbot=1;

for (int qtop=0;qtop<qbot;qtop++){x=queue[qtop];

for (int i=0;i<n;i++)if (f[x][i]>0 && Level[i]==-1)

Level[queue[qbot++]=i]=Level[x]+1;

}

return Level[T]!=-1;

}

#define Min(_,__) (((_)<(__))?(_):(__))

int extend(int x,int alpha){

int t;

if (x==T)return alpha;

for (int i=0;i<n;i++)if (f[x][i]>0 && Level[i]==Level[x]+1)

if (t=extend(i,Min(alpha,f[x][i])))

return f[x][i]-=t,f[i][x]+=t,t;

return Level[x]=-1,0;

}

int Dinic(){

int ret,t;ret=0;

while (makeLevel())while (t=extend(S,2100000000))

ret+=t;

return ret;

}

int main()

{

int x,y,M;

FILE *fin=fopen("pvz.in","r"),

*fout=fopen("pvz.out","w");

fscanf(fin,"%d %d",&R,&C);

N=R*C;

for (int i=0;i<N;i++)for (int j=0;j<N;j++)map[i][j]=0;

for (int i=0;i<R;i++)for (int j=0;j<C;j++)

for (int k=0;k<j;k++)map[i*C+j][i*C+k]=1;

for (int i=0;i<N;i++){

fscanf(fin,"%d %d",V+i,&M);

for (int j=0;j<M;j++){

fscanf(fin,"%d %d",&x,&y);

map[i][x*C+y]=1;

}

}

nc=0;

for (int i=0;i<N;i++)used[i]=0;

for (int i=0;i<N;i++)if (!used[i])dfs1(i);

for (int i=0;i<N;i++)used[i]=1;

for (int i=N-1;i>=0;i--)if (used[ord[i]]==1){

nc=0;

for (int j=0;j<N;j++)if (used[j]==1 && map[j][ord[i]])

{nc=1;break;}

if (nc)dfs2(ord[i]);

if (used[ord[i]]==1)used[ord[i]]=2;

}

n=N+2;S=0;T=n-1;

nc=0;

for (int i=0;i<n;i++)for (int j=0;j<n;j++)f[i][j]=0;

for (int i=0;i<N;i++)if (used[i]){

if (V[i]>0)nc+=(f[S][i+1]=V[i]);

else f[i+1][T]=-V[i];

}

for (int i=0;i<N;i++)for (int j=0;j<N;j++)if (map[i][j])

f[j+1][i+1]=2100000000;

fprintf(fout,"%d\n",nc-Dinic());

fclose(fin);fclose(fout);

return 0;

}

【第二题:管道取珠】

题目意思:合并两个01串,问所有的结果对应的种类数的平方和。

一看就是dp。只不过,不知道如何dp罢了。

dp的思路是:考虑两个状态间所有结果的出现次数之积之和。

dp(l,i,j):

状态1:上边i个,下边l-i

状态2:上边j个,下边l-j

例:状态1可以产生01001一共3个,状态2可以产生01001一共5个,则对dp(l,i,j)的贡献为3*5=15

这样,dp(l,i,j)=sigma{

dp(l-1,i,j) 两个状态下边的管道的最后一个球相等

dp(l-1,i-1,j-1) 两个状态上边的管道的最后一个球相等

dp(l-1,i-1,j) 1=2

dp(l-1,i,j-1) 1=2

}

复杂度Θ((N+M)NM)程序很短。

#include <cstdio>

#define MODULO 1024523

#define NMax 500

using namespace std;

char A[NMax+1],B[NMax+1];

int N,M;

int dp[2][NMax+1][NMax+1];

int main()

{

FILE *fin=fopen("ball.in","r"),*fout=fopen("ball.out","w");

fscanf(fin,"%d %d",&N,&M);

fscanf(fin,"%s%s",A,B);

for (int i=0;i<=N;i++)for (int j=0;j<=M;j++)dp[0][i][j]=0;

dp[0][0][0]=1;

int *tmp,a,l,*t2;

for (int l=1;l<=N+M;l++){a=l&1;

for (int i=0;i<=N;i++)for (int j=0;j<=N;j++){

if (i>l || j>l || l-1-i>=M || l-1-j>=M)dp[a][i][j]=0;

else{

tmp=&(dp[a][i][j]);*tmp=0;t2=&(dp[a^1][i][j]);

if (l>i && l>j && B[l-1-i]==B[l-1-j])*tmp+=*t2;

if (l>i && j   && B[l-1-i]==A[ j-1 ])*tmp+=*(t2-1);

if (i   && l>j && A[ i-1 ]==B[l-1-j])*tmp+=*(t2-NMax-1);

if (i   && j   && A[ i-1 ]==A[ j-1 ])*tmp+=*(t2-NMax-2);

while (*tmp>=MODULO)*tmp-=MODULO;

}

}

}

fprintf(fout,"%d\n",dp[(N+M)&1][N][N]);

fclose(fin);fclose(fout);

return 0;

}

考场上我和大众一起,暴力蒙30分。

【第三题:描边】

题目意思:求一个圆和长方形组成的图形的面积。

这是做法纷呈的一个题。

我的做法:暴力撒点,判断是否在图形内,然后统计。

我得到了60分。

50分做法:手算。一个安徽小牛如此。但是……他只得到了10分。

97分做法:扫描线+数学。

扫描可以按交点扫描,也可以暴力分区间。

  评论这张
 
阅读(2998)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017