-->

SHOI 2017

5/6

还有一题留坑待填吧,我实在填不动了……..


bzoj4868: [Shoi2017]期末考试

很容易看出来这个函数是单峰函数
因为如果出成绩的时间太长 学生会有意见 造成C贡献的多
如果太短 则老师不开心 所以A和B的贡献多
而且这些贡献如果偏离答案越多 贡献就会越大
所以这个函数是个单峰函数
每一次三分后维护前缀和用log时间来判断
判断的时候很显然B比A小的话全部用B 如果B比A大的话就尽量先用A 把小的变大 然后再用B
时间复杂度$$O(N2logN)$$


bzoj4869: [Shoi2017]相逢是问候

有点像洛古的一道题啊
这道题其实就是求
$$c^{c^{c^{.^{.^{a_i}}}}}$$

然后用到两个知识
$$n->phi(n)$$最多只需要log次左右就可以到1
$$a^x\equiv a^{x \bmod \varphi(n) + \varphi(n)} \pmod n (x\ge \varphi(n))$$
就是拓展欧拉定理

所以我们只要维护一个线段树 每个点暴力最多修改log次 log次变换后 这个值是不变的
因为
$$ x \bmod 1 + 1 = 1 (x > 0) $$

但是这里有两个问题就是

我们要维护多一个phi=1,因为ai有可能等于0
假设p=3 c=2

$$2^{2^{0}} \bmod 3$$
其实就是
$$2^{(2^{0}) \bmod 2 +2} \bmod 3$$
其实上面是少了个$$0 \bmod 1 + 1$$ 因为0比1小

那么到此为止 你是不是认为以后再怎么操作 这个值是不会变的呢?
其实不是的
因为再添多一个2的时候 值会改变,不信你看下式和上式相不相同
$$2^{(2^{(2^{0}) \bmod 1 +1 })\bmod 2 +2} \bmod 3$$
原因也很简单 你希望以后都是$$2^{?},?=1$$ 但是第一个式子却没有做到 ?=0
所以再补一个1就好了

然后还有一个问题是我们如何判断
$$a^x\equiv a^{x \bmod \varphi(n) + \varphi(n)} \pmod n (x\ge \varphi(n))$$ 后面的条件我们应该如何处理
我是用快速幂的时候搞了点奇怪的东西 使得次幂小的不容易被上式忽略掉,次数大的一般没有什么问题
(不知道我这样搞有没有漏洞,但是准确率还是非常高的,很难卡)

时间复杂度大概是$$O(NlogN2logP)$$

好像还可以预处理出phi的所有次方,然后O(1)询问次幂 对于上诉条件用其他奇怪的方法判断呢?
好像有人这么写的,时间复杂度少了一个log


bzoj4870: [Shoi2017]组合数问题

从定义分析式子就是NK个数,取出的数的个数%K=R的方案数
这个东西可以用dp来解决
$$dp[i][j]$$允许用前i个数,取出的数的个数j%K=R的方案数
矩阵乘法统计就好了


bzoj4872: [Shoi2017]分手是祝愿

这道题一开始就没什么思路啊,可能状态不是很对?
首先我们先考虑最优情况 肯定是从最大的按到最小的
而且这个是唯一解 所以对于初始状态 都有一个离目标状态的正确选择的步数假设为c
(这里所说的正确选择,指的是在唯一解中已经确定了每个位置按还是不按,所有正确选择就是某个位置按和不按的状态和唯一解相同)
然后问题就是在数轴上 从c点走到k点,随机走的概率
设f[i]为走到i点的概率
$$f[i] = \frac{i}{n}f[i-1]+\frac{n-i}{n}f[i+1]+1 [i>k]$$
这个状态就是i这个点推到后面去的
(其实这里我也觉得很奇怪,我习惯是后面推到前面,但是问了很多个大佬都告诉我是这样的)
然后这个是二次递推式 我们没有办法直接求
可是有个性质
$$f[n] = f[n-1] + 1 $$

$$g[i] = f[i] - f[i-1] [i>k]$$
其中
$$g[n] = 1$$
化简上式可得:
$$\frac{i}{n} (f[i]-f[i-1]) = \frac{n-i}{n} (f[i+1]-f[i]) +1 $$
$$g[i] = \frac {n-i}{i} g[i+1] + \frac{n}{i}$$
然后简单的跑个逆元这道题就结束了

bzoj4873: [Shoi2017]寿司餐厅

假设你懂什么是最大权闭合子图,而且你知道怎么实现,你就会做了
就是 i!=j时 有
$$f[i][j] -> f[i+1][j],f[i][j-1]$$
然后对于每个ai开多一个点就好了

最大权闭合子图的怎么做:
ST-> 正权点 流量:点权
负权点 -> ED 流量:点权的绝对值
原图的边都连inf 跑一遍最小割
$$Ans = 正点权和 - 最小割答案$$
证明大概就是每个点 只需要对后面的点负责 不用对前面的负责 所以要把后面的路径上所有边都删掉
选择一个正权点->不割他的边(或者说割一条正权点的边就是以后都不用选择了,流量流不出来)
选择一个负权点 -> 割他的边