noip普及组复赛模拟试题22(答案)

军方截获的信息由n（n<=30000）个数字组成，因为是敌国的高端秘密，所以一时不能破获。最原始的想法就是对这n个数进行小到大排序，每个数都对应一个序号，然后对第i个是什么数感兴趣，现在要求编程完成。【输入格式】第一行n，接着是n个截获的数字，接着一行是数字k，接着是k行要输出数的序号。【输出格式】k行序号对应的数字。【输入样例】Secret.in5121112612373243【输出样例】Secret.out7123121programsecret;constmax=30000;varn,i,x,k:longint;a:array[1..max]oflongint;proceduresort(l,r:longint);vari,j,t,mid:longint;begini:=l;j:=r;mid:=a[(l+r)div2];repeatwhilea[i]<middoinc(i);whilea[j]>middodec(j);ifj>=ithenbegint:=a[i];a[i]:=a[j];a[j]:=t;inc(i);dec(j)end;untili>j;ifl<jthensort(l,j);ifi<rthensort(i,r);end;beginassign(input,'secret.in');assign(output,'secret.out');reset(input);rewrite(output);readln(n);fori:=1tondoread(a[i]);sort(1,n);readln(k);fori:=1tokdobeginreadln(x);writeln(a[x]);end;close(input);close(output);end.输入151210361271261237589101999777654456890134624391014输出127536127134890输入2481812244341036127126123758910199977765445689013455522110888865685431920141710输出241812654656134456108有一只坏的里程表：它总是跳过数字3和数字8。也就是说，当前显示已走过两公里时，如果车子再向前走一公里，那么将显示4公里，而不是三公里（数字3跳过了）。再比如，当前是15229公里，车子再向前走一公里，显示的是15240公里，而不是15230公里。数字8也同样跳过现在，给你里程表上显示的数字，请你告诉我车子真正走了多少公里。输入：15输出：12programyx;constalph='01245679';varn,m,w,g,t:longint;st:string;beginassign(input,'yx.in');assign(output,'yx.out');reset(input);rewrite(output);readln(n);m:=0;t:=1;whilen<>0dobeging:=nmod10;n:=ndiv10;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硬币游戏DescriptionFarmerJohn的奶牛喜欢玩硬币游戏，因此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_iOutput第1行：1个整数表示第1个玩家能拿走的最大钱数。SampleInput513172SampleOutput9Hint样例说明：第1个玩家先取走第1枚，第2个玩家取第2枚；第1个取走第3，4两枚，第2个玩家取走最后1枚。SourceUSACONOV09SILVER***********************************************************************************本题是求最优解，常用的方法有DP、贪心、搜索。对N=2000的数据规模，搜索显然是会超时的。每步都取最优的贪心明显不对，样例就是反例。根据题设条件，发现问题状态和两个因素有关：当前剩下的硬币数量和对手上一次拿走的硬币数量。对于当前状态，要得到最优解，需要枚举自己能拿走的硬币数量x。一旦这次自己拿走了x枚硬币（自然可以算出本次所拿的总钱数），就交由对手走，状态就转移成剩下total-x枚硬币（total是“上上”次取走硬币后，剩下的总硬币枚数），上一次拿走x枚硬币。对手也会拿走最多钱数的硬币。这里有个关键的地方要想通：在交给对方走之后，自己还能在以后的游戏中拿走多少钱数的硬币？答案是：剩下total-x枚的总钱数减去对手拿走的总钱数（这个值恰好是剩下total-x枚硬币，上一次拿走x枚硬币所表示的最优解）令DP[c][p]表示剩下c枚硬币，上次对手拿走p枚硬币的最优解。SUM[i][j]表示从第i枚到第j枚硬币的钱数之和。DP[c][p]=max{SUM[c-i+1][c]+(SUM[1][c-i]-DP[c-i][i])}1<=i<=min(2*p,c)SUM[c-i+1][c]表示本次自己拿走第i枚的钱数和SUM[1][c-i]-DP[c-i][i]表示在剩下的局面中自己还能拿的钱数和上式化简得：DP[c][p]=max{SUM[1][c]-DP[c-i][i]}边界状态：DP[0][*]=0(剩下0枚硬币，当然只能拿走0了)目标状态：ans=DP[N][1]可以先将SUM预处理出来。但是整个DP仍然有N^2个状态，每次转移是O(N)，所以整个时间为O(N^3)。要通过全部数据，需要进一步优化才行。分析后发现，在按上述方程计算两个相邻状态DP[c][p]和DP[c][p+1]时做了很多重复:DP[c][p]=max{SUM[1][c]-DP[c-i][i]}1<=i<=min(2*p,c)DP[c][p+1]=max{SUM[1][c]-DP[c-i][i]}1<=i<=min(2*(p+1),c)=max{DP[c][p],SUM[1][c]-DP[c-(2*p+1)][2*p+1],SUM[1][c]-DP[c-(2*p+2)][2*p+2]}这样就把转移时间降为O(1)，整个时间降为O(N^2)了。当然，在处理2*p+1>c和2*p+2>c要特别小心，否则就要造成数组访问出界的错误。programP1075;constmaxn=2000;varf:array[0..maxn,0..maxn]oflongint;sum:array[0..maxn+1]oflongint;n,ans:longint;proceduregf_init;vari:longint;beginreadln(n);fori:=ndownto1doreadln(sum[i]);fori:=1tondoinc(sum[i],sum[i-1]);end;functionmax(x,y:longint):longint;beginifx>ythenexit(x)elseexit(y);end;//f[i,j]表示剩下的i枚硬币~上一次取的个数是j个的最优值proceduregf_work;vari,j:longint;beginfori:=1tondof[0,i]:=0;fori:=1tondoforj:=1tondobeginf[i,j]:=f[i,j-1];ifi-(2*j-1)>=0thenf[i,j]:=max(f[i,j],sum[i]-f[i-(2*j-1),2*j-1]);ifi-(2*j)>=0thenf[i,j]:=max(f[i,j],sum[i]-f[i-(2*j),2*j]);end;end;proceduregf_print;beginwriteln(f[n,1]);end;begingf_init;gf_work;gf_print;end.输入12358451218161091512输出59输入201000020000150002300045000900005000015000600006500055000340004200045000800007600079000850002700039000输出503000宝物筛选(Treasure.pas/c/cpp)【题目描述】终于，破解了千年的难题。小FF找到了王室的宝物室，里面堆满了无数价值连城的宝物……这下小FF可发财了，嘎嘎。但是这里的宝物实在是太多了，小FF的采集车似乎装不下那么多宝物。看来小FF只能含泪舍弃其中的一部分宝物了……小FF对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件，他粗略的估算了下每样宝物的价值，之后开始了宝物筛选工作：小FF有一个最大载重为W的采集车，洞穴里总共有n种宝物，每种宝物的价值为v[i]，重量为w[i]，每种宝物有m[i]件。小FF希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。【输入格式】第一行为一个整数N和W，分别表示宝物种数和采集车的最大载重。接下来n行每行三个整数，其中第i行第一个数表示第i类品价值，第二个整数表示一件该类物品的重量，第三个整数为该类物品数量。【输出格式】输出仅一个整数ans，表示在采集车不超载的情况下收集的宝物的最大价值。【输入样例】420393591942813【输出样例】47【数据范围】对于30%的数据：n≤∑m[i]≤10^4;0≤W≤10^3对于100%的数据：n≤∑m[i]≤10^5；0≤W≤4*10^4;1≤n≤100.分析：用多重背包模型~可以过30%的数据~需要做的是将背包的个数分解~用二进制表示~最后做一个01背包的模型需要注意的是将所有的个数都包括好~如2=1+1;5=1+2+2;4=1+2+1；代码：vara,w,m,b,w1:array[0..10000]oflongint;f:Array[0..100000]ofint64;i,j,k,o,p,l,m1,n,x,y,ans:longint;functionmax(a,b:longint):longint;beginifa>bthenmax:=aelsemax:=b;end;procedureinit;beginassign(input,'treasure.in');assign(output,'treasure.out');reset(input);rewrite(output);readln(n,m1);fori:=1tondoreadln(a[i],w[i],m[i]);end;proceduremain;begink:=n;fori:=1tondobeginifm1divw[i]<m[i]thenm[i]:=m1divw[i];x:=m[i];y:=1;while(y<=x)dobegininc(k);a[k]:=a[i]*y;w[k]:=w[i]*y;x:=x-y;y:=y*2;end;ifx<>0thenbegininc(k);a[k]:=x*a[i];w[k]:=x*w[i];end;end;fillchar(f,sizeof(f),0);fori:=n+1tokdoforj:=m1downto0doifj-w[i]>=0thenf[j]:=max(f[j],f[j-w[i]]+a[i]);end;procedureprint;beginwriteln(f[m1]);close(input);close(output);end;begininit;main;print;end.输入1018012923591914128111310