为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
Asia-Pacific Informatics Olympiad
目录 |
[编辑] 简介
The Asia-Pacific Informatics Olympiad (APIO) is a new IOI-like competition for delegations within the South Asian / Western Pacific region. The contest will be held online, with students competiting at contest sites within their own country or area.
[编辑] APIO 2007
Starea Reports Studio APIO 2007 -Asia Pacific Informatics Olympiad Time：July 23rd ,2007 School：DQYZ Contact: xiaoxinghai [at] gmail.com 题目名称 Mobile Backup Zoo 题目时限 1s 1s 2s 内存限制 32M 32M 32M
[编辑] Problem 1 : 风铃
你准备给弟弟Ike 买一件礼物，但是，Ike 挑选礼物的方式很特别：他只喜欢那些能按照他的特有方式排成有序的东西。你准备给Ike 买一个风铃。风铃是一种多层的装饰品，一般挂在天花板上。每个风铃都包含一些由竖直的线连起来的水平杆。每根杆的两端都有线连接，下面或者挂着另一根水平杆，或者挂着一个玩具。为使你的弟弟满意，你需要选一个满足下面两个条件的风铃：
(1) 所有的玩具都在同一层(也就是说，每个玩具到天花板之间的杆的个数是一样的)或至多相差一层。
(2) 对于两个相差一层的玩具，左边的玩具比右边的玩具要更靠下一点。
风铃可以按照下面的规则重新排列：任选一根杆，将杆两端的线“交换”。也就是解开一根杆左右两端的线，然后将它们分别绑到杆的另一端。注意这个操作不会改变下面的杆上线的排列顺序。
由于你正在参加信息学奥林匹克的训练，所以你决定设计一个算法，判断能否通过重新排列，将一个给定的风铃变为Ike 喜欢的样子。考虑上面的例子，上图中的风铃满足条件(1)，却不满足条件(2)——最左边的那个玩具比它右边的要高。但是，我们可以通过下面的步骤把这个风铃变成一个Ike 喜欢的形式： 现在这个风铃就满足Ike 的条件了。你的任务是：给定一个风铃的描述，求出最少需要多少次交换才能使这个风铃满足Ike 的条件(如果可能的话)。
输入的第一行包含一个整数n (1≤ n ≤ 1 00 000)，表示风铃中有多少根杆。接下来的n 行描述杆的连接信息。这部分的第i 行包含两个由空格分隔的整数li 和ri，描述杆i 的左右两端悬挂的东西。如果挂的是一个玩具，则对应的值为-1，否则为挂在下面的杆的编号。如果杆i 下面挂有其它杆，则这些杆的编号将严格大于i。杆1 位于风铃的顶部。
输出仅包含一个整数。表示最少需要多少次交换能使风铃满足Ike 的条件。如果不可能满足，输出-1。
解:
树形动态规划
1) 读入，构造二叉树，同时计算各结点深度，和叶子覆盖数.注意发现二叉树叶子深度差大于1时及时退出，否则1个大数据超时
2) 判无解，3种结点，全部最高叶子1，最低叶子2和高低混合叶子3扫一遍，如果一个结点左右儿子属于3类型则无解
3) 动态规划 f[i]:=f[l[x]]+f[r[x]]+1{当count[x]<count[r]}
program mobiles; {-------------------------------------------------- [mobiles.pas] APIO2007_day1_mobiles by HL-drf on May. 12th ---------------------------------------------------} uses math; const limit = 200000+10; type node = array [1..limit] of longint; var l,r,p,c,h,ty : node; i,n,tot : longint; maxh,minh,ans : longint; wa : boolean; procedure rfs(x:longint); begin if c[l[x]]<c[r[x]] then inc(ans); if l[x]<=n then rfs(l[x]); if r[x]<=n then rfs(r[x]); end; procedure dfs(x:longint); begin inc(c[x]); if x<>1 then dfs(p[x]); end; function qfs(x:longint):integer; var a,b:longint; begin if x>n then begin if h[x]=maxh then ty[x]:=1 else ty[x]:=2; exit(ty[x]); end else begin a:=qfs(l[x]); b:=qfs(r[x]); if (a=b) and (a<>3) then ty[x]:=a else if (a=b) and (a=3) then begin ty[x]:=3; wa:=true; end else if ((a=1) and (b=2)) or ((a=2) and (b=1)) then ty[x]:=3 else ty[x]:=max(a,b); end; exit(ty[x]); end; procedure add(b:integer); begin inc(tot); if b=1 then l[i]:=tot else r[i]:=tot; c[tot]:=1; p[tot]:=i; h[tot]:=h[i]+1; if h[tot]<minh then minh:=h[tot] else if h[tot]>maxh then maxh:=h[tot]; dfs(i) end; begin assign(input,'mobiles.in'); reset(input); assign(output,'mobiles.out'); rewrite(output); readln(n); tot:=n; minh:=limit; maxh:=0; ans:=0; for i:= 1 to n do begin readln(l[i],r[i]); if l[i]=-1 then add(1) else begin p[l[i]]:=i; p[r[i]]:=i; h[l[i]]:=h[i]+1; end; if r[i]=-1 then add(0) else begin p[l[i]]:=i; p[r[i]]:=i; h[r[i]]:=h[i]+1; end; if maxh-minh>1 then break; end; if maxh=minh+1 then qfs(1); if (maxh-minh>1) or wa then begin writeln('-1'); close(input); close(output); halt; end; rfs(1); writeln(ans); close(input); close(output); END.
[编辑] Problem 2 : 数据备份
你在一家IT 公司为大型写字楼或办公楼（offices）的计算机数据做备份。然而数据备份的工作是枯燥乏味的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。已知办公楼都位于同一条街上。你决定给这些办公楼配对（两个一组）。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。然而，网络电缆的费用很高。当地电信公司仅能为你提供K 条网络电缆，这意味着你仅能为K 对办公楼（或总计2K 个办公楼）安排备份。任一个办公楼都属于唯一的配对组（换句话说，这2K 个办公楼一定是相异的）。此外，电信公司需按网络电缆的长度（公里数）收费。因而，你需要选择这K 对办公楼使得电缆的总长度尽可能短。换句话说，你需要选择这K 对办公楼，使得每一对办公楼之间的距离之和（总距离）尽可能小。下面给出一个示例，假定你有5 个客户，其办公楼都在一条街上，如下图所示。这5 个办公楼分别位于距离大街起点1km, 3km, 4km, 6km 和12km 处。电信公司仅为你提供K=2 条电缆。上例中最好的配对方案是将第1 个和第2 个办公楼相连，第3 个和第4 个办公楼相连。这样可按要求使用K=2 条电缆。第1 条电缆的长度是3km―1km =2km，第2 条电缆的长度是6km―4km = 2 km。这种配对方案需要总长4km 的网络电缆，满足距离之和最小的要求。
输入的第一行包含整数n 和k，其中n（2 ≤ n ≤100 000）表示办公楼的数目，k（1≤ k≤ n/2）表示可利用的网络电缆的数目。接下来的n 行每行仅包含一个整数（0≤ s ≤1000 000 000）, 表示每个办公楼到大街起点处的距离。这些整数将按照从小到大的顺序依次出现。
输出应由一个正整数组成，给出将2K 个相异的办公楼连成k 对所需的网络电缆的最小总长度。
Program backup; Var s,d,f,g:array [0..100000] of longint; n,k,i,j,y:longint; Procedure Min(var a:longint; b:longint); begin if (b<>-1) and (b<a) then a:=b; end; Begin assign(input,'backup.in'); reset(input); assign(output,'backup.out');rewrite(output); readln(n,k); for i:= 1 to n do read(d[i]); for i:= 1 to n do s[i]:=d[i]-d[i-1]; for j:= 1 to n do begin g:=f; fillchar(f,sizeof(f),255); for i:= y to n do begin if g[i-2]<>-1 then f[i]:=g[i-2]+s[i]; if f[i-1]<>-1 then min(f[i],f[i-1]); end; end; writeln(f[n]); close(input); close(output); END.
以上代码不正确
[编辑] Problem 3 : 动物园
新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上，它包含一大圈围栏，每个围栏里有一种富有异国风情的动物。如下图所示：你是动物园的公关主管。你要做的是，让每个参观动物园的游客都尽可能高兴。今天有一群小朋友来到动物园参观，你希望能让他们在动物园度过一段美好的时光。但这并不是一件容易的事——有些小朋友喜欢某些动物，而有些小朋友则害怕某些动物。例如，Alex 喜欢可爱的猴子和考拉，而害怕张牙舞爪的狮子。而Polly 会因狮子有美丽的鬃毛而喜欢它，但害怕有臭味的考拉。你可以选择将一些动物从围栏中移走以使得小朋友不会害怕。但你移走的动物也不能太多，否则留给小朋友们观赏的动物就所剩无几了。每个小朋友站在大围栏圈的外面，可以看到连续的5 个围栏。你得到了所有小朋友喜欢和害怕的动物信息。当出现下面两种情形之一时，小朋友就会高兴：
至少有一个他害怕的动物（从视线可见的范围内）被移走，或 至少有一个他喜欢的动物没有被（从视线可见的范围内）移走。
例如，考虑下图中的小朋友和动物：
小朋友 可见的围栏 害怕的动物 喜欢的动物 Alex 2,3,4,5,6 围栏4 围栏2,6 Polly 3,4,5,6,7 围栏6 围栏4 Chaitanya 6,7,8,9,10 围栏9 围栏6,8 Hwan 8,9,10,11,12 围栏9 围栏12 Ka-Shu 12,13,14,1,2 围栏12,13,2 -
假如你将围栏4 和12 的动物移走。Alex 和Ka-Shu 将很高兴，因为至少有一个他们害怕的动物被移走了。这也会使Chaitanya 高兴，因为他喜欢的围栏6和8 中的动物都保留了。但是，Polly 和Hwan 将不高兴，因为他们看不到任何他们喜欢的动物，而他们害怕的动物都还在。这种安排方式使得三个小朋友高兴。现在换一种方法，如果你将围栏4 和6 中的动物移走，Alex 和Polly 将很高兴，因为他们害怕的动物被移走了。Chaitanya 也会高兴，因为虽然他喜欢的动物6 被移走了，他仍可以看到围栏8 里面他喜欢的动物。同样的Hwan 也会因可以看到自己喜欢的围栏12 里的动物而高兴。唯一不高兴的只有Ka-Shu。如果你只移走围栏13 中的动物，Ka-Shu 将高兴，因为有一个他害怕的动物被移走。Alex, Polly, Chaitanya 和Hwan 也会高兴，因为他们都可以看到至少一个他们喜欢的动物。所以有5 个小朋友会高兴。这种方法使得最多的小朋友高兴。
输入的第一行包含两个整数N, C，用空格分隔。N 是围栏数(10≤N≤10 000)，C 是小朋友的个数(1≤C≤50 000)。围栏按照顺时针的方向编号为1,2,3,…,N。接下来的C 行，每行描述一个小朋友的信息，以下面的形式给出：
E F L X1 X2 … XF Y1 Y2 … YL
其中：
E 表示这个小朋友可以看到的第一个围栏的编号(1≤E≤N)，换句话说，该小朋友可以看到的围栏为E, E+1, E+2, E+3, E+4。注意，如果编号超过N 将继续从1 开始算。如：当N=14, E=13 时，这个小朋友可以看到的围栏为13,14,1, 2 和3。F 表示该小朋友害怕的动物数。L 表示该小朋友喜欢的动物数。围栏X1, X2, …, XF 中包含该小朋友害怕的动物。围栏Y1, Y2, …, YL 中包含该小朋友喜欢的动物。X1, X2, …, XF, Y1, Y2, …, YL 是两两不同的整数，而且所表示的围栏都是该小朋友可以看到的。小朋友已经按照他们可以看到的第一个围栏的编号从小到大的顺序排好了(这样最小的E 对应的小朋友排在第一个，最大的E 对应的小朋友排在最后一个)。注意可能有多于一个小朋友对应的E 是相同的。 仅输出一个数，表示最多可以让多少个小朋友高兴。
解:
压缩动态规划
a. 学会位运算之后，这道题思路便十分清晰了
1) 枚举前4个动物的状态
2) 递推f[I,k]表示动规到以i为视野结束标志的小朋友为止,后4个窗口状态为k的时候，最多的高兴的小朋友
f[I,k]:=f[i-1,k and not (1<<4)] + Val (阶段i新增的高兴小朋友)
b. 细节注意
1) 小朋友的高兴和不高兴的表最好用1个5位二进数存，这样判断的时候一个check 函数就可以了
exit((kid[j].x and not k<>0) or (kid[j].y and k<>0));
2）注意破环后 当 i=1 时，i-1应该算 n
3）思路一定要清晰，就能在百行内打完.
4) 其实压缩dp并不难
5) 注意结构化程序设计
6) 注意数据范围
7) 理解<<和>>
8) 深刻默写 zoo.pas
9) 调试方法： Procedure Bin + Debug 法， GDB break 法★
10) Believe yourself
Program zoo; // [APIO 2007 zoo.pas] by HL-drf on July 23th AC 100% within 2s// Type kids = record B,L,F,X,Y :longint end; child = record S,B,T :longint end; Var f : array [0..10000, 0..1<<4] of longint; kid : array [0..50000] of kids; c : array [0..10000] of child; r:longint; i,j,k,n,m,v,s,t,o : longint; ans,val,z : longint; Procedure max(var a:longint; b:longint); begin if b>a then a:=b; end; Function check(j:longint):boolean; begin exit((kid[j].x and not k<>0) or (kid[j].y and k<>0)); end; Function Viable(i:longint):boolean; begin if (i>4) and (i<9) then begin t:=k; for j:= 10-i to 5 do t:= t and not (1<<(j-1)); if t<>s>>(i-5) then exit(false); end else if i<=4 then begin t:=s; for j:= i+1 to 4 do t:= t and not (1<<(j-1)); if k>>(5-i)<>t then exit(false); end; exit(true); end; Procedure SDP(i:longint); begin if c[v].b=i then begin for k:= 1<<5-1 downto 0 do begin if not viable(i) then continue; if i=1 then o:=f[n ,k and not (1<<4)] else o:=f[i-1,k and not (1<<4)]; val:=0; for j:= c[v].s to c[v].t do if Check(j) then inc(val); max(f[i,k>>1],val+o); max(ans,f[i,k>>1]); end; inc(v); end else for k:= 1<<5-1 downto 0 do begin if not viable(i) then continue; if i<>1 then max(f[i,k>>1],f[i-1,k and not (1<<4)]) else max(f[i,k>>1],f[n, k and not (1<<4)]); end; end; Begin assign(input,'zoo.in'); reset(input); assign(output,'zoo.out'); rewrite(output); readln(n,m); for i:= 1 to m do with kid[i] do begin read(b,f,l); for j:= 1 to f do begin read(z); if (b>=n-3) and (z<=4) then x:=x or (1<<(z+n-b)) else x:=x or (1<<(z-b)) end; for j:= 1 to l do begin read(z); if (b>=n-3) and (z<=4) then y:=y or (1<<(z+n-b)) else y:=y or (1<<(z-b)); end; inc(b,4); if b>n then dec(b,n); if b<>c[r].b then begin inc(r); c[r].b:=b; c[r].s:=i; c[r].t:=i; end else inc(c[r].t); end; for s:= 1<<4-1 downto 0 do begin fillchar(f,sizeof(f),0); v:=1; for i:= 5 to n do SDP(i); for i:= 1 to 4 do SDP(i); end; writeln(ans); close(input); close(output); END.
