NOIP2008

笨小猴 (word.pas/c/cpp) 【问题描述】 笨小猴的词汇量很小，所以每次做英语选择题的时候都很头痛。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！ 这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。 【输入】 输入文件word.in只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。 【输出】 输出文件word.out共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”； 第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。 【输入输出样例1】 word.in word.out error Lucky Word 2 【输入输出样例1解释】 单词error中出现最多的字母r出现了3次，出现次数最少的字母出现了1次，3-1=2，2是质数。 【输入输出样例2】 word.in word.out olympic No Answer 0 【输入输出样例2解释】 单词olympic中出现最多的字母i出现了2次，出现次数最少的字母出现了1次，2-1=1，1不是质数。 第一题 【无奈】一看到字母就想用map做了，一边读入一边统计次数，过程中更新min和max，最后判断一下就行了。 #include <iostream> #include <cstdio> #include <algorithm> #include <map> using namespace std; int main(){ freopen("word.in", "r", stdin); freopen("word.out", "w", stdout); map<char,int>mp; mp.clear(); char cc[100]; int maxx = 0, minn = 100; int idc = 0; while(scanf("%c", &cc[++idc]) != '\n'){ if(cc[idc] == '\n') break; mp[cc[idc]]++; } for(int i=1; i<idc; i++){ int sum = mp[cc[i]]; char cmax, cmin; if(sum > maxx){ maxx = sum; cmax = cc[i]; } if(sum < minn){ minn = sum; cmin = cc[i]; } } //cout << maxx << ' ' << minn << endl; int ans = maxx - minn; bool flag = false; if(ans == 0 || ans == 1){ printf("No Answer\n%d", 0); return 0; } for(int i=2; i<=(ans>>1); i++){ if(ans % i == 0) flag = true; } if(flag == true){ printf("No Answer\n%d", 0); return 0; } printf("Lucky Word\n%d", ans); return 0; } 火柴棒等式 (matches.pas/c/cpp) 【问题描述】 给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示： 注意：加号与等号各自需要两根火柴棍如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）n根火柴棍必须全部用上

【输入】 输入文件matches.in共一行，又一个整数n（n<=24）。 【输出】 输出文件matches.out共一行，表示能拼成的不同等式的数目。

【输入输出样例1】 matches.in matches.out 14 2 【输入输出样例1解释】 2个等式为0+1=1和1+0=1。

【输入输出样例2】 matches.in matches.out 18 9 【输入输出样例2解释】 9个等式为： 0+4=4 0+11=11 1+10=11 2+2=4 2+7=9 4+0=4 7+2=9 10+1=11 11+0=11 第二题 由于一开始想不到一个很巧妙的解决方案，所以自然而然就想到了暴力枚举的方法，先做一个判断，因为n<=24，经过简单的推算，加数是小于七百多的（保守一点的话就小于1111，用1111+1=1112进行判断）。于是枚举这一条无上光明的大道就为你敞开了，画风一变，直接枚举，1000*1000，跑完了事。下面的代码中，main里面隐掉的部分是真实的运行，为了追求速度，果断打表【微笑】。

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int r[10]={6,2,5,5,4,5,6,3,7,6};//为了方便计算用数组形成一个映射 int ans, n, lim; int get(int s){//计算所用火柴根数 int p = 0; if(s == 0) p = 6; while(s){ p += r[s % 10]; s /= 10; } return p; } void dfs(int n, int s, int a){//s=0->第一个加数，s=1->第二个加数，a->当前和的值 if(s == 2){ if(get(a) == n) ans++; return; } for(int i=0; i<=lim; i++){ //if(s==1&&i==a)continue; int d = get(i); if(d > n) continue; dfs(n-d, s+1, a+i);//枚举加数 } return; } int main() { //freopen("out.txt","w",stdout); freopen("matches.in","r",stdin); freopen("matches.out","w",stdout); scanf("%d",&n); /* lim = 1000; ans = 0; dfs(n-4,0,0); printf("%d\n",ans); */ if(n < 13) printf("0\n"); if(n == 13) printf("1\n"); if(n == 14) printf("2\n"); if(n == 15) printf("8\n"); if(n == 16) printf("9\n"); if(n == 17) printf("6\n"); if(n == 18) printf("9\n"); if(n == 19) printf("29\n"); if(n == 20) printf("39\n"); if(n == 21) printf("38\n"); if(n == 22) printf("65\n"); if(n == 23) printf("88\n"); if(n == 24) printf("128\n"); return 0; } 传纸条 (message.pas/c/cpp) 【问题描述】 小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行 、n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。 在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。 还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。

【输入】 输入文件message.in的第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1<=m,n<=50）。 接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。

【输出】 输出文件message.out共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

【输入输出样例】 message.in message.out 3 3 0 3 9 2 8 5 5 7 0 34

【限制】 30%的数据满足：1<=m，n<=10 100%的数据满足：1<=m，n<=50 第三题 这是一个特别明显的dp题目，问题是两条路的最优，我们没有办法用常规的方式求两次，因为如果我们分先后求这两条路的话，并没有办法解决路途不能交叉的限定。那么怎么办呢？？这里有一个很重要的思维转换，每一条路的最优并不能保证两条路的最优，但是两条路子路径的最优却一定意味着两条路的最优，其实更单一路径求最优是一个原理。只要能想到两条路一起走这种方式，问题一下子就解决了。正向走过去和反向走回来其实并没有区别。还有一点就是优化，把五维降成三维，因为每一次只能走一步，而且只有两个方向可供选择，所以说只要步数确定了，横向或纵向的距离确定了，位置也就确定了。（注意，最后输出的不是dp【m】【m】【m】而是dp【m】【m-1】【m+n-2】原因是对不能交叉的判定，如果判定的方法和起点终点不同，或许不同）。

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int m,n,mp[60][60],dp[55][55][102];//同时走两条路dp【s（步数）】【x1】【y1】【x2】【y2】 // 化成三维 dp【s】【y1】【y2】（x1=s-y1，x2=s-y2） const int INF =(1<<30); int ma(int a,int b) { return a>b?a:b; } int main() { freopen("message.in","r",stdin); freopen("message.out","w",stdout); scanf("%d%d",&m,&n); for(int i=m;i>0;i--) for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]); for(int i=1;i<=m;i++) for(int j=0;j<i;j++) for(int z=1;z<m+n-1;z++) { int xi=z-i+1,xj=z-j+1,yi=m-i+1,yj=m-j+1; if(xi<0||xj<0||xi>n||xj>n)continue; dp[i][j][z]=dp[i][j][z-1]; if(j-1>0)dp[i][j][z]=ma(dp[i][j][z],ma(dp[i-1][j-1][z-1],dp[i][j-1][z-1])); if(i-1>j)dp[i][j][z]=ma(dp[i][j][z],dp[i-1][j][z-1]); dp[i][j][z]+=mp[yi][xi]+mp[yj][xj]; } int ans=dp[m][m-1][m+n-2]; printf("%d",ans); return 0; } 双栈排序 (twostack.pas/c/cpp) 【问题描述】 Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。 操作a 如果输入序列不为空，将第一个元素压入栈S1 操作b 如果栈S1不为空，将S1栈顶元素弹出至输出序列 操作c 如果输入序列不为空，将第一个元素压入栈S2 操作d 如果栈S2不为空，将S2栈顶元素弹出至输出序列 如果一个1~n的排列P可以通过一系列操作使得输出序列为1, 2,…,(n-1), n，Tom就称P是一个“可双栈排序排列”。例如(1, 3, 2, 4)就是一个“可双栈排序序列”，而(2, 3, 4, 1)不是。下图描述了一个将(1, 3, 2, 4)排序的操作序列：a, c, c, b, a, d, d, b 当然，这样的操作序列有可能有几个，对于上例(1, 3, 2, 4)，a, c, c, b, a, d, d, b是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。 【输入】 输入文件twostack.in的第一行是一个整数n。 第二行有n个用空格隔开的正整数，构成一个1~n的排列。 【输出】 输出文件twostack.out共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。 【输入输出样例1】 twostack.in twostack.out 4 1 3 2 4 ………a b a a b b a b 【输入输出样例2】 twostack.in twostack.out 4 2 3 4 1 ……..0 【输入输出样例3】 twostack.in twostack.out 3 2 3 1 ………..a c a b b d

【限制】 30%的数据满足： n<=10 50%的数据满足： n<=50 100%的数据满足： n<=1000 第四题 最后一道是一个二分图染色问题，最容易想到的方法就是打一个模拟，应该可以过三个点，这道题最重要的一点就是要想清楚为什么纯模拟不行，下面提供一组测试数据 10 10 2 3 1 7 9 8 4 5 6 可以说明这个问题，这里提供的方法是数组模拟，当然直接用栈也完全没问题。既然直接模拟不行那么又怎么来操作呢？方法就是在模拟之前就做一个判断，哪些数是至始至终都不能放在一起的，所以就是一个二分图染色了。这个判断条件就是，后进入的数比先进入的数大，并且先进入的数无法出栈（可以结合下面的代码理解）。有了一个颜色，再去模拟就没有多大问题了。

#include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; int a[1001], f[1001], la[1001], lb[1001], co[1001], head[1001], pa, pb, n, idcc; //co[]栈编号，la[]栈1，lb[]栈二，pa，pb头指针 struct ln{ int to, nxt; ln(){ to = nxt = 0; } void adde( int a, int b ){ to = a, nxt = b; } }ed[2005]; void adde( int u, int v ){ ed[++idcc].adde(u, head[v]); head[v] = idcc; ed[++idcc].adde(v, head[u]); head[u] = idcc; } void dfs( int u, int c ){ co[u] = c; for( int i = head[u]; i; i = ed[i].nxt ){ int v = ed[i].to; if(co[v] == c){ printf("0\n"); exit(0);//退出主程序 } if(!co[v]) dfs(v, 3-c);//1,2两个栈 } } int main() { freopen("twostack.in", "r", stdin); freopen("twostack.out", "w", stdout); scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &a[i]); f[n + 1] = 0x3f3f3f3f; for(int i=n; i>=1; i--) //从后往前 f[i] = min(f[i+1], a[i]);//找到一个比当前数小的即可，所以只保存最小值 for(int i=1; i<n; i++) for(int j=i+1; j<=n; j++) if( a[i] < a[j] && f[j + 1] < a[i]){//i在j前且i比j小，且i不能弹出时 adde(i, j); }//i，j不能在同一个栈中 for(int i=1; i<=n; i++) if(!co[i]) dfs(i, 1); int idc = 1;//当前需要输出的值 for(int i=1; i<=n; i++){ if(co[i] == 1){ la[++pa] = a[i]; printf("a "); } else{ lb[++pb] = a[i]; printf("c "); } while(pa && la[pa] == idc || pb && lb[pb] == idc){ if(pa && la[pa] == idc){ pa--; printf("b "); } else{ pb--; printf("d "); } idc++; } } return 0; }

考试总结 一次08年noip真题练习。第一道题比较简单，做法也很多，这一次我是用map做的，因为本身对STL不太熟悉，所以就想尝试一下。还好，没有爆掉。第二题因为数据规模很小，所以可以直接枚举，1000*1000就ok了。不幸的是当时在推算范围的时候不准确，导致不敢放开手用暴力。明明10min完全可以解决的问题，又冥思苦想了好久，用一个特别麻烦的办法优化，最后还爆零了！所以说还是应该在题目的分析上多下点功夫，避免这种费力不讨好的事情发生。更精细化的思考问题，验证方法，确认无误之后再动键盘就可以行云流水一气呵成了。第三题是一个dp的题目，考试的时候思想没有转过来，还总是想着要怎么样实现才能让他去了之后再回来，其实两条路一起走一下子就解决了。还有就是时空的优化，把五维降成三维，其实不一定非要一下子就想到最优的解法，可以尝试着把最好想的方法写出来，然后再通过对这个方式的模拟，寻找dp各元素之间的关系，如此一来，降次的方式就不难想到了。最后一道是二分图染色问题，我只是打了一个模拟，过了三个点，直到后来还纠结了好久，一直没有想清楚为什么纯模拟不行，最后找了组测试数据 10 10 2 3 1 7 9 8 4 5 6 才发现问题，这就说明对题目的考虑还不够周全，举反例的能力还不够。所以还应该更严谨的验证方法的正确性。