当前位置:首页 >> IT/计算机 >>

NOIP2008提高组解题报告


NOIP2008 提高组解题报告 提高组解题报告 石家庄二中 李博杰 1.笨小猴 【问题描述】 输入一个由小写字母构成的字符串,统计出现最多与最少字母的个数,若两数之差为质数,输 出"Lucky Word"和差值;否则输出"No Answer"和 0. 【题目类型】 模拟 【建议编程时间】 10 分钟(细心一些,避免出错). 【解题分析】 1,读入字符串(文件) 2,构造一个数组,记录 a-z 各字符出现的次数.枚举字符串中每个字符,将该字符对应数组元素 加一. 3,枚举数组中 a-z,找出最大值和非零最小值,求出它们的差. 4,判断差值是否为素数,数据规模很小,可用试除法.注意 0,1 的特殊情况. 5,输出,注意大小写,换行符. 2.火柴棒等式 【问题描述】 给 n 根火柴棒,问能拼出多少种形如"A+B=C"的等式. 【题目类型】 搜索 【建议编程时间】 30 分钟.若某些问题未考虑到,调试 20 分钟. 【解题分析】 读入整数 n,减去加号和等号需要的 4 根火柴. 采用搜索方法,先递归枚举火柴拆分成每个数字对应根数(存在数组里),再枚举加号和等号的 位置,计算对应的 A,B,C,最后判断 A+B=C,统计总数. 输出 tot,注意换行. 【编程注意】 注意最高位不能为零,即除非该数为零,最高位不为零. 递归函数两个入口,表示当前剩余火柴根数,当前位数.枚举下一根火柴的数字,记录,递归(剩 余-当前火柴,位数+1). 当剩余根数为零时,枚举 A,B,C 的拆分方式. 计算 A 时,先将 A 设为首位,若首位为零且位数大于 1,则失败退出(最高位不为零)从首位+1 到 末位:A*=10, A+=a[i]. 字符串转为整数的常用方法. 注意个数为 0 时的特殊处理. 3.传纸条 【问题描述】 从 m*n 的矩阵中,只能向下,右两个方向走,找到两条互不相交的路径,使得两条路径上的权值 之和最大. 【题目类型】 双线程动态规划 【建议编程时间】

40 分钟.这里的编程时间包括调试时间. 【空间复杂度】 约 27M,全局变量完全可承受.50*50*50*50*sizeof(int)=2.5*10^7. 【解题分析】 读入矩阵,注意行列. 采用一个四维数组记录当前两条路走到的位置(i1,j1,i2,j2)时取得的最大值,初始化为 0,表示不 可能到达.(0,0,0,0)为 1,最后减 1 输出. 一个四重循环枚举两条路分别走到的位置.由于每个点均从上或左继承而来,故内部有四个 if, 分别表示两个点从上上,上左,左上,左左继承来时,加上当前两个点所取得的最大值.例 如,f[i][j][k][l] = max{f[i][j][k][l], f[i-1][j][k-1][l] + a[i][j] + a[k][l]},表示两点均从上面位置走来. 输出右下角处的最大值 f[m][n][m][n],注意换行. 【编程注意】 在数组边界处特殊处理,避免数组越界. 若待继承的点最大值为零,则停止判断,不能从这里走来. 显然,非矩阵右下角的汇合点,两个位置不能重合(否则路径相交),若重合则最大值为 0,不可达. 4.双栈排序 【问题描述】 通过两个栈 S1,S2,将一个给定的输入序列升序排列.定义 a 操作将元素压入 S1 栈,b 操作从 S1 栈中取出栈顶元素,c 操作将元素压入 S2 栈,d 操作从 S2 栈中取出栈顶元素.求字典序最小的 操作序列. 【建议编程时间】 贪心算法 40 分钟(包括调试),可得 30 分. 【解题分析】(贪心算法,30 分) 1,读入序列 2,若能进入 S1 栈,则执行 a 操作,进入 S1 栈;重复执行 b 操作,将 S1 栈中当前元素弹出,直到不 可行为止. 3,若能进入 S2 栈(c),并将 S2 中符合要求的元素弹出(d),直到不可行. 4,若两栈均无法进入,失败退出 5,输出操作序列 【判断是否能进栈】 若当前元素小于栈顶元素,则进栈,栈元素个数自增;否则不能进栈.因为栈中必须保持降序,这 样才能保证依次输出时升序. 【判断是否能出栈】 用全局变量表示当前取出的最大元素.若栈内元素个数不为零,且当前栈顶元素等于最大元素 +1(因为元素是 1-n 依次取出的),则取出该元素,最大元素自增,栈元素个数自减. 【正确解题分析】(转载,感谢提供解题方法的大牛) 这道题大概可以归结为如下题意: 有两个队列和两个栈,分别命名为队列 1(q1),队列 2(q2),栈 1(s1)和栈 2(s2).最初的时候,q2,s1 和 s2 都为空,而 q1 中有 n 个数(n<=1000),为 1~n 的某个排列. 现在支持如下四种操作: a 操作,将 q1 的首元素提取出并加入 s1 的栈顶. b 操作,将 s1 的栈顶元素弹出并加入 q1 的队列尾. c 操作,将 q1 的首元素提取出并加入 s2 的栈顶. d 操作,将 s2 的栈顶元素弹出并加入 q1 的队列尾.

请判断,是否可以经过一系列操作之后,使得 q2 中依次存储着 1,2,3,…,n.如果可以,求出字典序 最小的一个操作序列. 这道题的错误做法很多,错误做法却能得满分的也很多,这里就不多说了.直接切入正题,就是 即将介绍的这个基于二分图的算法. 注意到并没有说基于二分图匹配,因为这个算法和二分图匹配无关.这个算法只是用到了给一 个图着色成二分图. 第一步需要解决的问题是,判断是否有解. 考虑对于任意两个数 q1[i]和 q1[j]来说,它们不能压入同一个栈中的充要条件是什么(注意没 有必要使它们同时存在于同一个栈中,只是压入了同一个栈).实际上,这个条件 p 是:存在一个 k,使得 i<J<K 且 Q1[K]<Q1[I]Q1[I],这显然是不正确的. 接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件 p.这里 我们来证明它的逆否命题,也就是"如果不满足条件 p,那么这两个数一定可以压入同一个栈." 不满足条件 p 有两种情况:一种是对于任意 i<J<K 且 Q1[I]Q1[I];另一种是对于任意 IQ1[J]. 第一种情况下,很显然,在 q1[k]被压入栈的时候,q1[i]已经被弹出栈.那么,q1[k]不会对 q1[j]产生 任何影响(这里可能有点乱,因为看起来,当 q1[j]<Q1[K]的时候,是会有影响的,但实际上,这还需 要另一个数 R,满足 J<K<R 且 Q1[R]<Q1[J]<Q1[K],也就是证明充分性的时候所说的情况…而事实 上我们现在并不考虑这个 R,所以说 Q1[K]对 Q1[J]没有影响). 第二种情况下,我们可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈. 这样,原命题的逆否命题得证,所以原命题得证. 此时,条件 p 为 q1[i]和 q1[j]不能压入同一个栈的充要条件也得证. 这样,我们对所有的数对(i,j)满足 1<=i<J<=N,检查是否存在 I<J<K 满足 P1[K]<P1[I] 二分图的两部分看作两个栈,因为二分图的同一部分内不会出现任何连边,也就相当于不能压 入同一个栈的所有结点都分到了两个栈中. 此时我们只考虑检查是否有解,所以只要 O(n)检查出这个图是不是二分图,就可以得知是否有 解. 此时,检查有解的问题已经解决.接下来的问题是,如何找到字典序最小的解. 实际上,可以发现,如果把二分图染成 1 和 2 两种颜色,那么结点染色为 1 对应当前结点被压入 s1,为 2 对应被压入 s2.为了字典序尽量小,我们希望让编号小的结点优先压入 s1. 又发现二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编 号最小的结点,将它染色为 1 并从它开始 DFS 染色,直到所有结点都被染色为止.这样,我们就得 到了每个结点应该压入哪个栈中.接下来要做的,只不过是模拟之后输出序列啦~ 还有一点小问题,就是如果对于数对(i,j),都去枚举检查是否存在 k 使得 p1[k]<P1[I]<P1[J]的话, 那么复杂度就升到了 O(N^3).解决方法就是,首先预处理出数组 B,B[I]表示从 P1[I]到 P1[N]中的 最小值.接下来,只需要枚举所有数对(I,J),检查 B[J+1]是否小于 P1[I]且 P1[I]是否小于 P1[J]就可 以了. 附代码(除去注释不到 100 行),带注释.代码中的 a 数组对应文中的队列 p1. 已经过掉所有标准数据,以及 5 7 2 4 1 6 3 这组让很多贪心程序挂掉的数据~ #include using namespace std; const int nn = 1002, mm = nn * 2, inf = 1000000000; int n, tot, now; int a[nn], b[nn], head[nn], color[nn];

int adj[mm], next[mm]; int stack[3][nn]; bool result; void addEdge(int x, int y) //加边 { ++ tot; adj[tot] = y; next[tot] = head[x]; head[x] = tot; } bool dfs(int i) //DFS 染色,检查图是否是二分图的经典算法 { int temp = head[i]; while (temp) //邻接表,检查每一条边 { if (! color[adj[temp]]) //如果与当前结点的结点还未染色 { color[adj[temp]] = 3 - color[i]; //进行染色 dfs(adj[temp]); //DFS } if (color[adj[temp]] == color[i]) return false; //如果两个相邻结点染色相同,说明此图不是二分图,返回无解 temp = next[temp]; } return true; } int main() { freopen("twostack.in", "r", stdin); freopen("twostack.out", "w", stdout); //输入 scanf("%d", &n); for (int i = 1; i = 1; -- i) b[i] = min(b[i + 1], a[i]); //"min" in STL //枚举数对(i,j)并加边 tot = 0; for (int i = 1; i <= n; ++ i) for (int j = i + 1; j <= n; ++ j) if (b[j + 1] < a[i] && a[i] < a[j]) {

addEdge(i, j); addEdge(j, i); } //DFS 染色 memset(color, 0, sizeof(color)); result = true; for (int i = 1; i <= n; ++ i) //每次找当前未染色的编号最小的结点,并染颜色 1 if (! color[i]) //当前位置尚未被染色 { color[i] = 1; if (! dfs(i)) //染色时出现矛盾,此时图不是一个二分图,即无法分配到两个栈中 { result = false; //记录无解 break; } } if (! result) //无解 printf("0"); else //有解 { //模拟求解 now = 1; for (int i = 1; i <= n; ++ i) { //将当前数字压入对应的栈 if (color[i] == 1) printf("a "); else printf("c "); stack[color[i]][0] ++; stack[color[i]][stack[color[i]][0]] = a[i]; //this will work even if stack[1][0] = 0 //循环检查,如果可以的话就从栈顶弹出元素 while (stack[1][stack[1][0]] == now || stack[2][stack[2][0]] == now) { if (stack[1][stack[1][0]] == now) { printf("b "); stack[1][0] --; } else if (stack[2][stack[2][0]] == now) {

printf("d "); stack[2][0] --; } now ++; } } } 第四题上述程序转载自 www.oibh.org. 结语 以上四道题全部做完,需要约 140 分钟,距离三小时的时限还有 40 分钟,可以编一些特殊的,极 端的数据对程序进行测试. 这个阶段要做好源代码备份,除非发现重大问题,不要修改程序源代码,尤其在离终场 10 分钟 以内时,因为此时头脑紧张,极易改错. 这样下来,330 分不是大问题,在河北省就进入省队了.但是,很多平时成绩不错的大牛考试时 粗心大意,丢分现象十分严重.这次考试的题目很水,更考察选手的细心认真程度.真正的高手 不仅会做难题,水题也能保证不出错.只有不出错,才能省队,因为第四题竞赛时几乎没人想出 正确解法;只有保证错误不足半道,才能一等奖,因为河北省一等奖分数线是 280 分.实际上,对 于如此普及组难度的水题,即使实力一般,也可能拿到不错的成绩. 希望 NOIP2008 成功的同学总结经验,再接再厉,创造更好的成绩;NOIP 失利的同学不要气馁, 总结教训,认真细致,下次再争取.

NOIP2008 复赛提高组第四题 twostack 解题报告(2008-11-16 15:19:06) 标签: noip2008 复赛 提高组 普及组 twostack 第分类:编程经验 四题 noip 复测数据 能 AC 的题解: #include <string> #include <fstream> using namespace std; ifstream fin ("twostack.in"); ofstream fout ("twostack.out"); string ways[1000],*pw=ways; int n; int queue[1001]; int stack1[500][1001],stack2[500][1001]; int *p1[500],*p2[500]; bool cmp(string a,string b) { int len=(a.length()<b.length())?a.length():b.length(); for (int i=0;i<len;i++) if (a[i]!=b[i]) return a[i]<b[i];

return a.length()<b.length(); } void qsort(string *low,string *high) { string *i=low,*j=high; string mid=*(low+(high-low)/2); while (i<=j) { while (cmp(*i,mid)) i++; while (cmp(mid,*j)) j--; if (i<=j) { string tmp=*i;*i=*j;*j=tmp; i++;j--; } } if (i<high) qsort(i,high); if (j>low) qsort(low,j); } bool isMin(int num,int *begin,int *end) { for (;begin<=end;begin++) if(*begin<num) return false; return true; } void run(int iP1,int iP2,int i,string way) { p1[iP1]=stack1[iP1]; p2[iP2]=stack2[iP2]; int *p=stack1[iP1-1]; for (;p<p1[iP1-1];p++) *(p1[iP1]++)=*p; p=stack2[iP2-1]; for (;p<p2[iP2-1];p++) *(p2[iP2]++)=*p; while (i<n) { if (p1[iP1]==stack1[iP1]) { //stack1[iP1]为空

*(p1[iP1]++)=queue[i++]; //操作 a way+=" a"; continue; }else if (*(p1[iP1]-1)>queue[i]) //stack1[iP1]栈顶元素大于当前元素 { if (p2[iP2]!=stack2[iP2] && *(p2[iP2]-1)>queue[i] && *(p1[iP1]-1)>*(p2[iP2]-1) && !isMin(queue[i],&queue[i+1],&queue[n-1])) //如果能压 stack2[iP2]则 DFS 这个看完数 据才想到 ,失策 。

{ *(p2[iP2]++)=queue[i]; run(iP1+1,iP2+1,i+1,way+" c"); p2[iP2]--; } *(p1[iP1]++)=queue[i++]; way+=" a"; continue; //操作 a

}else if (isMin(*(p1[iP1]-1),&queue[i+1],&queue[n-1])) //判断 stack1[iP1]栈顶元素是否 在剩余元素中最小 { if (p2[iP2]==stack2[iP2]) //stack2[iP2]为空 我就是漏了这个 ToT { p1[iP1]--; way+=" b"; continue; 素 }else if (*(p2[iP2]-1)>*(p1[iP1]-1)) //或 stack1[iP1]栈顶元素小于 stack2[iP2]栈顶元 这个我也漏了 ToT { p1[iP1]--; way+=" b"; continue; } } if (p2[iP2]==stack2[iP2]) //stack2[iP2]为空 { *(p2[iP2]++)=queue[i++]; //操作 c way+=" c"; continue; }else if (*(p2[iP2]-1)>queue[i]) //stack2[iP2]栈顶元素大于当前元素 { *(p2[iP2]++)=queue[i++]; way+=" c"; continue; //操作 c

}else if (isMin(*(p2[iP2]-1),&queue[i+1],&queue[n-1])) //判断 stack2[iP2]栈顶元素是否 在剩余元素中最小 { //如果 stack1[iP1]为空就不可能执行到这里 if (*(p1[iP1]-1)>*(p2[iP2]-1)) //stack2[iP2]栈顶元素小于 stack1[iP1]栈顶元素 这 个我也漏了 ToT { p2[iP2]--; way+=" d"; continue; }

} return; } while (p1[iP1]!=stack1[iP1] || p2[iP2]!=stack2[iP2]) //出栈 { if (p1[iP1]==stack1[iP1]) { way+=" d"; p2[iP2]--; }else if (p2[iP2]==stack2[iP2]) { way+=" b"; p1[iP1]--; }else if(*(p1[iP1]-1)<*(p2[iP2]-1)) { way+=" b"; p1[iP1]--; }else{ way+=" d"; p2[iP2]--; } } *(pw++)=way; } int main(int argc, char *argv[]) { int iP1=0,iP2=0; p1[0]=stack1[0]; p2[0]=stack2[0]; string way; fin >>n; for (int i=0;i<n;i++) fin >>queue[i]; *(p1[0]++)=queue[0]; way="a"; int i=1; run(1,1,i,way); if (pw==ways) { fout <<0 <<endl; return 0; } qsort(ways,pw-1); fout <<ways[0] <<' ' <<endl; return 0;

}

NOIP2008 提高组解题报告
angwuy

1 word
这道题完全是送分题,只需要直接统计,再判断素数。 参考程序: var st:string; max,min,i:longint; a:array['a'..'z']of longint; ch:char; function fun(n:longint):boolean; var i:longint; begin if n<2 then begin fun:=false;exit;end; for i:=2 to n-1 do if n mod i=0 then begin fun:=false;exit;end; fun:=true; end; begin assign(input,'word.in'); reset(input); assign(output,'word.out'); rewrite(output); readln(st); fillchar(a,sizeof(a),0); for i:=1 to length(st) do inc(a[st[i]]); max:=0; min:=101; for ch:='a' to 'z' do if a[ch]>0 then begin if a[ch]>max then max:=a[ch]; if a[ch]<min then min:=a[ch];

end; if fun(max-min) then begin writeln('Lucky Word'); writeln(max-min); end else begin writeln('No Answer'); writeln(0); end; close(input); close(Output); end.

2 matches
搜索题,由于输入的情况只有 25 种,所以打表也是一种可行的方法。在数据最 大时, 经过人工和电脑证明是不会到达四位数的, 所以可以直接用 O(1000*1000) 的搜索算法 参考程序: const mat:array[0..9]of longint=(6,2,5,5,4,5,6,3,7,6); function fun(m:longint):longint; var t:longint; begin t:=0; while m>0 do begin inc(t,mat[m mod 10]); m:=m div 10; end; fun:=t; end; var a:array[0..1000] of longint; n,i,j,ans:longint; begin assign(input,'matches.in'); reset(input); assign(output,'matches.out'); rewrite(output); readln(n); if n<10 then begin writeln(0);close(output);exit;end; a[0]:=6;

for i:=1 to 1000 do a[i]:=fun(i); dec(n,4); for i:=0 to 1000 do if a[i]<n then begin for j:=0 to 1000-i do if a[i]+a[j]+a[i+j]=n then inc(ans); end; writeln(ans); close(input); close(output); end.

3 message
DP 题,两条路线必定一上一下,而且,当到达某一列后,前面对后面的不会有 影响,符合动态规划的无后效性,方程如下: 用 dp[I,j,k]表示当到达 I 列时,上路线在 j 行到,下路线在 k 行到的最大值。 另外加一个预处理,sum[I,j1,j2]表示在第 I 列 j1 到 j2 行的数加起来的和。 边界条件: dp[2,1,k]:=sum[1,1,k]; 递推方程: dp[I,j,k]:=max(dp[I-1,j2,k2]+sum[I-1,j,j2]+sum[I-1,k,k2]) {j<=j2<k<=k2} 答案: max(dp[m,j,n]+sum[m,j,n]) 参考程序: const maxn=10; var a:array[1..maxn,1..maxn]of longint; dp,sum:array[1..maxn,1..maxn,1..maxn]of longint; n,m,i,j,k,i1,i2,j1,j2,k1,k2:longint; function max(a,b:longint):longint; begin if a>b then max:=a else max:=b; end; begin assign(input,'message.in'); reset(input); assign(output,'message.out'); rewrite(output); readln(m,n); for i:=1 to m do begin

for j:=1 to n do read(a[i,j]); readln; end; for i:=1 to m do begin for i1:=1 to n do begin sum[i,i1,i1]:=a[i,i1]; for i2:=i1+1 to n do sum[i,i1,i2]:=sum[i,i1,i2-1]+a[i,i2]; end; end; fillchar(dp,sizeof(dp),255); for i:=2 to n do dp[2,1,i]:=sum[1,1,i]; for i:=2 to m-1 do for j:=1 to n-1 do for k:=j+1 to n do if dp[i,j,k]>-1 then begin for j2:=j to k-1 do for k2:=k to n do dp[i+1,j2,k2]:=max(dp[i+1,j2,k2],dp[i,j,k]+sum[i,j,j2]+sum[i,k,k2]); end; k:=0; for i:=1 to n-1 do k:=max(k,dp[m,i,n]+sum[m,i,n]); writeln(k); close(input); close(output); end. 第四题的解题报告都有很多大牛写了,那我就不在这里献丑了 好象是用二分图来做的,在 OIBH 上有详细的题解


相关文章:
NOIP2008普及组 复赛解题报告
NOIP2008 普及组 解题报告 [日期:2008-11-17] 来源: 作者:张恩权 [字体:大中小] NOIP2008 解题报告 张恩权 一、ISBN 号码 基础字符串处理题,心细一点的...
更多相关标签: