[LLH邀请赛]大数计算器

[LLH邀请赛]大数计算器

Time Limit:10000MS  Memory Limit:165536K
Total Submit:15 Accepted:4
Case Time Limit:1000MS

Description

TBL试图用计算器求C(N,M),可是失败了。还是你来帮他编写一个大数计算器吧。 因为答案可能很大
TBL看了会晕,所以如果答案超过12位,就以“XXX…XXXXXXXXX”的格式输出。

Input

两个非负整数N、M。

Output

一个整数表示C(N,M)。(可能包含“…”)

Sample Input

10%的分数,答案不超过int64。
30%的分数,N<=1,000。
50%的分数,N<=30,000。
100%的分数,N<=1,000,000,0<=M<=N。

Sample Output

输入样例1
10 5
输入样例2
100 50

Hint

输出样例1
252
输出样例2
100…812497256

Source
首先用素数分解把除法给消掉。。然后末几位没神马压力。。
关键是前几位。。我的办法是只保存前100位。。然后暴力算。。。
居然可以 AC囧。。。

[JSOI2009]游戏Game

[JSOI2009]游戏Game

Time Limit:10000MS  Memory Limit:165536K
Total Submit:21 Accepted:12
Case Time Limit:1000MS

Description

Input

输入数据首先输入两个整数N,M,表示了迷宫的边长。
接下来N行,每行M个字符,描述了迷宫。

Output

若小AA能够赢得游戏,则输出一行"WIN",然后输出所有可以赢得游戏的起始位置,按行优先顺序输出
每行一个,否则输出一行"LOSE"(不包含引号)。

Sample Input

3 3
.##

#.#

Sample Output

2 3
3 2

Hint

对于100%的数据,有1≤n,m≤100。
对于30%的数据,有1≤n,m≤5。

Source

JSOI2009Day2
这题好那个啥囧。。。2个月前见到此题毫无思路。。。
然后上个星期突然有一点思路了。。
然后又考虑了N久。。。
(其实是看到了一道数学题,就是(2n+1)*(2n+1)的正方形上求证放的人有必胜策略,这个题目随便放在一个点上,然后吧其它的点按多米诺骨牌配对,然后每次别人走到一个点上我就到配对的那个点上。。。肯定赢。。。)
然后接着想。。那么这个是不是也跟最大匹配有关系呢。。。
想了很久秃然明白了囧。。。
如果一个点一定在最大匹配里。。。
所以从这点出发的交替路肯定只能到达匹配中的点。。
那么每次我都肯定可以顺着匹配边走。。。别人就被我搞死了。。。
如果一个点可以不在最大匹配里。。
那么在那个图里面。。。对方每次顺着匹配边走。。我就被搞死了。。。
所以只需要知道每个点是否可以不在最大匹配里。。。
一开始我直接暴力。。TLE。。
后来发现可以不在的点其实就是当前从vs可达的之类的。。。
就可以A了。。速度爆慢囧。。
Code:

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define tr(e,x) for(vector<int>::iterator e=x.begin();e!=x.end();e++)
#define All(x) x.begin(),x.end()
#define pb push_back
#define OK puts("OK")
const int inf=~0U>>1,maxn=100,maxv=maxn*maxn+10;
using namespace std;
struct Edge
{
int t,c;
Edge*next,*op;
Edge(int _t,int _c,Edge*_n):
t(_t),c(_c),next(_n){}
}*E[maxv]={};
void AddEdge(int s,int t,int c)
{
E[s]=new Edge(t,c,E[s]);
E[t]=new Edge(s,0,E[t]);
E[s]->op=E[t];E[t]->op=E[s];
}
int n,m,v,vs,vt;
bool M[maxn][maxn];
void BuildGraph()
{
v=n*m;vs=v++;vt=v++;
rep(i,n)rep(j,m)
if(M[i][j])
if((i+j)&1)
{
#define A(i,j) ((i)*m+(j))
#define build(ii,jj)
if(M[ii][jj])
AddEdge(A(i,j),A(ii,jj),1)
AddEdge(vs,A(i,j),1);
if(i)build(i-1,j);
if(j)build(i,j-1);
if(i+1<n)build(i+1,j);
if(j+1<m)build(i,j+1);
#undef build
}
else
{
AddEdge(A(i,j),vt,1);
#undef A
}
}
int Vis[maxv]={},flag=0;
int dfs(int x,int m)
{
if(x==vt)return m;
Vis[x]=flag;
for(Edge*e=E[x];e;e=e->next)if(e->c&&Vis[e->t]!=flag)
{
int d=dfs(e->t,min(m,e->c));
if(d) return e->c-=d,e->op->c+=d,d;
}
return 0;
}
void Init()
{
scanf("%d%d",&n,&m);char c;
rep(i,n)
{
scanf(" ");
rep(j,m)
c=getchar(),M[i][j]=c==’.';
}
}
bool dead[maxv]={},type;
bool Type(int v)
{
return (v%m+v/m)&1;
}
int C;
void dfs(int x)
{
Vis[x]=flag;
if(Type(x)==type)
dead[x]=true;
for(Edge*e=E[x];e;e=e->next)
if(e->c==type&&Vis[e->t]!=flag)
dfs(e->t);
}
void Solve()
{
++flag;int Max=0;
while(int d=dfs(vs,inf))++flag,Max+=d;
++flag;
type=1;
dfs(vs);dead[vs]=false;
++flag;
type=0;
dfs(vt);dead[vt]=false;
bool has=false;
rep(i,v)if(dead[i]){has=true;break;}
if(has)
{
puts("WIN");
rep(i,v)if(dead[i])
{
int x=i/m,y=i%m;
printf("%d %dn",x+1,y+1);
}
}
else
{
puts("LOSE");
}
}
int main()
{
//freopen("in","r",stdin);
Init();
BuildGraph();
Solve();
}

Booking 会场预约

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]覆盖问题

[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算法。。。

    我在站军姿的时候热的不行。。只好瞎想分散注意力囧。。。莫名其妙想到了这么一个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邀请赛]参观路线

[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邀请赛]巧克力棒

[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函数。。
就差不多了。。。

Page 2 of 212