noip 2008题解

笨小猴

原题

笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！
这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。

输入输出样例

输入样例#1：

error

输出样例#1：

Lucky Word
2

输入样例#2：

olympic

输出样例#2：

No Answer
0

思路

简单的暴力
简单的判断质数

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
char a[150];
int num[50],maxx=-11,minx=147258963;
int check(int x){
    int flag=0;
    if(x==0||x==1) return 1;
    if(x==2) return 0;
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0){
            flag=1;
            break;
        }
    }
    return flag;
}
int main(){
    for(int i=1;i<=100;i++){
        num[i]=0;
    }
    scanf("%s",a);
    int len=strlen(a);
    for(int i=0;i<len;i++){
        num[a[i]-'a']++;
    }
    for(int i=0;i<=50;i++){
        maxx=max(maxx,num[i]);
        if(num[i]>0) {
            minx=min(minx,num[i]);
        }
    }
    if(check(maxx-minx)) printf("No Answer\n0");
    else printf("Lucky Word\n%d",maxx-minx);
    return 0;
}

火柴棒等式

原题

给你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根火柴棍必须全部用上

输入输出格式

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

输入输出样例

样例输入1：

14

样例输出1：

2

样例输入2：

18

样例输出2：

9

思路

先用数组记下，0~9每一个数所用的火柴棒数，
然后向后所算出每一个所需的数所用的火柴棒数
那么？
到底要算到多少呢？
1是需要火柴棒数最少的

假设现在有1111+0=1111;
一共就用了8+2+6+2+8=26 根火柴棒，
显然 对于其他所有的和大于1111的情况。
所用的棒数都一定大于20。

所以
算到1111，就足以满足需求了
对于一个数的棒数要多少，具体见代码

代码

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 2400
#define INF 1000007
using namespace std;
int n,a[N];
int num[]={6,2,5,5,4,5,6,3,7,6};
int main(){
    cin >> n;
    n-=4;
    int ans=0;
    for(int i=0;i<10;i++) a[i]=num[i];

    for(int i=10;i<N;i++)
    {
        int tmp=i;
        while(tmp)
        {
            a[i]+=a[tmp%10];
            tmp/=10;
        }
    }

    for (int i=0;i<N/2;i++)
        for (int j=0;j<N/2;j++)
    {
        int k=i+j;
        if (a[i]+a[j]+a[k]==n) {ans++;}
    }

    cout<<ans;
    return 0;
}

传纸条

原题

小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个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共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

输入输出样例

输入样例#1：

3 3
0 3 9
2 8 5
5 7 0

输出样例#1：

34

代码

#include<cstdio>
#include<iostream>
using namespace std;

int dp[55][55][55][55];
int n, m;
int map[55][55];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &map[i][j]);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            for(int k = 1; k <= n; k++) {
                int l;
                if(i + j - k > 0)l = i + j - k;
                else continue;
                dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+map[i][j]+map[k][l];
                if(i == k && j == l)dp[i][j][k][l] -= map[i][j];
            }
        }
    }
    printf("%d\n",dp[n][m][n][m]);
    return 0;
}

双栈排序

题目描述

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】

4
1 3 2 4

【输入样例2】

4
2 3 4 1

【输入样例3】

3
2 3 1

【输出样例1】

a b a a b b a b

【输出样例2】

0

【输出样例3】

a c a b b d

说明

30%的数据满足： n<=10
50%的数据满足： n<=50
100%的数据满足： n<=1000

思路

1. Introduction
   双栈排序，顾名思义，就是利用两个栈，对一串数字进行排序。但是，这种排序方式与其他排序方式有一定的差别，它并不能满足所有数串的排序。因此，对于能进行双栈排序的数串，我们称之为“可双栈排序序列”，反之，称之为“不可双栈排序序列”。
   读者可以先根据“a b a a b b a b”自行尝试一下1 3 2 4的双栈排序，了解它的大致过程。
   

   双栈排序
   对于本题，我采用的方法是二分图染色法。那么什么是二分图？什么是染色法？怎么构造二分图？怎么染色？这是完成这道题之前必须回答的问题，同时也是网上教程欠缺的重要内容。

2. Bipartite graph(二分图)
   二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
   对于学过离散数学的同学，就很容易理解上面这段定义了。 G=(V, E)，其中G代表图，V代表这个图的所有顶点的集合，E代表这个图所有连线的集合，即是边集。现如今如果能将V这个顶点集分成两个互不相交的子集A、B，E这个边集内所有边的两个顶点分别属于A、B两个子集的话，我们就称这个图为二分图。
   没有学过的同学看一下下面的这张图，再参照上面的定义，应该也能了解得差不多吧。
   

   二分图
   了解了二分图是什么东西后，接下来我们需要了解染色这一概念。
   什么是染色？就是给对象标记一种“颜色”(这里的颜色其实可以用数字定义)，其主要作用是便于分类、记，而不是实现真正意义上的染色。 故我们可以创建一个数组，每个数组的下标对应一个元素，数组的每个元素的值代表该对象标记的颜色。如此，就完成了染色这一步骤。
   而且，染色还可以用于判别一个图是否是二分图。下文会提到。
   在数据结构中，我们可以通过建立二维数组(布尔矩阵) picture[MAX][MAX]来实现二分图。二维数组的横向index代表A顶点子集，纵向index代表B顶点子集(当然也可以倒过来)。如若两个顶点i, j有连接，则在对应的picture[i][j] 与 picture[j][i]处赋值为1或true。
   虽然二维数组可以代表图，但并不代表每一个二维数组都是二分图。那么如何检验呢？那就要通过深度优先搜索dfs进行染色验证了。
   对于深度优先搜索，我只提供相关链接，就不详细阐述了：Depth-first_search 如果上面链接看完后还是不懂，可以自行查书或者百度相关博客进行学习。
   二分图的条件：通过深度优先搜索对每个顶点进行染色，如果相邻顶点颜色相同或者是同一顶点出现染不同颜色的情况，则说明该图不是二分图。

3. Solution
   （注：引用部分来自博文sicily双栈排序）
   双栈排序的方法便是二分图染色法。即对数字串进行两个两个逐次遍历，如果符合规则A的便将二者连接起来，则当遍历结束后完成构图。然后通过dfs染色，确立真正的二分图。然后借助染色表(记录每个元素颜色的数组)，进行相应的push(), pop()操作，最终便能完成排序。
   而这一规则A便是：

考虑对于任意两个数q[i]
和q[j],它们不能压入同一个栈中的充要条件: 存在一个k,使得i<j<k
且q[k]<q[i]<q[j]。

其证明过程如下：
定理：考虑对于任意两个数q[i]和q[j],它们不能压入同一个栈中的充要条件: 存在一个k,使得i<j<k且q[k]<q[i]<q[j]。

证明：

充分性：即如果满足上述条件，那么q[i]和q[j]一定不能压入同一个> 栈。
证明(反证法)假设这两个数压入了同一个栈,那么压入q[k]，因为q[k]比q[i]和q[j]都小，所以很显然,当q[k]没有被弹出的时候，另两个数也都不能被弹出(否则输出序列的数字顺序就不是1,2,3,…,n了)。而之后,无论其它的数字在什么时候被弹出,q[j]总是会在q[i]之前弹出，而q[j]>q[i],这显然是不正确的.
必要性：如果两个数不可以压入同一个栈，那么它们一定满足上述条件。
证明逆否命题：也就是”如果不满足上述条件，那么这两个数一定可以压入同一个栈。”不满足上述条件有两种情况： 情况1：对于任意i<j<k且q[i]<q[j]，q[k]>q[i]；（即对任意三个数，最小的总是在最前面）
情况2：对于任意i<j，q[i]>q[j]。
第一种情况：在q[k]被压入栈的时候，q[i]已经被弹出栈。那么,q[k]不会对q[j]产生任何影响(这里可能有点乱，因为看起来,q[j]<q[k]
的时候是会有影响的，但实际上，这还需要另一个数r，满足j<k<r
且 q[r]<q[j]<q[k]
,也就是证明充分性的时候所说的情况。而事实上我们现在并不考虑这个r，所以说q[k]对q[j]没有影响)。
第二种情况：可以发现这其实就是一个降序序列，所以所有数字都可以压入同一个栈。这样，原命题的逆否命题得证，所以原命题得证。

解题步骤

1. 检查数列中的数字是否满足进入同一个栈的条件，如果不满足则将边连上，构造二分图。
2. 用dfs染色，把二分图染成1和2两种颜色，使得染色为1的结点被压入s1栈，染色为2结点被压入s2栈。具体：每次选取一个未染色的编号最小的结点，将它染色为1，并从它开始dfs染色，直到所有结点都被染色为止。这样，我们就得到了每个结点应该压入哪个栈中。注意dfs结束之后未被染色的数字是可以被放入同一个栈的，所以优先染色为1。如果发现某一个数字两次要染不同的颜色，则为不能输出。

代码

# include <iostream>
# include <stack>
# define MAX 1003
using namespace std;

bool picture[MAX][MAX];   //二分图
int color[MAX];  // 颜色
int temp[MAX];  //存要排序的物品
int small[MAX];  //判断是否满足规则
int num; 
bool flag; // 是否用两个栈来排序

/* 用dfs染色 */
void set_color(int i, int c) {
    color[i] = c;
    for (int j = 0; j < num; j++) {
        if (picture[i][j]) {  // 找相邻的点
            if (color[j] == c) {    // 相邻点有相同颜色则不满足条件
                flag = false;
            }
            if (!color[j]) {  // if the point has never be drawn, set the color of it
                set_color(j, 3-c);  // 3-c only have two result: 1, 2, represent stack1 and stack2
            }
        }
    }
}
/* 根据规则建图*/
void Creat_Picture() {
    small[num] = 0x7FFFFFFF;  // INT_MAX, you can set the number that bigger than the elements you put
    for (int i = num-1; i >= 0; i--) {
        small[i] = temp[i];
        if (small[i+1] < small[i]) {   // create the array for the rule
            small[i] = small[i+1];
        }
    }
    for (int i = 0; i < num-1; i++) {
        for (int j = i+1; j < num; j++) {
            if (temp[i] < temp[j] && small[j+1] < temp[i]) {
                picture[i][j] = picture[j][i] = 1;    // create the gragh according to the rule
            }
        }
    }
    for (int i = 0; i < num; i++) {
        if (!color[i]) {       // 如果还未染色就默认作为1，（要保证字典序最小）
            set_color(i, 1);
        }
    }
}

void Calculate() {
    if (flag == false) {
        cout << "0" << endl;
        return;
    }
    stack<int> stack1;  // 存颜色为1的
    stack<int> stack2; //存颜色为2的
    int count = 0; // Use for judging whether we should add the space用来判断是否要加入
    int aim = 1; // Use for judging whether we should pop the element
    for (int i = 0; i < num; i++) {
        if (color[i] == 1) {
            stack1.push(temp[i]);
            count++;
            cout << "a";
            if (count < num*2) {
                cout << " ";
            }
        } else {
            stack2.push(temp[i]);
            count++;
            cout << "c";
            if (count < num*2) {
                cout << " ";
            }
        }
        // while-loop is important, we should pop the element after we push the element
        while ((!stack1.empty() && stack1.top() == aim) ||
               (!stack2.empty() && stack2.top() == aim)) {
            if (!stack1.empty() && stack1.top() == aim) {
                stack1.pop();
                count++;
                aim++;
                cout << "b";
                if (count < num*2) {
                    cout << " ";
                }
            } else {
                stack2.pop();
                count++;
                aim++;
                cout << "d";
                if (count < num*2) {
                    cout << " ";
                }
            }
        }
    }
    cout << endl;
}

int main(void) {
    while(cin >> num) {
        flag = true;
        for (int i = 0; i < MAX; i++) {
            color[i] = 0;
            temp[i] = 0;
            small[i] = 0;
            for (int j = 0; j < MAX; j++) {
                picture[i][j] = 0;
            }
        }
        for (int i = 0; i < num; i++) {
            cin >> temp[i];
        }
        Creat_Picture();
        Calculate();
    }
    return 0;
}