Boleyn Su's Blog – 第 21 页

开学了[2010年3月14日]

其实已经开学有三周了，可是才发觉已经开学了。走在校园里，看到同学们往来穿梭，看到篮球场的优美的抛物线，才发觉，真的，已经开学三周了。
开学后的第一周，是在机房里度过的。停课三天，让我失去了体会与同学重逢那种感觉的机会。每天与机器对话，虽然写的是我爱的程序，但总少了一些课堂里的那种热闹的气氛。开着的音响，放着的歌，渐渐的也会成为嘈杂的声响，把我做题的节拍打乱。是有一些想那些可爱的他与她，但竞赛，只有付出才有回报，而这付出，注定会让我失去很多东西，但，必定会让我得到快乐。
开学后的第一个星期六，是信息学奥林匹克竞赛重庆代表队选拔赛在一中举行的日子，也就是小学奥数老师所说的“养兵千日，用兵一时”的那“一时”了。和老师、同学会合后，我们一起进入了考场。内心忐忑，担心自己会想以前一样在关键的考试中考砸（小学的奥数和初中的希望杯都发挥得很差）。进入考场，我镇定了下来，喝了几口水，然后从容的看了一遍考卷。半小时后，我敲完了第一题的程序，我自信能AC（AC:即Accept，可以理解为得满分）。然后剩下的3题就顺利的做了，因为即使后面几题做得不太好，凭第1题的AC也差不多可以进队了。5小时后，考试结束。到食堂吃饭，吃不下，很激动。之后到考场外等成绩，前三题，我总分列第三，加上联赛，总分第一，但是令我失望的是老师讲第一题我0分。确定能进队后，我和同学离开了。
当天晚上，得知第一题数据出错，之前的分数不对，第一题，我AC了！
第二周，我完全沉浸在这胜利的的喜悦之中。从老师那里得知的数据，我看到了选拔赛的分数，我236分居第一，加上联赛分数总分456领先第二名100多分。很高兴，然后又是忙碌的投入竞赛事业中去了。
第三周，竞赛班的同学们陪着我度过了我的第十七个生日，我感觉自己很快乐。
三周，很快就过去了，却感觉自己脑中满是竞赛，不曾发觉已经开学很久了，已经是高二下期了。开学了，不能再像放假时那么自由的玩了，也不能像停课时那样自由。开学了，忙碌的学习未完待续。

URAL1028[Stars]

线段树，不习惯啊，写着很累。多亏有WSC的CODE做参考。

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-19

DESCRIPTION:

$DESCRIPTION

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

using std::find;

#include <cassert>

//using std::assert;

class Application

{

static const int oo=32000;

int N;

vector<pair<int,int> > point;

void insert(vector<int>& st,int where,int l,int r,int in)

{

if (l<=in&&in<=r) st[where-1]++;

if (l>=r) return;

int mid=(l+r)/2;

if (l<=in&&in<=mid) insert(st,where*2,l,mid,in);

if (mid+1<=in&&in<=r) insert(st,where*2+1,mid+1,r,in);

}

int ask(vector<int>& st,int where,int l,int r,int as)

{

if (r<=as) return st[where-1];

else

{

if (l>=r) return 0;

int mid=(l+r)/2;

int get=0;

if (l<=as) get+=ask(st,where*2,l,mid,as);

if (mid+1<=as) get+=ask(st,where*2+1,mid+1,r,as);

return get;

}

public:

Application()

{

cin>>N;

point.resize(N);

for (int i=0;i<N;i++)

cin>>point[i].first>>point[i].second;

}

int run()

{

vector<int> counter(N,0);

vector<int> st(oo*4);

for (int i=0;i<N;i++)

{

counter[ask(st,1,0,oo,point[i].first)]++;

insert(st,1,0,oo,point[i].first);

}

for (int i=0;i<N;i++)

cout<<counter[i]<<endl;

return 0;

}

};

int main()

{

Application app;

return app.run();

}

URAL1027[D++ Again]

水题，不说。

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-19

DESCRIPTION:

$DESCRIPTION

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

#include <cstdio>

//using std::EOF;

class Application

{

string file;

public:

Application()

{

char rc;

while ((rc=cin.get())!=EOF) file.push_back(rc);

}

int run()

{

bool comment=false;

int counter=0;

int last=~(1<<31);

bool answer=true;

for (int i=0;i<file.size();i++)

{

if (comment)

{

if (file[i]==’*’) last=i;

else if (file[i]==’)’&&last+1==i) comment=false;

}

else if (counter)

{

if (file[i]==’*’&&last+1==i)

{

counter–;

last=~(1<<31);

comment=true;

}

else if (file[i]==’)’)

{

counter–;

}

else if (file[i]=='(‘)

{

counter++;

last=i;

}

else

{

bool valid=false;

for (char* j=“=+-*/0123456789)(\n”;*j;j++)

if (file[i]==*j) valid=true;

if (!valid) answer=false;

}

else

{

if (file[i]=='(‘)

{

counter++;

last=i;

}

else if (file[i]==’)’)

{

answer=false;

}

if (comment||counter) answer=false;

cout<<(char*)(answer?“YES”:“NO”)<<endl;

return 0;

}

};

int main()

{

Application app;

return app.run();

}

USACO[Elite 2010 March Competition/silver]

USACO终于升到金组了。本来该满分的，但是。。。

有一道题，无解应该输出’NONE’，我输出’NONE.’，其实在比赛结束前就发现了的。不过我重传文件是可能传错了，所以WA一个点，总分960。

还有，WSC也升金组了，他也是960，同一个点WA，不过他是在无解的时候不输出。

一点点遗憾。

题目有点水，我觉得就只有第二题有意思点。

下面是我打的注释：

第一行是最先打的，我们猜guess个为true，那么保证得分min{abs{guess-t[i]-N}}，而要做的就是最大化它。即答案为max{min{abs{guess-t[i]-N},i=1 to K},guess=0 to N}。此时时间复杂度是O(K*N)。

太慢了，于是我写下了第二行和第三行注释。令d[i]=N-t[i]，那么要求的变成max{min{abs{guess-d[i]},i=1 to K},guess=0 to N}，其实这一步是没有多大用的，不过本人很喜欢abs(guess-d[i])，因为它有几何意义。即在数轴上guess到d[i]的距离。

然后,看图：

显然，无论guess在数轴的哪个位置，min{abs{guess-d[i]}一定等于离guess最近的两个点（或一个点）到guess的距离的最小值。所以我们只要把d[]排序一下下，就OK了。O(∩_∩)O~

下面贴代码（有改动，现在可以全部AC）。

CODE:

PROG: rocks

LANG: C++

ID: boleyn.2

TITLE: The Rock Game [Tom Conerly, 2010]

CONTENT:

Before the cows head home for rest and recreation, Farmer John wants

them to get some intellectual stimulation by playing a game.

The game board comprises N (1 <= N <= 15) identical holes in the

ground, all of which are initially empty. A cow moves by either

covering exactly one hole with a rock, or uncovering exactly one

previously covered hole. The game state is defined by which holes

are covered with rocks and which aren’t. The goal of the game is

for the cows to reach every possible game state exactly once and

then return to the state with all holes uncovered.

The cows have been having a tough time winning the game. Below is

an example of one of their games:

Holes

time 1 2 3

—————–

0 O O O Initially all of the holes are empty

1 O O X The cow covers hole 3

2 X O X The cow covers hole 1

3 X O O The cow uncovers hole 3

4 X X O The cow covers hole 2

5 O X O The cow uncovers hole 1

6 O X X The cow covers hole 3

7 X X X The cow covers hole 1

Now the cows are stuck! They must uncover one hole and no matter

which one they uncover they will reach a state they have already

reached. For example if they remove the rock from the second hole

they will reach the state (X O X) which they already visited at

time 2.

Below is an example of a valid solution for N=3 holes:

Holes

time 1 2 3

—————–

0 O O O Initial state: all of the holes are empty

1 O X O The cow covers hole 2

2 O X X The cow covers hole 3

3 O O X The cow uncovers hole 2

4 X O X The cow covers hole 1

5 X X X The cow covers hole 2

6 X X O The cow uncovers hole 3

7 X O O The cow uncovers hole 2

8 O O O The cow uncovers the 1st hole

which returns the game board to the start having, visited each state once.

The cows are tired of the game and want your help. Given N, create

a valid sequence of states that solves the game. If there are

multiple solutions return any one.

PROBLEM NAME: rocks

INPUT FORMAT:

* Line 1: A single integer: N

SAMPLE INPUT (file rocks.in):

OUTPUT FORMAT:

* Lines 1..2^N+1: A string of length N containing only ‘O’ and ‘X’

(where O denotes a uncovered hole and X denotes a covered

hole). The jth character in this line represents whether the

jth hole is covered or uncovered in this state. The first and

last lines must be all uncovered (all O).

SAMPLE OUTPUT (file rocks.out):

OOO

OXO

OXX

OOX

XOX

XXX

XXO

XOO

OOO

#include <fstream>

using std::ifstream;

using std::ofstream;

using std::endl;

#include <cstring>

using std::memset;

class Application

{

ifstream cin;

ofstream cout;

static const int MAXN=15;

int N;

bool print(int state)

{

for (int i=0;i<N;i++)

if ((1<<i)&state) cout<<‘X’;

else cout<<‘O’;

cout<<endl;

return true;

}

void dfs(int step,int state)

{

static bool visited[1<<MAXN];

static bool finished;

if (finished) return;

if (step==(1<<N)&&(!state))

{

finished=true;

print(state);

return;

}

if (!visited[state])

{

visited[state]=true;

for (int i=0;i<N;i++)

if (!finished) dfs(step+1,state xor (1<<i));

visited[state]=false;

}

if (finished) print(state);

}

public:

Application(char* input,char* output)

:cin(input),cout(output)

{

cin>>N;

}

~Application()

{

cin.close();

cout.close();

}

int run()

{

dfs(0,0);

return 0;

}

};

int main()

{

Application app(“rocks.in”,“rocks.out”);

return app.run();

}

PROG: teststr

LANG: C++

ID: boleyn.2

TITLE: Test Taking [Tom Conerly, 2010]

CONTENT:

Farmer John has to take his annual farming license test. The test

comprises N (1 <= N <= 1,000,000) true/false questions. After FJ’s

dismal performance on last year’s test Bessie wishes to help him.

Bessie has inside information that the number of questions whose

answer is true will be one of t_1, t_2, t_3,…, or t_K (0 <= t_i

<= N; 0 <= K <= 10,000) — even though Bessie has no information

about any answer to any specific question. Bessie wants to know the

best score that FJ is guaranteed achieve by exploiting this information

carefully, even if he doesn’t know the actual answers to any test

questions.

To demonstrate Bessie’s idea, consider a license test with N=6

questions where Bessie knows that the number of questions with the

answer ‘true’ is either 0 or 3. FJ can always get at least 3 answers

correct using logic like this: If FJ answers ‘false’ on every

question and there are 0 questions with the answer ‘true’ then he

will get all 6 correct. If there are 3 questions with the answer

‘true’ then he will get 3 answers correct. So as long as he marks

every answer as ‘false’ he is guaranteed to get at least 3 correct

without knowing any answer to the test questions.

On the other hand, consider what happens if FJ chooses an inferior

strategy: he guesses that some 3 answers are ‘true’ and the other

3 are ‘false’. If it turns out that NO answers are ‘true’ then FJ

will get 3 answers correct, the ones he guessed were false. If 3

answers are ‘true’ then FJ could get as few as 0 answers correct.

If he answered incorrectly on all 3 of that answers for which he

guessed ‘true’, and the other 3 (for which he guessed ‘false’) are

true, then he gets 0 correct answers. Even though FJ could get 3

correct in this case by guessing ‘false’ every time, he can not

always guarantee even 1 correct by guessing some 3 answers as ‘true’,

so this strategy can not guarantee getting any answer correct. FJ

should use the previous paragraph’s strategy.

Given Bessie’s inside information, determine the number of answers

FJ can always get correct using this information assuming he uses

it optimally.

PROBLEM NAME: teststr

INPUT FORMAT:

* Line 1: Two space-separated integers: N and K

* Lines 2..K+1: Line i+1 contains a single integer: t_i

SAMPLE INPUT (file teststr.in):

6 2

OUTPUT FORMAT:

* Line 1: A single integer, the best score FJ is guaranteed to achieve

SAMPLE OUTPUT (file teststr.out):

#include <fstream>

using std::ifstream;

using std::ofstream;

using std::endl;

#include <cstring>

using std::memset;

#include <algorithm>

using std::sort;

class Application

{

ifstream cin;

ofstream cout;

static const int MAXK=10000;

int N,K;

int t[MAXK+2];

inline int abs(int n)

{

return n>-n?n:-n;

}

public:

Application(char* input,char* output)

:cin(input),cout(output)

{

cin>>N>>K;

for (int i=1;i<=K;i++) cin>>t[i];

}

~Application()

{

cin.close();

cout.close();

}

int run()

{

//max{min{abs{guess+t[i]-N}}}

//d[i]=N-t[i]

//max{min{abs{guess-d[i]}}}

int d[MAXK+2];

for (int i=1;i<=K;i++)

d[i]=N-t[i];

sort(d+1,d+K+1);

int answer=0;

for (int i=1;i<=K;i++)

if (answer<(d[i+1]-d[i])/2) answer=(d[i+1]-d[i])/2;

if (answer<N-d[K]) answer=N-d[K];

if (answer<d[1]) answer=d[1];

cout<<answer<<endl;

int answer=0;

for (int guess=0;guess<=N;guess++)

{

int min=N;

for (int i=1;i<=K;i++)

{

//cout<<guess<<“,”<<i<<“=abs(“<<guess<<“+”<<t[i]<<“-“<<N<<“) “<<abs(guess+t[i]-N)<<endl;

if (abs(guess+t[i]-N)<min) min=abs(guess+t[i]-N);

}

cout<<guess<<“min=”<<min<<endl;

if (min>answer) answer=min;

}

cout<<answer<<endl;

return 0;

}

};

int main()

{

Application app(“teststr.in”,“teststr.out”);

return app.run();

}

PROG: sboost

LANG: C++

ID: boleyn.2

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-13

DESCRIPTION:

Need For Speed [Jeffrey Wang, 2007]

Bessie is preparing her race car for the upcoming Grand Prix, but

she wants to buy some extra parts to improve the car’s performance.

Her race car currently has mass M (1 <= M <= 1,000) and is able

to push itself forward with a force of F (1 <= F <= 1,000,000).

The Race Car Performance Store has N (1 <= N <= 10,000) parts

conveniently numbered 1..N. Bessie can buy as many or as few parts

as she wishes though the store stocks no more than one instance

of each part.

Part P_i adds force F_i (1 <= F_i <= 1,000,000) and has mass

M_i (1 <= M_i <= 1,000). Newton’s Second Law decrees that F =

MA, where F is force, M is mass, and A is acceleration. If Bessie

wants to maximize the total acceleration of her race car (and

minimize the mass otherwise), which extra parts should she choose?

Consider a race car with initial F=1500 and M=100. Four parts are

available for enhancement:

i F_i M_i

1 250 25

2 150 9

3 120 5

4 200 8

Adding just part 2, e.g., would result in an acceleration of

(1500+150)/(100+9) = 1650/109 = 15.13761.

Below is a chart of showing the acceleration for all possible

combinations of adding/not-adding the four parts (in column one,

1=part added, 0=part not added):

Parts Aggregate Aggregate

1234 F M F/M

0000 1500 100 15.0000

0001 1700 108 15.7407

0010 1620 105 15.4286

0011 1820 113 16.1062

0100 1650 109 15.1376

0101 1850 117 15.8120

0110 1770 114 15.5263

0111 1970 122 16.1475 <– highest F/M

1000 1750 125 14.0000

1001 1950 133 14.6617

1010 1870 130 14.3846

1011 2070 138 15.0000

1100 1900 134 14.1791

1101 2100 142 14.7887

1110 2020 139 14.5324

1111 2220 147 15.1020

Thus, the best additional part combination is parts 2, 3, and 4.

PROBLEM NAME: sboost

INPUT FORMAT:

* Line 1: Three space-separated integers: F, M, and N

* Lines 2..N+1: Line i+1 contains two space separated integers: F_i

and M_i

SAMPLE INPUT (file sboost.in):

1500 100 4

250 25

150 9

120 5

200 8

OUTPUT FORMAT:

* Lines 1..P: The index values of P extra parts, one per line, that

Bessie should add to her racecar. If she should not add any,

output ‘NONE’ (without quotes). The output should be given in

increasing order, so if the optimal set of parts is {2,4,6,7},

then the output should be in the order 2,4,6,7 and not, for

example, 4,2,7,6. Solutions will be unique.

SAMPLE OUTPUT (file sboost.out):

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

#include <fstream>

using std::ifstream;

using std::ofstream;

using std::endl;

#include <sstream>

using std::stringstream;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

struct Compare

{

bool operator()(const pair<int,pair<int,int> >& a,

const pair<int,pair<int,int> >& b)

{

return (long long int)(a.second.first)*(long long int)(b.second.second)

(long long int)(b.second.first)*(long long int)(a.second.second);

}

}compare;

class Application

{

ifstream cin;

ofstream cout;

int N;

pair<int,pair<int,int> > FM;

vector<pair<int,pair<int,int> > > fm;

public:

Application(char* input,char* output)

:cin(input),cout(output)

{

cin>>FM.second.first>>FM.second.second>>N;

fm.resize(N);

for (int i=0;i<N;i++)

{

cin>>fm[i].second.first>>fm[i].second.second;

fm[i].first=i+1;

}

int run()

{

sort(fm.begin(),fm.end(),compare);

int i=0;

while (compare(fm[i],FM)&&(i<fm.size()))

{

FM.second.first+=fm[i].second.first;

FM.second.second+=fm[i].second.second;

i++;

}

fm.resize(i);

if (i)

{

sort(fm.begin(),fm.end());

for (int i=0;i<fm.size();i++)

cout<<fm[i].first<<endl;

}

else cout<<“NONE”<<endl;

return 0;

}

};

int main()

{

Application app(“sboost.in”,“sboost.out”);

return app.run();

}

URAL1026[Questions and answers]

水题，不说。

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-18

DESCRIPTION:

$DESCRIPTION

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

class Application

{

int N;

vector<int> database;

int K;

vector<int> query;

public:

Application()

{

cin>>N;

database.resize(N);

for (int i=0;i<N;i++) cin>>database[i];

string s;

cin>>s;

cin>>K;

query.resize(K);

for (int i=0;i<K;i++) cin>>query[i];

}

int run()

{

sort(database.begin(),database.end());

for (int i=0;i<K;i++) cout<<database[query[i]-1]<<endl;

return 0;

}

};

int main()

{

Application app;

return app.run();

}

URAL1025[Democracy in danger]

水题，不说。

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-18

DESCRIPTION:

$DESCRIPTION

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

class Application

{

int K;

vector<int> vote;

public:

Application()

{

cin>>K;

vote.resize(K);

for (int i=0;i<K;i++) cin>>vote[i];

}

int run()

{

sort(vote.begin(),vote.end());

int answer=0;

for (int i=0;i<(K+1)/2;i++)

answer+=(vote[i]+1)/2;

cout<<answer<<endl;

return 0;

}

};

int main()

{

Application app;

return app.run();

}

URAL1024[Permutations]

水题，找环，然后，所有环的节点数求最小公倍数。（置换群的术语我不会O(∩_∩)O~）

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-18

DESCRIPTION:

$DESCRIPTION

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

class Application

{

int N;

vector<int> P;

int gcd(int a,int b)

{

return b?gcd(b,a%b):a;

}

int lmc(int a,int b)

{

return a/gcd(a,b)*b;

}

public:

Application()

{

cin>>N;

P.resize(N);

for (int i=0;i<N;i++)

{

cin>>P[i];

P[i]–;

}

int run()

{

vector<bool> visited(N,false);

int answer=1;

for (int i=0;i<N;i++)

if (!visited[i])

{

int j=i;

int counter=0;

while (!visited[j])

{

counter++;

visited[j]=true;

j=P[j];

}

answer=lmc(answer,counter);

}

cout<<answer<<endl;

return 0;

}

};

int main()

{

Application app;

return app.run();

}

URAL1023[Buttons]

简单的博弈。巨水。

求满足条件K mod (L+1)=0的最小L。

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-18

DESCRIPTION:

$DESCRIPTION

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

class Application

{

int K,L;

public:

Application()

{

cin>>K;

}

int run()

{

//K%(L+1)=0

for (L=2;L<K;L++)

if (!(K%(L+1))) break;

cout<<L%K<<endl;

return 0;

}

};

int main()

{

Application app;

return app.run();

}

URAL1022[Genealogical tree]

水题，拓扑排序，我用的O(N^3)的，懒得优化了。赶进度啊，没办法！

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-18

DESCRIPTION:

$DESCRIPTION

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

class Application

{

int N;

vector<vector<bool> > isChild;

public:

Application()

{

cin>>N;

isChild=vector<vector<bool> >(N,vector<bool>(N,false));

for (int i=0;i<N;i++)

{

int child;

for (;;)

{

cin>>child;

if (child) isChild[i][child-1]=true;

else break;

}

int run()

{

vector<bool> printed(N);

for (int i=0;i<N;i++)

{

for (int c=0;c<N;c++)

if (!printed[c])

{

bool haveFather=false;

for (int f=0;f<N;f++)

if ((!printed[f])&&(isChild[f][c]))

haveFather=true;

if (!haveFather)

{

cout<<c+1<<char(i+1==N?’\n’:’ ‘);

printed[c]=true;

break;

}

return 0;

}

};

int main()

{

Application app;

return app.run();

}

URAL1021[Sacrament of the sum]

水题。

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-18

DESCRIPTION:

$DESCRIPTION

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

class Application

{

static const int SUM=10000;

int aN,bN;

vector<int> a,b;

public:

Application()

{

cin>>aN;

a.resize(aN);

for (int i=0;i<aN;i++) cin>>a[i];

cin>>bN;

b.resize(bN);

for (int i=0;i<bN;i++) cin>>b[i];

}

int run()

{

bool have=false;

for (int i=0,j=0;i<aN;i++)

{

while (a[i]+b[j]>SUM) j++;

if (a[i]+b[j]==SUM) have=true;

}

cout<<(char*)(have?“YES”:“NO”)<<endl;

return 0;

}

};

int main()

{

Application app;

return app.run();

}