第十六轮非官方题解

出题人好像鸽了

A. 超简单题 (普及组 T1 Only)

一个简单的贪心，我们知道n个线段一定要用全，否则一定不优
接下来我们就要判断一个边长为a,b,c的三角形能否被搞出来，c=总长-a-b
那么我们用布尔数组f[a][b]表示其中两边为a,b能否被表示出来（背包问题）
直接dp就可以过了
当然可以用bitset进行优化

B. 超级水题 (普及组 T2 Only)

我们可以从小到大枚举数字j出现的所有位置，那么对于以后出现的数字，一定会比j大，那么在j所在位置之前的数字就会对逆序对数有贡献，动态统计逆序对数，用树状数组即可

C. 大送分题 (提高组 T1 Only)

每次修改都是伪随机的。

修改到最小值的概率为 $1/n$，此时暴力扫一遍数列求出最小值即可。

期望时间复杂度 $O(m)$

D. 人口普查题 (普及组 T3 / 提高组 T2)

来自 QOJ Round #6 的 B 题

令f[i][j]表示将s的前i个字母修改为t的前i个字母的代价。
操作1：f[i][j]=f[i][j-1]+a
操作2：f[i][j]=f[i-1][j]+b
操作3：f[i][j]=f[i-1][j-1]+c
由于a+b<=2*d，因此每个数只会交换一次，并且交换后不会替换。
操作4：记k为s中上一个t[j]的位置，l为t中上一个s[i]的位置，f[i][j]=f[k-1][l-1]+d+(i-k-1)*b+(j-l-1)*a
时间复杂度O(|s||t|)

E. 打卡签到题 (普及组 T4 Only)

把n!末尾所有零都去掉，然后对10取模
对10取模不太好处理，我们从n!提一个2出来，先对5取模，然后再乘2
1/2在mod 5意义下等于3
两边对5取模，就是（5k)!/(10^k) = (1*2*3*4)^k*3^k*k!
设f(n)=n去掉末尾所有0
也就是f(5k!)=f(2^k*k!) (mod 10)
如果n=5k+t, 那么暴力乘上多的t个数

F. 最简单题 (提高组 T3 Only)

这是一道原创题，放最后讲jian，出题人拍脑袋的时候觉得很easy，但是实际情况确实挺难调的……
这是一道大模拟题，可以说不怎么考察算法水平，主要考察代码能力。
现在提供两种做法：
做法一：直接在展开图上进行操作，将18种转动情况分类讨论过去，部分类似的可以进行合并。
做法二：将展开图先转化成三维魔方，其中每个魔方的单元格子记下6面的颜色，没有颜色记为0，然后转动情况写起来会少很多，最后再将三位魔方转化成展开图输出。
做法一比做法二容易想，也不用进行输入输出的转化，就是细节偏多，做法二主要难度在于要将平面图转化成三维图。
出题人写了做法二。
欢迎提供更优秀的做法。

G. 白给题 (提高组 T4 / 省选组 T1)

令 $b_i$ 表示 $a_i$ 下一次出现的位置，那么询问等价于求 $b_l \sim b_r$ 中 $>r$ 的数的个数。

用树套树维护 $b$，并对每个值开一个 std::set 记录它出现的位置，每次修改时在 std::set 中查询它的前驱和后继并修改它们的b值。

区间修改后，可以把这个区间缩起来，只保留它的左端点。每个修改操作只会使段数+2，每次修改 $b$ 值会使段数-1。时间复杂度 $O((n+m)\log^2 n)$

H. 神秘题 (省选组 T2 Only)

对于 30%的数据
枚举一个子网格图的一个顶点，一边往下扫一边维护区域内的点数，统计答案。
时间复杂度：O(N^3)
对于 60%的数据：
我觉得这题可能有 N^2 的解法，但是我没想到。希望有想法的同学与我交流一下。
对于 100%的数据：
显然，题目可化简为：给定 N 个数的一个排列，问这个序列中有多少个子区间的数恰好是连续的。
进一步可以化为：有多少种情况使得，相邻的 k 个数中最大值和最小值的差小于等于 k-1。
大致有两种解法，一种是分治，一种是线段树。
这里主要讲一下分治的解法。
考虑分治，对于当前分治区间[L,R]，记区间中点为 mid。当前区间的答案就是Ans[L..mid]+Ans[mid+1..R]+跨过中点的合法区间数，然后就分为两种情况了：
1.最小值和最大值在同侧。
2.最小值和最大值在异侧。
下面只考虑最值同在左，和最小值在左，最大值在右的情况。其余两种是对称的。
对于最值同在左侧的情况，我们枚举左边界在哪，然后可以计算出右边界的位置，在判断是否合法，统计答案。时间复杂度：O(N).
对于最小值在左侧，最大值在右侧的情况，可以用单调栈+桶来完成这个任务。时间复杂度：O(N).
总的时间复杂度：O(NlogN)/O(NlogN^2)
简单提一下，线段树解法的思路大致也是维护一个单调栈，
然后进行区间修改和查询，统计答案。
时间复杂度：O(NlogN).

I. 大原题 (省选组 T3 Only)

测试点1~3：送分点，手玩。
测试点4：每种颜色的两个点分别出现在第1列和第m列，dp求带权最长上升子序列。
测试点5~6：有些颜色会出现在同一侧，加一个区间dp即可。
测试点7：每一圈有两种颜色，可以直接连起来。
测试点8：一些圈的两种颜色交替出现，但是上下两圈都是空的。
测试点9：每种颜色都可以直线连起来。
测试点10：把价值为0的颜色看做障碍，同上。

J. 思考题 (附加)

看不懂，可以参考 https://codeforces.com/blog/entry/62010?#comment-460369

30 分可以考虑直接暴力在自动机上跳，需要卡常

uooogoo的博客

博客