发布时间 : 星期四 文章noip普及组复赛模拟试题22（答案）更新完毕开始阅读
军方截获的信息由n（n<=30000）个数字组成，因为是敌国的高端秘密，所以一时不能破获。最原始的想法就是对这n个数进行小到大排序，每个数都对应一个序号，然后对第i个是什么数感兴趣，现在要求编程完成。 【输入格式】
第一行n，接着是n个截获的数字，接着一行是数字k，接着是k行要输出数的序号。
【输出格式】
k行序号对应的数字。 【输入样例】Secret.in 5
121 1 126 123 7 3 2 4 3
【输出样例】Secret.out 7 123 121
program secret; const max=30000; var n,i,x,k:longint;
a:array[1..max] of longint; procedure sort(l,r:longint); var i,j,t,mid:longint; begin i:=l;j:=r;
mid:=a[(l+r)div 2]; repeat
while a[i]
if l begin assign(input,'secret.in'); assign(output,'secret.out'); reset(input); rewrite(output); readln(n); for i:=1 to n do read(a[i]); sort(1,n); readln(k); for i:=1 to k do begin readln(x); writeln(a[x]); end; close(input); close(output); end. 输入 15 12 10 36 127 126 123 75 89 101 999 777 654 456 890 134 6 2 4 3 9 10 14 输出12 75 36 127 134 890 输入24 8 18 12 24 434 10 36 127 126 123 75 89 101 999 777 654 456 890 134 555 221 108 888 656 8 5 4 3 19 20 14 17 10 输出24 18 12 654 656 134 456 108 有一只坏的里程表：它总是跳过数字3和数字8。也就是说，当前显示已走过两公里时，如果车子再向前走一公里，那么将显示4公里，而不是三公里（数字3跳过了）。再比如，当前是15229公里，车子再向前走一公里，显示的是15240公里，而不是15230公里。数字8也同样跳过 现在，给你里程表上显示的数字，请你告诉我车子真正走了多少公里。 输入： 15 输出： 12 program yx; const alph='01245679'; var n,m,w,g,t:longint; st:string; begin assign(input,'yx.in'); assign(output,'yx.out'); reset(input); rewrite(output); readln(n); m:=0;t:=1; while n<>0 do begin g:=n mod 10; n:=n div 10; str(g,st); w:=pos(st,alph)-1; m:=m+t*w; t:=t*8; end; writeln(m); close(input); close(output); end. 输入27 输出 22 输入 4567 输出 1838 输入 44565677 输出 7231862 硬币游戏 Description Farmer John的奶牛喜欢玩硬币游戏，因此FJ发明了一种称为“Xoinc”的两人硬币游戏。 初始时，一个有N(5 <= N <= 2,000)枚硬币的堆栈放在地上，从堆顶数起的第I枚硬币的币值为C_i (1 <= C_i <= 100,000)。 开始玩游戏时，第一个玩家可以从堆顶拿走一枚或两枚硬币。如果第一个玩家只拿走堆顶的一枚硬币，那么第二个玩家可以拿走随后的一枚或两枚硬币。如果第一个玩家拿走两枚硬币，则第二个玩家可以拿走1，2，3，或4枚硬币。在每一轮中，当前的玩家至少拿走一枚硬币，至多拿走对手上一次所拿硬币数量的两倍。当没有硬币可拿时，游戏结束。 两个玩家都希望拿到最多钱数的硬币。请问，当游戏结束时，第一个玩家最多能拿多少钱呢？ Input 第1行：1个整数N 第2..N+1行：第i+1行包含1个整数C_i Output 第1行：1个整数表示第1个玩家能拿走的最大钱数。 Sample Input 5 1 3 1 7 2 Sample Output 9 Hint 样例说明：第1个玩家先取走第1枚，第2个玩家取第2枚；第1个取走第3，4两枚，第2个玩家取走最后1枚。 Source USACO NOV09 SILVER *********************************************************************************** 本题是求最优解，常用的方法有DP、贪心、搜索。 对N=2000的数据规模，搜索显然是会超时的。每步都取最优的贪心明显不对，样例就是反例。 根据题设条件，发现问题状态和两个因素有关：当前剩下的硬币数量和对手上一次拿走的硬币数量。对于当前状态，要得到最优解，需要枚举自己能拿走的硬币数量x。一旦这次自己拿走了x枚硬币（自然可以算出本次所拿的总钱数），就交由对手走，状态就转移成剩下total-x枚硬币（total是“上上”次取走硬币后，剩下的总硬币枚数），上一次拿走x枚硬币。对手也会拿走最多钱数的硬币。这里有个关键的地方要想通：在交给对方走之后，自己还能在以后的游戏中拿走多少钱数的硬币？答案是：剩下total-x枚的总钱数减去对手拿走的总钱数（这个值恰好是剩下total-x枚硬币，上一次拿走x枚硬币所表示的最优解）