出门考试去……
Friday, 20. April 2007, 23:23:08
不知能否高高兴兴回家来？
Posts tagged with "NOI"
PKU2265,2507
Friday, 8. September 2006, 11:54:10
正在做，做一下记录先
Program PKU2265; Const f:array[2..8,1..2]of integer=((0,1),(-1,1),(-1,0),(0,-1),(1,-1),(1,0),(0,1)); Var k,i,r:integer; p:integer; x,y:integer; f1,f2:text; Procedure Init; Var t:real; Begin Read(f1,k); t:=(-3+sqrt(12*k-3))/6; if abs(t-trunc(t))<=1e-10 then p:=trunc(t) else p:=trunc(t)+1; r:=k-(3*sqr(p-1)+3*(p-1)+1); End; Procedure Main; var t,q:integer; Begin t:=r; x:=p-1;y:=0; if t>0 then Begin inc(x,f[2,1]);inc(y,f[2,2]);dec(t);End; q:=p-1; While (t>0)and(q>0) do Begin dec(t);dec(q); inc(x,f[3,1]);inc(y,f[3,2]); End; for i:=4 to 8 do Begin q:=p; while (t>0)and(q>0) do Begin dec(t);dec(q); inc(x,f[i,1]);inc(y,f[i,2]); End; End; End; Procedure Print; Begin writeln(f2,x,' ',y); End; Begin assign(f1,'input.in'); assign(f2,'output.out'); reset(F1);rewrite(F2); Repeat Init; Main; Print; Until eof(f1); Close(f1);Close(F2); End.
Program PKU2507; const zero=1e-15; Var x,y,c:extended; f1,f2:text; ans:extended; Procedure Init; Begin read(f1,x,y,c); c:=1/c; End; Function Get(left,right:extended):extended; Var t,k,a,b:extended; Begin k:=(left+right)/2; a:=sqrt(sqr(x)-sqr(k)); b:=sqrt(sqr(y)-sqr(k)); t:=(a+b)/(a*b); if (abs(t-c)<zero)and(t-c>0) then Get:=k else if t-c<zero then Get:=Get(k,right) else if t-c>zero then Get:=Get(left,k); End; Function Get_Min(a,b:extended):extended; Begin if a>b then Get_Min:=b else get_min:=a; End; Procedure Print; Begin writeln(f2,ans:0:3); End; Begin assign(f1,''); assign(f2,''); reset(f1);rewrite(f2); Repeat Init; ans:=get(0,Get_Min(x,y)); Print; Until EOF(f1); close(f1);close(f2); End.
3日集训--5.17
Thursday, 18. May 2006, 00:01:37
题一 求最大子序列和
（ 文件名 maxq.* 时间限制：1s ）
[问题描述]
已知一个整数序列b1,b2,……bn,(n>0)试确定s,t(1<=s<=t<=n)使得 P=bs +bs+1 +…+bt最大。
如数列：
2 5 1 3 -100 –5 10 5 20 -2 10 -50 -10 3
最大连续项的和 P=10+5+20-2+10=43。
[输 入]：
第一行： n
第 2--n+1行：n项的整数序列。
[输 出]
第一行： s的值
第二行： t的值
第三行：最大连续项的和
[输入输出样例]
maxq.in ：
14
2
5
1
3
-100
-5
10
5
20
-2
10
-50
-10
3
maxq.out：
7
11
43
[数据规模]：对30%的数据，n<=500；对100%的数据，n<=5000；
嗯，双指针
题二 银河英雄传说
（ 文件名： galaxy.* 时间限制： 2s ）
[问题描述]:
公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。
宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。
杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, …, 30000。之后，他把自己的战舰也依次编号为1, 2, …, 30000，让第i号战舰处于第i列(i = 1, 2, …, 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体(头在前尾在后)接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。
然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。
在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。
作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。
最终的决战已经展开，银河的历史又翻过了一页……
[输入]:
输入文件galaxy.in的第一行有一个整数T（1<=T<=500,000），表示总共有T条指令。
以下有T行，每行有一条指令。指令有两种格式：
M i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。
C i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。
[输出]:
输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理：
如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。
[输入输出样例]
galaxy.in
4
M 2 3
C 1 2
M 2 4
C 4 2
galaxy.out
-1
1
[样例说明]
战舰位置图：表格中阿拉伯数字表示战舰编号
第一列1 第二列2 第二列3 第四列4 ……
初始时 1 2 3 4 ……
M 2 3 1 3
2 4 ……
C 1 2 1号战舰与2号战舰不在同一列，因此输出-1
M 2 4 1 4
3
2 ……
C 4 2 4号战舰与2号战舰之间仅布置了一艘战舰，编号为3，输出1
加路径压缩的并查集
题三 登山问题
（ 文件名： dengshan.* 时间限制: 2s ）
[问题描述]:
攀登某高山，假定上下山速度相等。从山脚到顶峰有 N 天的路程 。某登山队有 P 名队员，每人每天可负载最大给养量和每天消耗的给养量不尽相同。只要在 N 天内全队有一个队员登上顶峰，并且在 2N 天内所有参加登山的队员安全返回山脚，就算此次登山成功。登山规则：参加登山的队员同时同地出发,给养可以相互补给，但必须由登山队员随身携带。
求在参加登山的队员数最少的情况下消耗总给养量尽可能少的计划。
[输入]
dengshan.in
第一行： N P
N，P表示从山脚到顶峰有N天的路程，共有P名队员
第 2--P+1行：q cost take
q表示队员编号，cost表示q号队员每天给养消耗量， take表示q号队员最大可携带给养量。
[输出]
dengshan.out
第一行： P 可完成登山计划的最少人数
第 2--P+1行:x y z
x表示队员编号
y表示所带给养
z表示x队员出发z天后开始返回
从下至上为依次返回的队员,即p+1行为第1个返回的队员,第p行为第2个返回的队员,......,第3行为第p-1个返回的队员,第2行为最后登顶的队员。
[输入输出样例]
样例输入
6 5
1 1 8
2 1 7
3 2 14
4 2 6
5 4 16
样例输出
4
1 8 6
3 14 4
2 7 2
5 11 1
略带一些贪心的搜索
嗯，270达成
（ 文件名 maxq.* 时间限制：1s ）
[问题描述]
已知一个整数序列b1,b2,……bn,(n>0)试确定s,t(1<=s<=t<=n)使得 P=bs +bs+1 +…+bt最大。
如数列：
2 5 1 3 -100 –5 10 5 20 -2 10 -50 -10 3
最大连续项的和 P=10+5+20-2+10=43。
[输 入]：
第一行： n
第 2--n+1行：n项的整数序列。
[输 出]
第一行： s的值
第二行： t的值
第三行：最大连续项的和
[输入输出样例]
maxq.in ：
14
2
5
1
3
-100
-5
10
5
20
-2
10
-50
-10
3
maxq.out：
7
11
43
[数据规模]：对30%的数据，n<=500；对100%的数据，n<=5000；
嗯，双指针
题二 银河英雄传说
（ 文件名： galaxy.* 时间限制： 2s ）
[问题描述]:
公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。
宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。
杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, …, 30000。之后，他把自己的战舰也依次编号为1, 2, …, 30000，让第i号战舰处于第i列(i = 1, 2, …, 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体(头在前尾在后)接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。
然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。
在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。
作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。
最终的决战已经展开，银河的历史又翻过了一页……
[输入]:
输入文件galaxy.in的第一行有一个整数T（1<=T<=500,000），表示总共有T条指令。
以下有T行，每行有一条指令。指令有两种格式：
M i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。
C i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。
[输出]:
输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理：
如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。
[输入输出样例]
galaxy.in
4
M 2 3
C 1 2
M 2 4
C 4 2
galaxy.out
-1
1
[样例说明]
战舰位置图：表格中阿拉伯数字表示战舰编号
第一列1 第二列2 第二列3 第四列4 ……
初始时 1 2 3 4 ……
M 2 3 1 3
2 4 ……
C 1 2 1号战舰与2号战舰不在同一列，因此输出-1
M 2 4 1 4
3
2 ……
C 4 2 4号战舰与2号战舰之间仅布置了一艘战舰，编号为3，输出1
加路径压缩的并查集
题三 登山问题
（ 文件名： dengshan.* 时间限制: 2s ）
[问题描述]:
攀登某高山，假定上下山速度相等。从山脚到顶峰有 N 天的路程 。某登山队有 P 名队员，每人每天可负载最大给养量和每天消耗的给养量不尽相同。只要在 N 天内全队有一个队员登上顶峰，并且在 2N 天内所有参加登山的队员安全返回山脚，就算此次登山成功。登山规则：参加登山的队员同时同地出发,给养可以相互补给，但必须由登山队员随身携带。
求在参加登山的队员数最少的情况下消耗总给养量尽可能少的计划。
[输入]
dengshan.in
第一行： N P
N，P表示从山脚到顶峰有N天的路程，共有P名队员
第 2--P+1行：q cost take
q表示队员编号，cost表示q号队员每天给养消耗量， take表示q号队员最大可携带给养量。
[输出]
dengshan.out
第一行： P 可完成登山计划的最少人数
第 2--P+1行:x y z
x表示队员编号
y表示所带给养
z表示x队员出发z天后开始返回
从下至上为依次返回的队员,即p+1行为第1个返回的队员,第p行为第2个返回的队员,......,第3行为第p-1个返回的队员,第2行为最后登顶的队员。
[输入输出样例]
样例输入
6 5
1 1 8
2 1 7
3 2 14
4 2 6
5 4 16
样例输出
4
1 8 6
3 14 4
2 7 2
5 11 1
略带一些贪心的搜索
嗯，270达成
Friends
Poll
你的DND第一次PC给了什么职业？
- 高呼着战战战的野蛮人
(0%)
- 混吃等死的吟游诗人 (0%)
- 记不清自己信仰的牧师 (0%)
- 宠物屡被DM杀害的德鲁伊 (25%)
- 简约而不简单的战士 (0%)
- 穷的叮当响的武僧 (0%)
- 从来没有成功乘骑冲锋过的圣武士 (50%)
- 宿敌被DM从MM中删除的巡林客 (0%)
- 谢教父所倡导的游荡者 (25%)
- 华丽的施法者，术士／法师 (0%)
Total: 4 votes
| S | M | T | W | T | F | S |
|---|---|---|---|---|---|---|
 November 2009January 2010
| ||||||
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 | 31 | ||
Tags
Recent visitors
Try a faster and more secure Web browser. Download Opera
WIDGETIZEHelp | Disclaimer | Terms of service | Web analytics powered by HitsLink
