【灰色头像模拟赛】

根据投票结果。。。。
时间定为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

[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]瞭望塔

[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 捉迷藏

[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在网盘上囧。。。

Page 4 of 41234