下面开始题解：
P60. 美丽的中国结
题目背景
kitty刚刚高三毕业.看到同学们都回家的回家,旅游的旅游,她的心里有些落寞.英俊潇洒风流倜傥迷倒万千KL却仅对kitty感冒的fish看在眼里,急在心里.一天,fish提出和kitty两个人一起外出旅游.kitty犹豫了几天,想好能瞒过家长的理由后（要问是什么……自己猜去）,答应了.fish很高兴地带着kitty去登记了（别想歪,登记旅游团而已……）,日照青岛五日游.当然啦,他们玩得很高兴.虽然这次旅行是fish先提议的,但kitty因为玩得很畅快（刚高考完嘛）,所以想送给fish一份礼物,一份能让见多识广的fish都无法忘怀的礼物.她从路边 9¾站台的某算命先生那里得知中国结具有增加RP的效果,而这正是fish所需要的,因此她决定动手给fish编一个奇特的中国结.
题目描述
中国结形式多样,fish会喜欢什么样的呢?思考几天后,kitty决定给fish编一个树状的中国结.这个中国结有n个结点（编号1,2,…,n）,这n个结点之间总共恰有n-1条线相连,其中结点1上是树的根.这是一个奇特的中国结,因此它的编织方式也很奇特.在编织过程中的每一步骤,kitty有时需要将一个结点子树里的所有结点i的状态全部取反（如果原来结点i已经打结,则解开i,否则将结点i打结）,有时又需要知道一个结点的子树里有多少已经打结的结点,你能帮助可爱的kitty完成这份礼物吗?
数据规模
对于40% 的数据,1≤n≤10000, 1≤m≤20000
对于100%的数据,1≤n≤100000, 1≤m≤100000
输入格式
输入第一行有个整数n,表示这个中国结有n个结点以下n-1行,每行有两个整数u和v(1≤u,v≤n),表示结点u和v间有一条线相连；再一行有个整数m,表示kitty要进行的步骤数以下m行,每行可能为:"C x":表示将结点x的子树中所有结点的状态取反（包括x）或"Q x":表示kitty想知道结点x的子树中有多少已经打结的结点（包括x）
输出格式
对于每个“Q x”输出一行整数,表示结点x的子树中有多少已经打结的结点（包括x）
样例输入
5
1 2
1 3
2 4
2 5
5
Q 1
C 1
Q 1
C 2
Q 1
样例输出
0
5
2
题解
这是 MM 群七夕模拟赛的一道题（这个模拟赛题目质量很高，建议一做），看到如此大数据范围的询问题，大家的第一反应肯定就是——这是一道数据结构题。的确，本题考的是线段树的操作。
我们对题目中的树进行一次 DFS，将遍历的顺序记录在线段树（下面简记作 A[]）中，并记录每个树节电进入和离开时在线段树中的位置（下面简记作 St[x] 和 End[x]），这样原题目中的树便映射到了我们定义的线段树上了。
后面就比较简单了，我们在每个线段树节电记录一个域：state[x]（节电状态）、sum[x]（子树打结数），题目中的两个操作即是对线段树作如下操作：
C x：
state[St[x]..End[x]] 全部取反
Q x：
询问 sum[St[x]..End[x]]
我采用的数组模拟线段树，空间复杂度 O(n)，时间复杂度 O(nlgn)
参考程序
注意：程序中用到自己实现的栈是因为在 RQNOJ 上提交时直接递归的 dfs 会栈溢出，调内存也没调好（现在想想可能是当时指令错了），于是我就自己模拟实现了一个栈。
program p60(input, output);
const
maxn = 100000;
var
ch, ch2: char;
First, Last, Next, E: array [0..maxn * 2] of longint;
StartPos, EndPos: array [1..maxn] of longint;
Sum: array [1..maxn * 4] of longint;
Visited: array [1..maxn] of boolean;
Sign: array [1..maxn * 4] of boolean;
STPoint, LL, RR, Answer, Len, EdgeCount, u, v, n, m, i: longint;
List: array [1..maxn] of record
u, q: longint
end;
flag: boolean;
procedure addEdge(u, v: longint);
begin
inc(EdgeCount);
Next[Last[u]] := EdgeCount;
Last[u] := EdgeCount;
E[EdgeCount] := v;
if First[u] = 0 then
First[u] := EdgeCount
end;
procedure Maintain(k, l, r: longint);
var
mid, lc, rc: longint;
begin
if Sign[k] then
begin
Sign[k] := false;
if l < r then
begin
lc := k shl 1;
rc := lc + 1;
mid := (l + r) shr 1;
Sign[lc] := not sign[lc];
Sign[rc] := not sign[rc];
Sum[lc] := mid - l + 1 - Sum[lc];
Sum[rc] := r - mid - Sum[rc]
end
end
end;
procedure Change(k, l, r: longint);
var
mid: longint;
begin
if (LL <= l) and (r <= RR) then
begin
Sign[k] := not Sign[k];
Sum[k] := r - l + 1 - Sum[k]
end
else
begin
mid := (l + r) shr 1;
Maintain(k, l, r);
if LL <= mid then
Change(k shl 1, l, mid);
if mid + 1 <= RR then
Change(k shl 1 + 1, mid + 1, r);
Sum[k] := Sum[k shl 1] + Sum[k shl 1 + 1]
end
end;
procedure Question(k, l, r: longint);
var
mid: longint;
begin
if (LL <= l) and (r <= RR) then
inc(Answer, Sum[k])
else
begin
mid := (l + r) shr 1;
Maintain(k, l, r);
if LL <= mid then
Question(k shl 1, l, mid);
if mid + 1 <= RR then
Question(k shl 1 + 1, mid + 1, r)
end
end;
procedure Push(uu, qq: longint);
begin
inc(STPoint);
with List[STPoint] do
begin
u := uu;
q := qq
end
end;
procedure Pop;
begin
dec(STPoint)
end;
begin
fillchar(First, sizeof(First), 0);
fillchar(Last, sizeof(Last), 0);
fillchar(Next, sizeof(Last), 0);
fillchar(Visited, sizeof(Visited), 0);
fillchar(Sign, sizeof(Sign), 0);
fillchar(Sum, sizeof(Sum), 0);
EdgeCount := 0;
readln(n);
for i := 1 to n - 1 do
begin
readln(u, v);
addEdge(u, v);
addEdge(v, u)
end;
STPoint := 0;
Push(1, First[1]);
Visited[1] := true;
Len := 1;
StartPos[1] := Len;
while STPoint > 0 do
with List[STPoint] do
begin
flag := false;
while q > 0 do
if not Visited[E[q]] then
begin
Push(E[q], First[E[q]]);
Visited[E[q]] := true;
inc(Len);
StartPos[E[q]] := Len;
q := Next[q];
flag := true;
break
end
else
q := Next[q];
if not flag and (q = 0) then
begin
EndPos[u] := Len;
Pop
end
end;
readln(m);
for i := 1 to m do
begin
read(ch);
read(ch2);
readln(u);
LL := StartPos[u];
RR := EndPos[u];
if ch = 'C' then
Change(1, 1, n)
else
begin
Answer := 0;
Question(1, 1, n);
writeln(Answer)
end
end
end.
P113. 聪明的猴子
题目描述
在一个热带雨林中生存着一群猴子，它们以树上的果子为生。昨天下了一场大雨，现在雨过天晴，但整个雨林的地表还是被大水淹没着，部分植物的树冠露在水面上。猴子不会游泳，但跳跃能力比较强，它们仍然可以在露出水面的不同树冠上来回穿梭，以找到喜欢吃的果实。 现在，在这个地区露出水面的有N棵树，假设每棵树本身的直径都很小，可以忽略不计。我们在这块区域上建立直角坐标系，则每一棵树的位置由其所对应的坐标表示(任意两棵树的坐标都不相同)。 在这个地区住着的猴子有M个，下雨时，它们都躲到了茂密高大的树冠中，没有被大水冲走。由于各个猴子的年龄不同、身体素质不同，它们跳跃的能力不同。有的猴子跳跃的距离比较远(当然也可以跳到较近的树上)，而有些猴子跳跃的距离就比较近。这些猴子非常聪明，它们通过目测就可以准确地判断出自己能否跳到对面的树上。
【问题】
现已知猴子的数量及每一个猴子的最大跳跃距离，还知道露出水面的每一棵树的坐标，你的任务是统计有多少个猴子可以在这个地区露出水面的所有树冠上觅食。
输入格式
第1行为一个整数，表示猴子的个数M(2<=M<=500)； 第2行为M个整数，依次表示猴子的最大跳跃距离（每个整数值在1--1000之间）； 第3行为一个整数表示树的总棵数N(2<=N<=1000)； 第4行至第N+3行为N棵树的坐标（横纵坐标均为整数，范围为：-1000--1000）。 （同一行的整数间用空格分开）
输出格式
包括一个整数，表示可以在这个地区的所有树冠上觅食的猴子数。
样例输入
4
1 2 3 4
6
0 0
1 0
1 2
-1 -1
-2 0
2 2
样例输出
3
题解
这一题实际上是一道很基础的算法题，至于很少有人做出的原因很可能是题目未读懂。我们先来简单分析一下题意。
先对单一猴子进行考虑，我们将树网（暂且这么说吧）当作图中的节点，跳遍全部树即表示整个图连通。显然，这是一个平面图。那么跳遍这个平面图的节点所需要的跳跃距离至少是多少呢？
相信读者已经看出来了，这正是其最小生成树中最大边的长度！证明是很容易的，这里就不加赘述。
算法在实现时，我们首先计算出任意两树之间的距离，再使用 Kruskal 算法计算出最小生成树的最大边劝，再逐个比较每个猴子的跳跃距离即可。算法空间复杂度 O(n^2)，时间复杂度 O(n^2+m)。
当然求平面图的最小生成树还有更快的算法，这里略去。
参考程序
program p113(input, output);
const
maxm = 500;
maxn = 1000;
var
Count, sum, m, n, i, j, k: longint;
monkey: array [1..maxm] of longint;
tree: array [1..maxn] of record
x, y: longint
end;
Edge: array [1..maxn * maxn] of record
a, b: longint;
Length: extended
end;
ufs, size: array [1..maxn] of longint;
ma: extended;
function findset(u: longint): longint;
begin
if ufs[u] = 0 then
exit(u)
else
begin
ufs[u] := findset(ufs[u]);
exit(ufs[u])
end
end;
procedure union(a, b: longint);
var
u, v: longint;
begin
u := findset(a);
v := findset(b);
if size[u] <> s do
dec(j);
if i <= j then
begin
tt := Edge[i].Length;
Edge[i].Length := Edge[j].Length;
Edge[j].Length := tt;
t := Edge[i].a;
Edge[i].a := Edge[j].a;
Edge[j].a := t;
t := Edge[i].b;
Edge[i].b := Edge[j].b;
Edge[j].b := t;
inc(i);
dec(j)
end
until i > j;
if j > left then
qsort(left, j);
if i <> b then
exit(a)
else
exit(b)
end;
procedure Kruskal;
var
i, cc: longint;
begin
ma := 0;
cc := 0;
for i := 1 to Count do
if findset(Edge[i].a) <> findset(Edge[i].b) then
begin
ma := max(ma, Edge[i].Length);
union(Edge[i].a, Edge[i].b);
inc(cc);
if cc = n - 1 then
break
end
end;
begin
fillchar(ufs, sizeof(ufs), 0);
fillchar(size, sizeof(size), 0);
readln(m);
for i := 1 to m do
read(monkey[i]);
readln(n);
for i := 1 to n do
with tree[i] do
readln(x, y);
Count := 0;
for i := 1 to n - 1 do
for j := i + 1 to n do
begin
inc(Count);
with Edge[Count] do
begin
a := i;
b := j;
Length := sqrt(sqr(tree[i].x - tree[j].x) + sqr(tree[i].y - tree[j].y))
end
end;
qsort(1, Count);
Kruskal;
sum := 0;
for i := 1 to m do
if monkey[i] >= ma then
inc(sum);
writeln(sum)
end.
P218. 奥运手拉手
题目描述
奥运会即将来临，为了迎接奥运会，Wish 和同伴们一起进行了一场名叫“奥运手拉手”的游戏。这个游戏的规则是这样的：
1. Wish 和朋友们在一起共有 n 个人
2. 这 n 个人围坐一圈，从某一个人开始顺时针编号为 1-n
3. 从第一个人开始报数，每次从 1 开始报，每报到 m，就让那个人出列，然后继续从 1 开始报数
4. n - 1 个人出列后，最后留在圈中的那个人获得胜利
Wish 很想赢得游戏，而且，他认为特定位置的出列次序应该有某种数学上的联系，为了验证他的猜想，他需要一些实际的数据。但是众所周知 Wish 是个大大大菜鸟，他只会朴素的模拟，对于较大的 n 和 m 无法得出答案，于是他找到了参加信息学竞赛的你，你可以帮助他吗？
数据规模
1 <= m <= n <= 200000
0 <= k <= 1000
输入格式
第一行三个数：n, m, k第二行至第 k + 1 行：每行一个数 ai
输出格式
共 k + 1 行第一行一个数 d，为最后出列的人在游戏开始时的编号第二行至第 k + 1 行，每行一个数 bi，表示第 ai 个人在第 bi 轮报数时出列
题解
我都不好意思说这是难题了…………-_-，大家都知道这是 Josephus 问题，但是为什么都不会呢。。。。。。这一题我不想写题解，只帖上程序了。
参考程序
program p202(input, output);
const
maxn = 200000;
var
n, m, k, head, i, j, d, count: longint;
key, left, right, size: array [0..maxn] of longint;
List: array [1..maxn] of longint;
procedure MakeTree(const l, r, current: longint);
var
mid: longint;
begin
mid := (l + r) shr 1;
key[current] := mid;
if mid > l then
begin
inc(count);
left[current] := count;
MakeTree(l, mid - 1, count)
end
else
left[current] := 0;
if mid < r then
begin
inc(count);
right[current] := count;
MakeTree(mid + 1, r, count)
end
else
right[current] := 0;
size[current] := size[left[current]] + size[right[current]] + 1
end;
function select(const t, k: longint): longint;
begin
if k = size[left[t]] + 1 then
select := key[t]
else if k <= size[left[t]] then
select := select(left[t], k)
else
select := select(right[t], k - size[left[t]] - 1)
end;
function delete(var t: longint; const k: longint): longint;
begin
dec(size[t]);
if (key[t] = k) or ((k < key[t]) and (left[t] = 0)) or ((k > key[t]) and (right[t] = 0)) then
begin
delete := key[t];
if (left[t] = 0) or (right[t] = 0) then
t := left[t] + right[t]
else
key[t] := delete(left[t], key[t] + 1)
end
else
if k < key[t] then
delete := delete(left[t], k)
else
delete := delete(right[t], k)
end;
begin
size[0] := 0;
readln(n, m, k);
count := 1;
MakeTree(1, n, 1);
j := 0;
head := 1;
for i := 1 to n do
begin
j := (j + m - 1) mod (n - i + 1) + 1;
d := select(head, j);
dec(j);
delete(head, d);
List[d] := i
end;
writeln(d);
for i := 1 to k do
begin
readln(d);
writeln(List[d])
end
end.
PS：大家看到这么多的标程，请一定保重。。。。
没有评论:
发表评论