Power OJ 1089 成绩查询 浮点数处理

1089: 成绩查询

Time Limit:4000MS Memory Limit:65536KB

Description

NOIP乐山一中模拟赛的成绩出来了,很多同学急切的想知道自己的成绩,所以经学校商量后决定在网站上公布。但时间很紧!现在提供每个人的用户名、成绩,需要你将成绩排序并根据用户输入的成绩排名输出对应的用户名和排名(成绩少的排名靠前,因为noip题目用的时间越少,排名越靠前)。成绩相同的,用户名字典序小的排名靠前。

Input

第一行是一个正整数n,表示OIer数。
接下来的n 行每行有一个字符串和一个小数,第i 行是编号为i-1 的人的信息,中间用一个空格分隔,字符串代表用户名(只能由大、小写字母,数字和下划线组成),小数代表该人的成绩,每行的首尾不会有多余的空格。
然后是一个正整数m,表示查询的次数。
接下来m 行是每一次查询的信息,每行一个实数k。

Output

对应每一个数k,你都要输出用时为k 且排名最靠前的OIer的用户名及排名(一个正整数),中间用一个空格分隔,如果没有符合条件的人的话就输出”No This OIer”(没有两边的引号)。

Power OJ 1088 寻找考场 模拟

1088: 寻找考场

Time Limit:1000MS Memory Limit:65536KB

Power OJ 2480 放积木 状压DP/二分匹配

2480: 放积木

Time Limit:1000MS Memory Limit:65536KB

Power OJ 2478 最短路问题 多维最短路

http://www.oj.swust.edu.cn/problem/show/2478

2478: 最短路问题

Time Limit:5000MS Memory Limit:65536KB

Power OJ 2477 过河问题 BFS或者DP

http://www.oj.swust.edu.cn/problem/show/2477

2477: 过河问题

Time Limit:1000MS Memory Limit:65536KB

 

用dp[i][j][k]表示达到有i个60重量的人和j个120重量的人,并且船在位置k(k=0时代表在本岸,k=1时代表在对岸)这个状态所需的最小的次数。每次对一个状态进行转移的时候,枚举要上船的两类人的个数,k取反即可进行转移。很显然,假设有x个重量为60的人,y个重量为120的人,起始状态为dp[x][y][0]=0,目标状态为dp[0][0][1]。对起始状态进行BFS即可!

 

Power OJ 2475 Xor问题

http://www.oj.swust.edu.cn/problem/show/2475

2475: Xor问题

Time Limit:2000MS Memory Limit:65536KB

 

由于区间异或可以转化为异或的前缀和的问题,对于第i个数,求得前面从哪个数开始到这第i个数的异或和最大,再统计所有i对应的最大值的最大值。怎么求一个i对应的最大值呢?考虑将位置i之前的所以的前缀异或和放进字典树,按数的二进制bit建树。进行查询的时候,先尝试往被查询的数的某一位的反方向走,此时,这一位的答案的bit为1,否则,往顺方向走,这一位的答案bit为0.

注意!由于答案可能是整个区间,所以还需要在空的字典树先插入一个0。

 

Power OJ 2474 F(k) 前缀和+二分

2474: F(k)

 思路:维护一个数组v,v[i]表示数i在f(k)数组中出现了几次,由于长度未知,所以用 vector来维护。看题面可知,v[1]=1,v[2]=v[3]=2。按照题目意思,暴力维护这个数组即可。当维护到的f(k)的长度大于20E的时候停止维护。
 然后再求出v数组的前缀和。这时,v[i]所表示的意思,就是f(k)数组中所有小于等于i的数的个数。
 对于每一次查询,在v[i]中进行二分查找即可然后输出下标即可。