NOIP2008提高组复赛 解题思路

1、字符串中统计字母出现次数 最大减最小的 然后判断质数 字符串长度<=100
2、给出n<=24个火柴棍，求最多能摆出多少a+b=c形式的等式。数字的摆法和计算器相同，a,b,c>=0
3、双进程方格取数：m*n的棋盘，m,n<=50，不需使用高精度
4、给出1..n的排列，两个栈S1、S2，入栈出栈共4个操作：（n<=1000）
    A：输入队列头入S1
    B：弹出S1栈顶元素，进入输出队列
    C：输入队列头入S2
    D：弹出S2栈顶元素，进入输出队列
    要求将1..n的排列排序，采用字典序最小的操作方法


个人感觉是，单就难度来看，奥赛历史最简单，由于类似2，3题的模型大多数能拿一等的同学们都见过。

我的想法：
1、水，最多40分钟搞定
2、如果是考试的话，10000*10000的枚举，差不多写程序+跑+打表=10+3+2min就够了吧（不过我用的是骗

分手段，一个一个手算。然后IF-THEN,IF-THEN，最后15分钟搞定）。
3、经典题目，斜向划分阶段。35分钟搞定（前三个题目1小时思路+编程+检查够了）

4、本届唯一挑战性题目。考虑到要求字典序最小，那么按照ABCD的顺序贪心即可。
对于当前的状态，设该进入到输出序列中的是p，输入队列头是q，S1栈顶是t1，S2栈顶是t2，那么依次判

断，容易知道q>=p
i)如果q<t1或者t1不存在，执行A，continue;
ii)如果t1=p，执行B，continue;
iii)如果q<t2或者t2不存在，执行C，continue;
iv)如果q=t2，执行D，continue;
v)输出无解信息，halt;

这个算法应该是错误的。 一个反例是：7 2 5 1 4 6 3。
在上述四个判断条件中，能够产生冲突的只有i和iii，在i和iii冲突的时候需要判断。
所以我对上述算法进行修改：
i)如果((q<t1或者t1不存在)and(输入队列中不存在x，使得q<t2<x<t1)) ，执行A，continue;
ii)如果t1=p，执行B，continue;
iii)如果q<t2或者t2不存在，执行C，continue;
iv)如果q=t2，执行D，continue;
v)输出无解信息，halt;

归纳法证明算法正确性：
当n很小的时候（至少我没举出反例）算法是正确的。
设n<k成立，考虑n=k的情况。
当q=k时，显然(不存在x，使得q<t2<x<t1)，也没有q<t1或者q<t2的情况，所以k能够入栈的充要条件是t1

不存在或者t2不存在。
只要最大的数k放在了栈底，对其他的数都是没有影响的。所以算法依然正确。

证毕。（表述的很不规范。）