首页 > 代码库 > NOIP2008解题报告
NOIP2008解题报告
2008年的题目相对比较简单，都不是很麻烦，认真写就能写对。
第一题：
题目大意：给出一个小写单词，求出最少出现的字母的出现次数和最多出现的字母的出现次数。
解题过程：直接hash模拟就好。
第二题：
给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：
注意：
1. 加号与等号各自需要两根火柴棍
2. 如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）
3. n根火柴棍必须全部用上。n<=24
解题过程：
1.一开始看到A+B=C，想到直接枚举，但是也有可能出现1111+0=1111的情况。。因此不好确定枚举的范围。
2.于是决定用dfs两个加数，然后看剩下的火柴能否拼出和。对于任意一个数，可以在它的末尾加上0~9的数字，代价是相应需要的火柴数量，这样保证不会重复。有个小优化，不过我懒得写了，就是令第一个数不比第二个数大，搜到结果时，如果第一个数和第二个数相等，ans+1，否则ans+2。这样可以减少一半的搜索量，不过数据如此小，不写也无所谓。
第三题：
题目大意：就是方格取数的变形，变成了2个人一起走，且另外一个人走过的地方不能再走。
解题过程：
和2000年方格取数那题几乎一样。只不过00年的是走过的地方可以再走，只不过得到的分数为0，因此只要在00年那题的动态规划方程里改一下，如果i=j且没有到达终点的时候，F[k][i][j]=-inf. F[k][i][j]表示走了k步，第一个人向下走了i步，第二个人向下走了j步的最大得分。
动态规划的部分代码：
1 for (int k=1;k<=n+m-2;k++) 2 for (int i=0;i<n;i++) 3 for (int j=0;j<n;j++) 4 { 5 if (i==j&&k!=n+m-2) 6 { 7 g[k][i][j]=-210000000; 8 continue; 9 }10 if (i!=0 && j!=0)11 g[k][i][j]=ma(g[k][i][j],g[k-1][i-1][j-1]);12 if (i!=0 && j!=k)13 g[k][i][j]=ma(g[k][i][j],g[k-1][i-1][j]);14 if (i!=k && j!=k)15 g[k][i][j]=ma(g[k][i][j],g[k-1][i][j]);16 if (i!=k && j!=0)17 g[k][i][j]=ma(g[k][i][j],g[k-1][i][j-1]);18 g[k][i][j]+=a[i+1][1+k-i]+a[j+1][1+k-j];19 }
第四题：
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希望知道其中字典序最小的操作序列是什么。
解题过程：
1.一开始手工模拟了一下，感觉可以贪心。如果当前元素比栈顶元素大，那么肯定不能放到栈顶。（有点类似汉诺塔。）贪心策略如下：能往A栈放的就尽量往A栈放，否则放B栈，如果两个都没法放，就输出无解。如果当前元素就是下一个要到输出队列的元素，那么进栈A然后出来，也就是操作’a‘+’b‘，然后用一个while把该出来的都出来。。很快写好，自己写栈也才1000b左右，但是提交只能过5个点。。考试来不及这样写也不错。。
2.正解：参考博客http://blog.csdn.net/kqzxcmh/article/details/9566813 写的非常清晰，代码也简洁易懂，短小精悍。。
首先根据栈的性质，S[i],S[j]两个元素不能进入同一个栈 <=> 存在k,满足i<j<k,使得S[k]<S[i]<S[j]. 不会证明，但绝对正确。。简单点说，就是对于入栈序列的某个元素，在它前面的且比它大的元素必须是递增的（从右往左看递增，从左往右递减。）这样好理解，但是编程时还是用存在k,满足i<j<k,使得S[k]<S[i]<S[j]. 来写。
因此只要找出所有不能在同时在同一个栈的入栈序列出现的数对（i，j），让前面的元素尽量进A栈。这实际上是一个判断二分图的过程，用染色的方法判断，如果不是二分图必然无解。如果是，模拟出栈即可。
我的代码：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 5 char ans[2014]; 6 int n,a[1010],stack1[1010],stack2[1010],top1,top2,cur; 7 int p[1010],q[1010]; 8 int g[1010],color[1010],edge[1010][1010],flag=1; 9 10 void pop()11 {12 while (stack1[top1]==cur||stack2[top2]==cur)13 {14 if (stack1[top1]==cur)15 {16 cur++;17 top1--;18 printf("b ");19 }20 else21 {22 cur++;23 top2--;24 printf("d ");25 }26 }27 }28 29 void dfs(int x,int c)30 {31 if (!flag)32 return;33 color[x]=c;34 for (int i=1;i<=n;i++)35 if (edge[x][i])36 {37 if (color[i]==c)38 {39 flag=0;40 return;41 }42 if (!color[i])43 dfs(i,3-c);44 }45 }46 47 void solve()48 {49 g[n+1]=210000;50 for (int i=n;i>=1;i--)51 g[i]=a[i]<g[i+1]? a[i]:g[i+1];52 for (int i=1;i<n;i++)53 for (int j=i+1;j<=n;j++)54 if (a[i]<a[j]&&g[j+1]<a[i])55 edge[i][j]=edge[j][i]=1;56 for (int i=1;i<=n;i++)57 if (!color[i])58 dfs(i,1);59 if (!flag)60 {61 cout<<0<<endl;62 return;63 }64 cur=1;65 stack1[0]=stack2[0]=210000;66 for (int i=1;i<=n;i++)67 {68 if (color[i]==1)69 {70 printf("a ");71 stack1[++top1]=a[i];72 }73 else74 {75 printf("c ");76 stack2[++top2]=a[i];77 }78 pop();79 }80 pop();81 }82 83 int main()84 {85 //freopen("in.txt","r",stdin);86 //freopen("out.txt","w",stdout);87 cin >> n;88 for (int i=1;i<=n;i++)89 scanf("%d",&a[i]);90 solve();91 return 0;92 }