链接: (https://njoj.org/Contest/749/)

总体很屎.. F题的n^2一直觉得会T没有敲, 没想到其实是对的.. 1小时的时候做了A, C, J.. 然后就一直吃屎F..

A

划水, 对字符串t也可以使用这种变换.. WA了一发.

B

几何, 占坑

C

给定你一个数n，请你统计出在[a,b]这个区间中和n互质的数的个数。两个数互质当且仅当他们除了1之外没有其他的公共因子或者他们最大的公共因子是1。1和任何数是互素的。

容斥原理, 把求[1, r]的与n互质的数转换成[1, r]的与n不互质的数. 然后容斥一发

搞定. (这其实是我第一次写容斥.. 一发就对蛮爽的)

D

还是容斥, 占坑.

E

比较烦, 坑不填了

F

将一个给定的数列，拆分成K个不降序列，每个数出现且只出现一次，且在各序列中各个数相对于原数列的相对顺序不变。如7 6 9 8 10可以拆成 7 9 10和6 8。求最小的K值。

水题.. 然而没敢写n^2.. 后面4小时都在死磕这题..

最初想法.. 以 7 6 9 8 10为例.. 输入7, 新增一个序列, 输入6, 新增一个序列, 输入9, 放在之前最大的7的后面, … 类推..

其实这是n^2的.. 当时我想n^2太慢, 来个二分, 结果不知道咋二分, 其实仔细想想, 维护的那个数组肯定是递减的数组..

需要面壁 . 这种线性表的题已经不知道多少次被卡住了, 很烦. 当时一直在O(n)和nlogn那里死磕.. 没有稍微自习分析下. 需要做一些这种练习题.

G

给出一个非负整数A，将这个数字的最低位移动到最高位（原来的最高位变为次高位，次低位变成最低位），得到非负整数B，发现B恰好是A的k倍。现给出A的最低位的值n，和倍数k，求最小的非负整数B。

比赛的时候没有看题..

H

anti-nim 游戏. 主要是nim都忘了..

nim游戏是谁拿了最后一个石子谁赢, 这个游戏相反, 拿了最后一个的输.

nim游戏的必败态就是x1 ^ … ^ xn = 0的状态.

考虑anti-nim. 如果全部都是1, 那么n为奇数必败, 为偶数必胜.

如果有很多1, 以及一个大于1, 必胜(可以根据1的个数选择把>1变成=1或=0)

SG=x1 ^ x2 ^ … ^ xn.

当SG = 0. 充裕堆石子个数>1, 孤单堆=1.

S0: SG>0, 充裕堆为0.

S1: SG>0, 充裕堆为1.

S2: SG>0, 充裕堆>1.

T0: SG=0, 充裕堆=0

T2: SG=0, 充裕堆>1

显然S0为必败, T0必胜. S可以转移到S/T, T只能转移到S.

S1必胜, 因为其可以转移到S0.

T2只能转移到S1/S2, S1必胜, 若T0想赢只能转移到S2, 而S2可以重新转移回T2. 因此T2最终只能转移到S1, 必败.

因此S2必胜.

I

没有看题, 题解说是2-SAT等我写一次2-SAT再说. 挖坑.

J

水题