T1 音标
考虑模拟。
每次读取一行字符串,从头到尾枚举,判断这个字母应该变为哪一个字母,然后直接替换并输出即可。
这样,我们就可以通过这道题目。
T2 躲藏
设原字符串数组为s,模数2000120420010122为Mod,将字符串中所有的大写字母预先变为小写
字母。
考虑动态规划。
令f[i][j],(j=1,2,3,4)表示前i个字符中,匹配了字符串"ewbe"的前多少位,那么有转移方程:
f[i][1]=(f[i−1][1]+(s[i]==′c′))%Mod
f[i][2]=(f[i−1][2]+(s[i]==′w′)∗f[i−1][1])%Mod
f[i][3]=(f[i−1][3]+(s[i]==′b′)∗f[i−1][2])%Mod
f[i][4]=(f[i−1][4]+(s[i]==′c′)∗f[i−1][3])%Mod
理论上这样还是不能通过本题,因为数组的开小大概需要35MB左右,超过内存限制。我们来考虑优化这个状态设计。
容易发现,每一个字符的状态都只从它前一个字符的状态转移过来,显然我们可以考虑使用滚动数组来优化空间开销,这样就可以通过本题。
我们考虑去掉第一维的状态, 只保留第二维的状态。那么转移方程就变为:
f[1]=(f[1]+(s[i]==′c′))%Mod
f[2]=(f[2]+(s[i]==′w′)∗f[1])%Mod
f[3]=(f[3]+(s[i]===′b′)∗f[2])%Mod
同一个位置有且仅有一个字符,不难发现转移方程间是不会相互影响的。因此,省去第一维的状态是正确的。
这样,我们就可以通过这道题目。
T3 博弈
数据组数较多,我们优先考虑预处理数组,然后直接回答询问。
考虑贪心。
当k=1时,游戏会一直继续下去,谁也无法取胜,故平局。
对2≤k的每一个k,枚举每一个数字,考虑它需要做几次操作,才能将这个数字变成全部为零的数字。
可以看出,最后的答案只与总操作数的奇偶性有关,而数字的总操作数是一定的,故这是一个假的博弈论。
对操作数求一个前缀和,判断其奇偶性,即可。
这样,我们就可以通过这道题目。
T4 妹纸
比较容易可以看出,假设我们要计算k取模后的值,我们只需要看k mod (r−1)是否在区间[l,r)中,如果在,那么结果为0,否则结果为k mod (r−1)。
这样,整个序列就会变成:
1,2,……,l−1,0,0,……,0,1,2,……
其中,l−1到下一个1之间共有r−l+1个0。
聪明的读者可以看出,询问区间必定是由最多三个等差数列求和而得。
不妨称1,2...,l−1为一个连续段
我们可以将区间(a,b]分成三个部分,第一段为开始部分到第一个连续段结束(如果开始位置不在连续段内,则第一段记做0),第三段为最后一个连续段开始到结束部分(如果结束位置不在连续段内,则第三段记做0),中间段即为多个连续段的和。
显然,这三段都可以使用一些等差数列求和的公式来计算,细节较多,可以参考样例代码。
这样,我们就可以通过这道题目。
T5 幻方
考察选手空间力和想象力。
由于是从内部观察激光发射器的位置,比较难以想象。
我们假设从外部观察。设正面、左面与顶面的交的方块为参考点,记做(1,1,1),沿着正面的项边为x轴,项面的左侧边为y轴,正面的左侧边为z轴。
这样,从内部看这六个面,分别是:
●正面: x轴从大到小,z轴从小到大。
●背面: x轴从小到大,z轴从小到大。
●左侧面: y轴从小到大,z轴从小到大。
右侧面: y轴从大到小,z轴从小到大。
●项面: x轴从小到大,y轴从小到大。
●底面: x轴从小到大,y轴从大到小。
对于每个面的激光发射器,将一个二维坐标标记,然后枚举空间中每一个坐标, 判断是否三组坐标都被标记(即(x,y)、(x,z),(y,z)), 如果都被标记,那么答案加1。
这样,我们就可以通过这道题目。
T6 异或与T7重复
考虑动态规划。
令f[i][0/1]表示第i个点不选择(0) 或选择(1)时的最大独立集的大小是多少。
那么我们可以设计出转移方程:
f[i][0]=∑max(f[son[i]][0],f[son[i]][1])
f[i][1]=∑f[son][0]
其中,son[i]表示i的子节点。
先来考虑第二个式子。如果当前节点被选择了,那么它的所有子节点都不能被选择,这个比较容易理解。
再考虑第一个式子。如果当前节点没有被选择,那么它的所有子节点可以被选择,也可以不被选择。
读者可能会有一个疑问:为什么当前节点没有被选择,它的子节点不被选择时,最大独立集的大小反而会增大呢?
我们不妨考虑一条长度为偶数的链,如图所示。

我们可以选择0、2、4三个点,也可以选择0、2、5三个点。倘若节点4后跟了许多节点,显然我们应该放弃节点4的贡献,而将4的所有子节点贡献计算到答案中。
对树做完树形DP之后,那么答案即为f[s][1]。
这样,我们就可以通过这道题目。
T7 旅游
考虑动态规划。
令f[i][0/1]表示第i个点不选择(0) 或选择(1)时的最大独立集的大小是多少。
那么我们可以设计出转移方程:
f[i][0]=∑max(f[son[i]][0],f[son[i]][1])
f[i][1]=∑f[son][0]
其中,son[i]表示i的子节点。
先来考虑第二个式子。如果当前节点被选择了,那么它的所有子节点都不能被选择,这个比较容易理解。
再考虑第一个式子。如果当前节点没有被选择,那么它的所有子节点可以被选择,也可以不被选择。
读者可能会有一个疑问:为什么当前节点没有被选择,它的子节点不被选择时,最大独立集的大小反而会增大呢?
我们不妨考虑一条长度为偶数的链,如图所示。

我们可以选择0、2、4三个点,也可以选择0、2、5三个点。倘若节点4后跟了许多节点,显然我们应该放弃节点4的贡献,而将4的所有子节点贡献计算到答案中。
对树做完树形DP之后,那么答案即为f[s][1]。
这样,我们就可以通过这道题目。
T8 纪年
不难发现,天干与地支的组合每60年为一个循环,我们可以直接将两个年份之间的差对60取模后,模拟即可。
亦可寻找年份与天干地支的关系,通过找规律寻找到答案。
这样,我们就可以通过这道题目。
T9 排名
通过公式,对每个人计算得分,然后排序即可。
可能需要注意排序时的常数问题。
这样,我们就可以通过这道题目。
T10 零点
对开头和结尾单独处理它们可能的整数零点,然后对每一"段函数计算零点是否为整数。
我们有斜率计算公式k=x2−x1y2−y1,那么就有y1=x2−x1y2−y1x1+b,所以可以得到b=y1−x2−x1y2−y1x1。所以即有方程:
y=(x2−x1y2−y1)x+(y1−x2−x1y2−y1x1)
令 y=0, 则 x=x1−y1y2−y1x2−x1 。
类似的,可以推出左右两条射线的方程,这里留给读者独立思考。
注意,可能有精度问题,可能会爆int,可能会有无数个整数零点的情况,需要选手多加判断。
这样,我们就可以通过这道题目。