输入：

第 一行四个数N，M分别表示点数，边数
然后 M行，每行a和b和c表示有 一条从a到b的长度为c的有向 边。
结点编号从0到N-1

输出：

一 个数表示答案。如果WJMZBMR在最坏情况下无法到达1号点。输出-1

样例输 入

Sampe Input 1:
3 3

0 1 1

0 2 2

2 1 3
Sample Input 2：
4 5
0 2 1
0 3 1
2 3 1
2 1 1
3 1 1

样例输 出：

Sample Output 1:
5
Sample Output 2:
3

样例的 解释：

Sample 1 Explanation:
在WJMZBMR在0号结点的时候，让0->1的桥断掉，WJMZBMR就只能走0->2->1的路径了，长度为5.
Sample 2 Explanation:
WJMZBMR一开始可以往2号结点和3号结点走，但是如果WJMZBMR往3号结点走。那么如果3->1的桥被切断，WJMZBMR就无路可走悲剧了。所以WJMZBMR只能一开始往2号结点走，然后2->1被切断（注意，这就是最坏情况， 也是NZK神犇的决策），WJMZBMR就只能往2->3->1走了。总长度为3。

数据范围： 40%的数据 N<=20

100%的数据 N<=300 M<=1000 一些解释： 这个题目是为了对应NOIP2009 trade出的图论题，因为本身的模型涉及二人博弈有点绕，本来不想出的，但由于此题的算法比较好，还是出了。我已经尽量将题目写清楚了，如果还是有不理解的，可以去答疑贴问，不过最好自己先看两遍，我怕被问爆囧T_T。

 断桥残雪(snow.in/snow.out)
引子：
         断桥是否下过雪

我望着湖面

水中寒月如雪

指尖轻点融解

断桥是否下过雪

又想起你的脸

若是无缘再见

白堤柳帘垂泪好几遍

背景：

在美丽的WJMZBMR的家乡，有很多的断桥，在冬天的时候，就会出现断桥残雪的景象。WJMZBMR不禁会哼起许嵩的《断桥残雪》。
    但有时候这对交通也是一种阻碍T_T，在这里我们把位置看成节点，把连接位置之间的桥看成边。由于某些信春哥的原因，这些桥都是单向的囧。
    但是由于雪大的原因，有些桥是会突然断掉的。由于WJMZBMR是信春哥的，桥不会在WJMZBMR走过的时候断掉，只会在WJMZBMR到它前面的时候突然断掉。而且春哥告诉WJMZBMR，只有一座桥由于有一次春哥在上面跑步承受了春哥的霸气有断掉的可能。
    但春哥日理万机已经忘掉了是哪座桥了T_T。
    WJMZBMR想从他的家去春哥那里膜拜！他的家是0号结点，春哥在1号。
    WJMZBMR想知道在最坏的情况下，他最少需要多少时间能到到达春哥所在处。

数学定义：

这个是为了更加清楚的说明写的，如果您在上面已经看懂了就不用看了。如果您在上面没有看懂的话就别管上面的了。直接看数学模型吧。

这是一个二人博弈问题。假设是WJMZBMR在跟NZK神犇玩游戏。
给你一个带权有向图，每条边有一个经过的时间，有两个玩家WJMZBMR和NZK神犇在玩游戏， WJMZBMR的目标是最快的从结点0到达结点1，他可以沿着一条边走到另一条边并花去一定的时间。
NZK神犇的目标是让WJMZBMR到达结点1的时间最长，NZK神犇的能力是在一个特定的时间让一条边断掉，但只能使用一次，并且不能在WJMZBMR在一条边上的时候使用。
求两者都是最优决策的情况下，WJMZBMR到达结点1的时间。

素颜(face.in/face.out)
引子：
      如果再看你一眼

是否还会有感觉

最真实的喜怒哀乐全都埋葬在昨天

不掺任何的表演

轰轰烈烈那几年

我怀念 别怀念

怀念也回不到从前
背景：

WJMZBMR已经长大了，不由感觉物是人非，又听起了许嵩的素颜，感到很伤感，想起很久以前自己玩过的一个游戏。不由感觉“当年素面朝天要多纯洁就有多纯洁”
    这个游戏是这样的，给你一个无穷大的棋盘，上面有一些黑棋子，WJMZBMR有无穷多的黑棋子。然后WJMZBMR如果看到三个黑棋子组成了一个两边平行于坐标轴的矩形的3个顶点，而第四个顶点上没有黑棋子，那么他就会在那个顶点上放一个黑棋子。一直到没有可以放的条件为止。
    WJMZBMR想知道他能否无限放下去？如果不能，请输出棋盘上最后的棋子数量。

数学定义：

P.S 下面这段话可能比较繁琐，因为要有数学定义就写了，如果你已经看懂就忽略数学定义这一块吧T_T。。。
三个棋子(x1,y1),(x2,y2),(x3,y3)如果满足
x1,x2,x3三个数有两个是一样的，另一个不一样。
y1,y2,y3也是。
    那么他们就是可以组成一个合法的平行与坐标轴矩形的3个顶点。
    第四个顶点就可以放上一个棋子。

输入：

第一行N表示有N个黑棋子一开始就在棋盘上。
接下来N行，每行都表示一个棋子的坐标，其中X坐标在前，Y坐标在后。

输出：

一行，如果能无限放下去，输出-1
否则输出最后的棋子数（不保证范围）

样例输入：

3
0 0

0 1

1 0

样例输出： 4 数据范围： 对于40%的数据，N<=5000
对于100%的数据, N<=200000
x和y都在longint（Pascal）和int(C++)的范围

灰色头像(gray.in/gray.out)
引子：
       你灰色头像不会再跳动
       哪怕是一句简单的问候
       心贴心的交流一页页翻阅多难过
       是什么 坠落 升空
       又想起你曾说的陪我到最后
       暖色的梦变冰凉的枷锁
       如果时光倒流我们又能抓得住什么。
背景：

    WJMZBMR喜欢上QQ。。但是很多人的头像已经变成灰色了。这让他压力很大。而且WJMZBMR的好友太多了，大量的灰色头像让他无法准确的找到他想找的好友。。
    今天WJMZBMR决定清理一下他的QQ，找出那些不会在跳动的头像并且把它们踢掉。为此他翻出了最近一个月的聊天记录。
    如果一个头像在在最近一个月中与WJMZBMR聊天次数小于等于2次，WJMZBMR就会认为这是不会再跳动的灰色头像然后把他删掉。
    那么请你为WJMZBMR写个程序完成这件事情，并输出剩下的头像。

定义：

头像其实就是ID，是一个长度小于等于30的，由小写或者大写英文字母组成的字符串。

严格的数学定义：

给出一些字符串，输出其中出现次数大于等于3次的。
关于输出的顺序，出现次数多在前，如果次数一样多就按字典序从小到大，相同的ID只输出一次。

输入格式:

第一行N表示聊天记录的长度
接下来N行每行一个字符串表示与WJMZBMR聊天的ID。

输出格式:

第一行表示要输出的头像的个数M
之后M行每行一个字符串表示输出的ID(请按给定顺序输出,两个相同的ID只输出一次)

样例输入：

6
Gx
tracyhenry
seventhplus
Gx
seventhplus
Gx

样例输出:

1
Gx

数据范围：

20%的数据N<=1000
100%的数据 N<=100000

根据投票结果。。。。
时间定为10月5日晚上6点到9点半（因为很多人都要吃饭，延迟半个小时结束好了）。。
再次重申题目都在NOIP的范围内，没有任何超纲。。
由于我是手测的。所以估计要到6日早上出结果。大家晚上也不用熬夜等了T_T。。
提交请发送至邮箱WJMZBMR@gmail.com
最好能只提交一次，否则我会分不清楚的囧。。不过多次也不要紧。。
题目会给大家惊喜的嘿嘿。。。。
题目会同时放到网盘上和。。这个百度空间上。。
关于提交格式的。
请大家用自己的ID给自己的压缩包起名字。
同时题目的输入输出文件是xxx.in/xxx.out的话，源程序就是xxx.cpp/xxx.pas
那么建一个文件夹叫你的ID，然后把四个源程序放进去就行了（不用自建文件夹）。
然后为了避免重名。。只能让大家把名字起的有个性一点了囧。。。
这。。我发现题目里面有些bug。。
但是改pdf可能已经来不及了。。
就是第一题的输出格式里面说按字典序输出，其实是按上面“严格的数学定义里”给定的顺序输出。
忘改了。。
同时字典序是按ASCII码的大小来判定的。。
还有第四题的输入里面的重量和价值应该是价格和喜爱度。
密码！！：是nimendongde
题目带密码压缩包下载地址：
cid-d5ca79e9c509746d.office.live.com/self.aspx/OI/%E7%81%B0%E8%89%B2%E5%A4%B4%E5%83%8F%5E_Final.rar

[CTSC2008]图腾totem

Time Limit:30000MS  Memory Limit:165536K
Total Submit:31 Accepted:9
Case Time Limit:4000MS

Description

在完成了古越州圆盘密码的研究之后，考古学家小布来到了南美大陆的西部。相传很久以前在这片土地上生活着两个部落，一个部落崇拜闪电，另一个部落崇拜高 山，他们分别用闪电和山峰的形状作为各自部落的图腾。
小布的团队在山洞里发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包 含的信息仅与这N个点的相对位置有关，因此不妨设坐标分别为(1, y1) , (2, y2), …, (n, yn)，其中y1~yn是1~N的一个排列。
小布的团队打算研究在这幅壁画中包含着多少个图腾，其中闪电图腾的定义图示如下（图腾的形式只与4个纵坐标值的相对大小排列顺序有关）：

崇拜高山的部落有两个氏族，因而山峰图腾有如下两种形式，左边为A类，右边为B类（同样，图腾的形式也都只与4个纵坐标值的大小排列顺序有关）：

小布的团队希望知道，这N个点中两个部落图腾数目的差值。因此在本题中，你需要帮助小布的团队编写一个程序，计算闪电图腾数目减去山峰图腾数目的 值，由于该值可能绝对值较大，本题中只需输出该值对16777216的余数（注意余数必为正值，例如-1对16777216的余数为16777215）。

Input

第一行包含一个整数N，为点的数目。
接下来一行包含N个整数，分别为y1, y2, …, yn。保证y1, y2, …, yn是1~N的一个排列。

Output

仅包含一个数，表示闪电图腾数目与山峰图腾数目的差值对16777216的余数。

Sample Input

【样例输入一】
5
1 5 3 2 4
【样例输入二】
4
1 2 4 3

Sample Output

【样例输出一】
0

【样例输出二】
16777215

Hint

样例一中共有1个闪电图腾（1324）和1个B类山峰图腾（1532）。
样例二中仅有一个A类山峰图腾（1243），故差值为-1，答案为16777215。
【数据规模】
对于10%的数据，N ≤ 600；
对于40%的数据，N ≤ 5000；
对于100%的数据，N ≤ 200000。

Source

哇咔咔。。居然让我A掉了这题。。。
先谢国家。。
再谢gyz神牛和nzk神牛。。。
设f(xxxx)表示排序xxx出现的数量。。
那么我们要求的是f(1324)-f(1243)-f(1432)
注意到f(1243)=f(12xx)-f(1234)。。这两个都很好求。。所以1243解决了。。
但其他两个几乎不可做啊。。题目既然让我们相减，这两个式子必然是有所关联的。。
f(1324)-f(1432)
我们尝试着在两边都+上一个f。。
(f(1324)+f(1423))-(f(1432)+f(1423))
=
f(1x2x)-f(14xx)
这两个都是线段树可做的。。所以问题就解决了。。。
1x2x的做法是把所有数字从小到大加入序列。。
当加入数字x的时候，没有加入的就是空白，它一定比x大
对每个数字维护它后面的空白数量。
然后维护子段和。。
考虑当前加入的数字为2就差不多了。。

14xx的做法来自nzk
吧所有数字从左到右加入按大小组成的序列。。。
那么考虑当前的数字为4.。那么xx必然是它和1之间的空白。。
那么维护每个数字后面的空白数量，的空白的数量的平方
并对这两个进行子段和的维护。。。。
就差不多了囧。。。
代码见网盘。。

[ZJOI2008]瞭望塔

Time Limit:10000MS  Memory Limit:165536K
Total Submit:39 Accepted:22
Case Time Limit:2000MS

Description

致力于建设全国示范和谐小村庄的H村村长dadzhi，决定在村中建立一个瞭望塔，以此加强村中的治安。
我们将H村抽象为一维的轮廓。如下图所示

我们可以用一条山的上方轮廓折线(x1, y1), (x2, y2), …. (xn, yn)来描述H村的形状，这里x1 < x2 < …< xn。瞭望塔可以建造在[x1, xn]间的任意位置, 但必须满足从瞭望塔的顶端可以看到H村的任意位置。可见在不同的位置建造瞭望塔，所需要建造的高度是不同的。为了节省开支，dadzhi村长希望建造的塔 高度尽可能小。
请你写一个程序，帮助dadzhi村长计算塔的最小高度。

Input

第一行包含一个整数n，表示轮廓折线的节点数目。接下来第一行n个整数, 为x1 ~ xn. 第三行n个整数，为y1 ~ yn。

Output

仅包含一个实数，为塔的最小高度，精确到小数点后三位。

Sample Input

【输入样例一】
6
1 2 4 5 6 7
1 2 2 4 2 1
【输入样例二】
4
10 20 49 59
0 10 10 0

Sample Output

【输出样例一】
1.000

【输出样例二】
14.500
【数据规模】
对于60%的数据， N ≤ 60；
对于100%的数据， N ≤ 300，输入坐标绝对值不超过106，注意考虑实数误差带来的问题。

Source
。。这。。裸的半平面交啊T_T。。
不过因为一个很SB的原因。。WA了N次。。
一般我设无穷大都是用~0U>>1..
但这个在double上就不够大了。。
囧啊。。。。
算出能看到所有点的集合然后扫描一遍就可以了。。

[ZJOI2007]Hide 捉迷藏

Time Limit:40000MS  Memory Limit:165536K
Total Submit:121 Accepted:48
Case Time Limit:5000MS

Description

捉迷藏
Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构 造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达。
游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子 们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia 希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。

我们将以如下形式定义每一种操作：

C(hange) i 改变第i个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。
G(ame) 开始一次游戏，查询最远的两个关灯房间的距离。

Input

第一行包含一个整数N，表示房间的个数，房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b，表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q，表示操作次数。接着Q行，每行一个操作，如上文所示。

Output

对于每一个操作Game，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关着灯的，输出0；若所有房间的灯都开 着，输出-1。

Sample Input

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G

Sample Output

4
3
3
4

Hint

对于20%的数据， N ≤50, M ≤100；
对于60%的数据， N ≤3000, M ≤10000；
对于100%的数据， N ≤100000, M ≤500000。

Source

这个题目CQX的题解是用线段树加上括号序列的性质。。但我觉得太繁琐了。。
还是树链剖分的树的分治好理解。。但是好理解归好理解。。一看就知道要写N行囧。。
本着锻炼代码能力，歌颂伟大领袖毛主席的想法。。我还是去写了。。
写了半天。。居然1A了囧。。。。
其实基于链的树的分治就是把树
…………..
….   ….
….
的形状。。。
然后每条路径就是它所在的最高链中一段，加上通下去的两条。。。
Code在网盘上囧。。。

       哎。。。最近比较懒。。已经懒到贴代码了。。所以弄了个马甲叫nimendongde然后密码是123456A了题之后就可以直接看了。。。
不过被人盗了T_T。。。。
囧掉了。。。发现SkyDrive这个网盘很方便啊T_T。。。以后有神马东西就传上去好了T_T。。

[Sdoi2009]Bill的挑战

Time Limit:4000MS Memory Limit:65536K
Total Submit:33 Accepted:11
Case Time Limit:1000MS

Description

Input

本题包含多组数据。
第一行：一个整数T，表示数据的个数。
对于每组数据：
第一行：两个整数，N和K（含义如题目表述）。
接下来N行：每行一个字符串。

Output

1
2 1
a?
?b

Sample Input

Sample Output

Source

Day2
俄。。这个题目也只要知道方法就很好做了。。而这种方法在TC上出现。。
设Ret[Set]表示“跟”Set集合中字符串匹配的数量。。
注意是跟，不是刚好跟。。所以可以扫描一边搞出来。。
算出所有Ret[Set]
再用Ans[Set]表示刚好跟Set集合中字符串匹配的数量
那么Ans[Set]=Ret[Set]-(Ans[a] )(Set 是a的真子集)..
从大到小算出Ans[Set]再统计就可以了T_T。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define All(x) x.begin(),x.end()
using namespace std;
const int maxn=15,maxL=50,mod=1000003;
int T,N,K;
string A[maxn];
bool C[maxn];
int Ret[1<<maxn];
void Calc_Ret()
{
    static char Fixed[maxL];
    memset(Fixed,0,sizeof Fixed);
    int Set=0;
    int ret=1;
    rep(i,N)if(C[i])
    {
        Set|=1<<i;
        rep(j,A[i].size())
        if(A[i][j]!=’?’)
        {
            if(Fixed[j]&&A[i][j]!=Fixed[j])
            {
                ret=0;
            }
            else
            {
                Fixed[j]=A[i][j];
            }
        }
    }
    rep(j,A[0].size())if(!Fixed[j])ret*=26,ret%=mod;
    Ret[Set]=ret;
}
void Generate_Ways(int str)
{
    if(str==N)
    {
        Calc_Ret();
        return;
    }
    //D choose A[str]
    C[str]=false;
    Generate_Ways(str+1);
    //choose A[str];
    C[str]=true;
    Generate_Ways(str+1);
}
void Calc_Ans()
{
    int Ans=0;
    for(int i=(1<<N)-1;i>=0;i–)
    {
        for(int subset=(i-1)&i;subset>0;subset=(subset-1)&i)
            Ret[subset]=(Ret[subset]-Ret[i]+mod)%mod;
        if(i)Ret[0]=(Ret[0]-Ret[i]+mod)%mod;
    }
    rep(i,(1<<N))
    {
        int cnt=0;
        rep(j,N)if(i>>j&1)cnt++;
        if(cnt==K)Ans+=Ret[i],Ans%=mod;
    }
    cout<<Ans<<endl;
}
void Input_Data()
{
    cin>>N>>K;
    rep(i,N)cin>>A[i];
}
int main()
{
    //freopen("in","r",stdin);
    cin>>T;
    rep(i,T)
    {
        Input_Data();
        Generate_Ways(0);
        Calc_Ans();
    }
}

对于30%的数据，T ≤ 5，M ≤ 5，字符串长度≤ 20；对于70%的数据，T ≤ 5，M ≤ 13，字符串长度≤ 30；对于100%的数据，T ≤ 5，M ≤ 15，字符串长度≤ 50。50