Boleyn Su's Blog – 第 13 页

USACO[Elite 2010 March Competition/gold]gather

恩，直接DFS，注意用long long int，我就是开始没用long long int，结果错了几次。

思路：

先找一个节点DFS，把树变成有根树，然后统计每个节点的子孙和自己一共有多少牛，记为cow[节点编号]，一共有多少牛，记为total_cow，以及全部牛到这个叶子节点所需的花费，记为cost[节点编号]。

然后再DFS，还是从先前找的的叶子开始。

当搜到root时cost[children of root]=cost[root]+(cow_total-cow[children of root])*length(from root to children of root)-cow[children of root])*length(from root to children of root)。

解释：cost[root]是到当前节点集合的费用，如果到孩子那里去集合，那么就要把从孩子哪儿赶来的牛赶回去，所以-cow[children of root])*length(from root to children of root)，然后还要把不是在孩子及其子孙那里的牛赶过来，所以+(cow_total-cow[children of root])*length(from root to children of root)。

CODE:

PROG: gather

LANG: C++

ID: boleyn.2

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-23

DESCRIPTION:

TITLE: Great Cow Gathering [Jeffrey Wang from a contest, 2010]

CONTENT:

Bessie is planning the annual Great Cow Gathering for cows all

across the country and, of course, she would like to choose the

most convenient location for the gathering to take place.

Each cow lives in one of N (1 <= N <= 100,000) different barns

(conveniently numbered 1..N) which are connected by N-1 roads in

such a way that it is possible to get from any barn to any other

barn via the roads. Road i connects barns A_i and B_i (1 <= A_i <=

N; 1 <= B_i <= N) and has length L_i (1 <= L_i <= 1,000). The Great

Cow Gathering can be held at any one of these N barns. Moreover,

barn i has C_i (0 <= C_i <= 1,000) cows living in it.

When choosing the barn in which to hold the Cow Gathering, Bessie

wishes to maximize the convenience (which is to say minimize the

inconvenience) of the chosen location. The inconvenience of choosing

barn X for the gathering is the sum of the distances all of the

cows need to travel to reach barn X (i.e., if the distance from

barn i to barn X is 20, then the travel distance is C_i*20). Help

Bessie choose the most convenient location for the Great Cow

Gathering.

Consider a country with five barns with [various capacities] connected

by various roads of varying lengths. In this set of barns, neither

barn 3 nor barn 4 houses any cows.

1 3 4 5

@–1–@–3–@–3–@[2]

[1] |

@[1]

Bessie can hold the Gathering in any of five barns; here is the

table of inconveniences calculated for each possible location:

Gather —– Inconvenience ——

Location B1 B2 B3 B4 B5 Total

1 0 3 0 0 14 17

2 3 0 0 0 16 19

3 1 2 0 0 12 15

4 4 5 0 0 6 15

5 7 8 0 0 0 15

If Bessie holds the gathering in barn 1, then the inconveniences

from each barn are:

Barn 1 0 — no travel time there!

Barn 2 3 — total travel distance is 2+1=3 x 1 cow = 3

Barn 3 0 — no cows there!

Barn 4 0 — no cows there!

Barn 5 14 — total travel distance is 3+3+1=7 x 2 cows = 14

So the total inconvenience is 17.

The best possible convenience is 15, achievable at by holding the

Gathering at barns 3, 4, or 5.

PROBLEM NAME: gather

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single integer: C_i

* Lines N+2..2*N: Line i+N+1 contains three integers: A_i, B_i, and

L_i

SAMPLE INPUT (file gather.in):

1 3 1

2 3 2

3 4 3

4 5 3

OUTPUT FORMAT:

* Line 1: The minimum inconvenience possible

SAMPLE OUTPUT (file gather.out):

#include <stdio.h>

#include <vector>

using std::vector;

const long long int oo=1000000000000000000ll;

const int MAXN=100000;

int N;

long long int C[MAXN+1];

long long int A[MAXN-1],B[MAXN-1],L[MAXN-1];

vector<long long int> children[MAXN+1],length[MAXN+1];

long long int total_cow;

long long int cow[MAXN+1];

long long int cost[MAXN+1];

long long int answer;

void prepare(int root,int father_of_root=0)

{

total_cow+=C[root];

cow[root]+=C[root];

for (int i=0;i<children[root].size();i++)

if (children[root][i]!=father_of_root)

{

prepare(children[root][i],root);

cow[root]+=cow[children[root][i]];

cost[root]+=cost[children[root][i]]

+cow[children[root][i]]*length[root][i];

}

//printf(“cost and cow of %d : %d %d\n”,root,cost[root],cow[root]);

}

void get_answer(int root,int father_of_root=0)

{

//printf(“cost of %d: %d\n”,root,cost[root]);

if (cost[root]<answer) answer=cost[root];

for (int i=0;i<children[root].size();i++)

if (children[root][i]!=father_of_root)

{

cost[children[root][i]]=cost[root]

+(total_cow-cow[children[root][i]]*2)

*length[root][i];

get_answer(children[root][i],root);

}

void print(long long int long_long_int)

{

if (long_long_int>=10)

print(long_long_int/10);

printf(“%d”,int(long_long_int%10));

}

int main()

{

freopen(“gather.in”,“r”,stdin);

freopen(“gather.out”,“w”,stdout);

scanf(“%d\n”,&N);

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

scanf(“%d\n”,&C[i]);

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

scanf(“%d %d %d\n”,&A[i],&B[i],&L[i]);

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

{

children[A[i]].push_back(B[i]);

children[B[i]].push_back(A[i]);

length[A[i]].push_back(L[i]);

length[B[i]].push_back(L[i]);

}

int leaf;

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

if (children[i].size()==1)

{

leaf=i;

break;

}

prepare(leaf);

answer=oo;

get_answer(leaf);

printf(“%lld\n”,answer); //for Linux/Unix

printf(“%I64d\n”,answer); //for Windows

//for anywhere

print(answer);

printf(“\n”);

fclose(stdin);

fclose(stdout);

return 0;

}

USACO[Elite 2010 February Competition/gold]slowdown

起初一直纠结如何一一的将每头奶牛到达P[i]的停顿时间求出来，后来才发觉思路没对。

正确的做法是直接DFS搜到一个点就求到它所需的停顿时间。

具体做法：

设path为DFS过程中的栈，那么某个点的停顿时间就等于在这个栈中有几个牧场的所有者比当前牧场的所有者先出栏。

例如，对于上图（样例），如果出栏顺序为42153。

那么我们开始DFS，首先到1，栈：[1]，栈中没有比当前节点1先出栏的，所以到1这个牧场的牛无需停顿。

然后到4，栈：[1,4]，栈中没有比当前节点4先出栏的，所以到4这个牧场的牛无需停顿。

然后到2，栈：[1,4,2]，栈中比当前节点2先出栏的只有一个(4)，所以到2这个牧场的牛需停顿1次。

然后栈pop一下变成[1,4]。

然后到5，栈：[1,4,5]，栈中比当前节点5先出栏的有两个(1和4)，所以到5这个牧场的牛需停顿2次。

然后栈pop一下变成[1,4]，再pop一下，变成[1]。

然后到3，栈：[1,3]，在3前出栏的有一个(1)，所以到3这个牧场的牛需停顿1次。

所以输出：

具体实现有用到线段树。

CODE:

PROG: slowdown

LANG: C++

ID: boleyn.2

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-22

DESCRIPTION:

TITLE: Slowing down [Jelle van den Hooff, 2010]

CONTENT:

Every day each of Farmer John’s N (1 <= N <= 100,000) cows conveniently

numbered 1..N move from the barn to her private pasture. The pastures

are organized as a tree, with the barn being on pasture 1. Exactly

N-1 cow unidirectional paths connect the pastures; directly connected

pastures have exactly one path. Path i connects pastures A_i and

B_i (1 <= A_i <= N; 1 <= B_i <= N).

Cow i has a private pasture P_i (1 <= P_i <= N). The barn’s small

door lets only one cow exit at a time; and the patient cows wait

until their predecessor arrives at her private pasture. First cow

1 exits and moves to pasture P_1. Then cow 2 exits and goes to

pasture P_2, and so on.

While cow i walks to P_i she might or might not pass through a

pasture that already contains an eating cow. When a cow is present

in a pasture, cow i walks slower than usual to prevent annoying her

friend.

Consider the following pasture network, where the number between

parentheses indicates the pastures’ owner.

1 (3)

/ \

(1) 4 3 (5)

/ \

(2) 2 5 (4)

First, cow 1 walks to her pasture:

1 (3)

/ \

[1] 4* 3 (5)

/ \

(2) 2 5 (4)

When cow 2 moves to her pasture, she first passes into the barn’s

pasture, pasture 1. Then she sneaks around cow 1 in pasture 4 before

arriving at her own pasture.

1 (3)

/ \

[1] 4* 3 (5)

/ \

[2] 2* 5 (4)

Cow 3 doesn’t get far at all — she lounges in the barn’s pasture, #1.

1* [3]

/ \

[1] 4* 3 (5)

/ \

[2] 2* 5 (4)

Cow 4 must slow for pasture 1 and 4 on her way to pasture 5:

1* [3]

/ \

[1] 4* 3 (5)

/ \

[2] 2* 5* [4]

Cow 5 slows for cow 3 in pasture 1 and then enters her own private pasture:

1* [3]

/ \

[1] 4* 3*[5]

/ \

[2] 2* 5* [4]

FJ would like to know how many times each cow has to slow down.

PROBLEM NAME: slowdown

INPUT FORMAT:

* Line 1: Line 1 contains a single integer: N

* Lines 2..N: Line i+1 contains two space-separated integers: A_i and

B_i

* Lines N+1..N+N: line N+i contains a single integer: P_i

SAMPLE INPUT (file slowdown.in):

1 4

5 4

1 3

2 4

OUTPUT FORMAT:

* Lines 1..N: Line i contains the number of times cow i has to slow

down.

SAMPLE OUTPUT (file slowdown.out):

#include <stdio.h>

#include <vector>

using std::vector;

const int MAXN=100000;

int N;

int A[MAXN-1],B[MAXN-1];

int P[MAXN];

vector<int> children[MAXN+1];

int order[MAXN+1];

int counter[MAXN+1];

int segment_tree[MAXN<<2];

int ask(int pos,int L,int R,int root=1)

{

if (/*0<=L&&*/R<=pos) return segment_tree[root];

int LL=L,LR=(L+R)>>1,Lroot=root<<1;

int RL=LR+1,RR=R,Rroot=Lroot|1;

int get=0;

if (!(/*LR<0||*/pos<LL))

get+=ask(pos,LL,LR,Lroot);

if (!(/*RR<0||*/pos<RL))

get+=ask(pos,RL,RR,Rroot);

return get;

}

void insert(int pos,int L,int R,int inc,int root=1)

{

segment_tree[root]+=inc;

if (L==R) return;

int LL=L,LR=(L+R)>>1,Lroot=root<<1;

int RL=LR+1,RR=R,Rroot=Lroot|1;

if (LL<=pos&&pos<=LR)

insert(pos,LL,LR,inc,Lroot);

if (RL<=pos&&pos<=RR)

insert(pos,RL,RR,inc,Rroot);

}

void dfs_get_counter(int root,int father_of_root=0)

{

counter[root]=ask(order[root],0,N-1);

insert(order[root],0,N-1,+1);

for (int i=0;i<children[root].size();i++)

if (children[root][i]!=father_of_root)

dfs_get_counter(children[root][i],root);

insert(order[root],0,N-1,-1);

}

int main()

{

freopen(“slowdown.in”,“r”,stdin);

freopen(“slowdown.out”,“w”,stdout);

scanf(“%d\n”,&N);

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

scanf(“%d %d\n”,&A[i],&B[i]);

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

scanf(“%d\n”,&P[i]);

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

{

children[A[i]].push_back(B[i]);

children[B[i]].push_back(A[i]);

}

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

order[P[i]]=i;

dfs_get_counter(1);

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

printf(“%d\n”,counter[P[i]]);

fclose(stdin);

fclose(stdout);

return 0;

}

USACO[Elite 2010 February Competition/gold]ice

水水的BFS，说它水，是因为我用了STL，哈哈。

STL是个好东东！

CODE:

PROG: ice

LANG: C++

ID: boleyn.2

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-22

DESCRIPTION:

TITLE: Cows on Ice [Jelle van den Hooff, 2010]

CONTENT:

Bessie is ice skating on a large frozen lake modelled as a 2-dimensional

grid with coordinates in the range -1,000,000,000..1,000,000,000.

N (1 <= N <= 20,000) of the lake’s grid cells contain rocks

(conveniently numbered 1..N). The other cells contain slippery ice.

Since Bessie is not a very good skater, she traverses the lake’s

cells by pushing herself away from her current position near a rock

and sliding continuously in the same direction until she hits another

rock (stopping in the square before she hits the rock, of course).

Never good with complicated angles, Bessie can push herself only

straight north, east, south, or west. She can’t push herself through

the rock, of course, and thus generally has only three possible

directions to move.

Sliding is not without risks. Bessie must hit a rock or might end

up sliding for a very long time. She must aim her pushes carefully.

Consider the situation depicted below; Bessie wants to get to

location (x=5,y=1), which is east of her current location (. = ice,

* = rock, B = Bessie, G = goal). If she slides directly to the east,

she will slide past the location since she can stop only by

encountering a rock head on. One way to get to (5,1) is the following:

(a) (b) (c) (d)

4 …..*. …..*. …..*. …..*.

3 ..*…. slide ..*…. slide ..*…. slide ..*….

2 ……* north ..B…* east …..B* south ……*

1 .*B..G. ——> .*…G. ——> .*…G. ——> .*…B.

0 *….*. *….*. *….*. *….*.

0123456

Bessie could slide north, east, or south in situation (a), but only

north has a rock for stopping. For situation (b), she can slide

only east for the same reason.

For the input, rock i is located at cell X_i,Y_i (-1,000,000,000

<= X_i <= 1,000,000,000; -1,000,000,000 <= Y_i <= 1,000,000,000),

and no two rocks occupy the same position. Bessie starts at Bx,By

(which is next to a rock) (-1,000,000,000 <= Bx <= 1,000,000,000;

-1,000,000,000 <= By <= 1,000,000,000). Bessie’s goal is Gx,Gy

(-1,000,000,000 <= Gx <= 1,000,000,000; -1,000,000,000 <= Gy <=

1,000,000,000). Bessie can always reach the goal one way or another.

Bessie doesn’t mind sliding. However, pushing herself away from a

rock is very tiring. To prepare her, FJ would like to know the

minimum number of pushes Bessie needs to do.

PROBLEM NAME: ice

INPUT FORMAT:

* Line 1: Five space separated integers: N, Bx, By, Gx, and Gy

* Lines 2..N+1: Line i+1 describes a rock location with space

separated integers: X_i and Y_i

SAMPLE INPUT (file ice.in):

6 2 1 5 1

5 4

2 3

1 1

6 2

5 0

0 0

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum number of pushes for

Bessie to get to her goal

SAMPLE OUTPUT (file ice.out):

#include <stdio.h>

#include <set>

using std::set;

#include <map>

using std::map;

#include <queue>

using std::queue;

using std::pair;

using std::make_pair;

const int MAXN=20000;

int N,Bx,By,Gx,Gy;

int X[MAXN],Y[MAXN];

int main()

{

freopen(“ice.in”,“r”,stdin);

freopen(“ice.out”,“w”,stdout);

scanf(“%d %d %d %d %d\n”,&N,&Bx,&By,&Gx,&Gy);

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

scanf(“%d %d\n”,&X[i],&Y[i]);

map<int,set<int> > x;

map<int,set<int> > y;

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

{

x[X[i]].insert(Y[i]);

y[Y[i]].insert(X[i]);

}

set<pair<int,int> > inq;

queue<pair<pair<int,int>,int> > q;

inq.insert(make_pair(Bx,By));

q.push(make_pair(make_pair(Bx,By),0));

for (;;)

{

int get_x=q.front().first.first,

get_y=q.front().first.second;

//printf(“get:%d %d value%d\n”,get_x,get_y,q.front().second);

if (get_x==Gx&&get_y==Gy) break;

map<int,set<int> >::iterator xit=x.find(get_x),yit=y.find(get_y);

set<int>::iterator it;

if (xit!=x.end())

{

it=xit->second.upper_bound(get_y);

if (it!=xit->second.end())

if (inq.find(make_pair(get_x,*it-1))==inq.end())

{

q.push(make_pair(make_pair(get_x,*it-1),q.front().second+1));

inq.insert(make_pair(get_x,*it-1));

}

if (it!=xit->second.begin())

{

it–;

if (inq.find(make_pair(get_x,*it+1))==inq.end())

{

q.push(make_pair(make_pair(get_x,*it+1),q.front().second+1));

inq.insert(make_pair(get_x,*it+1));

}

if (yit!=y.end())

{

it=yit->second.upper_bound(get_x);

if (it!=yit->second.end())

if (inq.find(make_pair(*it-1,get_y))==inq.end())

{

q.push(make_pair(make_pair(*it-1,get_y),q.front().second+1));

inq.insert(make_pair(*it-1,get_y));

}

if (it!=yit->second.begin())

{

it–;

if (inq.find(make_pair(*it+1,get_y))==inq.end())

{

q.push(make_pair(make_pair(*it+1,get_y),q.front().second+1));

inq.insert(make_pair(*it+1,get_y));

}

q.pop();

}

printf(“%d\n”,q.front().second);

fclose(stdin);

fclose(stdout);

return 0;

}

USACO[Elite 2010 February Competition/gold]corral

今天准备四月的USACO金组月赛（第一次有资格参加，当然要准备一下），所以找了这场金组的题目来做。

然后，废话到此为止。

首先，第一题和APIO2009的会议中心一题有些像（不过现在我还没做出它），要用到一点贪心。

我的程序中最开始写的是动态规划，但是会TLE13（没想到数据会这么变态），后来改了一下，就AC了。但其实还可以优化的，不过我很懒。

然后看图：

很明显如果我们有红线，那么蓝线和灰线可以直接删除掉。即一条线如果被包含，那么选包含它的线一定比选它优。通过这一步操作后，所有线段的关系都像绿线和红线一样了。即他们不相互包含。最后，我们得到了一些线段，他们的左端点排成升序后，右端点也是升序。

然后，我们继续贪心，看图：

显然如果我们选了红线那么下一条线一定选深红的线，因为前面已经保证了左端点和右端点都为升序，所以贪心是对的。然后这一步就是选一条右端点最远，而左端点与已选线段相交的线。

通过预处理，这个操作可以O(1)，如果不是很贪心（比如我），现在就可以枚举一个地方把环切成链，然后做出。

如果还要贪心点，可以标记一下在已枚举的线段中的最优决策里被选中的线段，下次不枚举它。

那么可以O(n)求出最优，当然，由于前面的快排已经O(nlogn)了。所以，时间复杂度为O(nlogn)。

CODE:

PROG: corral

LANG: C++

ID: boleyn.2

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-22

DESCRIPTION:

TITLE: Covering the Corral [Richard Peng, 2009]

CONTENT:

The cows are so modest they want Farmer John to install covers

around the circular corral where they occasionally gather. The

corral has circumference C (1 <= C <= 1,000,000,000), and FJ can

choose from a set of M (1 <= M <= 100,000) covers that have fixed

starting points and sizes. At least one set of covers can surround

the entire corral.

Cover i can be installed at integer location x_i (distance from

starting point around corral) (0 <= x_i < C) and has integer length

l_i (1 <= l_i <= C).

FJ wants to minimize the number of segments he must install. What

is the minimum number of segments required to cover the entire

circumference of the corral?

Consider a corral of circumference 5, shown below as a pair of

connected line segments where both ‘0’s are the same point on the

corral (as are both 1’s, 2’s, and 3’s).

Three potential covering segments are available for installation:

Start Length

i x_i l_i

1 0 1

2 1 2

3 3 3

0 1 2 3 4 0 1 2 3 …

corral: +—+—+—+—+–:+—+—+—+- …

11111 1111

22222222 22222222

333333333333

|………………|

As shown, installing segments 2 and 3 cover an extent of (at least)

five units around the circumference. FJ has no trouble with the

overlap, so don’t worry about that.

PROBLEM NAME: corral

INPUT FORMAT:

* Line 1: Two space-separated integers: C and M

* Lines 2..M+1: Line i+1 contains two space-separated integers: x_i

and l_i

SAMPLE INPUT (file corral.in):

5 3

0 1

1 2

3 3

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum number of segments

required to cover all segments of the circumference of the

corral

SAMPLE OUTPUT (file corral.out):

#include <stdio.h>

const int MAXM=100000;

int C,M;

int x[MAXM],l[MAXM];

int answer;

int right[MAXM];

int f[MAXM];

void quick_sort(int L,int R)

{

int x_mid=x[(L+R)>>1];

int l_mid=l[(L+R)>>1];

int i=L,j=R;

while (i<=j)

{

while ((x[i]<x_mid)||(x[i]==x_mid&&x[i]+l[i]>x_mid+l_mid)) i++;

while ((x[j]>x_mid)||(x[j]==x_mid&&x[j]+l[j]<x_mid+l_mid)) j–;

if (i<=j)

{

int swap;

swap=x[i];

x[i]=x[j];

x[j]=swap;

swap=l[i];

l[i]=l[j];

l[j]=swap;

i++;

j–;

}

if (L<j) quick_sort(L,j);

if (i<R) quick_sort(i,R);

}

int main()

{

freopen(“corral.in”,“r”,stdin);

freopen(“corral.out”,“w”,stdout);

scanf(“%d %d\n”,&C,&M);

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

scanf(“%d %d\n”,&x[i],&l[i]);

quick_sort(0,M-1);

for (int i=0,j=0;j<M;)

{

x[i]=x[j];

l[i]=l[j];

j++;

while ((x[i]+l[i]>=x[j]+l[j])&&(j<M)) j++;

i++;

if (j>=M) M=i;

}

//for (int i=0;i<M;i++)

// printf(“%d %d\n”,x[i],x[i]+l[i]);

for (int i=M-1,j=M-1;i>=0;i–)

{

while ((x[j]>x[i]+l[i])&&(j>=0)) j–;

right[i]=j;

}

answer=MAXM;

for (int begin=M-1;;begin–)

{

if (x[begin]+l[begin]<C) break;

int X=x[begin]+l[begin]-C;

int L=x[begin]-X;

if (L<=0)

{

answer=1;

break;

}

//printf(“begin:%d\n”,begin);

//printf(“X=%d X+L=%d\n”,X,X+L);

f[begin]=1;

for (int i=begin-1,j=begin;i>=0;i–)

{

//while (x[j]>x[i]+l[i]) j–;

//printf(“i%d j%d\n”,i,j);

f[i]=f[right[i]]+1;

//f[i]=f[j];

//for (int k=j;k>i;k–)

// if (f[i]>f[k])

// f[i]=f[k];

//f[i]++;

if (x[i]<=X)

{

if (answer>f[i]) answer=f[i];

//printf(“begin:%d f[%d]=%d\n”,begin,i,f[i]);

break;

}

printf(“%d\n”,answer);

fclose(stdin);

fclose(stdout);

return 0;

}

APIO2008[免费道路/roads]

先计算至少需要多少鹅卵石路才能使得图连通，设为A，再计算总共有多少鹅卵石路，设为B。有解当且仅当A<=K<=B。

如果有解，先将必须的鹅卵石路加入，然后再加入一些鹅卵石路，使得一共加入了K条鹅卵石路。（注意，它们不能成环）。然后再加公路，同样不能成环。

然后，需要用到并查集。

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-21

DESCRIPTION:

$DESCRIPTION

#include <stdio.h>

#include <string.h>

#define MAXN 20000

#define MAXM 100000

//begin set

int set[MAXN];

int get_set(int u)

{

if (set[u]) return set[u]=get_set(set[u]);

else return u;

}

int is_friend(int u,int v)

{

return get_set(u)==get_set(v);

}

void union_set(int u,int v)

{

//if (is_friend(u,v)) return;

set[get_set(u)]=get_set(v);

}

//end set

struct Edge{int u,v,c;};

int N,M,K;

Edge edge[MAXM];

bool must[MAXM];

int top;

Edge print[MAXN];

int main()

{

//freopen(“roads.in”,”r”,stdin);

//freopen(“roads.out”,”w”,stdout);

scanf(“%d %d %d\n”,&N,&M,&K);

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

scanf(“%d %d %d\n”,&edge[i].u,&edge[i].v,&edge[i].c);

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

if (edge[i].c)

if (!is_friend(edge[i].u,edge[i].v))

union_set(edge[i].u,edge[i].v);

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

if (!edge[i].c)

if (!is_friend(edge[i].u,edge[i].v))

{

union_set(edge[i].u,edge[i].v);

must[i]=true;

print[top++]=edge[i];

}

if (top>=K) printf(“no solution\n”);

else

{

memset(set,0,sizeof(set));

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

if (must[i])

if (!is_friend(edge[i].u,edge[i].v))

union_set(edge[i].u,edge[i].v);

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

if (!must[i])

if (!is_friend(edge[i].u,edge[i].v))

{

union_set(edge[i].u,edge[i].v);

print[top++]=edge[i];

}

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

printf(“%d %d %d\n”,print[i].u,print[i].v,print[i].c);

}

//fclose(stdin);

//fclose(stdout);

return 0;

}

APIO2008[珠链交换器/beads]

就是记录一下每个球的路径。

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-21

DESCRIPTION:

$DESCRIPTION

#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

//LIB

int getNumQuestions()

{

int Q;

scanf(“%d\n”,&Q);

return Q;

}

void getQuestion(int& K, int& J)

{

scanf(“%d %d\n”,&K,&J);

}

void answer(int x)

{

printf(“%d\n”,x);

}

//END LIB

struct Record{int ball,pos,where;};

#define MAXN 300000

#define MAXM 300000

int N,M;

int exchange[MAXM];

int ball[MAXN];

int counter;

Record data[MAXM*2+MAXN];

int begin[MAXN];

int end[MAXN];

int compare(const void* a,const void* b)

{

if (((Record*)a)->ball<((Record*)b)->ball)

return –1;

else if (((Record*)a)->ball>((Record*)b)->ball)

return 1;

else if ((((Record*)a)->pos)<(((Record*)b)->pos))

return –1;

else return 1;

}

void swap(int& a,int& b)

{

int s=a;

a=b;

b=s;

}

int getAnswer(int K,int J)

{

int l=begin[K],r=end[K];

while (l+1!=r)

{

int mid=(l+r)>>1;

if (data[mid].pos<=J) l=mid;

else r=mid;

}

return data[l].where;

}

void prepare()

{

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

ball[i]=i;

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

{

data[counter].ball=i;

data[counter].pos=0;

data[counter].where=i;

counter++;

}

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

{

data[counter].ball=ball[exchange[i]-1];

data[counter].pos=i+1;

data[counter].where=exchange[i];

counter++;

data[counter].ball=ball[exchange[i]];

data[counter].pos=i+1;

data[counter].where=exchange[i]-1;

counter++;

swap(ball[exchange[i]-1],ball[exchange[i]]);

}

qsort(data,counter,sizeof(Record),compare);

int pointer=0;

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

{

begin[i]=pointer;

while (data[pointer].ball==i) pointer++;

end[i]=pointer;

}

int main()

{

//freopen(“beads.in”,”r”,stdin);

//freopen(“beads.out”,”w”,stdout);

scanf(“%d %d\n”,&N,&M);

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

scanf(“%d\n”,&exchange[i]);

prepare();

int Q=getNumQuestions();

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

{

int K,J;

getQuestion(K,J);

answer(getAnswer(K-1,J)+1);

}

//fclose(stdin);

//fclose(stdout);

return 0;

}

APIO2007[数据备份/backup]

首先，很容易想到动态规划，然后，由于时间复杂度为O(n*k)，当然只能拿部分分。

所以，看了题解，用贪心法做。

然后，当k=1时，显然，我们贪最短的线段。

假设我们得到了k=n时的最优解，然后如何从n推到n+1呢？

看下图：

APIO2007[数据备份/backup]解题报告 - 天之骄子 - 天之骄子的家

（注：两绿框间的狭缝里是有小黑点的，图不是很清楚。）

现在已有8条蓝线，且这是最优的（我们假设哈，图画的不好，不像是最优的）。

那么，我们要加一条线，就只需将其中一个part的红与蓝换色，然后费用就是改变后的蓝线长度和减去原来的长度和。然后贪最小的来改色。

然后关于part的划分，一个part是指以红色线段开头且结尾也为红色线段，中间一红一蓝相隔的几条连续线段。

这样贪，从n=1贪到n=k，然后就完了。

具体实现需要用到二叉堆。

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-20

DESCRIPTION:

$DESCRIPTION

#include <fstream>

using std::ifstream;

using std::ofstream;

using std::endl;

#include <vector>

using std::vector;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::min;

#include <queue>

using std::priority_queue;

#include <iostream>

using std::cin;

using std::cout;

class Application

{

static const unsigned int oo=1000000000;

//ifstream cin;

//ofstream cout;

int n,k;

vector<unsigned int> s;

public:

Application(const char* input,const char* output)

//:cin(input),cout(output)

{

cin>>n>>k;

s.resize(n);

for (vector<unsigned int>::iterator it=s.begin();

it!=s.end();

it++)

cin>>*it;

}

int run()

{

int m=n-1;

vector<int> left(m+2);

vector<int> right(m+2);

vector<int> value(m+2);

vector<bool> deleted(m+2,false);

value[0]=oo;

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

{

left[i]=i-1;

right[i]=i+1;

value[i]=s[i]-s[i-1];

}

value[m+1]=oo;

priority_queue<pair<int,int>,

vector<pair<int,int> >,

std::greater<pair<int,int> > > q;

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

q.push(make_pair(value[i],i));

int answer=0;

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

{

while (deleted[q.top().second]) q.pop();

deleted[left[q.top().second]]=true;

deleted[right[q.top().second]]=true;

answer+=value[q.top().second];

value[q.top().second]

=value[left[q.top().second]]

+value[right[q.top().second]]

-value[q.top().second];

right[left[left[q.top().second]]]=left[right[right[q.top().second]]]=q.top().second;

left[q.top().second]=left[left[q.top().second]];

right[q.top().second]=right[right[q.top().second]];

q.push(make_pair(value[q.top().second],q.top().second));

q.pop();

}

cout<<answer<<endl;

return 0;

}

};

int main()

{

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

return app.run();

}

APIO2007[风铃/mobiles]

本来挺水的题，却花了我好久时间啊，后来发现是一个边界出错了。唉。

然后，这道题就是直接做就行了。

需要注意的是如果递归深度超过32，可以直接判断无解，避免数据中出现变态的链。

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-19

DESCRIPTION:

$DESCRIPTION

#include <stdio.h>

#define MAXN 100000

#define NOCHILD -1

#define MAXDEPTH 32

#define MAX(a,b) ((a)>(b)?(a):(b))

#define get_height(root) ((root)==NOCHILD?0:height[(root)])

#define get_have(root) ((root)==NOCHILD?0:have[(root)])

#define is_full(height,have) (((1<<height)-1)==have)

struct Tree{int left,right;};

int n;

Tree tree[MAXN];

int height[MAXN];

long long int have[MAXN];

bool noanswer;

int answer;

int dfs_get_height(int root,int depth=1)

{

if (depth>MAXDEPTH)

return noanswer=true;

if (root==NOCHILD) return 0;

else

{

int left_height=dfs_get_height(tree[root].left,depth+1);

int right_height=dfs_get_height(tree[root].right,depth+1);

return height[root]=MAX(left_height,right_height)+1;

}

long long int dfs_get_have(int root,int depth=1)

{

if (depth>MAXDEPTH)

return noanswer=true;

if (root==NOCHILD) return 0;

else

{

long long int left_have=dfs_get_have(tree[root].left,depth+1);

long long int right_have=dfs_get_have(tree[root].right,depth+1);

return have[root]=left_have+right_have+1;

}

bool dfs_judge(int root)

{

if (noanswer) return false;

if (root==NOCHILD) return true;

int left=tree[root].left;

int right=tree[root].right;

int left_height=get_height(left);

int right_height=get_height(right);

long long int left_have=get_have(left);

long long int right_have=get_have(right);

bool left_is_full=is_full(left_height,left_have);

bool right_is_full=is_full(right_height,right_have);

if (left_height==right_height)

{

if (left_is_full)

return dfs_judge(right);

else if (right_is_full)

{

answer++;

return dfs_judge(left);

}

else return false;

}

else if (left_height+1==right_height)

{

if (right_is_full)

{

answer++;

return dfs_judge(left);

}

else if (left_is_full)

{

answer++;

return dfs_judge(right);

}

else return false;

}

else if (left_height==right_height+1)

{

if (left_is_full)

return dfs_judge(right);

else if (right_is_full)

return dfs_judge(left);

else return false;

}

else return false;

}

int main()

{

//freopen(“mobiles.in”,”r”,stdin);

//freopen(“mobiles.out”,”w”,stdout);

scanf(“%d\n”,&n);

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

{

int l,r;

scanf(“%d %d\n”,&l,&r);

if (l>0) tree[i].left=l-1;

else tree[i].left=NOCHILD;

if (r>0) tree[i].right=r-1;

else tree[i].right=NOCHILD;

}

dfs_get_height(0);

dfs_get_have(0);

if (dfs_judge(0)) printf(“%d\n”,answer);

else printf(“-1\n”);

//fclose(stdin);

//fclose(stdout);

return 0;

}

APIO2007[动物园/zoo]

先将小朋友和围栏变成链，具体做法是找个地方切开圈，然后因为是切开的，这里的状态要枚举。

然后做动态规划，可以用二进制数储存状态，当然，也可以不用。

用f[k][state]表示推到k位置且k位置的状态为state时的最优值，那么f[k][state]=MAX(f[k-1][pre_state])+inc。

然后解释一下state，这是一个二进制数，a[4]a[3]a[2]a[1]a[0]（a[i]=0或1），那么a[i]表示k+i位的动物是否被移走，1就移走，0就留下。

然后解释一下pre_state，pre_state可以推到state，即，若state=abcde，则pre_state=bcde0或bcde0。

然后解释一下inc，inc是increase的缩写，中文意思是增加，英文意思是increase。然后inc=看到的起始点为k并且被满足的孩子数。

然后，一步一步的推。

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-19

DESCRIPTION:

$DESCRIPTION

#include <stdio.h>

#include <string.h>

#include <time.h>

#define SIGHT 5

#define MAXC 50000

#define MAXN 10000

#define MAXK 2

#define K(k) ((k)%MAXK)

#define MAX(a,b) ((a)>(b)?(a):(b))

#define print(state,string)\

printf(“%s%d%d%d%d%d”,\

string,\

(((state)&(1<<4))>>4),\

(((state)&(1<<3))>>3),\

(((state)&(1<<2))>>2),\

(((state)&(1<<1))>>1),\

(((state)&(1<<0))>>0));

typedef unsigned bit;

struct Child{int pos;bit love,hate;};

int N,C;

Child children[MAXC];

int f[MAXK][1<<(SIGHT)];

int answer;

int main()

{

//freopen(“zoo.in”,”r”,stdin);

//freopen(“zoo.out”,”w”,stdout);

scanf(“%d %d\n”,&N,&C);

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

{

scanf(“%d “,&children[i].pos);

int love,hate;

scanf(“%d %d”,&love,&hate);

int pos;

for (int j=0;j<love;j++)

{

scanf(” %d”,&pos);

if (pos<children[i].pos) pos+=N;

children[i].love|=(1<<(pos-children[i].pos));

}

for (int j=0;j<hate;j++)

{

scanf(” %d”,&pos);

if (pos<children[i].pos) pos+=N;

children[i].hate|=(1<<(pos-children[i].pos));

}

scanf(“\n”);

//printf(“child%d’s data:\npos:%d\n”,i+1,children[i].pos);

//print(children[i].love,”love:”);printf(“\n”);

//print(children[i].hate,”hate:”);printf(“\n”);

}

for (int _start=0;_start<(1<<(SIGHT-1));_start++)

{

int start=_start<<1;

memset(f,0xf0,sizeof(f));

f[K(0)][start]=0;

int begin=0,end=-1;

for (int k=1;k<=N+1;k++)

{

while (children[begin].pos<k&&begin<C) begin++;

end=begin;

while (children[++end].pos==k) ;

for (int state=0;state<(1<<(SIGHT));state++)

{

int inc=0;

if (children[begin].pos==k)

for (int j=begin;j<end;j++)

if ((children[j].love&state)||(children[j].hate&(~state)))

inc++;

f[K(k)][state]=MAX(f[K(k-1)][(state<<1)&((1<<(SIGHT))-1)],

f[K(k-1)][((state<<1)|1)&((1<<(SIGHT))-1)])

+inc;

}

answer=MAX(f[K(N+1)][start>>1],answer);

}

printf(“%d\n”,answer);

//printf(“runing time:%d\n”,clock());

//fclose(stdin);

//fclose(stdout);

return 0;

}

APIO2009[抢掠计划/atm]

感觉和NOIP2009提高组第3题差不多，要强连通缩点，我用的是Tarjan算法，以前看不懂，现在才理解了。

然后再动态规划。

还有，就是数据很变态，单纯的递归过不了，要将之非递归化。

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-18

DESCRIPTION:

$DESCRIPTION

#include <stdio.h>

#define MAXN 500000

#define MAXM 500000

#define MIN(a,b) ((a)<(b)?(a):(b))

struct Link{Link* next;int to;};

int N,M;

Link* link[MAXN];

int money[MAXN];

int S,P;

bool isBar[MAXN];

int belong[MAXN];

void insert(int,int);

void tarjan(int);

int DP(int);

int main()

{

//freopen(“atm.in”,”r”,stdin);

//freopen(“atm.out”,”w”,stdout);

scanf(“%d %d\n”,&N,&M);

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

{

int u,v;

scanf(“%d %d\n”,&u,&v);

insert(u-1,v-1);

}

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

scanf(“%d\n”,&money[i]);

scanf(“%d %d\n”,&S,&P);

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

{

int pos;

if (i+1!=P) scanf(“%d “,&pos);

else scanf(“%d\n”,&pos);

isBar[pos-1]=true;

}

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

{

printf(“%d:”,root+1);

for (Link* i=link[root];i!=0;i=i->next)

printf(“%d “,i->to+1);

printf(“\n”);

}

tarjan(S-1);

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

if (belong[i]==i)

printf(“%d %d %d\n”,i+1,isBar[i],money[i]);

printf(“%d\n”,DP(S-1));

//fclose(stdin);

//fclose(stdout);

return 0;

}

void insert(int u,int v)

{

static int pool_counter;

static Link pool[MAXM*4];

pool[pool_counter].to=v;

pool[pool_counter].next=link[u];

link[u]=&pool[pool_counter++];

}

void tarjan(int start)

{

static int DFN[MAXN];

static int LOW[MAXN];

static int stamp;

static int stack[MAXN];

static bool instack[MAXN];

static int top;

static bool visited[MAXN];

static int depth;

static Link* i[MAXN];

static int root[MAXN];

i[depth]=link[root[depth]=start];

DFN[root[depth]]=LOW[root[depth]]=++stamp;

instack[stack[top++]=root[depth]]=true;

visited[root[depth]]=true;

{

//printf(“root=%d LOW=%d DFN=%d\n”,root[depth]+1,LOW[root[depth]],DFN[root[depth]]);

if (i[depth])

{

if (!visited[i[depth]->to])

{

i[depth+1]=link[root[depth+1]=i[depth]->to];

DFN[root[depth+1]]=LOW[root[depth+1]]=++stamp;

instack[stack[top++]=root[depth+1]]=true;

visited[root[depth+1]]=true;

i[depth]=i[depth]->next;

depth++;

}

else if (instack[i[depth]->to])

{

LOW[root[depth]]=MIN(LOW[root[depth]],DFN[i[depth]->to]);

i[depth]=i[depth]->next;

}

else i[depth]=i[depth]->next;

}

else

{

if (LOW[root[depth]]==DFN[root[depth]])

{

//printf(“GET:”);

//do instack[stack[–top]]=false,printf(“%d “,stack[top]+1);

//while (stack[top]!=root[depth]);

//printf(“\n”);

{

instack[stack[–top]]=false;

if (isBar[stack[top]])

isBar[root[depth]]=true;

if (stack[top]!=root[depth])

money[root[depth]]+=money[stack[top]];

belong[stack[top]]=root[depth];

for (Link* j=link[stack[top]];j!=0;j=j->next)

insert(root[depth],j->to);

}

while (stack[top]!=root[depth]);

}

if (depth>0)

LOW[root[depth-1]]=MIN(LOW[root[depth-1]],LOW[root[depth]]);

depth–;

}

while (depth>=0);

}

/*BACKUP 1ST VERSION

void tarjan(int root)

{

static int DFN[MAXN];

static int LOW[MAXN];

static int stamp;

static int stack[MAXN];

static bool instack[MAXN];

static int top;

static bool visited[MAXN];

DFN[root]=LOW[root]=++stamp;

instack[stack[top++]=root]=true;

visited[root]=true;

for (Link* i=link[root];i!=0;i=i->next)

if (!visited[i->to])

{

tarjan(i->to);

LOW[root]=MIN(LOW[root],LOW[i->to]);

}

else if (instack[i->to])

LOW[root]=MIN(LOW[root],DFN[i->to]);

if (LOW[root]==DFN[root])

{

instack[stack[–top]]=false;

if (isBar[stack[top]])

isBar[root]=true;

if (stack[top]!=root)

money[root]+=money[stack[top]];

belong[stack[top]]=root;

for (Link* j=link[stack[top]];j!=0;j=j->next)

insert(root,j->to);

}

while (stack[top]!=root);

//printf(“GET:”);

//do instack[stack[–top]]=false,printf(“%d “,stack[top]+1);

//while (stack[top]!=root);

//printf(“\n”);

}

int DP(int start)

{

static bool calced[MAXN];

static int MAX[MAXN];

start=belong[start];

if (!calced[start])

{

calced[start]=true;

for (Link* i=link[start];i!=0;i=i->next)

if (MAX[start]<DP(i->to))

MAX[start]=DP(i->to);

if (MAX[start]) MAX[start]+=money[start];

else if (isBar[start]) MAX[start]=money[start];

}

return MAX[start];

}