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的拼法如图所示：
注意：
- 加号与等号各自需要两根火柴棍
- 如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）
- 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
思路
-
Introduction
双栈排序，顾名思义，就是利用两个栈，对一串数字进行排序。但是，这种排序方式与其他排序方式有一定的差别，它并不能满足所有数串的排序。因此，对于能进行双栈排序的数串，我们称之为“可双栈排序序列”，反之，称之为“不可双栈排序序列”。
读者可以先根据“a b a a b b a b”自行尝试一下1 3 2 4的双栈排序，了解它的大致过程。
双栈排序
对于本题，我采用的方法是二分图染色法。那么什么是二分图？什么是染色法？怎么构造二分图？怎么染色？这是完成这道题之前必须回答的问题，同时也是网上教程欠缺的重要内容。 -
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 如果上面链接看完后还是不懂，可以自行查书或者百度相关博客进行学习。
二分图的条件：通过深度优先搜索对每个顶点进行染色，如果相邻顶点颜色相同或者是同一顶点出现染不同颜色的情况，则说明该图不是二分图。 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]没有影响)。
第二种情况：可以发现这其实就是一个降序序列，所以所有数字都可以压入同一个栈。这样，原命题的逆否命题得证，所以原命题得证。
解题步骤
- 检查数列中的数字是否满足进入同一个栈的条件，如果不满足则将边连上，构造二分图。
- 用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;
}
