KeBlog

The OI Algorithm Blog of Kewth

0%

有生之年。


103. Boys and Girls

求一个长为 \(n\) 的由 01 构成的环,满足恰有 \(x\) 个点的两侧有 0 ,恰有 \(y\) 个点的两侧有 1 。

时间复杂度:\(O(n)\)

题解

注意到每个点的两侧有三种情况:全是 0 ,全是 1 ,一边 0 一边 1 ,设上述三种情况的点的数量分别为 \(a\), \(b\), \(c\) ,容易知道有 \(c = x + y - n\), \(a = x - c\), \(b = y - c\)

我们把距离恰为 \(2\) 的点连边,得到一个新的环,准确来说,如果 \(n\) 是奇数,得到的是一个长为 \(n\) 的环,否则得到的是两个长为 \(dfrac{n}{2}\) 的环。

那么我们现在要做的就是在环上填 01 使得三种边的数量分别为 \(a, b, c\) ,注意到 \(c\) 必须是偶数,且 \(c\)\(0\) 的时候必须有 \(ab = 0\) 。假设只有一个环,就很容易构造一个解,两个环的话就把边集分成两个大小相等的部分,只要满足每个部分都合法即可。

阅读全文 »

有生之年。


233. Rubik's Rectangle

给定一个 \(H \times W\) 的网格,每个网格有个数字,每次操作可以翻转某行或某列,求一组合法操作使得该网格的数字排好序。

时间复杂度:\(O(HW(H+W))\)

题解

不妨假设 n, m 都是偶数(如果是奇数那么中间的一行或列可以独立)。

可以发现可以把格子染色,每种颜色恰好四个格子,满足任意翻转操作后颜色矩阵不变。

不妨假设每个数字在正确的颜色位置上。考虑每个颜色内的四个点,可以发现如果这些点构成偶排列那么就总可以在不影响其他颜色的前提下把这四个点排好序,如果是奇排列则总是不能。称每个颜色的左上角的点为代表点,把颜色的排列奇偶性作为标记放到代表点上,对于代表点标记构成的 01 矩阵 A ,如果 A 是全 0 矩阵自然是有解的。

而每次翻转对 A 的影响就是讲某一行或某一列的 01 给全部反转,因此只要能通过这个操作把 A 弄成 01 矩阵就能得到解,这就是个很 simple 的贪心了。

数据

这 spj 真难写。

不难想到如果随机选择一个排列放到网格上,那么极大的概率是无解。采用逆推的方式,从一个排好序的网格随机执行若干次操作得到一个打乱的网格,这样就可以保证数据有解。在此基础上加上一些扰动改变一些代表点的奇偶性即可得到强度较大的无解数据。

阅读全文 »

初赛到了考场才真实地认识到一个新的赛季又开始了,不过我已经精神退役了,所以考的比较佛。

初赛

10.09 才知道初赛日期是 10.11 ,没啥感觉,10.11 就跟过去裸考了。

湖南大学好热闹,但是没人和我面基。

不过碰到个小哥哥(应该是湖南大学的学生)问我这么多人是干啥,了解了一波情况后给我说了加油。

考试的时候那个字符串的题目把我整懵了,猜了几个结论糊弄过去。

考后发现 nth_element 那题还错了一个,看懂是个 nth_element 后就没仔细看实现了,没注意到它的实现有缺陷。

update: 膜拜我校高一选手初赛 AK !

阅读全文 »

本来装好 deepin.com.qq.im 后就可以愉快使用了,但是在某次滚动更新后突然发现 QQ/TIM 都中文乱码,困惑了很久都没找到解决方案。

在失败和重新尝试的断断续续的反复循环中,今天终于解决了。

其实就是下载 simsun.ttc 和 simsun.ttf 放到 .deepinwine/Deepin-QQ/drive_c/windows/Fonts 里头。

可能还要写个 zh.reg ,像下面这样,然而 deepin-wine 自带的 deepin-regedit 用不了,把 /usr/lib/deepin-wine/wine 拷贝到 /usr/lib/i386-linux-gnu/deepin-wine/wine 后似乎就好一点,但还是用不了,因此我并没有注册,但好像也还可以。

阅读全文 »

美食家

题目大意

给定一张 \(n\)\(m\) 边的有向图,边有不超过 \(w\) 的长度。现要求从点 \(1\) 出发经过长度恰为 \(T\) 的路径回到点 \(1\) ,每到达一个点就会获得等于该点点权的愉悦值。特别地,有 \(k\) 个美食节,形如“于时刻 \(t\) 到达点 \(x\) 会额外获得 \(y\) 的愉悦值”。最大化获得的愉悦值总和。

做法 1

考虑 \(k = 0\) 的情况,也就是忽略美食节。

不难得到这样一个 DP :设 \(f_{i,j}\) 表示在时刻 \(i\) 到达点 \(j\) 的最大愉悦值,转移枚举 \(j\) 的出边即可,复杂度 \(O(T(n+m))\)

做法 2

做法 1 的 DP 中转移与 \(i\) 无关,可以想到把 \(f_i\) 看做一个向量,用 max+ 矩阵描述转移,但是由于边有不等的长度,需要把连续 \(w\) 个时刻的状态合并为一个向量,这样一来就可以用 max+ 矩阵描述转移,使用矩阵快速幂,复杂度 \(O(m + (wn)^3 \log T)\)

做法 3 (正解)

现在考虑美食节,称有美食节的时刻为关键时刻,两个相邻的关键时刻之间是不受美食节影响的,可以套用矩阵快速幂的做法。那么就以关键时刻把时间轴分为 \(k+1\) 段,每段用矩阵快速幂,在关键时刻把美食节的影响加到状态上即可。这里矩阵快速幂不能每次暴力矩阵乘矩阵,需要预处理矩阵乘积的幂次,然后用向量乘矩阵的方式处理每一段。复杂度 \(O(m + (wn)^3 \log T + k (wn)^2 \log T)\)

阅读全文 »

想出一道不一般的积性函数前缀和的题,题没出出来,倒是发现不少有意思的东西。

一些定义

有些定义是我胡扯的。

对于积性函数 \(f\) ,称其特征函数 \(F\)\(f\) 关于质数 \(p\) 的函数,准确来说 \(F\)\(f\) 的特征函数当且仅当对于任意质数 \(p\)\(F(p) = f(p)\) ,可以发现 \(F\) 并不是唯一的,但是我们只考虑最简单的那个,例如对于任意质数 \(p\)\(f(p) = p + 1\) ,不妨令任意 \(x\)\(F(x) = x + 1\) ,可以发现 \(F\) 并不一定是积性函数。

记积性函数 \(I_m(x) = x^m\)

对于数论函数 \(f\) ,其前缀和函数记为 \(S_f\) ,满足 \(S_f(n) = \sum_{i=1}^n f(i)\)

\(B(n) = \lfloor \sqrt{n} \rfloor\)\(n / i = \lfloor \frac{n}{i} \rfloor\)

阅读全文 »

就呆机房考试了一上午,写个屁游记啊。

边打 APIO 边写游记,这感觉很妙啊。

阅读全文 »

我已经菜到只能刷板题了 QwQ 。

愈发意识到,会和熟练是两码事,熟练与不熟练的差距真的很大。

阅读全文 »

直奔主题

直接举例子吧,考虑这样一个问题:给定一个长为 \(n\) 的数列,要选恰好 \(k\) 个不交的子段使得选择的子段总和最大。

朴素 DP

朴素 DP 是设 \(f_{i,j,0/1}\) 表示考虑前 \(i\) 个选择 \(j\) 段最后一个有没有选的最大收益,时间复杂度 \(O(n^2)\) ,必须有一维 \(j\) 处理“恰好”这个限制。

有没有更优秀的复杂度呢?

阅读全文 »