Booking 会场预约

Time Limit:20000MS  Memory Limit:65536K
Total Submit:3 Accepted:3
Case Time Limit:2000MS

Description

PP大厦有一间空的礼堂，可以为企业或者单位提供会议场地。这些会议中的大多数都需要连续几天的时间（个别的可能只需要一天），不过场地只有一个，所以不 同的会议的时间申请不能够冲突。也就是说，前一个会议的结束日期必须在后一个会议的开始日期之前。所以，如果要接受一个新的场地预约申请，就必须拒绝掉与 这个申请相冲突的预约。
一般来说，如果PP大厦方面事先已经接受了一个会场预约，例如从10日到15日，就不会在接受与之相冲突的预约，例如从12日到17日。不过，有时出于经济利益，PP大厦方面有时会为了接受一个新的会场预约，而拒绝掉一个甚至几个之前预订的预约。
于是，礼堂管理员QQ的笔记本上笔记本上经常记录着这样的信息：

本题中为方便起见，所有的日期都用一个整数表示。例如，如果一个为期10天的会议从“90日”开始到“99日”，那么下一个会议最早只能在“100日”开始。
最近，这个业务的工作量与日俱增，礼堂的管理员QQ希望参加SHTSC的你替他设计一套计算机系统，方便他的工作。这个系统应当能执行下面两个操作：
A操作：有一个新的预约是从“start日”到“end日”，并且拒绝掉所有与它相冲突的预约。执行这个操作的时候，你的系统应当返回为了这个新预约而拒绝掉的预约个数，以方便QQ与自己的记录相校对。
B操作：请你的系统返回当前的仍然有效的预约的总数。

Input

输入文件的第一行是一个整数n，表示你的系统将接受的操作总数。
接下去n行每行表示一个操作。每一行的格式为下面两者之一：
“A start end”表示一个A操作；
“B”表示一个B操作。

Output

输出文件有n行，每行一次对应一个输入。表示你的系统对于该操作的返回值。

Sample Input

6
A 10 15
A 17 19
A 12 17
A 90 99
A 11 12
B

Sample Output

0
0
2
0
1
2

Hint

N< = 200000
1< = Start End < = 100000

Source

By cqx
额。。我似乎已经N年没有来除草了。。。。最近新高一上学弄的心力憔悴。。
然后又发现GCJ的题目很有意思看了很久。。。导致悲剧囧。。。
额。。庆祝一下BZOJA了300道了。。虽然说都是水题囧。。。
比如这道题目囧。。。。
我看到之后第一感觉是当前所有的区间肯定是不相交且有序的。。同时一旦冲突就删除了。。
那么很容易弄一个均摊复杂度OK的算法。。
用set维护当前所有区间，那么B就直接输出其大小。。
然后对于A。。每次找到可能跟新插入的区间相交的两个区间。。看看是否相交然后删除就可以了。。。
Code：

#include <utility>
#include <cstdio>
#include <set>
const int inf=~0U>>1;
using namespace std;
typedef pair<int,int> seg;
#define l first
#define r second
set<seg> S;
typedef set<seg>::iterator sit;
bool inter(seg a,seg b)
{
return !(a.l>b.r||b.l>a.r);
}
int main()
{
char t;int l,r;
int n;scanf("%d",&n);
while(n–)
{
scanf(" ");char c=getchar();
if(c==’A’)
{
scanf("%d%d",&l,&r);
seg a(l,r);
int ret=0;
for(;;)
{
sit it=S.lower_bound(a);
if(inter(*it,a)){ret++;S.erase(it);continue;}
it=S.lower_bound(a);
if(it!=S.begin())
{
–it;if(inter(*it,a)){ret++;S.erase(it);continue;}
}
break;
}
printf("%dn",ret);
S.insert(a);
}
else
printf("%dn",S.size());
}
}

[HAOI2007]覆盖问题

Time Limit:10000MS  Memory Limit:165536K
Total Submit:17 Accepted:8
Case Time Limit:1000MS

Description

某人在山上种了N棵小树苗。冬天来了，温度急速下降，小树苗脆弱得不堪一击，于是树主人想用一些塑料薄膜把这些小树遮盖起来，经过一番长久的思考，他决定 用3个L*L的正方形塑料薄膜将小树遮起来。我们不妨将山建立一个平面直角坐标系，设第i棵小树的坐标为（Xi,Yi），3个L*L的正方形的边要求平行 与坐标轴，一个点如果在正方形的边界上，也算作被覆盖。当然，我们希望塑料薄膜面积越小越好，即求L最小值。

Input

第一行有一个正整数N，表示有多少棵树。
接下来有N行，第i+1行有2个整数Xi,Yi，表示第i棵树的坐标，保证不会有2个树的坐标相同。

Output

一行，输出最小的L值。

Sample Input

4
0 1
0 -1
1 0
-1 0

Sample Output

1
数据范围
100%的数据，-1,000,000,000<=Xi,Yi<=1,000,000,000
30%的数据，N<=100
50%的数据，N<=2000
100%的数据，N<=20000

Source

这题直接将我虐成SB。。。。
首先这是SGU的原题，309.。
但这并不能帮助我们做题囧。。。。
以前写过一个贪心。。果断WA。。
首先二分。。
当时想的是肯定要选一个角上的正方形（这个可以证）
然后自然想肯定要选2个角上的正方形（这个不会证，实际上是错的我擦），
然后检查剩下的时候能包裹在一个正方形里面。。。。
WA。。。WA。。。WA。。。
后来发现了反例我擦。。。
然后想到第一个是对的，那我第一个包含的所有点给去掉，再找一次也是对的。。。
然后就AC了。。。
不过SGU上TLE了。。。

    我在站军姿的时候热的不行。。只好瞎想分散注意力囧。。。莫名其妙想到了这么一个SB算法。。
多串匹配，就是有N个串，问模板串里面有没有其中一个串。。
假设模板串长度为T。。那么N次KMP显然需要至少NT的时间，不是很理想。。
然后有一个很NB的Aho-Corasick算法。。可是我过于沙茶完全不会。。。
然后就想到一个非常沙茶的算法，具体说就是先对所有串进行new lcp的预处理。。
然后把模板串的SA求出来，
然后用二分查找的办法找出跟当前串匹配长度最长的后缀，再进行检查。。
分析以下复杂度囧。。。new lcp TLogT，SA TLogT，二分查找（每次检查都是LogT的）LogT^2
总共就是TLogT+N*LogT^2…勉强能过某道多串匹配的题目囧。。。。

[LLH邀请赛]参观路线

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

Description

Lambdaland由N个城市组成，任两个城市间都有一条道路相连。 下个月TBL准备参观Lambdaland。他将从城市1开始，以深度优先搜索顺序参观能所有遍历到的城市。 由于TBL是一位十分重要的人物，恐怖分子盯上了他，并在他出发之前炸毁了M条道路。 现在恐怖分子雇佣你写一个程序，求出TBL的参观路线。如果有多解，输出字典序最小的。

Input

第一行包括两个非负整数N、M。 接下来M行，每行两个整数A、B，表示城市A至城市B的道路被炸毁。

Output

每行一个整数，第i行的整数表示TBL第i次参观的城市编号。

Sample Input

4 4
1 2
1 3
2 3
3 4

Sample Output

1
4
2

Hint

20%的分数，N<=1,000，M<=50,000。
50%的分数，N<=30,000，M<=800,000。
100%的分数，N<=100,000，M<=1,000,000。
每个城市最多被参观一次，每条道路可被炸毁多次

Source

。。LLH邀请赛的题目好像都很水的样子囧。。。。
这个题目就是暴力遍历。。然后用一个set维护当前未到的点然后每次往后走就行了。。

玩具

Time Limit:10000MS  Memory Limit:165536K
Total Submit:175 Accepted:70
Case Time Limit:1000MS

Description

小球球是个可爱的孩子，他喜欢玩具，另外小球球有个大大的柜子，里面放满了玩具，由于柜子太高了，每天小球球都会让妈妈从柜子上拿一些玩具放在地板上让小球球玩。
这天，小球球把所有的N辆玩具摆成一排放在地上，对于每辆玩具i，小球球都会给它涂上一个正整数value[i]，以表示小球球对该玩具的喜爱程 度，value[i]越小则表示他越喜爱。当然对于两辆不同的玩具u,v(u<>v)，亦有可能value[i]=value[j]，也就是 说小球球对u,v两车的喜爱程度是一样的。
小球球很贪玩，他希望能从中间某个位置，连续的取出k辆玩具，使得这k辆车里喜爱程度最大的一辆车的喜爱程度正好等于k，且这k辆车中没有两辆车的喜爱程度是相同的。小球球希望知道k的最大值为多少。

Input

第一行一个整数N，表示小球球拥有的玩具数量。
接下来N行，每行一个整数，表示value[i]。

Output

一个整数k，即答案。

Sample Input

6
2
4
1
3
2
1

Sample Output

4

Hint

1<=Value[i]<=10^6
10%的测试数据 N<=10^5。
100%的测试数据 N<=10^6

Source

军训最后一天。。。这个题目很SB啊囧。。。可以立马看出实际上就是找最长的子排列（1…k）
然后就没神马压力了。。。
随便怎么搞都行。。比如说先枚举1的位置，然后枚举开头。。。

[LLH邀请赛]巧克力棒

Time Limit:10000MS  Memory Limit:165536K
Total Submit:42 Accepted:13
Case Time Limit:1000MS

Description

TBL和X用巧克力棒玩游戏。每次一人可以从盒子里取出若干条巧克力棒，或是将一根取出的巧克力棒吃掉正整数长度。TBL先手
两人轮流，无法操作的人输。 他们以最佳策略一共进行了10轮（每次一盒）。你能预测胜负吗？

Input

输入数据共20行。 第2i-1行一个正整数Ni，表示第i轮巧克力棒的数目。 第2i行Ni个正整数Li,j，表示第i轮巧克力棒的长度。

Output

输出数据共10行。 每行输出“YES”或“NO”，表示TBL是否会赢。
如果胜则输出"NO",否则输出"YES"

Sample Input

20%的分数，N<=5，L<=100。
40%的分数，N<=7。 50%的分数，L<=5,000。
100%的分数，N<=14，L<=1,000,000,000。

Sample Output

4 7 10 7 1 4 4 9 7 5 （其它8组输入„„）

Hint

YES
NO
其它8组输出„„）

Source
这个题目算下SG值就可以了。。。
再军训就不多说了。。
接上次。。。
可以注意到拿出来的和在外面的是互相独立的。。
所以他们的SG函数可以xor一下。。
然后可以计算任意子集的SG函数。。
就差不多了。。。

哎我太弱了。。。今天问了NZK神牛才知道应该怎么搞炯。。
套用zxytim神牛的话，Bash无比强大啊。。
所以Ubuntu下面评测直接写个脚本就OK了。。完全无压力。。
比如说一个例子。。a+b problem
首先要一个数据生成器：
datamaker.cpp
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
int main()
{
srand(clock());
cout<<rand()<<" "<<rand()<<endl;
}还要一个标程：
prog_std.cpp
#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;
int main()
{
long long a,b;
cin>>a>>b;
cout<<a+b<<endl;
}
然后写一个生成数据的脚本
makedata.sh
name=aplusb
maker=datamaker
g++ -o $maker $maker.cpp
for((i=0;i<10;i++))do
./$maker>$name.in$i;
done
std=prog_std
g++ -o $std $std.cpp
for((i=0;i<10;i++))do
./$std<$name.in$i>$name.out$i;
done然后运行这个。。。10个in和out就出来了炯。。。

然后写一个程序:
aplusb.cpp
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
int main()
{
long long a,b;
cin>>a>>b;
cout<<a+b<<endl;
}最后写一个checker
check.sh
cd /host/OI/Judge
name=aplusb
g++ -o $name $name.cpp
for((i=0;i<10;i++))
do
echo Data$i;
if time ./$name<$name.in$i | diff -q $name.out$i – ;then
echo AC;
else
echo WA;
fi;
done
然后打开check。。点在终端运行就可以直接使用了。。
测其它的话把name改掉就可以了。。。
Ubuntu太NB了。。Orz！！！！！！！！！！！！！！！

336. ElectionsTime limit per test: 7.50 second(s)
Memory limit: 65536 kilobytesinput: standard
output: standard

New parliament election in Berland is coming soon. Each of N political parties wants to be elected into the parliament. There is a law in Berland that allows only parties with more than a certain amount of votes be elected. Thus, some of the smaller parties are trying to use different technologies to collect necessary amount of votes.

The first technology is completely legal. Two or more parties can go to the elections together, forming so-called .

The second technology is not so legal. Some parties have specific information about their opponents. Those opponents don’t want this information to become public.

If several parties join into one election block, their information is joined together as well. Thus, they become more powerful. However, the opponents of each party of the block know something discreditable about the whole block. The party or block might have some ‘black’ information on itself.

Let us now enumerate parties with the integers from 1 to N. Parties and blocks are allowed to join together into new blocks. Those blocks are numbered with the consecutive integers (N+1, N+2, etc.).

You are to write a program that processes queries of two different kinds.

• Query ‘ 1 a b ‘ means that you have to answer the question: is there any discreditable information that party or block a knows about party or block b?
• Query ‘ 2 a b ‘ means that you need to join party or block a with party or block b. The new block will have all the information a has, and all the information b has. All the information that was known by some parties or blocks about a and b now concerns the newly created block.

InputThe first line of the input file contains integers N and M (1 ≤ N ≤ 10⁵; 1 ≤ M ≤ 2 · 10⁵). Next M lines contain pairs of integers a and b denoting that party a knows something discreditable about party b (1 ≤ a, b ≤ N). The next line contains single integer number Q (1 ≤ Q ≤ 2 · 10⁵). Each of the next Q lines contains a query. A query of the first kind looks like ‘1 a b’. A query of the second kind looks like ‘2 a b’. You should process queries in the order they are given. Each pair a, b references only existing parties or blocks. It is guaranteed that numbers a and b are different in any ‘2 a b’ query, but they can be equal in a ‘1 a b’ query. 

OutputWrite on the separate lines of the output file answer YES or NO for each query of the first kind.

Example(s) sample input sample output 4 6 1 2 1 3 3 2 4 4 2 4 1 2 4 1 3 4 2 2 3 1 5 4 1 4 5 NO YES NO 额。。其实这题挺裸的阿炯。。不知道为神马AC的人那么少炯。。
合并关系可以看成一颗树，那么如果先序遍历一下，一个顶点对应的所有原来的顶点
就是一个区间了。。那么只需要询问某个定点掌握的黑资料里面有没有一个区间内的数。。
用set进行启发式合并，就可以在LogN完成询问。。
然后set和启发式合起来就是O(NLogN^2)。。。
或者把黑资料也用一样的方式先序遍历一下
问题就变成一行数，然后每次询问一段数中有没有一个区间的数。。
用离线+树状数组可以NLogN搞定。。
或者用线段树可以NLogN + LogN^2*Q搞定。。
或者用划分树可以NLogN + LogN*Q搞定。。
Code:
www.ideone.com/a1nJa

额。。上次那个裸判是M^2的。。数据太弱这样都能过大囧。。。
构造性的数据很容易出囧。。。没办法只好再研究一下了瀑布汗。。
考虑这个问题。。实际上就是一个区间图的2-染色问题，
那么首先吧问题分成两部分。。
首先是给每个节点染色，
其次是判断这个样的染色可不可行。。
第一个问题如果不能是M^2的话。。我们需要对某条边，
快速的找出一个与它相交的边把它染掉，同时把它在可选边中删掉。。
不难发现用线段树可以在LogN的时间搞定。。
第二个问题分别考虑2个颜色好了。。
需要判断一堆边中有没有相交的。。怎么搞都行囧。。

410. Galaxy in dangerTime limit per test: 2 second(s)
Memory limit: 65536 kilobytesinput: standard
output: standard

Many years has already passed since the Logos galaxy was attacked by crazy space creatures, called mistkafers. With extreme efforts brave defenders of the galaxy managed to defeat the main forces of the opponent. The remaining enemies have been isolated on N different planets. 

Now the Government of a galaxy has a very difficult problem — to get rid from mistkafers in a galaxy as soon as possible. Namely to take them far beyond the galaxy and to dump them into a black hole. To cope with this problem, the Government needs help of winged pferds which can fly through black holes.

By a strange coincidence, there is exactly N pferds available for the Government. Pferds can fly only all together, and each of them can transport to a black hole only one mistkafer per day. Thus, every day pferds take Nmistkafers and transport them into a black hole. And every pferd is so logical and consecutive, that will take mistkafers from the same planet every time, and will not fly to a black hole without mistkafer. Therefore, if there is no mistkafers left on some planet, pferds cannot take them out further.

In order to prevent such situations, in the morning of each day the Government can send scientists to some of the planets. These scientists can clone mistkarefs (no matter how they do it, but after cloning the number of mistkafers on the planet is doubled). The cloning of mistkafers on one planet takes exactly one day, so that day pferds do not take off. 

Find out the minimal number of days which is required to get rid of mistkafers.

InputIn the first line of the input file the amount of planets N (1 ≤ N ≤ 100000) is given. The second line contains N natural numbers, each of them means the number of mistkafers on a corresponding planet. The quantity of mistkafers on each planet does not exceed one billion. 

OutputOn the first line of the output file print one number K — the answer to the problem. In case the number of days does not exceed one thousand, in the following K lines output the description of days in the chronological order. If on the i-th day there was a flight of the pferds, output on (i+1)-th line a phrase "flying mission" (without quotes), otherwise output a phrase "science mission to the planet j (without quotes), where j — is the number of a planet on which the cloning was made.

Example(s) sample input sample output 2
1 2 3
science mission to the planet 1
flying mission
flying mission
sample input sample output 2
2 1025 1035
题目是这个样子的。。
一堆数，两种操作。。一种是所有数-1
一种是一个数*2.。
用最少操作让所有数都变成0.。。。
首先可以发现-1的次数肯定就是最大的那个数。。
然后显然就是每次看看最小的那个数*2是不是比最大的那个大，
不是的话就把它*2.。。
然后答案比较小的话模拟一下。。
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1,maxn=100000;
using namespace std;
typedef long long ll;
int A[maxn],n,T[maxn];
struct cmp
{
bool operator()(int i,int j)const
{
return A[i]>A[j];
}
};
priority_queue<int,vector<int>,cmp> PQ;
int Solve()
{
int ret=0;
int Max=*max_element(A,A+n);
for(int T=0;T<Max;)
{
for(;;)
{
int t=PQ.top();
if((A[t]-T)*2>(Max-T))
{
int pass=2*(A[t]-T)-(Max-T);
T+=pass;
break;
}
A[t]-=T;A[t]*=2;A[t]+=T;PQ.pop();
PQ.push(t);ret++;
}
}
return ret+Max;
}
void Simulate()
{
while(PQ.size())PQ.pop();
rep(i,n)PQ.push(i);
int Max=*max_element(A,A+n);
rep(T,Max)
{
for(;;)
{
int t=PQ.top();
if((A[t]-T)*2>(Max-T))break;
A[t]-=T;A[t]*=2;A[t]+=T;PQ.pop();
PQ.push(t);
printf("science mission to the planet %dn",t+1);
}
puts("flying mission");
}
}
int main()
{
//freopen("in","r",stdin);
scanf("%d",&n);
rep(i,n)scanf("%d",A+i),PQ.push(i);
memcpy(T,A,sizeof A);
int ret=Solve();
cout<<ret<<endl;
if(ret<=1000)
{
memcpy(A,T,sizeof A);
Simulate();
}
}