NOI2009算法总结.doc

网易 新闻 微博 邮箱 闪电邮 相册 有道 手机邮 印像派 梦幻人生 更多 博客 博客首页 博客话题 热点专题 博客油菜地 找朋友 博客圈子 博客风格 手机博客 短信写博 邮件写博 博客复制 摄影 主题展区 每日专题 摄影人物志 摄影师专访 摄影点评 随便看看 注册 登录 显示下一条|关闭 fanhq666的博客导航首页 日志 相册 音乐 收藏 博友 关于我 日志fanhq666 加博友 关注他 最新日志挖掘Treap的潜力测试:chrome执行javascript神奇的HTML5和Ubuntu的纠结事NOIP2010让CPU占用率画正弦曲线该作者的其他文章博主推荐相关日志随机阅读首页推荐2011春运十大心酸画面登上美军潜艇探秘(图)在英国小岛快乐裸奔日美该如何应对歼20？苏紫紫：回应网络留言武汉大雪厚度惊人(图)更多 20090723做的题 植物大战僵尸修改钱数的方法NOI2009算法总结程序 2009-08-23 15:35:26 阅读406 评论1 字号：大中小订阅 NOI2009算法总结北京 范浩强今年OI可谓是盛况空前，大牛云集，精彩纷呈。在题目及算法上，都有了更多的趣味。Day1【第一题：变换序列】题目意思：每个位置上都有两个或一个可行的值，求字典序最小的可行的0N-1全排列。一看就是二分图。左边为0N-1的位置，右边为0N-1的数字。如果第x个位置可以填y，则连一条线。题目所求为最大匹配。这个匹配的求法，我使用的是Dinic，成功AC。题目比较恶心的是要输出字典序最小。我用的方法：Dinic初始解，从前往后扫描每个位置，尝试填字典序更小的那个数字，看是否可以在网络中找到一个“交错环”，如果有则增广之。北京的何行舟同学写的也是Dinic，结果最后一个点TLE了。看来，使用Dinic是有技巧的。张放大牛使用的“一通乱搞”，即，利用图的极端稀疏性，把问题转化为图中找环的问题，dfs之。题目给的数据很仁慈，实际复杂度未知的Dinic和线性的dfs都过了。【第二题：诗人小G】题目意思：给一个文章排版，使每行多出或少的字母数的K次方之和最小。这是一个经典的dp。设dpi表示前i个次放在整行中的最小代价。dpi=mindpj+Abs(lenth(j+1,i)-L)k有人说这个符合四边形法则，于是用单调队列优化就行了。（我感到怀疑）。有人用蒙分：每次选j=i-2000到i-1，得出的最优解即为答案，也有人把0.i-1分成若干份，每份里用三分搜索。总之，他们都AC了。我其实想到了单调队列的方法，只不过有一个细节不知道怎么写：题目要求如果差1000000000000000000就输出“Too hard to arrange”，而这个范围超出了纯long long的计算范围。还是张放大牛说的好：每次乘法前用double试乘一下，如果超long long直接忽略。最后，我只把第一个点搞掉了。【第三题：二叉查找树】题目意思：修改treap中若干个点的权值，使得修改代价+最后的访问代价最小。又是一个dp。先用key排一遍序（某个大牛坚持要对70个数使用快排，以避免超时）。最开始的想法：设dp(i,j)表示从i到j的区间构成的子树最优的代价。dp(i,j)=mindp(i,k-1)+dp(k+1,j)k的权值为ij间最小的dp(i,k-1)+dp(k+1,j)+Kk的权值不是最小的，K为修改代价。|k=i.j+sum(i,j)不过，悲惨的是，我这么做wa了10个点（出题的说应该对3个点）。为什么wa了？因为：没有考虑一个点权值向大调整的可能！正解如何？dp(i,j,k)=mindp(i,l-1,Weight(l)+dp(l+1,j,Weight(l)l的权值，Weight(l)，大于kdp(i,l-1,k)+dp(l+1,j,k)+Kl的权值，Weight(l)，小于k|k=i.j+sum(i,j)就是这么一个小小的改动，由wa变成了AC。北京的何博硕试图用随机化蒙分，结果，光荣的挂了。代码如下：#include #define NMax 70using namespace std;int dpNMaxNMaxNMax;int rankNMax,keyNMax,VNMax,weightNMax,ssNMax+1;int N,K;int dfs(int b,int e,int k)if (be)return 0;if (dpbek!=-1)return dpbek;dpbek=2100000000;int tmp;for (int i=b;i=e;i+)/case 1 : free the nodetmp=dfs(b,i-1,k)+dfs(i+1,e,k)+sse+1-ssb+K;if (tmp=k)tmp=dfs(b,i-1,ranki)+dfs(i+1,e,ranki)+sse+1-ssb;if (tmpdpbek)dpbek=tmp;return dpbek;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;iN;i+)fscanf(fin,%d,key+i);for (int i=0;iN;i+)fscanf(fin,%d,weight+i);for (int i=0;iN;i+)fscanf(fin,%d,V+i);for (int i=0;iN;i+)for (int j=i+1;jkeyj)t=keyi;keyi=keyj;keyj=t;t=Vi;Vi=Vj;Vj=t;t=weighti;weighti=weightj;weightj=t;for (int i=0;iN;i+)for (int j=ranki=0;jN;j+)ranki+=(weightjweighti);for (int i=ss0=0;iN;i+)ssi+1=ssi+Vi;for (int i=0;iN;i+)for (int j=0;jN;j+)for (int k=0;kN;k+)dpijk=-1;fprintf(fout,%dn,dfs(0,N-1,0);fclose(fin);fclose(fout);return 0;可以看出，今年day1的题目较去年简单了些，不过依然和我的水平有距离。Day2【第一题：植物大战僵尸】题目意思：一个矩阵，每次可以取走每行最右边的数，但是有些元素必须在他依赖的元素都取走后才能取。试图最大化取的元素和。有个大牛说这是经典的最大权封闭子图问题，可以转换为最小割。而我是在考试结束的那一刹那想出了那个网络流解法。有点像最大获利问题，构图的思路：先假设我们把正权的点都搞到了。令所有我们选择的点和源点在割的同一边，反之亦然。这样，每个正权点和源连一个变，流量是权值，负权和汇连一个边，流量是权值的相反数。如果x依赖y，则从x往y连一条无穷大的边。图很小，跑Dinic应该就过了。另外有一个特判：如果出现“依赖环”的情况，那么环中的点统统删，所有依赖删去的点的点统统删。出题的大牛说用搜索可以得80分，但要强剪枝。我考试的时候用启发式搜索+掐时得到了50分。代码：#include #define NMax 600using namespace std;char mapNMaxNMax,usedNMax;int N,R,C;int VNMax,ordNMax,nc;void dfs1(int id)/拓扑排序usedid=1;for (int i=0;iN;i+)if (mapidi & !usedi)dfs1(i);ordnc+=id;void dfs2(int id)/污染强联通分量usedid=0;for (int i=0;iN;i+)if (mapidi & usedi=1)dfs2(i);int S,T,fNMax+2NMax+2,n;int LevelNMax+2,queueNMax+2;int makeLevel()int qbot,x;for (int i=0;in;i+)Leveli=-1;LevelS=0;queue0=S;qbot=1;for (int qtop=0;qtopqbot;qtop+)x=queueqtop;for (int i=0;i0 & Leveli=-1)Levelqueueqbot+=i=Levelx+1;return LevelT!=-1;#define Min(_,_) (_)(_)?(_):(_)int extend(int x,int alpha)int t;if (x=T)return alpha;for (int i=0;i0 & Leveli=Levelx+1)if (t=extend(i,Min(alpha,fxi)return fxi-=t,fix+=t,t;return Levelx=-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;iN;i+)for (int j=0;jN;j+)mapij=0;for (int i=0;iR;i+)for (int j=0;jC;j+)for (int k=0;kj;k+)mapi*C+ji*C+k=1;for (int i=0;iN;i+)fscanf(fin,%d %d,V+i,&M);for (int j=0;jM;j+)fscanf(fin,%d %d,&x,&y);mapix*C+y=1;nc=0;for (int i=0;iN;i+)usedi=0;for (int i=0;iN;i+)if (!usedi)dfs1(i);for (int i=0;i=0;i-)if (usedordi=1)nc=0;for (int j=0;jN;j+)if (usedj=1 & mapjordi)nc=1;break;if (nc)dfs2(ordi);if (usedordi=1)usedordi=2;n=N+2;S=0;T=n-1;nc=0;for (int i=0;in;i+)for (int j=0;jn;j+)fij=0;for (int i=0;i0)nc+=(fSi+1=Vi);else fi+1T=-Vi;for (int i=0;iN;i+)for (int j=0;jN;j+)if (mapij)fj+1i+1=2100000000;fprintf(fout,%dn,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)=sigmadp(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 #define MODULO 1024523#define NMax 500using namespace std;char ANMax+1,BNMax+1;int N,M;int dp2NMax+1NMax+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+)dp0ij=0;dp000=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;jl | jl | l-1-i=M | l-1-j=M)dpaij=0;elsetmp=&(dpaij);*tmp=0;t2=&(dpa1ij);if (li & lj & Bl-1-i=Bl-1-j)*tmp+=*t2;if (li & j & Bl-1-i=A j-1 )*tmp+=*(t2-1);if (i & lj & A i-1 =Bl-1-j)*tmp+=*(t2-NMax-1);if (i & j & A i-1 =A j-1 )*tmp+=*(t2-NMax-2);while (