算法笔记 000

写给自己：

虽然你没有初高中的算法竞赛经验，但是你要相信你还是很优秀的，你的思维学学算法没有问题，加油！

前言

大一入学以来参加了几场算法竞赛，尤其最近几周，拉了两个佬打了校赛，又听说某个水赛报销报名费，想着去打着玩玩，也为了多经历比赛。感觉算法是那么难，又那么美。感触颇多，这些为数不多的经历，紧张而刺激，每每也收获许多。因此想着记录 & 复盘一下比赛。（先记录下校赛吧。

CPC校赛

我们队 AAAAC批发 最后获得了第 18 名的成绩，还算不错。我写了 1 题，G 题签到题非常可惜，也长记性了。

B 玩具球

有一棵高度为 $n$ 的满二叉树。根节点在第 $1$ 层，叶子节点在第 $n$ 层。节点按照堆式编号：根节点编号为 $1$，编号为 $x$ 的节点的左儿子编号为 $2x$，右儿子编号为 $2x + 1$​。
每个非叶子节点上都有一个开关，初始时所有开关都处于“关”状态。 现在依次从根节点放下 $m$ 个球。每个球从根节点出发，经过一个非叶子节点时：如果该节点开关为“开”，球会进入左儿子；如果该节点开关为“关”，球会进入右儿子。球离开该节点后，该节点的开关状态会立即翻转。球到达叶子节点后停止。
请你求出第 $m$ 个球最终停在哪个叶子节点。 有 $T$ 组测试数据，每组测试数据相互独立，所有开关都会重新从“关”状态开始。

输入格式
第一行包含一个整数 $T (1 \leq T \leq 10^4 )$，表示测试数据组数。
接下来 $T$ 行，每行包含两个整数 $n, m(1 \leq n \leq 60, 1 \leq m \leq 10^{18})$，表示满二叉树的高度以及要查询第 $m$​ 个球。

思路

开到二叉树和这种开关特性，首先想到某种动画演示的二进制进位器，想着肯定和二进制有关，但是需要发掘更深的规律。从 $n = 3$ 开始枚举，发现依次为：

graph TD
    %% 满二叉树示例
    1((1)) --> 2((2))
    1 --> 3((3))

    2 --> 4((4))
    2 --> 5((5))

    3 --> 6((6))
    3 --> 7((7))
    
    4 --> 8((球4))
    5 --> 9((球2))
    6 --> 10((球3))
    7 --> 11((球1))

继续枚举出 $n = 4$ ，写出前几个球对应最终二进制编号，发现如下规律

发现无论 $n = 3、4、5…$，答案第一位一定是 1，接着几位倒序看，高位当地位，0 当成 1，就是倒序的二进制数递增。显然 m 遍历所有节点后一定重置所有开关。

根据队友，结论题当你感觉是对的的时候，你很可能就是对的。
有时候枚举挺重要的。

题解

通过位操作（其实就是乘二除以二取模操作），对 $k - 1$ 倒序取反，有以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#define ll long long
cin >> T;
ll m;
while(T--)
{
    cin >> n >> m;
    // m mod 2 ^ (n - 1)，全部遍历后状态清零
    ll k = m % (1LL <<(n - 1)) - 1;
    ll ans = 0;
    for(int i = 0; i < n - 1; ++i){
        ans <<= 1;      // 左移一位
        if (k & 1){     // 末位为一，取反为 0 不用操作
        }
        else{
            ans += 1;   // 否则加 1
        }               // 这里 if else 写得很丑不过考场懒得改
        k >>= 1;
    }
    ans += 1LL << (n - 1); // 首位必定为 1
    cout << ans<< endl;
}

虽然这题是签到题，但是作为新手的我还是想了很久，不过也是我在团队赛场上第一次解出题目。
出题人给出的答案很简略，直接根据二叉树编号规则计算，结果上相同。但是我认为我这个想法更漂亮一些（虽然不见得快且好想）。

D 三角形

给定两个整数 $n,m$。你需要构造一个长度为 $n$ 的正整数序列 $a_1,a_2,…,a_n$，满足：
对所有 $1 \leq i \leq n$，都有 $1 \leq a_i \leq m $ ；从这 $n$ 个数的位置中任选三个不同的位置，它们对应的三个数都不能构成一个非退化三角形。
如果不存在这样的序列，请输出 $−1$。
三个正整数 $x,y,z$ 能构成非退化三角形，当且仅当它们都严格小于另外两个数之和。等价地，将它们排序为 $x \leq y \leq z$ 后，需要满足 $x+y \gt z$。

输入格式
输入一行两个整数 $n, m(3 \leq n \leq 10 ^ 6, 1 \leq m \leq 10^{18})$。

题解

签到题，队友写的，直接上题解了。不构成三角形需要 $z \ge x+y$。最优方案是斐波那契数列 $1,1,2,3,5…$。当最后一个数（遍历过程中任意一个数） $> m$ 时则无解。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

a[1] = 1;
a[2] = 1;
for(int i = 3; i <= n; i++)
{
    a[i] = a[i - 1] + a[i - 2];
    if(a[i] > m) 
    {
        cout << "-1";
        return 0;
    }
}
for(int i = 1; i <= n; i++)
{
    cout << a[i] << " ";
}

在考场上第一次听说 Special Judge 这种东西。

E 复读机

毒蛙有 $m$ 台复读机，第 $i$ 台复读机会一次性复读 $a_i$ 条消息，每条消息都是一个数字。它们会依次复读，形成一个长度为 $a_1+a_2+···+a_m$ 的序列。毒蛙的计算机存储结构并不够先进，所以复读机复读出的序列中混进了一些数字，形成了一个长度为 $n$ 的序列 $s$。
给定 $n,m$ 以及序列 $a$ 和序列 $s$，请你求出毒蛙复读机复读出的序列。如果有多个合法的序列，输出任意一个即可。

输入格式
第一行包含两个整数 $n,m(1 \leq m \leq n \leq 10^5)$，分别表示混入数字后的序列长度以及复读机数量。
第二行包含 $m$ 个正整数 $a_1+a_2+···+a_m(1 \leq a_i \leq n)$，表示每台复读机一次性复读的消息数量。
第三行包含n个正整数 $s_1,s_2,…,s_n(1 \leq s_i \leq n)$ ，表示混入数字后的序列。
保证一定存在至少一种合法答案。

输出格式
输出一行 $a_1+a_2+···+a_m$ 个整数，表示毒蛙的复读机复读出的序列。

题解

（其实理解题目在说什么最重要）考场上不能冷静下来审题就感觉看不懂。

依旧队友写的。如果某段相同序列中被混入了数字，搜索到原序列最后一个位置的时候，这个序列对应数字必定能出现次数达到 $a_i$，找到首个满足的数字，作为第一个序列，此时清空目前记忆，重新搜索。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

unordered_map<int, int> mp;
int i = 0;
for(int p = 0; p < n; p++) {
    mp[seq[p]] ++;
    if(mp[seq[p]] == a[i]) {            // 若当前位置到达，必定是当前位置的数
        for(int j = 0; j < a[i]; j++) 
            cout << seq[p] << " ";
        mp.erase(mp.begin(), mp.end()); // 清空记忆
        i++;
    }
}

G 灌水（我感觉我脑袋被灌了水）

下面来到我认为最难绷的一集：

给定平面上一个由 $n$ 个整点按顺时针顺序组成的凸多边形。在灌水前，你可以将整个多边形绕平面任意旋转一个角度。旋转后，从多边形的最低处开始向内灌水，水面始终保持水平。对于某个旋转角度和某个水面高度，若一个顶点位于水面之下或恰好在水面上，则称该顶点被水没过。
你需要选择一个旋转角度，并灌入尽可能少的水，使得恰好有 $m$ 个顶点被水没过。
在二维平面中，灌入水量定义为多边形内部位于水面以下部分的面积。可以证明，最小灌水量乘以 $2$ 后一定是整数。请输出这个整数。

*输入格式 第一行包含两个整数 $n,m(3 \leq n \leq 1000, 1 \leq m \leq n)$，分别表示凸多边形顶点数和需要被水没过的顶点数。
接下来 $n$ 行，每行包含两个整数 $x_i,y_i(−10^9 \leq x_i,y_i \leq 10^9)$，表示第 $i$ 个顶点坐标。
保证给定点按顺时针顺序构成严格凸多边形。

思路

首先思考为什么 $2$ 倍灌水量一定是整数。灌水量最小时，显然刚好连接第 $1$ 与 $m$ 个顶点。由于 $n$ 边凸多边形可以从一个顶点划分为 $n - 2$ 个三角形，每个三角形面积由 $\frac{1}{2}|x_1 y_2 - x_2 y_1|$ 表示，求和后整数运算必然结果为整数。

因此思路就是枚举每个顶点为起点，按顺时针数 $m$​ 个点的面积算最小值。为了避免重复计算，可以每次减去【上个起点，新的起点，旧的终点】的面积，再加上【新的起点，旧的终点，新的终点】的面积，便完成了一个状态更新。

赛后听讲时了解到，成环的情况有个技巧，把数组在结尾后复制一遍，这样就能避免取模的操作。

犯傻，最大的教训就是不要把待比较的 minS 和状态转移的 currentS 混在一起。我怎么会加一个 s2 = minS 在最开始呢。

我去我知道了，是初始化的时候在外面进行一次。我是傻逼。

题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#define ll long long
pair<ll, ll> xy[2001];	
// 直接全部省略 1/2
ll S(pair<ll, ll> p1, pair<ll, ll> p2, pair<ll, ll> p3) {
    return abs(((p1.first - p3.first) * (p1.second - p2.second))
               - (p1.first - p2.first) * (p1.second - p3.second));
}
int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> xy[i].first >> xy[i].second;
        xy[i + n] = xy[i];      // 复制一遍
    }
    // 计算初始 m 个点的面积为起点
    ll s0 = 0;
    for (int i = 0; i < m - 2; ++i) {
        s0 += S(xy[0], xy[i + 1], xy[i + 2]);
    }
    
    ll currentS = s0;
    ll minS     = currentS;
    for (int i = 0; i < n; ++i) {
        // 状态转移
        currentS -= S(xy[i], xy[i + 1], xy[i + m - 1]);
        currentS += S(xy[i + 1], xy[i + m - 1], xy[i + m]);
        minS = min(currentS, minS);
    }
    cout << minS;
}

H 染色

给定三个正整数 $n,m,k$。你需要构造一个 $n×m$ 的网格，并将每个格子染成 $1$ 到 $k$ 中的一种颜色，使得下面三个条件同时成立：

• 每种颜色至少出现一次；
• 对于每种颜色，所有染成该颜色的格子在四连通意义下形成一个连通块；
• 对于任意两种不同颜色 $x,y$，都存在一个颜色为 $x$ 的格子和一个颜色为 $y$ 的格子，它们有一条公共边。

如果无法构造满足条件的网格，输出 $−1$。

输入格式
输入一行三个整数 $n,m,k(1\leq n,m\leq 3000,1\leq k \leq n\times m)$。

输出格式
如果无解，输出一行一个整数$−1$。 否则输出 $n$ 行，每行 $m$ 个整数。第 $i$ 行第 $j$ 个整数表示第 $i$ 行第 $j$ 列格子的颜色，必须在 $1$ 到 $k$ 之间。

题解

没有学过图论，据说是染色定理，待学（

将每个格子视作一个点，如果两个格子相邻则连边，形成一张平面图。再将同一颜色的点合并为一个点，那么这个图依 然是平面图。
根据题意需要满足收缩后的图是 $k$ 个点的完全图 $K_k$。根据 Kuratowski 定理，$K_5$ 不是平面图。所以 $k \ge 5$ 时一定无解。

不妨设 $n \leq m$，分类讨论：

• $n = m = 1$：仅能 $k=1$。

• $n =1,m >1$：$1, 2, 2, 2…$ 可以实现 $k = 2$。

• $n =2,m \ge 2$：可以如下得到 $k=3$ 的构造。

  $$\begin{array}{cc} 1 & 3 & ... \\ 2 & 3 & ... \end{array}$$

  由外平面图性质，不存在 $k = 4$ 的构造。$k =1,2$ 构造略。

• $n \ge 3,m \ge n$：可以构造出如下 $k=4$ 的情况。

  $$ \begin{array}{cc} 4 & 1 & 3 & ... \\ 4 & 2 & 3 & ... \\ 4 & 3 & 3 & ... \end{array} $$

  ​ $k =1,2,3$ 构造略。

又鸽了几天，剩下题也没啥会写的，随便记点喽~

I 计算机

给定长度为n的非负整数序列$a_1,a_2,…,a_n$，请你根据递推公式计算序列$f$：

$f_i = \mathop{\max} \limits_{1\leq j < i} (f_j + (a_j \oplus a_i ))$​

特别的，$f_1 =0$。$1 \leq n \leq 10^6,a_i \leq 10^9$。

队友猜出是逐项异或之和，过题的一瞬间全部“卧槽”。

用到了异或的性质，我不会，直接上题解。

题解

由于$(x\oplus y)+(y\oplus z) \ge (x\oplus z)$。所以最优的 $j$ 一定是 $i −1$。则按照 $f_i =f_{i−1}+(a_{i−1}\oplus a_i)$ 计算即可

1
2
3
4

for(int i = 2; i <= n; i++) {
	ans += (a[i] ^ a[i - 1]);
}
cout << ans << endl;

剩下的题不会写了喵，就到这里吧，不知道能坚持学多久算法呢（）