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代码:请点按此处

CodeForces 236A Boy or Girl

题意

判断字符串长度是奇数还是偶数。

思路

代码

 

Codeforces 589A Email Aliases

题意

给出了一堆电子邮件地址,要你按照一定的规则分类,然后一类一类地输出。

思路

模拟。

只要正确地理解了题意基本不会有问题,在实现方面,可以考虑使用map的迭代器轻松地完成分类操作,令map的key为邮件地址的Hash(其实就是按照题目规则把等价但不同的邮件地址处理成同一个字符串),value为set<string>用来当作不同形态的邮件地址的容器。

代码

 

Codeforces 515B Drazil and His Happy Friends

题意

Translated by paryerhgq

Drazil有很多朋友,他们中有些人是快乐的,有些人是不快乐的。 Drazil想让他的朋友变得快乐。于是,他发明了以下的计划。
在他的朋友中,有n个男孩和m个女孩。我们把男孩从0到n-1编号,女孩从0到m-1编号。在第i天,Drazil邀请第i mod n个男孩和第i mod m个女孩一起吃饭(注意i从0开始)。如果两个人之中有一个是快乐的,那么另外一个也会变得快乐,否则,这两个人的心情状态不会改变。一个人一旦成为快乐的人(或者他原本就是快乐的),他能保持永远快乐。
Drazil想知道他是否可以使用该计划,使得他所有的朋友都变得快乐。

思路

注意到问题规模比较小,所以我们直接模拟就好了但是我们要至少操作2*nm次才可以。

有一种不暴力的解法,我们发现我们最后能够变快乐的人的编号x一定满足x = a (mod gcd(boy,girl)),其中boy是男生人数,girl是女生人数,a是某个一开始就快乐的人的编号,这样我们只要扫一遍所有快乐的人,在模gcd(boy,girl)的完全剩余系里标记一下就搞定了。

代码

暴力:

数学:

 

UVA 12946 Peanoland contacting Gaussland

题意

给出了一个从整数到复数的映射,你要求出给你的整数映射成的复数的实部和虚部。

思路

STL complex裸题。

直接模拟就好,当然自己写一个complex结构体也不是难事。

代码

 

UVA 12955 Factorial

题意

给出你一个数,问你这个数最少能用多少个数(可以重复)的阶乘表示出来。

思路

使用一种简单的贪心策略:

从一个刚好比给出的数小的阶乘开始,不断尝试减掉较大的阶乘,直到将给出的数减为0 。

这个贪心策略是合理的,因为如果我们当前可以减掉n!,我们减掉(n-1)!一定不如减掉n!优,因为n!=n*(n-1)!,相当于我们多减了n次,所以我们要减掉n!才能保证最优。

代码

 

CodeForces 583A Asphalting Roads

题意

修路,一次选定一个横排一个竖排,如果横排竖排都没修,就把横排和竖排都修好,否则不用管。给出你若干修路尝试,问你哪些尝试最终执行了。

思路

照着题意简单模拟一下就好了。

代码

 

UVA 10054 The Necklace

题意

给出若干二色珠子,问你能不能把他们重新排列以连成一条环,使得相邻的两个珠子颜色相同。

思路

转化为欧拉图问题。令结点代表不同的颜色,连接两个结点的边代表珠子。把珠子连成项链的过程转化为求出一种走法使得我们可以走完全部的边然后返回起点。这就是典型的欧拉回路问题了。

如果不会这个知识,请参考:有关欧拉图问题的一些总结

代码

 

URAL 2066 Simple Expression

题意

给出三个数,要你求出用这三个数进行加减乘运算可以得到的最小值是多少。

思路

问题规模相当小,可以枚举每一种算术组合。也可以使用一些贪心策略少枚举一些情况,详情请参考下面的代码。

代码

 

ZOJ 3254 Secret Code

题意

求小于等于M的数中有多少个可以使得A^x=B(mod C)成立。

思路

首先利用extended BSGS求出最小的x使得A^x=B(mod C)成立。

接下来我们要求出最小的len使得A^(x+len*k)=B(mod C),我们知道模C的指数循环节是Phi(C),对于某个特定的幂的最小循环节则一定是Phi(C)的约数。我们要枚举Phi(C)的各个素因数,不断试除试算,知道得到最小的循环节长度len。

得到了x和len之后,答案就是(M-x)/len+1。

代码

 

Scroll to top