NOIP2008 提高组复赛试题数据及个人题解
第一题 word
题意简述:给出一个单词,统计其中出现最多的字母出现的次数maxn,以及出现最少的字母的次数minn,如果maxn-minn是质数的话则作为一个Lucky Word..否则即为No Answer.
类型: 模拟水题....
代码:
#include <stdio.h> #include <string.h> int count[27],max,min; char s[200]; bool notprime[102]; int main() { freopen("word.in","r",stdin); freopen("word.out","w",stdout); gets(s); memset(count,0,sizeof(count)); for (int i=0;s[i];i++) count[s[i]-96]++; min = 2147483647; max = 0; for (int i=1;i<=26;i++) { if (!count[i]) continue; if (max<count[i]) max = count[i]; if (min>count[i]) min = count[i]; } int j; notprime[0] = true; notprime[1] = true; for (int i=2;i<=50;i++) { j = i*2; while (j<=100) { notprime[j] = true; j += i; } } max -= min; if (notprime[max]) { printf("No Answer\n"); max = 0; } else printf("Lucky Word\n"); printf("%d\n",max); return 0; }
第二题 matches
题意简述: 给你n(n<=24)根火柴棒,叫你拼出 "A + B = C"这样的等式,求方案数.
解题思路: 直接枚举A和B(事实证明只到3位数),事先预处理2000以内各个数所用的火柴数.直接枚举出解
代码:
#include <stdio.h> #include <string.h> int n,ans; int c[2002]={6,2,5,5,4,5,6,3,7,6}; int main() { freopen("matches.in","r",stdin); freopen("matches.out","w",stdout); scanf("%d",&n); for (int i=10;i<=1800;i++) c[i] = c[i/10]+c[i%10]; n -= 4;ans = 0; for (int i=0;i<=800;i++) for (int j=0;j<=800;j++) if (c[i]+c[j]+c[i+j]==n) ans++; printf("%d\n",ans); return 0; }
第三题 message
题意简述: 给一个矩阵(左上角和右下角固定为0),从左上角走两次到右下角,两次走的路径不能有交集(即一个点不能被走两次),求两次走过的格子上的数的和最大是多少.(类似二取方格数.)
解题思路: 二取方格数很经典的题目了,于是便直接以 f[i][j][k][p] 表示第一条路径走到(i,j),第二条路径走到(k,p)所取到的数的最大值..转移方程就很好办了..同时注意判断两条路不要从同一个点转移过来就好了.
#include <stdio.h> #include <string.h> int a[52][52],f[52][52][52][52],n,m,ni,nj,nk,np; int next[4][4]={0,-1,-1,0,-1,0,-1,0,0,-1,0,-1,-1,0,0,-1}; int main() { freopen("message.in","r",stdin); freopen("message.out","w",stdout); scanf("%d %d",&n,&m); memset(f,0,sizeof(f)); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&a[i][j]); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int k=1;k<=n;k++) for (int p=j;p<=m;p++) for (int m=0;m<=3;m++) { ni = i + next[m][0]; nj = j + next[m][1]; nk = k + next[m][2]; np = p + next[m][3]; if ((ni!=nk)||(nj!=np)) if (f[i][j][k][p] < f[ni][nj][nk][np] + a[i][j] + a[k][p]) f[i][j][k][p] = f[ni][nj][nk][np] + a[i][j] + a[k][p]; } printf("%d",f[n][m][n][m]); return 0; }
第四题 twostack
以下引用saybi的题解 http://sqybi.com/blog/archives/78
这道题大概可以归结为如下题意:
有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2).最初的时候,q2,s1和s2都为空,而q1中有n个数(n<=1000),为1~n的某个排列.
现在支持如下四种操作:
a操作,将 q1的首元素提取出并加入s1的栈顶.
b操作,将s1的栈顶元素弹出并加入q1q2的队列尾.
c操作,将 q1的首元素提取出并加入s2的栈顶.
d操作,将s2的栈顶元素弹出并加入q1q2的队列尾.
请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列.
这道题的错误做法很多,错误做法却能得满分的也很多,这里就不多说了.直接切入正题,就是即将介绍的这个基于二分图的算法.
注意到并没有说基于二分图匹配,因为这个算法和二分图匹配无关.这个算法只是用到了给一个图着色成二分图.
第一步需要解决的问题是,判断是否有解.
考虑对于任意两个数q1[i]和q1[j]来说,它们不能压入同一个栈中的充要条件是什么(注意没有必要使它们同时存在于同一个栈中,只是压入了同一个栈).实际上,这个条件p是:存在一个k,使得i<j<k且q1[k]<q1[i]<q1[j].
首先证明充分性,即如果满足条件p,那么这两个数一定不能压入同一个栈.这个结论很显然,使用反证法可证.
假设这两个数压入了同一个栈,那么在压入q1[k]的时候栈内情况如下:
…q1[i]…q1[j]…
因为q1[k]比q1[i]和q1[j]都小,所以很显然,当q1[k]没有被弹出的时候,另外两个数也都不能被弹出(否则q2中的数字顺序就不是1,2,3,…,n了).
而之后,无论其它的数字在什么时候被弹出,q1[j]总是会在q1[i]之前弹出.而q1[j]>q1[i],这显然是不正确的.
接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件p.这里我们来证明它的逆否命题,也就是"如果不满足条件p,那么这两个数一定可以压入同一个栈."
不满足条件p有两种情况:一种是对于任意i<j<k且q1[i]<q1[j],q1[k]>q1[i];另一种是对于任意i<j,q1[i]>q1[j].
第一种情况下,很显然,在q1[k]被压入栈的时候,q1[i]已经被弹出栈.那么,q1[k]不会对q1[j]产生任何影响(这里可能有点乱,因为看起来,当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]
MRain:程序是我自己写的(懒得按照格式输出了),已经过了所有标准数据.
var a,b,head,next,point,color:array[0..2001]of longint; s:array[1..2,0..1000]of longint; n,p,i,j,last:longint; procedure badend; begin writeln(0); close(output); halt; end; procedure addedge(a,b:longint); var t:longint; begin inc(p); point[p]:=b; if head[a]=0 then head[a]:=p else begin t:=head[a]; while next[t]<>0 do t:=next[t]; next[t]:=p; end; end; procedure dfs(now:longint); var t:longint; begin t:=head[now]; while t<>0 do begin if color[point[t]]=0 then begin color[point[t]]:=3-color[now]; dfs(point[t]); end; if color[point[t]]=color[now] then badend; t:=next[t]; end; end; begin assign(input,'twostack.in'); reset(input); assign(output,'twostack.out'); rewrite(output); fillchar(s,sizeof(s),0); fillchar(a,sizeof(a),0); readln(n); for i:=1 to n do read(a[i]); b[n+1]:=maxlongint;p:=0; for i:=n downto 1 do begin b[i]:=b[i+1]; if a[i]<b[i] then b[i]:=a[i]; end; for i:=1 to n do for j:=i+1 to n do if (b[j+1]<a[i])and(a[i]<a[j]) then begin addedge(i,j); addedge(j,i); end; for i:=1 to n do if color[i]=0 then begin color[i]:=1; dfs(i); end; last:=1; for i:=1 to n do begin if color[i]=1 then write('a ') else write('c '); inc(s[color[i],0]); s[color[i],s[color[i],0]]:=a[i]; while (s[1,s[1,0]]=last)or(s[2,s[2,0]]=last) do begin if s[1,s[1,0]]=last then begin write('b '); dec(s[1,0]); end; if s[2,s[2,0]]=last then begin write('d '); dec(s[2,0]); end; inc(last); end; end; close(input); close(output); end.
最后附上据说是四川省的测试数据
几种常用的字符串Hash
明天就NOIP了..
今天找到一堆常用的字符串Hash算法.贴出来分享+以后自己找也方便..
RS Hash:
function RSHash(S: string): Cardinal; var a, b: Cardinal; I: Integer; begin Result := 0; a := 63689; b := 378551; for I := 1 to Length(S) do begin Result := Result * a + Ord(S[I]); a := a * b; end; Result := Result and $7FFFFFFF; end;
JS Hash
function JSHash(S: string): Cardinal; var I: Integer; begin Result := 1315423911; for I := 1 to Length(S) do begin Result := ((Result shl 5) + Ord(S[I]) + (Result shr 2)) xor Result; end; Result := Result and $7FFFFFFF; end;
P.J.Weinberger Hash
function PJWHash(S: string): Cardinal; var OneEighth, ThreeQuarters, BitsInUnignedInt, HighBits, test: Cardinal; I: Integer; begin Result := 0; test := 0; BitsInUnignedInt := SizeOf(Cardinal) * 8; ThreeQuarters := BitsInUnignedInt * 3 div 4; OneEighth := BitsInUnignedInt div 8; HighBits := $FFFFFFFF shl (BitsInUnignedInt - OneEighth); for I := 1 to Length(S) do begin Result := (Result shl OneEighth) + Ord(S[I]); test := Result and HighBits; if test <> 0 then Result := ((Result xor (test shr ThreeQuarters)) and not HighBits); end; Result := Result and $7FFFFFFF; end;
最普遍的 ELF Hash:
function ELFHash(S: string): Cardinal; var X: Cardinal; I: Integer; begin Result := 0; X := 0; for I := 1 to Length(S) do begin Result := (Result shl 4) + Ord(S[I]); X := Result and $F0000000; if X <> 0 then begin Result := Result xor (X shr 24); Result := Result and not X; end; end; Result := Result and $7FFFFFFF; end;
简单的BKDR Hash
function BKDRHash(S: string): Cardinal; var seed: Cardinal; I: Integer; begin Result := 0; seed := 131; // 31 131 1313 13131 131313 etc.. for I := 1 to Length(S) do begin Result := Result * seed + Ord(S[I]); end; Result := Result and $7FFFFFFF; end;
SDBM Hash
function SDBMHash(S: string): Cardinal; var I: Integer; begin Result := 0; for I := 1 to Length(S) do begin Result := Ord(S[I]) + (Result shl 6) + (Result shl 16) - Result; end; Result := Result and $7FFFFFFF; end;
DJB Hash
function DJBHash(S: string): Cardinal; var I: Integer; begin Result := 5381; for I := 1 to Length(S) do begin Result := Result + (Result shl 5) + Ord(S[I]); end; Result := Result and $7FFFFFFF; end;
AP Hash:
function APHash(S: string): Cardinal; var I: Integer; begin Result := 0; for I := 1 to Length(S) do begin if (i and 1) <> 0 then Result := Result xor ((Result shl 7) xor Ord(S[I]) xor (Result shr 3)) else Result := Result xor (not (Result shl 11) xor Ord(S[I]) xor (Result shr 5)); end; Result := Result and $7FFFFFFF; end;
NOIP2008 提高组 Pascal 语言 初赛卷答案
一、单项选择题：（每题1.5分）
1. C 2. A 3. B 4. C 5. B
6. D 7. D 8. E 9. B 10. C
二、 不定项选择题 （共10题，每题1.5分，共计15分。每题正确答案的个数大于或等于1。多选或少选均不得分）。
11. ABD 12. AC 13. BC 14. B 15. ABC
16. ABD 17. BCD 18. ABC 19. ACD 20. ABCD
三、问题求解：（共2题，每题5分，共计10分）
1．7
2．3060
四、阅读程序写结果（共4题，每题8分，共计32分）
1. 23 （信心题）
2. 1,3,2 (简单递归)
3. 132/213/231/312/321/ （全排列）
4. defghijxyzabc/hfizxjaybcccc （字符串替换）
五．完善程序 (前6空，每空3分，后5空，每空2分，共28分)
（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查）
1. ① a[left]
② a[j] < value (或a[j] <= value)
③ a[i] > value （或a[i] >= value）
④ a[i] := value;
⑤ i,right,n-i+1
⑥ FindKth(left, i, n)
2.
① inc(j); (或者j := j+1;)
② a[i,j] > k
③ a[i,j] < k
④ answerx := i;
⑤ answery := j;
