Editoral for SCUT ICPC Team Qualification Round A

点按此处下载题面

PROBLEM A

很明显,双方最优策略是一直往前走,对手一直往前就能赢了,所以bx hao sui啊!

PROBLEM B

做这个题需要知道二项式定理,乘法逆元和等比数列求和,组合数取模。

    \[\sum_{i=1}^{n}(a^{i}+b^{i})^{k} = \sum_{i=1}^{n}\sum_{j=0}^{k} \binom{k}{j} a^{ij}b^{i(k-j)}=\sum_{j=0}^{k}\binom{k}{j} \sum_{i=1}^{n}q^{i}\]

    \[q = a ^ {j} b ^ {k-j}\]

后面就是等比数列的求和。

需要注意的是q=1的时候。

二项式系数可以用阶乘和逆元预处理,等比数列求和也可以用逆元求出来。复杂度O(Klog(N))。

PROBLEM C

这题求的是一个有向无环图的最小树形图。可以对每个点,选一个权值最小的入边加起来就是答案。

PROBLEM D

直接模拟统计出到最后时刻情怀值会受损多少。对于每个时间点,如果不能ak,则损害值增加tn-ti。最后总的损害值如果比原始情怀值小则just enjoy coding,否则fail to graduate。

PROBLEM E

PROBLEM F

PROBLEM G

 

PROBLEM H

对于每个数,我们需要满足的条件有两个:一个是各数位数字单调递减,第二个是这个数字满足被6整除。首先,如果直接枚举满足第二个条件的数,那么要枚举的数太多,复杂度太高。那么我们首先考虑满足第一个条件。各个数位的数字单调递减说明了各个数字不同(即每个数只能选一次),而数字只能在0-9这10个数选取(说明最多取10个数),且满足单调递减(说明对每组取的数,只有一个方案是符合的)。于是所有满足条件“各数位数字单调递减”的数字只有C(10, 1) + C(10, 2) + C(10, 3) + … + C(10, 9) + C(10, 10) = 2^10-1 = 1023。于是我们可以通过搜索的方法找到所有满足第一个条件的数,然后判断是否满足第二个条件。搜索的方法是先枚举高位,再枚举低位,每次枚举的数都得比高位的数小,直到没有数可以枚举(最小是0)结束。用递归可以解决。最后我们求出所有满足第一和第二个条件的数只有两百多个。注意最大的数会超出int的范围,所以我们可以用一个long long数组存下满足条件的数。接下来我们由于我们最多只有20组数据,所以我们可以判断每个合法的数是否小于或等于输入数据。

主要部分代码如下:

 

PROBLEM I

 

PROBLEM J

把下标乘上1000得到一个递推式子,

BX(n) = BX(n – 1000) + BX(n – 1234)。

答案就是BX(n*1000)

Author Information

ABCJ : doubility(czk)

DH : ConquererV587(kbx)

GI: Xdynix(rxy)

Editorial/Tutorial for TIC Weekly 2

Summary

本次比赛总体难度:BASIC

问题难度分布:
BASIC 4题 A C G I
MODERATE 3题 D E F
ADVANCED 2题 B H
HARD 1题 J

比赛的参加人数过少,所以无法从数据中观测到太多有价值的信息,不过大家的实现能力和读题的耐性还有待提高是一定的。

恭喜Winner:何|浩宁。

本次标题梗:同人社团Alstroemeria Records的音乐作品,下面的标题都是可以戳进去的。

A – Against, Perfect Cherry Blossom.

Vocal版来自专辑Double Counterpoint 是Alstroemeria Records与Syrufit的合作专辑

原始问题:URAL 2066 Simple Expression

难度:BASIC

知识点:暴力枚举 基本实现

详细题解与AC代码:请点按此处

B – Bad Apple!!

传说曲Bad Apple!!(fect. nomico)来源于专辑Lovelight

原始问题:UVA 10054 The Necklace

难度:ADVANCED

知识点:图论 欧拉回路

详细题解与AC代码:请点按此处

C – Crystallize Silver

来自专辑BLUE NOTE Original Score: クリスタライズシルバー 東方妖々夢

原始问题:CodeForces 583A Asphalting Roads

难度:BASIC

知识点:基本实现 模拟

详细题解与AC代码:请点按此处

 

 

 

D – Dark Road

来自专辑Harmony Original Score: 厄神様の通り道 東方風神録

原始问题:UVA 12955 Factorial

难度:MODERATE

知识点:贪心

详细题解与AC代码:请点按此处

E – End Of Daylight

个人比较喜欢的Vocal版本来自专辑Fragment Reactions 早期专辑亦有其他Arrange

原始问题:UVA 12946 Peanoland contacting Gaussland

难度:MODERATE

知识点:模拟 STL

详细题解与AC代码:请点按此处

F – Fragment Reaction

Fragment Reaction 专辑同名曲。

原始问题:HDU 1241 Oil Deposits

难度:MODERATE

知识点:DFS

详细题解与AC代码:请点按此处

G – Graphical Scenery

外援Ryo Ohnuki的原创曲 来自专辑DANCEFLOOR COMBAT

原始问题:Codeforces 515B Drazil and His Happy Friends

难度:BASIC

知识点:模拟 暴力 简单实现 GCD

详细题解与AC代码:请点按此处

H – How Is Your Eyes Crazy?

来自专辑Lovelight

原始问题:Codeforces 589A Email Aliases

难度:ADVANCED

知识点:STL 模拟

详细题解与AC代码:请点按此处

I – Imperishable Night

来自专辑Double Counterpart

原始问题:CodeForces 236A Boy or Girl

难度:BASIC

知识点:基本实现

详细题解与AC代码:请点按此处

J – Japanize Dream

AR社的首张东方同人专辑

原始问题:CodeForces 3C Tic-tac-toe

难度:HARD

知识点:模拟

详细题解与AC代码:请点按此处

ACM Course 2 中文配套题面

Problem B(Original:POJ 3624)音乐游戏

PROBLEM DESCRIPTION

hahaschool非常喜欢玩音乐游戏,虽然他的水平差到不行,但他依然非常享受。众所周知,音乐游戏有好多种,不过作为音游狗,hahaschool显然不会去玩粗制滥造的音乐游戏(比如节操大师),也不会去摸某些打着音乐游戏旗号的音乐播放器(比如deemo)。因为hahaschool比较胖,腿部的力量和灵活性有限,所以也无法玩主要依靠腿部游玩的游戏(比如Dance Dance Revolution),同时因为hahaschool是一个害羞的男孩子,所以不会去玩要求模仿游戏里的动作的游戏(比如Dance Evolution)。即使面临诸多限制,音乐游戏千千万,在音乐游戏的世界里hahaschool总是能找到偷税(划掉)愉悦的好办法,不过因为hahaschool有选择困难症,又是一个理性派,所以每当他走进机厅,总会陷入不知道玩什么的迷茫,浪费宝贵的时间。

欢乐的时光总是短暂的,为了更好地享受音乐游戏,刚刚到达广州市区某机厅的hahaschool拜托你帮他作出选择。假设这家机厅里面有N种音乐游戏(因为机厅非常有钱,所以游戏的种类可能会多达3402种),对于第i种游戏有愉悦程度Di(1<=Di<=100),第i种游戏要投币Wi个(1<=Wi<=400),对于每种游戏,hahaschool只会玩一盘,因为这样才能享受到不同的愉悦,玩完一盘之后hahaschool就能得到游戏对应的愉悦程度。现在hahaschool的手里有M枚游戏币,因为不明原因,M可能多达12880,hahaschool并不需要花完全部的游戏币,请你算出hahaschool最多能得到多少愉悦?

INPUT

第一行:两个空格分开的整数N和M

第二行一直到第N+1行:对于第i行,会有两个有空格隔开的数Wi和Di

N,M,Wi,Di的含义及约定范围在题面中已经给出

请注意,测试数据有多组,所有的数据都会放在一个文件里,请处理到文件结束。

OUTPUT

请输出一个整数,是hahaschool在题目的约束条件之下最高能获得的愉悦程度总和,独占一行。

SAMPLE INPUT

4 6
1 4
2 6
3 12
2 7

SAMPLE OUTPUT

23

Problem C(Original:HDU 1114)壕的魔法财布

PROBLEM DESCRIPTION

众所周知gy非常壕,那么他那么多钱都是从哪里来的呢?

根据《刑法》,我们有:

第三百九十五条第一款 国家工作人员的财产、支出明显超过合法收入,差额巨大的,可以责令该国家工作人员说明来源,不能说明来源的,差额部分以非法所得论,处五年以下有期徒刑或者拘役;差额特别巨大的,处五年以上十年以下有期徒刑。财产的差额部分予以追缴。

第九十三条本法所称国家工作人员,是指国家机关中从事公务的人员。国有公司、企业、事业单位、人民团体中从事公务的人员和国家机关、国有公司、企业、事业单位委派到非国有公司、企业、事业单位、社会团体从事公务的人员,以及其他依照法律从事公务的人员,以国家工作人员论。

显然这两条并没有什么卵用,既然我们无法通过巨额财产来源不明罪威胁gy说出他如此壕的原因,我们只能雇佣专业的情报人员。

很快,我们就得到了情报,gy如此壕的秘密在于它有一个宝具“魔法财布”,每当gy需要钱的时候,他只要打开财布,里面就会掉出来金币银币各种币,然后财布会暂时性的变空。

因为gy是壕,所以跟gy跟级花约会的时候一定会买非常奢华的礼物,然而财布掉出来的钱币未必能够支付这件东西的价格,这样就会让gy显得非常没面子,所以gy必须要事先估算出财布里面最少装了多少钱,选择支付得起的最奢华的礼物,这样才能突显他的高贵。

INPUT

在评测过程中,所有的数据都是在一个文件里,请处理到文件结束。

在输入文件中包括了T组数据,在文件的开头,给出了T,独占一行。

之后,对于每组数据的第一行,是两个用空格分隔开来的整数E和F。E表示一个空的财布的重量。F表示gy拿出财布时,他感受到的财布的重量。重量的单位是克,最多10000克,毕竟gy有神力。(1<=E<=F<=10000)

在每组数据的第二行,给出了一个整数N,独占一行。表示财布可能会生成N种钱币.(1<=N<=500)

接下来是N行,每一行会有两个整数P和W,用空格分隔。P表示当前行所表示钱币的价值,W表示当前行所表示钱币的重量。(1<=P<=50000,1<=W<=10000,重量以克给出)。

OUTPUT

请输出财布中所含钱币的最小价值,独占一行。请注意,如果通过给出的钱币无法通过某种方式使财布的重量正好等于gy感受到的财布的重量,请输出-1.

SAMPLE INPUT

3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4

SAMPLE OUTPUT

60
100
-1

Editorial for 2015 ACM Course Practice Contest 1

The topic of this contest is Brute Force Searching techniques including Depth-First-Searching and Breadth-First-Searching.

The problems are ALL selected by Guo Yu (Union Class) from PKU Online Judge.The dataset and problem description are altered and translated by him.

I assessed the difficulty of these problems,implemented the solutions and wrote this editorial.Should you have any question,  please feel free to leave a comment on this post.Thanks!

If you want to practice these problems after the match, please visit ACMコース1〜DFSとBFS.

For test datasets, altered problem descriptions, and standard implementation provided by original contest holder,please check this archive ACM Course 1 .

A 迷宫还是三维的好

Problem Description

hahaschool误入了一个三维迷宫,他需要尽快离开迷宫,回宿舍打osu.他只可以上下左右移动,不能跨过障碍物,请你帮他算出他走出迷宫所需的最短距离.

输入包含多组,每组数据第一行包含三个整数数H,L,W (均不超过30)分别表示迷宫的高,长,宽.
接下来依次输入0,到H – 1层的俯视图.每层俯视图包括L行,每行W个字符.
最后一组输入为0 0 0,不需处理.
图例:
S:起点(有且仅有一个)
E:终点(有且仅有一个)
#:障碍物
. : 路
每组数据输出一个整数表示最少的步数,如果不能到达终点,请输出一行osu!以表遗憾

Original Problem

POJ 2251

Difficulty

BASIC

Key Point

Breadth-First-Searching

Tutorial

Click the following link to read:

POJ 2251 Dungeon Master

B 门前大桥下,游过一群鸭

Problem Description

“门前大桥下,游过一群鸭,快来快来数一数,二四六七八”你唱出来了对不对~
由于这首歌流传较广,一唱起来便觉得这时间再无鸭可数,也便没了兴致.
于是你开始数江,河,湖,海,水塘,浴缸,下水道……总之一切能数的水体,都要数个遍!
给出水域分布图,需要你数共有多少个两两不相连的水域.其中一个或多个相连的水体被认为是一个水域.(当且仅当格子间有一条公共边,才认为两格子相连)

输入
输入包含多组数据
第一行N,M(均不超过100)表示地图的尺寸(N*M)
接下来N行表示地图
图例:
. :陆地
W :水体

输出
输出一个非负整数,表示水域的个数

Original Problem

POJ 2386

Difficulty

BASIC

Key Point

Depth-First-Searching

Tutorial

Click the following link to read:

POJ 2386 Lake Counting

C 不扶不行

Problem Description

众所周知,yinz是一位德高望重的老爷爷.但是由于上了年纪,走路只能扶墙.为了锻炼身体,他来到了一个迷宫,机智的yinz看着迷宫的地图,开始思考扶着哪面墙走能最快到达终点,请你帮助他.yinz只可能向前后左右四个方向移动.

第一行输入一个整数 T(T<10)表示数据组数.
接下来T组数据,每组数据第一行包含两个整数数L,W (3 <= L, W <= 40)分别表示迷宫的长,宽.接下来L行,输入迷宫的地图.
图例:
S:起点(有且仅有一个)
E:终点(有且仅有一个)
#:障碍物
. : 路

每组数据输出一个整数表示最少的步数,为了表示对老年人的尊重,数据保证能够到达终点.

Original

POJ 3083

Difficulty

ADVANCED

Key Point

Breadth-First-Searching,Manipulating Directional Vectors

Tutorial

Click the following link to read:

POJ 3083 Children of the Candy Corn

D 卡牌大师

Problem Description

欢迎来到召唤师峡谷,作为一名成熟的召唤师,你拥有许多各色各样的英雄.他们是卡牌大师,卡牌大师,卡牌大师….还有卡牌大师.现在,你要做的不是中单,而是洗牌.
你洗牌的手法很娴熟,左手右手一个慢动作,一看就是新东方出来的.新东方洗牌的动作是这样的,
开始有两堆数量相等的卡牌S1,S2你需要轮流用两堆的卡牌插入,如下图所示

洗牌
当然这仅仅是第一轮,如果对牌序还是不满意,你会将这堆牌上下等分(上面的部分为S1余下的为S2)重复上面的操作,直到满意为止.
你突然好奇,要多少次轮才能得到你满意的牌序.

输入
第一行输入一个正整数N (1 ≤ N ≤ 1000),表示有N组数据
每组数据第一行输入一个正整数C(1 ≤ C ≤ 100),表示S1堆的牌数(S2的与S1相等).接下来的两行,输入两行字符串,分别表示S1和S2,其中不同的字符表示不同的牌.最后输入目标牌序.

输出
每组数据输出两个正整数,分别表示对应第几组数据,第一次获得目标牌序的洗牌次数(如果不能获得则输出-1)

Original Problem

POJ 3087

Difficulty

BASIC

Key Point

Simulation,Brute Force

Tutorial

Click the following link to read:

POJ 3087 Shuffle’m Up

E 素数们

Problem Description

素数们人口比较稀疏,要知道除了2和3相邻外,其他的素数可没那么好运气.他们每次互相拜访都会花费大量的时间来寻找.但是现在好了,素数们有特殊的”快捷通道”.比如1033要去拜访8179,他可以每次只改动某一位数,到达其他素数,最终到达8179只需要6步(1033->1733->3733->3739->3779->8779->8179).现在这种”快捷通道”已经推广了,有很多素数迫不及待的准备拜访他的朋友,请你帮助他们算出使用”快捷通道”最少需要多少步才能见到他们的朋友

输入:第一行一个正整数T表示输入数据组数(不超过100组)
每组数据包含两个四位素数a,b (不存在0002,0017,0107等输入)
输出:
对于每组数据输出最少步数.

Tips:
素数判断可以用埃式筛法预处理O(n),之后O(1)查询.

Original Problem

POJ 3126

Difficulty

BASIC(Assuming you can implement the sieve of Eratosthenes)

Key Point

Sieve of Eratosthenes,Breadth-First-Searching

Tutorial

Click the following link to read:

POJ 3126 Prime Path

F 寻宝

Problem Description

你是一名勇士,名叫ZhuRenGong.今天收到消息,沉寂多年的宝物DaBaojian又重现江湖,为了避免一场腥风血雨,时间紧迫,必须尽快赶到,夺取DaBaojian.
你有三种移动方式,假设你所在的位置为x,你可以走到x-1,x+1,或者瞬移到2*x.那么,拯救苍生的任务就交给你了,勇士.

输入
多组数据,处理到文件结束.
每组数据包括两个正整数N(0 ≤ N ≤ 100,000),K(0 ≤ K ≤ 100,000)

输出
请输出最少的步数

Original Problem

POJ 3278

Difficulty

ADVANCED

Key Point

Breadth-First-Searching with some optimisation techniques

Tutorial

Click the following link to read:

POJ 3278 Catch That Cow

Scroll to top