Boleyn Su's Blog – 第 13 页

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];

}

APIO2009[采油区域/oil]

用g[i][j]表示以(i,j)和(i-K+1,j-K+1)为两个顶点的正方形的价值，然后递推求之。

f1_1[i][j]表示以(1,1)和(i,j)为两个顶点的矩形内最大的K*K的方形的价值，递推求之。f1_N,fM_1,fM_N用相似的方法弄出来。

然后，进入主要的部分，分情况。因为我们需要三个方块，其实就是将油区整个分为3份，然后每份里找一个方块。不难发现，一共只有6种情况。如下图：

然后，利用先前的预处理，加上枚举分割线，就可以得出结果了。

然后，可能会发现TLE，这可能是因为读文件太慢了，可以自己用底层函数重写输入语句。

CODE:

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-17

DESCRIPTION:

$DESCRIPTION

#include <stdio.h>

#define MAXM 1500

#define MAXN 1500

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

#define update(who,with) if ((who)<(with)) {(who)=(with);}

int M,N,K;

int map[MAXM][MAXN];

int f[MAXM][MAXN];

int g[MAXM][MAXN];

int maxx[MAXM];

int maxy[MAXN];

int max[MAX(MAXM,MAXN)];

int f1_1[MAXM][MAXN];

int f1_N[MAXM][MAXN];

int fM_1[MAXM][MAXN];

int fM_N[MAXM][MAXN];

int answer;

void update_case1234(int,int);

void update_case5();

void update_case6();

bool isNumber[256];

void read(int& who)

{

char get;

who=0;

while (isNumber[get=getchar()]) who=who*10+get-‘0’;

}

int main()

{

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

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

isNumber[‘0’]

=isNumber[‘1’]

=isNumber[‘2’]

=isNumber[‘3’]

=isNumber[‘4’]

=isNumber[‘5’]

=isNumber[‘6’]

=isNumber[‘7’]

=isNumber[‘8’]

=isNumber[‘9’]

=true;

read(M);

read(N);

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

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

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

{

//scanf(“%d”,&map[i][j]);

//if (j+1==N) scanf(“\n”);

//else scanf(” “);

read(map[i][j]);

}

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

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

{

if (j>=K)

f[i][j]=f[i][j-1]+map[i][j]-map[i][j-K];

else if (j>0)

f[i][j]=f[i][j-1]+map[i][j];

else

f[i][j]=map[i][j];

//printf(“f[%d][%d]=%d\n”,i+1,j+1,f[i][j]);

if (i>=K)

g[i][j]=g[i-1][j]+f[i][j]-f[i-K][j];

else if (i>0)

g[i][j]=g[i-1][j]+f[i][j];

else

g[i][j]=f[i][j];

//printf(“g[%d][%d]=%d\n”,i+1,j+1,g[i][j]);

if (maxx[i]<g[i][j]) maxx[i]=g[i][j];

if (maxy[j]<g[i][j]) maxy[j]=g[i][j];

}

//for (int i=0;i<M;i++) printf(“maxx[%d]=%d\n”,i+1,maxx[i]);

//for (int j=0;j<N;j++) printf(“maxy[%d]=%d\n”,j+1,maxy[j]);

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

for (int j=K-1;j<N;j++)

{

f1_1[i][j]=g[i][j];

if (i>0) update(f1_1[i][j],f1_1[i-1][j]);

if (j>0) update(f1_1[i][j],f1_1[i][j-1]);

//printf(“f1_1[%d][%d]=%d\n”,i+1,j+1,f1_1[i][j]);

}

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

for (int j=N-K;j>=0;j–)

{

f1_N[i][j]=g[i][j+K-1];

if (i>0) update(f1_N[i][j],f1_N[i-1][j]);

if (j<N-1) update(f1_N[i][j],f1_N[i][j+1]);

//printf(“f1_N[%d][%d]=%d\n”,i+1,j+1,f1_N[i][j]);

}

for (int i=M-K;i>=0;i–)

for (int j=K-1;j<N;j++)

{

fM_1[i][j]=g[i+K-1][j];

if (i<M-1) update(fM_1[i][j],fM_1[i+1][j]);

if (j>0) update(fM_1[i][j],fM_1[i][j-1]);

//printf(“fM_1[%d][%d]=%d\n”,i+1,j+1,fM_1[i][j]);

}

for (int i=M-K;i>=0;i–)

for (int j=N-K;j>=0;j–)

{

fM_N[i][j]=g[i+K-1][j+K-1];

if (i<M-1) update(fM_N[i][j],fM_N[i+1][j]);

if (j<N-1) update(fM_N[i][j],fM_N[i][j+1]);

//printf(“fM_N[%d][%d]=%d\n”,i+1,j+1,fM_N[i][j]);

}

//CASE 1 2 3 4

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

for (int j=K-1;j<=N-K;j++)

update_case1234(i,j);

//CASE 5

update_case5();

//CASE 6

update_case6();

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

//fclose(stdin);

//fclose(stdout);

return 0;

}

void update_case1234(int a,int b)

{

//CASE 1

if (a<M-1&&b<N-1)

update(answer,f1_1[a][b]+f1_N[a][b+1]+fM_N[a+1][0]);

//CASE 2

if (a>0&&b<N-1)

update(answer,fM_1[a][b]+fM_N[a][b+1]+f1_N[a-1][0]);

//CASE 3

if (a<M-1&&b<N-1)

update(answer,f1_1[a][b]+fM_1[a+1][b]+fM_N[0][b+1]);

//CASE 4

if (a<M-1&&b>0)

update(answer,f1_N[a][b]+fM_N[a+1][b]+fM_1[0][b-1]);

}

void update_case5()

{

static int maxx3[4][MAXM];

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

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

if (i>=K&&maxx3[k][i-1]<maxx3[k-1][i-K]+maxx[i])

maxx3[k][i]=maxx3[k-1][i-K]+maxx[i];

else if (i<K&&maxx3[k][i-1]<maxx[i])

maxx3[k][i]=maxx[i];

else

maxx3[k][i]=maxx3[k][i-1];

//printf(“case5=%d\n”,maxx3[3][M-1]);

if (answer<maxx3[3][M-1]) answer=maxx3[3][M-1];

}

void update_case6()

{

static int maxy3[4][MAXN];

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

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

if (i>=K&&maxy3[k][i-1]<maxy3[k-1][i-K]+maxy[i])

maxy3[k][i]=maxy3[k-1][i-K]+maxy[i];

else if (i<K&&maxy3[k][i-1]<maxy[i])

maxy3[k][i]=maxy[i];

else

maxy3[k][i]=maxy3[k][i-1];

//printf(“case6=%d\n”,maxy3[3][N-1]);

if (answer<maxy3[3][N-1]) answer=maxy3[3][N-1];

}