按照陈越姐姐的要求,成都的出题任务都避开了现役队员,所以出题的都是老人或教练。不过周一下午,ArcOfDream有幸在vls, hhanger的监督和LCLL的干扰下,提前做了一下这套题,主要目的是作为小白鼠检验一下题目。当然我们也只能以此弥补一下没能去成都旅游参加的遗憾了。比赛一结束所有东西都被销毁了,我可没有什么「完全記憶能力」,而且之后题目也做了修改,所以这里的描述可能和实际略有出入,特别的规模上1w和5w可能分不太清。正式比赛题目顺序有调整,H插到了原来的F(现在的G)的前面。

本来想写的是解题报告,不过这套题目将在下周作为The 2010 ACM-ICPC Asia Chengdu Regional Contest的Practice挂到ZOJ上,所以很多人恐怕不想看剧透吧,所以决定把题目描述和ArcOfDream的“实验报告”分开来。描述中灰底的变量是输入;黄底的变量是输出。


我是剧透的分割线


A Balanced Number

xgy

本题有100个case。一个10进制number称为balanced的,如果存在一个digit,其余digit关于这个digit的力矩和为0。例如4209关于0的力矩和是4*2+2*1-9*1=0。题目要求在区间[a, b]内的balanced number的个数。范围原本是1e9,经我们建议后加强到1e18。

B Battle

vls

本题只有10个case。题目就是在战争中,一个国家有n≤10000个城市,m≤50000条道路,其中一些道路坏了,修复道路有对应的费用。每个case要输出n行,第i行表示城市i被敌国占领时,依然要保持其余n-1个城市连通需要修复道路的最小费用,如果不可能,输出inf。题目保证原图连通。

C Binary Number

签名题。本题有100个case。定义f(a, b)为a和b二进制表示中不同的digit的个数,即Hamming距离。每个case是n≤100个不超过1e6的整数,有m≤100个查询,对每个查询x,输出使得f(x, y)最小的y

D Detect The Placement

vls

平面中已知一条入射光线和一个三棱镜,知道折射率,问光线将射到y=0的什么位置x。题目保证不会发生全反射。我们做的时候发现sample和标程输出的bug,据说vls的原题是三维的平行六面体。

E Double Maze

题目的背景就是Double Maze这个游戏,关于这个游戏的规则可以自行google。题目给的就是一个规模为6*6的Double Maze,然后要输出最短的solution,如果有多个最优解,输出字典序最小的。

F(G) Go?

cpcs

本题有100个case。对每个case,求调用gao(0, n, m)可能输出的最大值,其中gao的定义如下:

void gao(int depth, int n, int m) {
	printf("%d\n", depth);
	if (depth < m && x[a[depth]] + x[b[depth]] != c[depth]) {
		gao(depth + 1, n, m);
	}
}

其中a, bc都是题目输入给定的长度为m≤10000的数组,a和b的元素都是小于n≤100的非负整数,c的元素是0, 1或2,x是一个长度为n的不确定数组,其元素是0或1。

G(H) Jenga

Fire

本题有1000个case!题目的背景是Jenga这个游戏(wiki: Jenga),规则看wiki吧。Jenga的操作可分为三类:

  1. A(111) => B(101)
  2. A(111) => C(110)
  3. C(110) => D(010)

某个人进行某类操作的的成功率由输入给出的b[i][j]d[i][j],与及当前Jenga的高度n决定,操作的成功率就是max(0, min(1, b – n * d))。两个人轮流操作,要求对初始层数为n≤18的Jenga,先手在最优策略下胜利的概率

H(F) Error Curves

LCLL

本题有100个case。题目给定定义域在[0, 1000]的n≤10000个二次函数f_i(x)=ax^2+bx+c,其中a≥0。要求函数S(x)=max{f_i(x)}的最小值。原本听说只准备了十个气球,打算毙掉这道5min题了。

I Rescue

hhanger

本题有100个case。题目给n≤50000个石头,每个石头有整数坚硬度m[i]≤1e9,假设你有能力值p,那么你站在第i个石头上施法,可以使所有j≤i的石头的坚硬度减小max(0, p-(i-j)*(i-j))。如果石头的坚硬度小于0,那么就被破坏了。题目要求的是能在题目给定的k≤100000次内破坏所有石头所需的最小能力值p。

J similarity OOXX

LCLL

本题有100个case。题目的背景是分类。对4个对象,分类成AABB和CCDD应该是完全相同的,而XXYY和MNMN至少有两个不同。现在给出对n≤10000个对象的两种分类的结果,分类用字母表示,所以不超过26个。问至少有几个不同。

K Snooker

Fire

题目的背景就是斯诺克(wiki: Snooker)复杂的规则。这题是标准的Fire式蘑菇题,所以不知道死在哪里是很正常的,参考Tennis Scorer, Intelligent Pouring RobotGolf Match。能过的是ネ申。

10 Responses to “[ネタバレ注意]とある山寨の成都問題”
  1. fookwood says:

    只能水c题的菜鸟路过

  2. pfctgeorge says:

    呃… 貌似A题的4*2+2*1-9*1!=0 吧。。。

  3. Navi says:

    cpg那题a, b, c的下标写错了?

  4. K says:

    cpcs 的代码描述是不是错了?

  5. pfctgeorge says:

    貌似Error Curves这种让人内牛满面的题真被毙了哟~

  6. Navi says:

    sf个

  7.  
Leave a Reply