Ubuntu下的测评

哎我太弱了。。。今天问了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!!!!!!!!!!!!!!!

SGU 336. Elections

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 ≤ 105; 1 ≤ M ≤ 2 · 105). Next M lines contain pairs of integers a and b denoting that party a knows something discreditable about party b (1 ≤ ab ≤ N). The next line contains single integer number Q (1 ≤ Q ≤ 2 · 105). 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 ab 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

[Hnoi2010]Planar 2

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

410. Galaxy in danger

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();
}
}

Ticket to Ride

Time Limit:5000MS  Memory Limit:65536K
Total Submit:7 Accepted:5
Case Time Limit:1000MS

Description

给一张地图,地图上有一些城市,城市之间可能有线路连通,我们用一个无向图来表示以简化概念,每条边有个权值,表示选择这条边需要花费的费用。给定4对顶 点(可能重复),求一个权值最小的边集,使得任意一对顶点可以由选出的边集中的边相连。
按照惯例,下面给出一个例子:

Input

第1行2个整数,n和m,分别表示城市的个数和边的个数。
接下来n行,每行一个字符串,表示每个城市的名字。城市的名字为一个不超过20个字符,由小写字母构成的字符串。
再接下来m行,每行给出s1,s2和w,其中s1,s2为城市的名字,w为他们之间边的权值。
最后,给出4行,每行给出两个字符串,分别为要求的一对城市的名字。

Output

一行,输出最小的花费。

Sample Input

样例输入1:
10 15
stockholm
amsterdam
london
berlin
copenhagen
oslo
helsinki
dublin
reykjavik
brussels
oslo stockholm 415
stockholm helsinki 396
oslo london 1153
oslo copenhagen 485
stockholm copenhagen 522
copenhagen berlin 354
copenhagen amsterdam 622
helsinki berlin 1107
london amsterdam 356
berlin amsterdam 575
london dublin 463
reykjavik dublin 1498
reykjavik oslo 1748
london brussels 318
brussels amsterdam 173
stockholm amsterdam
oslo london
reykjavik dublin
brussels helsinki

样例输入2:
2 1
first
second
first second 10
first first
first first
second first
first first

Sample Output

样例输出1:
3907

样例输出2:
10

数据范围:
n<=30,m<=1000,w<=10000。

Source
这个题目非常好啊。。
以前WC有道题目跟这个很类似。。
首先答案肯定是个森另
所以状态可以看成Dp[at][mask]
at表示当前树的根在哪里,mask表示到过的地方(最多8位)
然后开始转移,跟那个不同的是,
如果mask里面状态是两两配对的话,
那么转移的时候经过的边权可以忽略。。
那么有2种转移。一种是at->go另一个地方。。
另一个是把同样在at的一个状态合并进来。。
然后瞎搞一下就OK了:
Code:

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=30,maxc=8;
using namespace std;
map<string,int> Map;
vector<int> Mark[maxn];
int n,m,Ans=inf;
int E[maxn][maxn];
struct State
{
int at,mask;
State(){}
State(int _at,int _mask):
at(_at),mask(_mask){}
void mark(int go)
{
rep(i,Mark[go].size())
mask|=1<<(Mark[go][i]);
}
bool full()
{
return mask+1==(1<<8);
}
bool movefree()
{
rep(i,4)
{
int t=(mask>>(i*2))&3;
if(t!=0&&t!=3)return false;
}
return true;
}
int hash()const{return (at<<8)+mask;}
};
queue<State> Q;
int TDist[maxn<<8];
bool TinQ[maxn<<8];
int&Dist(const State&st){return TDist[st.hash()];}
bool&inQ(const State&st){return TinQ[st.hash()];}
void spfa()
{
memset(TDist,-1,sizeof TDist);
memset(TinQ,0,sizeof TinQ);
rep(at,n)
{
State now(at,0);
now.mark(at);
Dist(now)=0;inQ(now)=true;
Q.push(now);
}
while(Q.size())
{
State now=Q.front();Q.pop();
int c=Dist(now);inQ(now)=false;
if(now.full())
{
if(c<Ans)Ans=c;
continue;
}
bool free=now.movefree();
State next;int w;
//let’s go
rep(go,n)
if((w=E[now.at][go])!=inf)
{
if(free)w=0;
int nc=c+w;
next.at=go;next.mask=now.mask;
next.mark(go);
if(Dist(next)==-1||Dist(next)>nc)
{
Dist(next)=nc;
if(!inQ(next))
Q.push(next),inQ(next)=true;
}
}
//or we merge somthing
rep(j,(1<<8))
{
State tmp(now.at,j);
int tmpc=Dist(tmp);
if(tmpc!=-1)
{
State next(now.at,j|(now.mask));
int nc=tmpc+c;
if(Dist(next)==-1||Dist(next)>nc)
{
Dist(next)=nc;
if(!inQ(next))
Q.push(next),inQ(next)=true;
}
}
}
}
}
void init()
{
cin>>n>>m;string a,b;int c;
rep(i,n)rep(j,n)E[i][j]=inf;
rep(i,n)cin>>a,Map[a]=i;
rep(i,m)
{
cin>>a>>b>>c;
int s=Map[a],t=Map[b];
E[s][t]=E[t][s]=min(E[s][t],c);
}
memset(Mark,-1,sizeof Mark);
rep(i,8)
{
cin>>a;Mark[Map[a]].push_back(i);
}
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
init();
spfa();
cout<<Ans<<endl;
}

[JSOI2008]火星人prefix

[JSOI2008]火星人prefix

Time Limit:10000MS  Memory Limit:165536K
Total Submit:127 Accepted:35
Case Time Limit:2000MS

Description

火星人最近研究了一种操作:求一个字串两个后缀的公共前缀。比方说,有这样一个字符串:madamimadam,我们将这个字符串的各个字符予以标号:
序号: 1 2 3 4 5 6 7 8 9 10 11
字符 m a d a m i m a d a m
现在,火星人定义了一个函数LCQ(x, y),表示:该字符串中第x个字符开始的字串,与该字符串中第y个字符开始的字串,两个字串的公共前缀的长度。比方说,LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0
在研究LCQ函数的过程中,火星人发现了这样的一个关联:如果把该字符串的所有后缀排好序,就可以很快地求出LCQ函数的值;同样,如果求出了LCQ函数 的值,也可以很快地将该字符串的后缀排好序。
尽管火星人聪明地找到了求取LCQ函数的快速算法,但不甘心认输的地球人又给火星人出了个难题:在求取LCQ函数的同时,还可以改变字符串本身。具体地 说,可以更改字符串中某一个字符的值,也可以在字符串中的某一个位置插入一个字符。地球人想考验一下,在如此复杂的问题中,火星人是否还能够做到很快地求 取LCQ函数的值。

Input

第一行给出初始的字符串。
第二行是一个非负整数M,表示操作的个数。
接下来的M行,每行描述一个操作。操作有3种,如下所示:
1、 询问。
语法:Q x y,x, y均为正整数。
功能:计算LCQ(x, y)
限制:1 <= x, y <= 当前字符串长度。
2、 修改。
语法:R x d,x是正整数,d是字符。
功能:将字符串中第x个数修改为字符d。
限制:x不超过当前字符串长度。
3、 插入:
语法:I x d,x是非负整数,d是字符。
功能:在字符串第x个字符之后插入字符d,如果x = 0,则在字符串开头插入。
限制:x不超过当前字符串长度。

Output

对于输入文件中每一个询问操作,你都应该输出对应的答案。一个答案一行。

Sample Input

7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

Sample Output

5
1
0
2
1

数据规模:
对于100%的数据,满足:
1、 所有字符串自始至终都只有小写字母构成。
2、 M <= 150,000
3、 字符串长度L自始至终都满足L <= 100,000
4、 询问操作的个数不超过10,000个。

对于第1,2个数据,字符串长度自始至终都不超过1,000
对于第3,4,5个数据,没有插入操作。

Source

这题把我搞毛了大囧。。。
无理由WA N次。。最后发现是爆Stack了瀑布汗。。。
因为我懒得一开始建Splay,所以一开始就是暴力插入。。
然后Splay会变成一条链,然后就爆Stack了。。。
我我我。。。10W个点就爆栈啊。。。
以后Splay看来一定要写非递归的囧。。
算法实际上挺简单的。。
就是用一个Splay维护Hash值,然后二分判定最大长度。。
Code:
www.ideone.com/XOZXT

[SHOI2008]Debt 循环的债务

[SHOI2008]Debt 循环的债务

Time Limit:1000MS  Memory Limit:165536K
Total Submit:22 Accepted:8
Case Time Limit:100MS

Description

Alice、Bob和Cynthia总是为他们之间混乱的债务而烦恼,终于有一天,他们决定坐下来一起解决这个问题。不过,鉴别钞票的真伪是一件很麻烦的 事情,于是他们决定要在清还债务的时候尽可能少的交换现金。
比如说,Alice欠Bob 10元,而Cynthia和他俩互不相欠。现在假设Alice只有一张50元,Bob有3张10元和10张1元,Cynthia有3张20元。一种比较直 接的做法是:Alice将50元交给Bob,而Bob将他身上的钱找给Alice,这样一共就会有14张钞票被交换。但这不是最好的做法,最好的做法 是:Alice把50块给Cynthia,Cynthia再把两张20给Alice,另一张20给Bob,而Bob把一张10块给C,此时只有5张钞票被 交换过。
没过多久他们就发现这是一个很棘手的问题,于是他们找到了精通数学的你为他们解决这个难题。

Input

输入的第一行包括三个整数:x1、x2、x3(-1,000≤x1,x2,x3≤1,000),其中
x1代表Alice欠Bob的钱(如果x1是负数,说明Bob欠了Alice的钱)
x2代表Bob欠Cynthia的钱(如果x2是负数,说明Cynthia欠了Bob的钱)
x3代表Cynthia欠Alice的钱(如果x3是负数,说明Alice欠了Cynthia的钱)
接下来有三行,每行包括6个自然数:
a100,a50,a20,a10,a5,a1
b100,b50,b20,b10,b5,b1
c100,c50,c20,c10,c5,c1
a100表示Alice拥有的100元钞票张数,b50表示Bob拥有的50元钞票张数,以此类推。另外,我们保证有 a10+a5+a1≤30,b10+b5+b1≤30,c10+c5+c1≤30,而且三人总共拥有的钞票面值总额不会超过1,000。

Output

如果债务可以还清,则输出需要交换钞票的最少张数;如果不能还清,则输出“impossible”(注意单词全部小写,输出到文件时不要加引号)。
输入一
10 0 0
0 1 0 0 0 0
0 0 0 3 0 10
0 0 3 0 0 0
输入二
-10 -10 -10
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
【数据规模】
对于30%的数据,x1、x2、x3 ≤ |50|。
对于100%的数据,x1、x2、x3 ≤ |1,000|。

Sample Input

输出一
5

输出二
0

Sample Output

Source

这个题目非常BT囧。。。
我被它搞死了。。。
恩。。办法是这个样子的。。搜索估计要悲剧。直接想Dp。
可以把题目转化成从一个状态A,B分别的钱数到另一个状态。。
然后发现状态可以是pos,a,b表示当前考虑到第pos种钱币,Alice现在的钱,Bob现在的钱。。
然后可以发现对同一种硬币来说,把多余的操作删掉,比如A给B给C。。可以发现要么是A给B,A给C
要么是B给A,C给A。。枚举哪个人被给之类的
由于。。a10+a5+a1≤30,b10+b5+b1≤30,c10+c5+c1≤30。。
这个对于10,5,1还是比较快的。。。
然后可以发现从小到大考虑到话,如果对于后面的数的最大公约数mod的值与目标状态不同
那么说什么也不行了。。
所以可以果断忽略。。
然后再考虑100,50,20.。
他们。。好像都是10的倍数囧。。
所以直接除以10之后再考虑。。就可以快N多从而避免TLE了囧。。
两个部分分别Dp。。。
最后组合一下。。。
就OK了。。

[JSOI2007]麻将

[JSOI2007]麻将

Time Limit:1000MS  Memory Limit:165536K
Total Submit:31 Accepted:10

Description

麻将是中国传统的娱乐工具之一。麻将牌的牌可以分为字牌(共有东、南、西、北、中、发、白七种)和序数牌(分为条子、饼子、万子三种花色,每种花色各有一 到九的九种牌),每种牌各四张。在麻将中,通常情况下一组和了的牌(即完成的牌)由十四张牌组成。十四张牌中的两张组成对子(即完全相同的两张牌),剩余 的十二张组成三张一组的四组,每一组须为顺子(即同花色且序数相连的序数牌,例如条子的三、四、五)或者是刻子(即完全相同的三张牌)。一组听牌的牌是指 一组十三张牌,且再加上某一张牌就可以组成和牌。那一张加上的牌可以称为等待牌。

在这里,我们考虑一种特殊的麻将。在这种特殊的麻将里,没有字牌,花色也只有一种。但是,序数不被限制在一到九的范围内,而是在1到n的范围内。 同时,也没有每一种牌四张的限制。一组和了的牌由3m + 2张牌组成,其中两张组成对子,其余3m张组成三张一组的m组,每组须为顺子或刻子。现给出一组3m + 1张的牌,要求判断该组牌是否为听牌(即还差一张就可以和牌)。如果是的话,输出所有可能的等待牌。

Input

包含两行。
第一行包含两个由空格隔开整数n, m (9<=n<=400, 4<=m<=1000)。第二行包含3m + 1个由空格隔开整数,每个数均在范围1到n之内。这些数代表要求判断听牌的牌的序数。

Output

输出为一行。
如果该组牌为听牌,则输出所有的可能的等待牌的序数,数字之间用一个空格隔开。所有的序数必须按从小到大的顺序输出。如果该组牌不是听牌,则输 出"NO"。

Sample Input

9 4
1 1 2 2 3 3 5 5 5 7 8 8 8

Sample Output

6 7 9

Source

我真是吐血啊。。两个麻将题完全不一样的瀑布汗。。。我顺着上一题的办法拼命搞。。
各种TLE+WA+MLE大囧。。。
最后发现TMD这题分明是贪心题啊。。我真是个沙茶。。。
首先枚举等的牌,
然后枚举哪个是一对,
然后从小到大扫描过去。。
可以发现当前的如果用3次或以上的顺子是沙茶的,所以用的顺子正好是除3的余数。。
然后扫描过去就OK了。。
复杂度是O(N^3)。。。
实际上Hash+Dp也能过很多点的样子。。
Code:
#include <cstdio>
#include <map>
#include <iostream>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=400;
using namespace std;
typedef unsigned long long ull;
int A[maxn]={},B[maxn]={},n,m;
bool Check()
{
rep(cur,n)
if(A[cur]>=2)
{
A[cur]-=2;
rep(i,n)B[i]=A[i];
bool ok=true;
for(int i=0;i<n;)
{
B[i]%=3;
if(!B[i])i++;
else
{
if(i+2<n)
{
if(B[i+1]<B[i]){ok=false;break;}
B[i+1]-=B[i];
if(B[i+2]<B[i]){ok=false;break;}
B[i+2]-=B[i];
i++;
}
else
{
ok=false;
break;
}
}
}
A[cur]+=2;
if(ok)return true;
}
return false;
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
cin>>n>>m;int x;
rep(i,m*3+1)
{
scanf("%d",&x);
A[–x]++;
}
int s=0;
rep(i,n)
{
A[i]++;
if(Check())
{
s++;
printf("%d ",i+1);
}
A[i]–;
}
if(!s)puts("NO");
}

[Zjoi2006]Mahjong麻将

[Zjoi2006]Mahjong麻将

Time Limit:1000MS  Memory Limit:65536K
Total Submit:3 Accepted:3

Description

Input

第一行一个整数N(N<=100),表示玩了N次超级麻将。
接下来N行,每行100个数a1..a100,描述每次玩牌手中各种牌的数量。ai表示数字为i的牌有ai张。(0<=ai& lt;=100)

Output

输出N行,若胡了则输出Yes,否则输出No,注意区分Yes,No的大小写!

Sample Input

3
2 4 0 0 0 0 0 …… 0(一共98个0)
2 4 2 0 0 0 0 …… 0(一共97个0)
2 3 2 0 0 0 0 …… 0(一共97个0)

Sample Output

Yes
Yes
No

Source

Day2

一开始我看AC人数这么少。。以为是BT的难题。。不敢做。。
不过刚刚仔细看了下怎么好像仿佛。。是水题?
注意到从左往右消去每个麻将,首先当前的只能影响3个。。
所以记录当前3个的个数就足够了囧。。同时还要知道那一对有没有被用过。。
所以状态就是 (pos,Apos,Apos+1,Apos+2,have_pair_used)
应该说Dp就可以了。。不过我有点懒。。。所以用了Hash+set。。速度很快啊囧。。
Code:
#include <cstdio>
#include <set>
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
#define Debug(x) cout<<#x<<"="<<x<<endl;
const int inf=~0U>>1,seed=131,maxn=100;
using namespace std;
typedef unsigned long long ull;
ull P[maxn+1];
set<ull> S;
int A[maxn];
bool ok;
void dfs(int p,bool can,ull code)
{
if(!S.insert(code).second)return;
while(p<maxn&&A[p]==0)p++;
if(p==maxn){if(!can)ok=true;return;}
//three consecutive
if(p+2<maxn&&A[p]&&A[p+1]&&A[p+2])
{
A[p]–;A[p+1]–;A[p+2]–;
ull ncode=code-P[p]-P[p+1]-P[p+2];
dfs(p,can,ncode);if(ok)return;
A[p]++;A[p+1]++;A[p+2]++;
}
//three same
if(A[p]>=3)
{
A[p]-=3;
ull ncode=code-P[p]*3;
dfs(p,can,ncode);if(ok)return;
A[p]+=3;
}
//four same
if(A[p]>=4)
{
A[p]-=4;
ull ncode=code-P[p]*4;
dfs(p,can,ncode);if(ok)return;
A[p]+=4;
}
//use pair
if(A[p]>=2&&can)
{
A[p]-=2;
ull ncode=code-P[p]*2-P[maxn];
dfs(p,!can,ncode);if(ok)return;
A[p]+=2;
}
}
void Solve()
{
ull ret=0;
rep(i,maxn)
{
scanf("%d",A+i);
ret*=seed;ret+=A[i];
}
ret*=seed;ret+=1;
S.clear();
ok=false;
dfs(0,true,ret);
if(ok)puts("Yes");
else puts("No");
}
int main()
{
//freopen("in","r",stdin);
P[0]=1;rep(i,maxn)P[i+1]=P[i]*seed;
int t;cin>>t;rep(i,t)Solve();
}

士兵占领

士兵占领

Time Limit:10000MS  Memory Limit:65536K
Total Submit:48 Accepted:32
Case Time Limit:1000MS

Description

有一个M * N的棋盘,有的格子是障碍。现在你要选择一些格子来放置一些士兵,一个格子里最多可以放置一个士兵,障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘 当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。

Input

第一行两个数M, N, K分别表示棋盘的行数,列数以及士兵的个数。
第二行有M个数表示Li。
第三行有N个数表示Ci。
接下来有K行,每行两个数X, Y表示(X, Y)这个格子是障碍。

Output

输出一个数表示最少需要使用的士兵个数。如果无论放置多少个士兵都没有办法占领整个棋盘,输出”JIONG!” (不含引号)

Sample Input

4 4 4
1 1 1 1
0 1 0 3
1 4
2 2
3 3
4 3

Sample Output

4
数据范围
M, N <= 100, 0 <= K <= M * N

Source

哎。。我太SB了。。这题我问了glassices神牛才知道怎么做。。神牛真是太强大了!!
Orz!!!!!
恩。。我一看到这个题目。。第一反应就是网络流。。然后立马感觉到Li和Ci就是所谓的下届,
然后想到上下界网络最小流囧。。。
感觉非常繁琐啊。。然后神牛告诉我说要转化一下。。
先把棋盘放满,如果不能满足就囧了。。
然后可以发现每个行和列能拿掉的最大值就知道了。。
然后最少数=全部数-最多能拿掉几个。。
就成最大流了囧。。
Code:
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxv=200+10,maxn=100;
using namespace std;
int vs,vt,n,m,k,v,ans=0;
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];
}
bool M[maxn][maxn]={};
int L[maxn],C[maxn];
void Fail()
{
puts("JIONG!");
exit(0);
}
void Init()
{
cin>>n>>m>>k;v=n+m;vs=v++;vt=v++;
rep(i,n)cin>>L[i];
rep(i,m)cin>>C[i];
int x,y;
rep(i,k)
{
scanf("%d%d",&x,&y);–x;–y;
M[x][y]=true;
}
rep(i,n)rep(j,m)if(!M[i][j])L[i]–,C[j]–,ans++;
rep(i,n)if(L[i]>0)Fail();
rep(i,m)if(C[i]>0)Fail();
}
void BuildGraph()
{
rep(i,n)AddEdge(vs,i,-L[i]);
rep(j,m)AddEdge(j+n,vt,-C[j]);
rep(i,n)rep(j,m)if(!M[i][j])
AddEdge(i,j+n,1);
}
bool vis[maxv]={};
int dfs(int no,int m)
{
if(no==vt)return m;
vis[no]=true;
for(Edge*e=E[no];e;e=e->next)if(!vis[e->t]&&e->c)
if(int d=dfs(e->t,min(m,e->c)))
return e->c-=d,e->op->c+=d,d;
return 0;
}
int CalFlow()
{
int flow=0;
do
{
memset(vis,0,sizeof vis);
int d=dfs(vs,inf);
if(d)flow+=d;
else break;
}while(1);
return flow;
}
int main()
{
//freopen("in","r",stdin);
Init();
BuildGraph();
cout<<ans-CalFlow()<<endl;
}

Page 1 of 41234