IOI 2012中国信息学国家集训队命题答辩试题册
一号
教练: 胡伟栋、唐文斌
中国计算机学会
2012年5月
答辩顺序
拆弹计划
命题人: 李超
【资源限制】
时间限制：3秒内存限制：512MB
【关键字】
序的应用，分治，线段树
【问题描述】
A 国和
B 国是两个超级大国，长期处于冷战状态。
A 国在
B 国中设有N个情报站，编号为1,2,3,……,N，第i个情报站的坐标是(X i, Y i)。
但是，A 国的工作人员发现，每个情报站里都被埋上了！
这些非常的特殊，必须同时拆除且仅拆除其中的三个，才能使所有都不爆炸。 拆除的总代价由两部分组成，第一部分为情报站之间联络的代价，第二部分为拆除所需要的代价。其中，联络的代价为要拆除的三个情报站的坐标的曼哈顿距离和，在第i个情报站拆除的代价为Z i。 现在A 国的指挥部门到了你，他想要知道，使所有都不爆炸的最小花费代价是多少。
【输入格式】
输入的第一行包含一个整数N。接下来N 行，第i+1 行有三个整数X i, Y i, Z i，表示第i个情报站的坐标与拆除的代价。
【输出格式】
输出一行，包含一个整数，表示使所有都不爆炸的最小花费代价。
【样例输入】
4
1 1 1
1 2 2
2 1 3
2 3 4
【样例输出】
10
【样例解释】
选择编号为1,2,3 的情报站拆除，总花费为(1+1+2)+(1+2+3)=10，是所有花费中总花费最小的。该数据中只有这一种选法。 机器翻译论文【数据规模与约定】
对于30%的数据，N≤ 500
对于50%的数据，N≤ 1000
对于70%的数据，N≤ 15000
另有10%的数据，在所有情报站拆除的花费代价均相同；化石工艺品
对于100%的数据，N≤ 100000，0 ≤ X i, Y i, Z i≤ 108
【说明】
对于两个点(X0, Y0), (X1, Y1)，它们的曼哈顿距离为|X0–X1| + |Y0–Y1|。
命题人: 徐捷
【问题描述】
给定N个仅有a ~ z组成的字符串a i，每个字符串都有一个权值v i，有M次操作，操作分三种：
Cv x v'：把第x个字符串的权值修改为v'；
Cs x a'：把第x个字符串修改成a'；
Q：求出当前的最大权字符串集合，使得这个集合中的字符串经过重新排列后满足除最后一个字符串外，前一个字符串是后一个的前缀(两个字符串相同也是前缀关系，也可以一个字符串都不选)。
园艺学报前50%的数据可以接受离线算法，后50%的数据要求在线算法。
【数据规模与约定】
数据分两种，A类数据可以用离线的方法来完成，B类数据必须使用在线算法。
令
字符串加密
系统工程与电子技术
命题人: 梁盾
【问题描述】
H国开发了一种新的字符串的加密方式，具体方法为将一个长度为N的由小写字母组成的字符串分成不超过K段，分别将每一段翻转，得到的新字符串即为加密以后的字符串。
H国为I国的敌国，I国为了打败H国，得到了一个加密以后的信息，我们想知道这个字符串在加密以前的样子，不过可能有多个答案，我们只要知道字典序最小的答案就可以了。
【输入格式】
第一行一个数T，表示数据组数。
对于每组数据，第一行两个数N, K分别表示字符串的长度和被分成了K段。
第二行一个长度为N的字符串。
【输出格式】
对于每组数据，输出一个长度为N的字符串，即加密前的可能的字典序最小的字符串。
【样例输入】
1
1 3
黎塘论坛bacbadcba
【样例输出】
ababcabcd
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议