TuringJudge monthly 图灵姬月赛 2019.11【解题报告】

babyec 2019-11-09 17:34:43 2019-11-10 12:43:24

A 打印

基础min判断,判断打印白纸和不打印白纸即可,记得使用long long。

B 斐波那契新列

学过dp的应该都可以想到50分dp想法,

那么100分怎么做呢,考察异或性质

设两个数a和b,设a^b=c;

那么 a^b=c

第四项=b^c=b^(a^b)=a;

第五项同理可得=b

第六项为c

循环节为3.

C 买铅笔

普通Dfs可拿60-70分。

暴力暴力总是好的。

正解先说结论:选择一段连续的区间即可

为什么呢?

假设我们维护一个%n意义下的前缀和sum,

若有sum[a]==sum[b]

则a-b这一段区间可以被n整除。

现说明一定存在这样一段区间,

Sum[0]-sum[m]共m+1个

但是%n只有0-n-1种结果,n<=m

那么由抽屉原理,一定存在两个位置的值在%n意义下相等,

极限数据10W,n^2找相等会超时,那么o(m)预处理相等位置

或者二分找相等都可以。

D Mr.white的字符串游戏

不难看得出来这是一道dfs题目。

唯一麻烦的是需要输出每一步的操作,利用stl的vector< pair <> >维护或者结构体维护均可。

恭喜以下同学

AMAZE UI
Hello world!