三个半小时五道题，CY 说考的就是心理素质…
考试策略：
做题顺序：T5->T3->T1->T2->T4
T5 是哈希水题，花 30 分钟搞定，T3 是一道搜索，花了 30 分钟，不过剪枝力度不够就挂了 QAQ，T1 考场花 1h 手打 splay（QAQ），T2 就花 40 分钟调对了那个 set（QAQ），然后放弃了 T4，花了半个小时检查。
经验和教训：
1. 考试时合理选择做的题目很重要，给每道题合理分配的时间也很重要。
2. 要好好学习 stl（QAQ）
3. 学会检查与放弃，要学会考虑特殊情况

T1

期望得分：100 实际得分：80
错误原因：未知，两个数据有问题，但是改了数据后那两个还是 TLE，或许是因为没有考虑负数。
题目描述：
Tiger 最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。
Tiger 拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：
该天的最小波动值
当最小波动值越大时，就说明营业情况越不稳定。
而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助 Tiger 来计算这一个值。
第一天的最小波动值为第一天的营业额。
数据范围：n 小于等于 32767,ai 小于等于 1000000, 答案保证 int 存的下
题目分析：
这是一道 splay 裸题。
这是一道 treap 裸题。
然而这题可以用 set 水过。
用 set 保存后二分查找即可，注意特判没有前驱和后继的情况。
然后用 s.lower_bound(x) 会比 lower_bound(s.begin(),s.end(),x) 快那么一些。
代码：
splay 版：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
#define LL long long
int n,rt,tot;LL ans;
struct node{int f,s[2];LL x;}a[32800];
int read(){
    LL q=0,w=1;char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+(LL)(ch-'0'),ch=getchar();
    return q;
}
int is(int i){return i==a[a[i].f].s[1];}
void spin(int i){//旋转操作
    int fa=a[i].f,g=a[a[i].f].f,h=is(a[i].f),me=is(i);
    a[fa].s[me]=a[i].s[!me],a[i].s[!me]=fa,a[fa].f=i;
    if(a[fa].s[me])a[a[fa].s[me]].f=fa;
    if(a[i].f=g)a[g].s[h]=i;
}
void splay(int i){//splay 操作
    while(a[i].f){
        if(!a[a[i].f].f)spin(i);
        else if(is(i)==is(a[i].f))spin(i),spin(i);
        else spin(a[i].f),spin(i);
    }
    rt=i;
}
void ins(int &i,int las,LL num){//插入操作
    if(!i){i=++tot,a[i].x=num,a[i].f=las,splay(i);return;}
    if(num<a[i].x)ins(a[i].s[0],i,num);
    else if(num>a[i].x)ins(a[i].s[1],i,num);
}
LL pre(int i,LL num){//找前驱
    if(!i)return INT_MIN;
    if(a[i].x<=num)return max(a[i].x,pre(a[i].s[1],num));
    else return pre(a[i].s[0],num);
}
LL nxt(int i,LL num){//找后继
    if(!i)return INT_MAX;
    if(a[i].x>=num)return min(a[i].x,nxt(a[i].s[0],num));
    else return nxt(a[i].s[1],num);
}
int main()
{
    freopen("turnover.in","r",stdin);
    freopen("turnover.out","w",stdout);
    int kl,i,j,t1,t2;
    n=read();
    ans=read(),ins(rt,0,ans);
    for(i=1;i<n;++i){
        kl=read();ans+=min(kl-pre(rt,kl),nxt(rt,kl)-kl);
        ins(rt,0,kl);
    }
    printf("%lld",ans);
    return 0;
}

set 版：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<set>
using namespace std;
int n,ans;
set<int>s;
set<int>::iterator pre,nxt;
int main()
{
    freopen("turnover.in","r",stdin);
    freopen("turnover.out","w",stdout);
    int i,x;
    scanf("%d",&n);
    scanf("%d",&ans);s.insert(ans);
    for(i=2;i<=n;++i){
        scanf("%d",&x);
        nxt=s.lower_bound(x);
        pre=nxt;--pre;
        if(nxt==s.begin())ans+=*nxt-x;//没有前驱
        else if(nxt==s.end())ans+=x-(*pre);//没有后继
        else ans+=min(x-(*pre),*nxt-x);
        s.insert(x);
    }
    printf("%d",ans);
    return 0;
}

T2

期望得分：100 实际得分：100
题目描述：
Great Bytelandish 的超级市场网络请你编写一个程序模拟促销商品的成本费用 (simulating costs of the promotion being prepared)。推销商品要遵守以下规则：
1. 想参与促销的顾客在自己的帐单上写下个人信息，然后将票据投入一个特制的投票箱中。
2. 促销期间，每天结束后，有 2 张票据将被取出——消费金额最大的和最小的两张账单。消费金额最大的那位顾客得到的奖品价值等于取出的 2 张账单的差额。
3. 为了避免多次得奖，所有取出的账单将不再放回箱中，其余的票继续参加促销活动。
由于商场的顾客特别多，所以每天投票箱中都至少有 2 张账单。你的任务是计算在促销期间，商家一共要送出多少前的礼品。
数据范围：
第一行是一个整数 n，1<=n<=5000，表示促销活动的持续时间。接下来有 n 行，每行有一系列的非负整数，每行的第一个数 k，0<=k<=10^5，表示这天的新增的账单数目。
其后 k 个数表示各个消费金额（不大于 10^6）。所有的投入箱中的账单数目不会超过 10^6。
题目分析：
本来也觉得是用 splay 的，结果发现要回收垃圾，然而我不会啊，于是我想了想，消费金额不大于 10^6？那不就可以用 set 水了吗？10^6 嘛，开个数组记录一下每个元素出现了多少次即可。
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<set>
using namespace std;
#define LL long long
int read(){
    LL q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+(LL)(ch-'0'),ch=getchar();
    return q;
}
int t[1000005];
set<int>s;
LL ans;int n;
set<int>::iterator kl;
int main()
{
    freopen("pro.in","r",stdin);
    freopen("pro.out","w",stdout);
    int i,j,num,x;int mi,mx;
    n=read();
    for(i=1;i<=n;++i){
        num=read();
        for(j=1;j<=num;++j)x=read(),++t[x],s.insert(x);
        kl=s.begin();mi=*kl;
        kl=s.end();--kl;mx=*kl;
        ans+=(LL)(mx-mi);
        --t[mi];if(!t[mi])s.erase(mi);
        --t[mx];if(!t[mx])s.erase(mx);
    }
    printf("%lld",ans);
    return 0;
}

T3

期望得分：30 实际得分：20
错误原因：没有想到良好的剪枝方法，所以 TLE 了。
题目描述：
某地发行一套彩票。彩票上写有 1 到 M 这 M 个自然数。彩民可以在这 M 个数中任意选取 N 个不同的数打圈。每个彩民只能买一张彩票，不同的彩民的彩票上的选择不同。
每次抽奖将抽出两个自然数 X 和 Y。如果某人拿到的彩票上，所选 N 个自然数的倒数和，恰好等于 X/Y，则他将获得一个纪念品。
已知抽奖结果 X 和 Y。现在的问题是，必须准备多少纪念品，才能保证支付所有获奖者的奖品。
数据范围：
1≤X, Y≤100，1≤N≤10，1≤M≤50。
解题思路：
搜索+剪枝
一开始写的时候也是贪心剪枝，而且是通分比较而不是用 double，可为什么 TLE 的那么惨呢？
我们来算一笔账：
$$2^{50}=1125899906842624$$
$$50^{10}=97656250000000000$$
好吧，我知道了。
比起枚举下一个选的数是什么（傻逼的我考场上打的），不如枚举每一个数选还是不选。
然后加剪枝：
1. 剩下的可以取的数里面取尽可能小的，都小于了 x/y，返回。
2. 剩下的可以取的数里面取尽可能大的，都大于了 x/y，返回。
3. 剩下的数不够取了，返回。
就可以过了。
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
#define db double
db s[55],mb,eps=1e-10;
int n,m,mx,my,ans;
void dfs(int x,int tot,double num){
    if(tot==n){
        if(num-mb>-eps&&num-mb<eps)++ans;
        return;
    }
    if(x==m+1)return;
    if(num>mb+eps)return;
    if(m-x+1<n-tot)return;//不够选了
    if(s[x+n-tot-1]-s[x-1]+num-mb<-eps)return;//最大的还小了
    if(s[m]-s[m-n+tot]+num-mb>eps)return;//最小的还大了
    dfs(x+1,tot,num),dfs(x+1,tot+1,num+1.0/x);
}
int main()
{
    freopen("money.in","r",stdin);
    freopen("money.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&mx,&my);
    mb=(double)mx/my*1.0;
    for(int i=1;i<=m;++i)s[i]=s[i-1]+1.0/i;
    dfs(1,0,0.0);
    printf("%d",ans);
    return 0;
}

T4

期望得分：10 实际得分：10
错误原因：感觉此题思维难度较高，没有时间做了，于是输出 “0”
题目描述：
CHRISTIANE 和 MATTHIAS 正在玩一个新游戏— 数字游戏，游戏规则是：CHRISTIANE 和 MATTHIAS 轮流选择大于或等于 2 的正整数，所选择的整数必须满足下列规则：
一个整数被一个玩者选择后，那么这个整数及它的倍数不能被（以后的任何玩者）选择
已被选择的任何 2 个整数或这两个整数的倍数之和不能被（以后的任何玩者）选择
为了简化题目，要求玩者所选择的整数不大于 20
第 1 个没有整数选择的玩者就是失败者，而另一个玩者就是赢家。
下面是一种玩法：MATTHIAS 首先选择 4，那么 CHRISTIANE 就不能选择 4，8，12，16，20 等整数，假设 CHRISTIANE 选择 3，那么 3，6，9，15，18 又不能选择，同时 7（=3+4），10（=2 *3+4），13（=3*3+4），19（=3*5+4），11（=3+2*4），14（=2*3+2*4），17（=3*3+2*4）等整数不能选择，那么就只留下 2 和 5 可以选择，现在 MATTHIAS 选择 2，由于 5=2+3，那么 CHRISTIANE 就没有整数可选择，从而 MATTHIAS 就是赢家。
现在他们已经玩了几轮了，给出游戏残局状态（保证合法），求必胜策略。
题目分析：
只有 20 个数… 状压如何？
对于每一个残局状态，先手只有两种情况：必胜和必败。如果对于某一种策略，可以使得后手必败，则先手必胜。如果找不到这种策略，则必败。
那么我们可以进行状压+记忆化搜索，对于选了某个数后就不可行的数，可以在 20 * 20 的时间复杂度里很快地搞出来（具体看代码）
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
int n=1;
int f[524300];
int bin[22];
int dfs(int zt){
    if(f[zt]!=0)return f[zt];
    if(!zt){f[zt]=-1;return f[zt];}
    int i,j,k,kl,t;
    for(i=2;i<=20;++i){
        if(!(zt&bin[i]))continue;
        kl=zt;kl^=bin[i];
        for(j=2;j<=20;++j)//排除已经不能选的数
            if(!(kl&bin[j])){
            for(k=j;k<=20;k+=i)
            if((kl&bin[k]))kl^=bin[k];
        }
        if(dfs(kl)<0){f[zt]=1;return 1;}//必胜
    }
    f[zt]=-1;return -1;//必败
}
int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    int x,i,j,k,zt=0,kl,t,bj=0;
    bin[2]=1;for(i=3;i<=20;++i)bin[i]=bin[i-1]<<1;
    while(scanf("%d",&x)!=EOF)zt|=bin[x];
    for(i=2;i<=20;++i){//这一段是复制粘贴 dfs 函数里的那一段的 QWQ
        if(!(zt&bin[i]))continue;
        kl=zt;kl^=bin[i];
        for(j=2;j<=20;++j)
            if(!(kl&bin[j])){
            for(k=j;k<=20;k+=i)
            if((kl&bin[k]))kl^=bin[k];
        }
        if(dfs(kl)<0){bj=1;printf("%d ",i);}
    }
    if(!bj)printf("0");
    return 0;
}

T5

期望得分：100 实际得分：100
题目描述：
MICROWIN 公司发布了新版本的操作系统——Windoors。虽然这个操作系统性能优越，运行稳定，价格低廉，简单易用，但是销售状况并不乐观。经过国际侦探秘密调查和取证，发现了一个人人都知道的问题。绝大部分用户选择了 “性价比” 更高的盗版软件……
MICROWIN 公司为了夺回该操作系统的市场，通过网络秘密调用使用者信息，搜集了几乎所有 Windoors 使用者的安装密码。操作系统在安装过程中，应由用户输入唯一的安装密码才能被安装成功并且使用。正版用户都有自己唯一的一组安装密码，而盗版用户则使用了相同的安装密码。依据这一特征，请你帮助 MICROWIN 公司找到盗版用户使用的安装密码。这样，MICROWIN 公司就可以终止所有使用这个密码的 Windoors 用户的使用权。
密码的规范：每组有效的密码是一行由二十五个字符组成的字符序列，且均由字母组成。如：I L O V E N K A C M I L O V E F R I E N D S H I P。注意：字母是大小写不敏感的，也就是说上面的密码也可以写成：I l o v e N k A c M i L o V e F r I E N d S h I p。
由于网络传输错误和其他不可预知的故障，任何不符合密码规范的字符序列均不能算做密码，并且该字符序列忽略不记。而盗版用户的密码则为出现次数最多的密码。
数据范围：1<= n <= 10000
题目分析：裸哈希。我用的 SDBM_hash
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
#define ull unsigned long long
int n;ull mod=999997;
char s[10005][30];
int h[1000000],num[10005],bh[10005],ne[10005];
ull has[10005];
int ans,mx,tot,js;
void add(int x){
    ull re=0,kl;int i,j;
    for(i=0;i<25;++i)re=(re<<16)+(re<<6)-re+s[x][i]-'a';
    kl=re%mod;if(kl<0)kl=-kl;
    for(i=h[kl];i!=-1;i=ne[i])
        if(has[i]==re&&(!strcmp(s[x],s[bh[i]]))){
            ++num[i];
            if(num[i]>mx)mx=num[i],ans=bh[i],js=1;
            else if(num[i]==mx)++js;
            return;
        }
    ++tot,num[tot]=1,bh[tot]=x,has[tot]=re;
    ne[tot]=h[kl],h[kl]=tot;
    if(num[tot]>mx)mx=num[tot],ans=bh[tot],js=1;
    else if(num[tot]==mx)++js;
}
int main()
{
    freopen("windoors.in","r",stdin);
    freopen("windoors.out","w",stdout);
    int i,j,l,bj;
    memset(h,-1,sizeof(h));
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%s",s[i]);
        l=strlen(s[i]);
        if(l!=25){--i,--n;continue;}
        bj=0;
        for(j=0;j<25;++j)
            if(s[i][j]>='A'&&s[i][j]<='Z')s[i][j]=s[i][j]+32;
            else if(s[i][j]<'a'||s[i][j]>'z'){bj=1;break;}
        if(bj){--i,--n;continue;}
        add(i);
    }
    if(js!=1)printf("no solution");
    else printf("%s",s[ans]);
    return 0;
}