10月刷题表②

· · 个人记录

【190pts】20191025垃圾测试

MZOJ139 小奇采药

垃圾题，垃圾搜索

MZOJ140 小奇的数列2

更新一下，发现并证明了一个**性质：在暴力$\Theta(n^2)$的基础上，我们把扩展到的点全部标记，表示这个点不可能作为$a_k$并产生一个$\ge$的区间，证明显然易证，实际上由于出题人不会造数据，可以很轻松的跑到最快，好像数据也很难构造出卡的**

MZOJ141 小奇学数论（分段打表80pts）

无聊的题目

MZOJ141 小奇学数论（容斥原理80pts）

容斥原理做法，我计算不来复杂度

搜索时要剪枝优化

P5023 填数游戏(65pts)

P5023 填数游戏

这题太太太太太难了！！！

实在没辙只能抄题解公式了。。。

学习PT2 NOIP2018 复盘

讲师全程吹b 2333

【251pts, Rank \ 2】2019洛谷秋令营提高组第二轮

T1 T103932 爆炸弓！

T100066 动态网络流

线段树

前提是你发现了是线段树就很简单了

T100433 买菜(51pts)

看了半个下午题解并没有弄懂那个证明，如果串的长度相同出现次数如何统计嘛

P1247 取火柴游戏

P2575 高手过招

阶梯NIM博弈 + \mathcal{SG}函数

\text{阶梯NIM博弈结论：奇数阶梯的石子异或和, 不等于0则必胜, 否则必败。}

证明显然易证

博弈论自闭啊。。。一考就炸

\color{Red}{\text{2019.10-26 17:36:13 刷过洛谷提高组试炼场}}

P2118 比例简化

水普及组水题

震惊，竟然忘记判断gcd(a, b) = 1就AC了

P2670 扫雷游戏

继续水普及组水题

P2010 回文日期

这题就要考一点细心了

考虑只需要枚举四位数就够了

虽然一次AC了, 但其实还有更简单的办法

枚举月份会更加简单，因为年份的合法性很好判断，而月份的合法性更难判断

枚举月份可以省略判断平年闰年，因为0229倒过来9220年一定是闰年

参加洛谷10月月赛III

T104062 小D与笔试

模拟题Hash

T104063 小E与美食

排序下即可

T104064 小C与桌游

开始看大家的分数就知道这个题有坑，然而我却找不到坑

喜得46pts然后想了很久都不知道贪心错在哪

后来我发现我仅仅是证明了第一问的贪心是是正确的，却没有管第二问的贪心

也就理所当然的以为第二问也是那样搞

然而找到错之后，又想了很久该如何处理这个问题

解决办法是开2个堆维护Min和Max

然后就一直卡在了76pts也不知道哪里错了

原因：$1.$清空队列的位置写错了，一直没发现 $2. $没有判断$q2$队列是否为空就强行取出，导致死循环$...
\color{Red}{\text{取出队首时一定要判断是否队列不为空}}

P5350 序列

这题$ODT$是真的伤 为什么本机对拍千组数据不会$RE$, 交上去全部$RE

改了一下，疑似是迭代器过期的问题，也就是说像用一个变量t保存之前的迭代器，然后再遍历一遍，然后在删除是错的

尽管上述操作都没有动set里面的元素(没有插入或删除)

然后我自己造的数据放到洛谷上，也得到了RE

此外其他坑点已在代码中说明

此外，造数据时是freopen("debug.txt", "w", stdout)这句话执行完之后输出数据才全部写入文件

\color{Red}{\text{迭代器一定要现配现用！}}

P2197 【模板】nim游戏

模板233

UVA11426 拿行李（极限版） GCD - Extreme (II)

P1390 公约数的和

P2398 GCD SUM

P2568 GCD

上面3题思路类似，有异曲同工之妙

顺便复习了下线性筛欧拉函数

设

g(n, i) = \sum_{x = 1}^{n}[gcd(x, n) = i]

则可以得到

g(n, i) = \phi(\dfrac{n}{i})

该柿子超级有用

P1045 麦森数

哇，又是一道普及组吊打提高组的题目

第一问计算位数我就不会。。。

高精度模板复习

P1050 循环

哇，普及比提高难系列专场

后$k$位的循环节一定是后$k - 1$位循环节的子集 换句话说就是如果后$k$位的循环节存在的话，一定是后$k - 1$位循环节长度的整数倍

P1062 数列

翻阅题解区，找到了一种\Theta(n)的算法【生成法】，可以生成1 \sim n的题目中的数列

此外，也可以在\Theta(\log n)时间内求出第n项

需要证明二进制下的"第n项所表示的数"(如101 = 3^2 + 3^0)与数列中的第n项一一对应

P1748 H数

生成法，构造法，求出整个数列

\text{unsigned long long}输出方法%llu

P2119 魔法阵

前缀和，组合计数，和提高组Day1 \ T2或Day2\ T1差不多

思想：设D - C = t, 可以枚举t, A, C这三个变量，然后套一套前缀和优化至\Theta(n^2)

由于前面带了一个\dfrac{1}{9}的常数，所以可以过

10.28晚学习完毕普及组7-数学

洛谷题目\color{Red}{81 \Rightarrow 75}

重要题目：

P1650 田忌赛马（很难想的贪心，也可以DP）

P1120 小木棍 ［数据加强版］（毒瘤搜索，打算以后参见算法进阶复习）

P3386 【模板】二分图匹配（匈牙利算法）

每次清空vis数组

P3958 奶酪（应该使用\text{unsigned long long}）

\color{Red}{\text{LONG\_LONG\_MAX的极限大约是}9.22 \times 10^{18}}

UVA1395 苗条的生成树 Slim Span（最小差值生成树，加强版见P4234 最小差值生成树）

全排列生成算法Get√

P5367 【模板】康托展开

康托展开复习

顺便看了下逆康托展开

P1088 火星人

P1094 纪念品分组(Review)

这个贪心算法证明还是有难度的

又让我想起了田忌赛马那道题这样就是不对的

P1056 排座椅

太菜了，打了11min代码，还是比yxc打得慢。。

用pair的大佬

P2672 推销员(Review)

首先，确定最远的住户只需要1个就够了，并且当最远的住户确定后，剩下的住户一定是最大的前X - 1个（剩下的住户满足距离 \le 最远住户）

不妨把所有满足上述条件的解分为两类：

  • 最远住户属于前X大
  • 最远住户不属于前X大

使用前后缀\max优化即可

10.29牛客暑期NOIP真题班普及组8-贪心 完结

P1080 国王游戏

今天学了高精度除法，终于AC了这道毒瘤题

其实高精度的题挺好的

P1233 木棍加工

考试的话我又凉了

这题竟然考的是LIS, 好吧，虽然最后我看出来了要覆盖DAG

但是没有想到可以一维排序，另一维求LIS

P2123 皇后游戏（还没写）

终于看懂题解了

牛客网CSP-S集训1

A.仓鼠的石子游戏

看了题解后有一个结论是: 对于任何一种不能再涂色的状态，已经涂色的石子数为偶数

实际上，无论怎样构造，都无法构造出反例，并且，你总可以找到一个√位置的相邻位置放×（设√表示颜色1，×表示颜色2）

考试时写了一个SG函数暴力算出了1 \sim 7的SG函数值， 惊奇的发现除了1的SG值都是0, 以为自己写挂了，然后发现第三个样例又对不上，然后调试了半天，发现自己每写错，第三个样例对得上...就是除了1的SG函数值都是0

报名CSP-S第二轮

B.乃爱与城市拥挤程度(Solution 1，树形DP, \Theta(nk^2 \log n)）

为啥我想的如此复杂

树形DP, \Theta(nk^2 \log n)

B.乃爱与城市拥挤程度（Solution 2, 树形DP, \Theta(nk \log n)）

这才是T2正经的树形DP

这个DP的状态设计挺关键的，为什么我没有这样设计状态？一个原因是我把条件中的K带入了状态里，导致方程没法转移，并且我习惯性的喜欢设f[x][i]距离恰好为i的....

这两个错误导致我无法在考试时间内做出这道题

由于错误的把K当成必要条件带入状态，导致我的DP方程无法转移，于是我就被迫改成二维状态进行表示

虽然是\Theta(nk^2 \log n)的复杂度，但还是卡过去了，但是这样无论思考还是代码实现都比正常写法困难的多

\color{Red}{\text{启示1：在树形DP中，当 <= i的状态就已经可以转移时，没有必要改成严格等于i}}

此外，就本题而言，我们发现....(难以描述)

\color{Red}{\text{启示2：一定不要把题目给你的K带入状态计算。状态是灵活可变的，只要最后能变出题目要求的状态就可以}}

C.小w的魔术扑克(30pts \sim 80pts)

跑二分图匹配

顺便复习了下匈牙利算法

C.小w的魔术扑克

把看似数据结构的题转化为图论模型！！

二分图还比较容易想到，但更应该观察那个二分图的性质！当然观察出来也很难啊

对于每张牌，把a[i]和b[i]连边，那么形成的联通块中，如果它不是一棵树，就一定可以全部打出

使用并查集搞一搞就可以了

P2123 皇后游戏

这题还真的是国王游戏的加强加强版

化简\min-\max函数的柿子就很困难啊，需要通过人脑智慧进行拆分

然后那个比较就更鬼畜了，柿子是要求排序后满足

\min(a_i, b_j) \le \min(b_i, a_j)

但根据这个柿子直接排序是会出锅的, 因为它不满足STL标准的传递性

然后分类讨论的三种情况我就真不知道该如何想到

COJ 高速公路 (highway)

相当好的一道树形DP题啊

自己想了一会，觉得z >= 0 和 一条链的分可以做

于是就实现了它，但是实现后恍然发现z >= 0的做法是假的

我也不管了，就把一条链的部分分交了上去，然后只AC了一个点

我看了下题解，题解没有讲部分分做法

我随便找了个AC程序进行对拍，然而并找不出错，神奇！！！

后来看了下那个程序的可读性还可以，就仔仔细细的看了一遍，又细细的想了一下为啥它要把1和n当作根节点各跑一次

觉得它是错的，然后出了一组数据轻松Hack

浪费了时间后我又重新找了一篇来看，不得不说这篇写的可以

用结构体封装了三元组维护最大，次打，次次大，然后查询也方便了很多

此外还有一个很重要的技巧，那就是对于第二次最小值的DP， 可以直接把把边权取反，转化成同样的求最大值的DP问题，就不用再写一遍了

COJ 高速公路 (highway)

继续对拍失败，仍不知道一条链怎么做

好吧，对拍出来问题了，一条链它不一定是按顺序输入的，导致我V数组的记录有问题，应该令V[x] = z，表示x \Rightarrow y这条边的边权是z

P1043 数字游戏

区间DP, 比较套路

但是要注意各种边界问题，注意判断状态的合法性，这个确实有点麻烦

P1043 数字游戏(DP优化)

总觉得DP复杂度过高，挺奇怪的

通过观察yxc的代码，发现他没有枚举另一个区间的k

换句话说，我们转移时只要保证i \sim p划分k - 1个, p + 1 \sim j划分成1个，这样一定会DP到最优解

同时它避免了冗余等效状态的枚举，时间复杂度降至\Theta(n^3 m)

P1095 守望者的逃离（Review）

这道题的DP很奇怪，能把两种技能分开进行两次DP

根本原因是:经过计算，不难发现，如果时间足够多，那么一直使用闪烁技能总是会比跑步技能优，所以最优解一定可以是先尽可能的使用闪烁技能，最后再可能使用跑步技能

P2258 子矩阵（Review）

做这道题的关键是发现当我们搜索出行的选择方案后，**行的信息就是已知的，那么列的选择就可以使用$DP$来降低复杂度**

蒟蒻的我再次复习可重集和容斥原理

MZOJ#143. 到不了(10pts)

倍增写的，不知道哪里错了

【\text{260pts, Rank 8}】牛客CSP-S提高组赛前集训营2

考试节奏把控的不错，部分分拿的比较足，但有一个很重要的前提是T1没有挂