想法

持续正反馈的任务清单计划

碎碎念：

封面（姑且算是吧）是缘之空里的瑛，也算是主角之一了，最近推了缘之空的穹线和瑛线，无法自拔…

好吧接下来说下正题，这个其实就是一个任务清单，不过一般任务清单自己一般懒得的去完成，然后逐渐就忘记了这东西，并且涉及人物计划还可能很费时，之前也算是尝试了好多次，但都是以失败告终，一是当时高中时间安排的比较严格，没有自由安排的时间，完全不需要任务清单这种东西，另外就是这里的重点。对于一个任务清单，可能完成一项任务，任务本身对自己的正反馈不一定可以补偿完成任务的付出。然后现在也算是大二了，怕没有个任务清单的话，导致一学期过得浑浑噩噩的，需要一个东西来设定自己的计划。

介绍：

然后这次打算用一种方式解决上面的问题，首先重要的一点是，完成一项任务后要得到一定的奖励，这个奖励要对应完成任务所需要的付出，于是想来想去，感觉最好的奖励就是金钱了，然后就是给自己设定一些计划，用金钱去衡量完成任务得到的收益，以及完成任务所需要的付出。

这里有两点需要严格遵守的，一个是自己要严格一些，一些杂七杂八的东西就不要加到计划清单了，并且必须要完成的东西不要加进来，例如完成学校的作业等，这里列举一下算是值得加到任务清单事情：

  • 阅读一本书的第 x 章
  • 学习主席树并完成习题
  • 打完一场 Codeforce 并把力所能及的题补掉（这个任务可重复完成）

另外一个重点是，每个任务的任务量一定小，不要上来就抛出一个 “阅读《算法导论》”的任务，对于这样难以完成的任务一定要拆开，比如拆成阅读完第几章等。

另外一点是拿金钱当奖励的，所以某些日常需求用到的钱是要和这里的奖励分开的，比如要买几点应季的衣服，或者普通吃顿饭，买书，就不必用奖励的前，对于“想要买个好一点的耳机”、“这个游戏真好玩，想买”这样的需求，就要从奖励里拿出了。

实现：

计划大概是那样的，这里我打算暂时用印象笔记当工具，每个计划对应一个提醒，每次添加计划的时候输入计划的名字和奖励。

以后打算写一个网页或移动端的程序的，想来想去有点复杂，还是用印象笔记实现好了。

最后：

以上大概就是全部的计划了，可以看得出来，完全要靠直接去遵守规则的，看起来有点像小孩子的过家家。不过如果能进行下去，感觉对自己应该是非常有益的，写这篇博客也算是警示一下自己吧，看看能坚持多久。

历程

2017年暑假集训

一、时间内容

2017年暑假，学校 ACM 算法实验室。对一个月集训的总结，也算是应付一下学校的社会实践作业。时间为7月24日至8月26日，总共五周34天。

时间差不多是早上8点就得到实验室，不过这次不像寒假集训那样每天要签到，结果日常迟到，刚开始几天还好，之后都是迟到个10几分钟…

老师对集训的安排是周一至周六全天训练，周日休息一天，除周二以外每天上午自己去刷专题学习算法，下午就进行组队赛，周三是一天都是学习算法和补题。周六是上午+下午两场个人赛，一周下来总共六场比赛，除去个人赛三个小时外，每场比赛都是5小时，训练强度可以说是挺高的了。

二、体验与经历

这里就以时间为顺序写一下集训的趣事和重要经历好了。

我是在集训开始前几天就来学校刷了一会专题，搞了搞数论，算是弄懂了逆元、中国剩余定理、扩展欧几里得算法…对于基本的数论题算是没问题了，然后对数论不像之前那么怕了，讲道理我到时非常想仔细研究一下数论来着，毕竟算是数学中的皇后、最纯粹的数学了，然而图论真的是太有意思了～

然后过了几天就开始正式集训了，刘老师首先开始讲话，看参加集训的人数，大概有个100+人，看刘老师说是分算法组和数据结构组两部分，算法组的基本上就是面向比赛的集训队队员了，数据结构组，看刘老师的意思是想要把我们学校整体的水平提高上来，整个计院差不多700人，这样相当于有个1/6人都在大一结束的时候就完成了数据结构的学习，如果进展的好的话，可以说是非常恐怖了。

对于数据结构组我不太清楚，刘老师说了一下对算法组的安排，就是上面说的那样了，然后张老师在 VJ 上抓了 kuangbin 的专题，算是我们学习的大纲了。

接下来防不胜防的，刘老师说要开一场个人赛，算是让我们找到状态，当时就整个人就方了。

然后第二天上午就开始比赛了，由于过去一个多月了，记得也不是太清楚了，反正刚开始就是一堆的水题，唯一用到数据结构也就是单调栈和线段树，当时状态还不错，不过单调栈看了紫书才敲出来 ORZ 。最后 A 完7题后，就在看一个类似约瑟夫环的题，刚开始还以为是一个纯数学题，不过之前刷了很多的线段树的题，然后用朴素的思想想了一下，维护下标这个信息，突然发现用线段树可以搞，于是最后半个小时就非常开心的敲起了线段树，不得不说金桔的线段树的板子真的好用，然后自信的交上去，给了一个 Wrong Answer，然后比赛还有不到十分钟，本来没怎么有希望了，然后又去查了一下代码，区间更新 lazy 标记直接覆盖掉了，没累加，改掉之后交上去居然 A 了，非常开心，这时候也就五分钟了，于是和后面机位的 xuanhuang 聊了起来。开始第一场比赛 AK 可以说是非常开心了。

比赛结束后，就是日常的训练了，不过刚开始我们队比赛状态并不怎么好，经常前两个小时 A 完题，就咸鱼了，三个人坐着没事干。

然后就是每周的个人赛了，第一周的搜索算是非常开心，自己本身刷紫书的题的时候做了不少的搜索题，底子算是还可以，然后印象比较深的时候是一个题从 TLE 加剪枝优化，慢慢调成了 AC，非常开心，两次排名都是 Rank1。

组队赛的时候，非常幸运可以参加多校赛，也算是去见识下区域赛的题型，发现数学题居多，上来就是莫比乌斯反演、矩阵快速幂、快速傅里叶变换、卷积…刚开始打的一脸懵逼，感觉也就是做前几到简单题就尽力。然后感觉对于区域赛，感觉也只能思维活跃一点，把直接力所能及的题，做出来就好了。然后区域赛尽可能去拿一个铜牌甚至是银牌，如果是银牌的话，那就非常稳了，整个大二就可以平稳的去刷金牌题和知识点了（幻想ing）。

之后几个周都是一样的安排，整天不是刷题就是比赛，非常单调，值得一提的是最短路的测试赛又体验了一下 AK 的感觉，感觉自己对最短路理解也算是比较深了。

集训前几天一直在搞图论，先去学了下网络流，裸的 FF 算法， EK 算法， Dinic 算法都看了一下，网络流专题也算是刷了一半。感觉网络流算是图论里面一个比较重要的知识点了，之前区域赛的网络赛中经常有网络流的题。刷网络流的时候顺便去看了一下二分图匹配的问题，感觉匹配这个东西有点神奇，好多看起来和图论无关的问题，都可以转化到二分图的模型上，然后跑最大匹配就能解决好多问题。

之后因为实验室要开算法讲堂，然后就被叫去讲强连通缩点，于是用了一个星期咸鱼突刺了一下，算是弄清了强连通、边-双连通、点-双连通，然后就开始填算法讲堂的模板了，反反复复修正了得一两天，最后填的也不怎么样，等学离散数学的时候，一定要好好在图论上扩展一下！

最后只能就这样将强连通了，感觉讲的算是比较失败的了，没学过的估计没听懂，学过的也基本上不用听的。对比之前学长讲的树链剖分，当时我只看卿学姐的视频学了一下概念，然后听学长讲的居然听懂了，然后拿着板子去切了几个题，也算是会基本的树链剖分了，其实树链剖分实质上就是一种映射，目的是将一条链上的点映射到若干段连续的区间上，然后对于链上的修改，就对这几段连续的区间进行修改，对于连续的区间修改可以用线段树进行维护。于是这样树链剖分的题重点还算是在线段树上。

其他有意思的事情就是被派去辅导数据结构组的刷题了，然后发现他们是在做的 CCCC 的题，之前天梯赛训练的时候刷过的，然后给一个同学讲了一下树的同构的判断，发现直接好久没写过的指针了，我本以为给他写一个指针的比较好理解来着，最后写起来发现数组的好些太多了。另外一个就是看了一下目录树，之前在白书上面看到过，上面说的是静态排错，手写一个简单 shell ，也算是一个大模拟题了。看起来还是比较容易，记得天梯赛的时候，这个题曾经水过了20+分。

最后就是结训赛了，其实也都是比较水的题，大家都当做娱乐来做的，其实也挺娱乐的，最开心的是做出来了一道区域赛的 DP 题，感觉还可以，最后罚时有点多Rank2，还可以。

三、一些感悟

一个多月以来，基本上都是自学算法，学习新算法也是自己去百度找资料、翻书，比起之前集训都是学长来讲内容，感觉自己的自学能力算是提高了不少。学习能力也是提高了不少，比如匈牙利算法，当初只用了一上午不到，就学完并刷了好多例题了。

另外一个重要的提升是，最近比赛的时候不再像之前那样，每次前两三个小时做出来题，之后就没事干了，现在基本上五个小时都在看题，尤其是最近一场比赛，前三个半小时都是爆零，知道三个半小时后才切掉了第一题，之后半小时又切了一题，最后十分钟队友又切了一道 KMP 的题，顿时咸鱼翻身。

之后也是打算继续搞算法竞赛，目测会打到大三吧。

ACM►DP►数位DP

HDU6156 - Palindrome Function（数位DP）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6156

题目大意：

设函数 f(n, k) 的取值为，若 n 在 k 进制下为回文数字，那么函数值为 k 否则 为 1 。

给出 a ，b ，L， R。

求 $\sum_{i=a}^b$ $ \sum_{j = L}^R$ $f(i, j)$ 。

解题过程：

CCPC 网络赛的题，算是一个裸的板子题了，数位 DP 之前也算是做过，不过没做过这种类型的数位 DP ，然后弃疗了。过了好久把数位 DP 的专题刷掉之后才来补的。

题目分析：

定义状态dp[start][pos][flag][k]

表示在 k 进制下以 start 位置开始的回文串，在 pos 位置下，回文串个数，flag 表示当前串是否为回文串。

对于前导零是忽略掉的，选取前导零就视为将 start 位置减一。对于回文串，前一半随意枚举就可以，后一半要进行判断。即对 (start+1)/2 > pos的情况进行判断，这时候要用一个数组记录之前枚举的数字。

AC代码：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAX = 50;

LL dp[MAX][MAX][2][MAX];
int num[MAX], tmp[MAX], k;

LL dfs(int cur, int start, bool flag, bool bound) {
    if (cur < 0) return flag;
    if (!bound && dp[cur][start][flag][k] != -1) return dp[cur][start][flag][k];
    int last = bound ? num[cur] : k - 1;
    LL ans = 0;
    for (int i = 0; i <= last; i++) {
        //判断是否为前导零
        bool st = (cur == start && i == 0);
        bool new_flag = flag;
        if (flag) {
            //如果当前是回文串的后半段的话，就判断下当前是否构成回文串
            if (!st && cur < (start + 1) / 2) new_flag = (tmp[start - cur] == i);
        }
        tmp[cur] = i;
        ans += dfs(cur - 1, st ? start - 1 : start, new_flag, bound && (i == last));
    }
    if (!bound) dp[cur][start][flag][k] = ans;
    return ans;
}

LL solve(int n) {
    if (n == 0) return 1;
    int len = 0;
    while (n) {
        num[len++] = n % k;
        n /= k;
    }
    return dfs(len - 1, len - 1, true, true);
}

int main() {
    int T;
    scanf("%d", &T);
    memset(dp, -1, sizeof(dp));
    for (int Case = 1; Case <= T; Case++) {
        int a, b, l, r;
        scanf("%d %d %d %d", &a, &b, &l, &r);
        LL ans = 0;
        //枚举进制
        for (int i = l; i <= r; i++) {
            k = i;
            LL t = (solve(b) - solve(a - 1));
            ans += (b - a + 1) + t * (k - 1);
        }
        printf("Case #%d: %lld\n", Case, ans);
    }
}
ACM►DP

Gym 100917J Judgement(背包DP+bitset)

题目链接：

https://vjudge.net/problem/Gym-100917J

题目大意：

给出两个长度为 n 序列 $ A_ {i}, B_ {i} $ 和 p , q。如果存在一个集合$c_ 1,c_ 2,c_ 3 \dots c_ k$，使得$(\sum A_ {c_ i} \ge p \wedge \sum B_ {c_ i} < q) \bigvee (\sum A_ {c_ i} < p \wedge \sum B_ {c_ i} \ge q)$ 那么输出 NO，并用 01 输出集合中的元素，全集为1~n。

解题过程：

比赛的时候想用贪心暴力水一发的，居然水道37组样例，结果还是不对，赛后补的，也算是学下 bitset 了。

题目分析：

跑两次 DP，定义 dp[i] = j 的含义为，第一个序列的和为 i 时，第二个序列的最大值为 j。

我们只跑 i < p 的，如果存在 j >= q，那么就不符合上面的条件了。

然后对第一个序列第二个序列交换位置，再跑一次。

最后答案要输出路径，记录下最后从哪个状态转移而来的，并输出状态。

AC代码：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1123456;

int n;
int a[MAX], b[MAX];
bitset<120> fa[MAX];
int dp[MAX];

bool solve() {
    int p = a[0], q = b[0];
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < MAX; i++) fa[i].reset();
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = p; j >= 0; j--) {
            if (dp[j] < 0) continue;
            if (j + a[i] < p && dp[j + a[i]] < dp[j] + b[i]) {
                dp[j + a[i]] = dp[j] + b[i];
                fa[j + a[i]] = fa[j];
                fa[j + a[i]].set(i);
                if (dp[j + a[i]] >= q) {
                    puts("NO");
                    for (int k = 1; k <= n; k++) {
                        printf("%d", (int)fa[j+a[i]][k]);
                    }
                    puts("");
                    return true;
                }
            }
        }
    }
    for (int i = 0; i <= n; i++) swap(a[i], b[i]);
    return false;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 0; i <= n; i++) scanf("%d", &b[i]);
    if (!(solve() || solve())) puts("YES");
}
ACM►数学►矩阵快速幂

矩阵快速幂小结

感谢&资料：

非常感谢一些 up 主和博主分析的资料，矩阵快速幂好多书上没详细讲，于是搜了一些资料。

简介：

矩阵快速幂其实就是矩阵乘法 + 快速幂，上面的视频还讲了扩展的幂运算的含义，挺不错的，代码上的体现就是，将原本的数字相乘换成了矩阵相乘，其他都是一样的，实质就是加速了矩阵的幂运算，对原本 $O(n)$的幂运算加速到$O(\log n)$。

1
2
3
4
5
6
7
8
9
10
Mat pow_mod(Mat a, int k) {
    Mat rst(a.n, a.m);
    rst.unit();
    while (k) {
        if (k & 1) rst = rst * a;
        a = a * a;
        k >>= 1;
    }
    return rst;
}

这就是一个矩阵快速幂的核心代码，我这里重载了乘号，然后看起来和普通的快速幂根本没什么区别，unit 函数是将矩阵初始化为单位矩阵。

应用：

通过上面的描述，矩阵快速幂其实就是加速矩阵的幂运算，但是这个有什么用呢？

在 ACM 竞赛中矩阵快速幂通常用来加速递推式的计算，将原本 $O (n)$ 的计算过程加速到 $O(k\log n)$ k 与矩阵的大小有关。

一个简单的例子就是用来计算斐波那契数列，假设要求斐波那契数列的第 n 项 $f_n$ 当 n 比较小直接用循环跑就可以了，这样是 $O(n)$ ，但是当 n 非常大甚至高达 $10^9$ 时用过这种朴素的方法进行递推肯定是超时的。

这时候就要用到矩阵快速幂，首先，也是最核心的一部，要找到递推关系和转移矩阵，对于斐波那契数列，非常任意就可以找到：

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} f_{n-1} \\ f_{n-2} \end{bmatrix} = \begin{bmatrix} f_{n-1} + f_{n-2} \\ f_{n-1} \end{bmatrix} = \begin{bmatrix} f_n \\ f_{n-1} \end{bmatrix}$

我们称第一个矩阵为转移矩阵，第二个一般是一个$n \times 1$的向量，右边的向量每乘一次转移矩阵，向量中的每个元素根据递推式往后推了一次。

这时我设 $A_n = \begin{bmatrix} f_n \\ f_{n-1} \end{bmatrix}$ , $T = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$那么显然有 $A_n = T^{n-1} \cdot A_{1}$.

转移我们对 T 这个转移矩阵就行快速幂，就可以再乘以 $A_1$ 就能算出来 $A_n$，复杂度是 $O(k\log n)$ 。

通过上面的分析，其实矩阵快速幂在应用的时候，难点是找出转移矩阵 T 和 $A_1$ ，下面给出一些简单的递推式练手：

$f_n = a\cdot f_{n-1} + b\cdot f_{n-2} + c$ (a, b, c是常数)

$\begin{bmatrix} a & b & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} f_{n-1} \\ f_{n-2} \\\ c \end{bmatrix} = \begin{bmatrix} f_n \\ f_{n-1} \\\ c\end{bmatrix}$

$f_n = c^n - f_{n-1}$

$\begin{bmatrix} -1 & c \\ 0 & c \end{bmatrix} \cdot \begin{bmatrix} f_{n-1} \\ c^{n-1} \end{bmatrix} = \begin{bmatrix} f_n \\ c^{n} \end{bmatrix}$

板子：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;

struct Mat {
    ll v[112][112];
    int n, m;

    Mat(int tn, int tm) {
        n = tn, m = tm;
        memset(v, 0, sizeof(v));
    }

    void unit() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == j) v[i][j] = 1;
                else v[i][j] = 0;
            }
        }
    }

    void read() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%lld", &v[i][j]);
            }
        }
    }

    void out() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                printf(j == m - 1 ? "%d\n" : "%d ", v[i][j]);
            }
        }
    }

    Mat operator*(const Mat &a) {
        Mat rst(n, a.m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < a.m; j++) {
                ll t = 0;
                for (int k = 0; k < m; k++) {
                    t += v[i][k] * a.v[k][j] % MOD;
                    t = t % MOD;
                }
                rst.v[i][j] = t;
            }
        }
        return rst;
    }
};

Mat pow_mod(Mat a, int k) {
    Mat rst(a.n, a.m);
    rst.unit();
    while (k) {
        if (k & 1) rst = rst * a;
        a = a * a;
        k >>= 1;
    }
    return rst;
}


int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    Mat a(n, n);
    a.read();
    pow_mod(a, m).out();
}

简单练习：

ACM►DP

CodeForces748E - Santa Claus and Tangerines(递推|二分DP)

题目链接：

http://codeforces.com/problemset/problem/748/E

题目大意：

给出 n 个数，可以将一个数 k 拆成 k / 2 和 (k + 1) / 2，把这 n 个数至少拆成 k 个数，使得这 k 个数中最小的尽量的大。

解题过程：

感觉就是二分答案 + DP，用 DFS 写的DP，结果 T 了好久，还以为是卡常数，试了好久，最后去翻了博客，才发现写成递推就稳了….

而且看到了一个神奇的做法。

题目分析：

第一种做法是，二分答案，然后DP去验证是否有解。

dp[i] 表示最多可以得到多少个 i，然后对于所有的 $i / 2 \ge mid$，让 dp[i] 累加到 dp[i/2], dp[(i+1)/2] 上。对于 $i/2 < mid$ 直接统计到结果上，如果最后结果大于等于 k，表示有解。

第二种做法，直接枚举答案，并在一次递推中维护。

dp[i] 数组含义和上面一样，枚举到一个数字的时候，先让答案加上 dp[i]，这时候应该把 i 的父亲减去，因为 i 的父亲已经分解成 i 了，不应该对答案有贡献，但是只需要减去 $2i$和$2i-1$，就可以了因为 $2i+1$会在枚举 i+1 的时候减去。

注意对1特判一下，1没有$2i-1$这个父亲。

AC代码：

##做法一

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>

using namespace std;

const int MAX = 10000000 + 10;

int data[MAX];
long long dp[MAX];

int n, m, mid, mmm;

int Scan() {
    int res = 0, ch, flag = 0;
    if ((ch = getchar()) == '-')
        flag = 1;
    else if (ch >= '0' && ch <= '9')
        res = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9')
        res = res * 10 + ch - '0';
    return flag ? -res : res;
}

bool ok() {
    long long rst = 0;
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; i++) {
        dp[data[i]]++;
    }
    for (int i = mmm; i >= mid; i--) {
        if (i / 2 >= mid && dp[i] > 0) {
            dp[i / 2] += dp[i];
            dp[(i + 1) / 2] += dp[i];
        } else rst += dp[i];
    }

    return rst >= m;
}

int main() {
    n = Scan();
    m = Scan();
    int l = 1, r = 0;
    for (int i = 0; i < n; i++) {
        data[i] = Scan();
        r = max(r, data[i]);
    }
    int ans = r >= m ? 1 : -1;
    mmm = r;
    while (l <= r) {
        mid = (l + r) / 2;
        if (ok()) {
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }

    printf("%d\n", ans);
}

##做法二

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000000;

int a[maxn + 1], n, m, mx;

long long dp[maxn * 10 + 1], cur;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), cur += a[i], dp[a[i]]++, mx = max(mx, a[i]);
    if (cur < m) return puts("-1"), 0;
    cur = 0;
    for (int i = mx; i; i--) {
        cur += dp[i];
        //减去父亲贡献
        if (i * 2 <= mx) cur -= dp[i << 1];
        if (i * 2 - 1 <= mx && i != 1) cur -= dp[i * 2 - 1];
        //找到的第一个符合条件的答案即是最大值
        if (cur >= m) return printf("%d\n", i), 0;
        //对当前数拆分
        dp[i >> 1] += dp[i];
        dp[i + 1 >> 1] += dp[i];
    }
}
ACM►二进制

CodeForces744B - Hongcow's Game（交互+二进制）

题目链接：

http://codeforces.com/problemset/problem/744/B

题目大意：

给出一个矩阵，矩阵主对角线元素均为 0，选择可以最多进行 20 次询问。

每次询问选择一些行，回答会输出每一行中这些列的最小的元素。

矩阵大小小于等于 1000 。

解题过程：

想了半天没思路，到是有想到先询问一下奇数行和偶数行，然后没往后想…

也算是见识了一下新套路，这样利用位运算有点类似之前在知乎上看到的小白鼠测毒药的问题了233

题目分析：

按二进制位将所有行分组，首先按最后一位分组，0为一组，1为一组，然后倒数第二位，以此类推，然后每次都查询一组里面所有的列。

这样这样考虑，对于第 i 行的第 j 列($j \ne i$) ，既然不相等那么至少有一个二进制位是不同的，那么 i 和 j 至少有一次会被分到不同的组里面。这样对于所有行的每个元素都符合上面的描述，答案就可以求出来了。

对每次询问，如果这某一行的对角线所在的列也在分组中的话，就不更新答案。

AC代码：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX = 1123;

int ans[MAX];

int main() {
    int n;
    cin >> n;
    memset(ans, INF, sizeof(ans));

    //数据不会超过1000
    for (int i = 0; i < 10; i++) {
        vector<int> data1, data2;
        for (int j = 1; j <= n; j++) {
            //按二进制位为0或1分组
            if (j & (1 << i)) data1.push_back(j);
            else data2.push_back(j);
        }

        //询问第一组
        if (data1.size()) {
            cout << data1.size() << endl;
            for (int j = 0; j < data1.size(); j++) {
                cout << data1[j] << " ";
            }
            for (int j = 1; j <= n; j++) {
                int t;
                cin >> t;
                //对对角线不在分组中的列更新答案
                if ((j & (1 << i)) == 0) {
                    ans[j] = min(ans[j], t);
                }
            }
            cout << endl;
            fflush(stdout);
        }

        //询问第二组
        if (data2.size()) {
            cout << data2.size() << endl;
            for (int j = 0; j < data2.size(); j++) {
                cout << data2[j] << " ";
            }
            for (int j = 1; j <= n; j++) {
                int t;
                cin >> t;
                if (j & (1 << i)) ans[j] = min(ans[j], t);
            }
            cout << endl;
            fflush(stdout);
        }
    }

    fflush(stdout);
    cout << -1 << endl;
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
}
ACM►图论►连通性

POJ1904 - King's Quest & HDU4685 - Prince and Princess（强连通 + 二分图匹配）

题目链接：

http://poj.org/problem?id=1904

http://acm.hdu.edu.cn/showproblem.php?pid=4685

题目大意：

POJ1904：

一个国王有 N 个儿子，并且有 N 个公主，每个王子可以和一些喜欢公主结婚。公主没有限制。现在给出了一个 王子-公主 的完美匹配。

现在问每个王子，可以和那些公主结婚，结婚后其他的王子仍然可以完美匹配。

HDU4685:

题意和上面一样，不过没给出初始的匹配，不保证完美匹配，公主和王子的数量也有可能不同。

解题过程：

一开始完全没思路，然后去翻了一堆的博客才看懂。

题目分析：

首先以王子和公主为点建图，对每个王子向他们喜欢的公主连一条有向边。

然后进行二分图匹配，对一堆匹配的 王子-公主 从公主向王子建一条有向边。

进行强连通缩点，每个王子对于属于同一强连通分量中喜欢的公主都可以选择。

为什么这样就这样呢？可以类比网络流的退流或者匈牙利的思想，当一王子选择强连通里的非匹配的公主的话，那么这个公主的原配一定也可以选择另一个公主，并且一定可以经过若干次换妻 play 使得强连通分量内的所有王子都有匹配的公主，这里就不严格的证明了。

对于第二个题，可能有一些王子或公主一开始就没有匹配，但是他按题意应该是可以选择一些公主或者王子并不影响其他人匹配的。

这时候我们对没有匹配的公主增加一个虚拟的王子并匹配建边，并且这个王子喜欢所有的公主。对于没有匹配的王子新增一个虚拟的公主来匹配，并且这个公主被所有王子喜欢。

为什么要喜欢所有的公主或者被所有王子喜欢，是为了让这个虚拟王子/公主有机会参加所有人的换妻 play 中，注意这里虚拟节点没必要和虚拟节点建边。

AC代码：

####POJ1904：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXM = 500000 + 10;
const int MAXN = 4000 + 10;

struct Edge {
    int u, v, nxt;
} edge[MAXM];

int head[MAXN], etot;


//本题的算法复杂度是 O(N+M) 的，读入数据也是 O(N+M) 对总时间影响较大
//用输入挂加速后由 9s 变成了 500ms
int Scan() {
    int res = 0, ch, flag = 0;
    if ((ch = getchar()) == '-')
        flag = 1;
    else if (ch >= '0' && ch <= '9')
        res = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9')
        res = res * 10 + ch - '0';
    return flag ? -res : res;
}

void Out(int a) {
    if (a > 9)
        Out(a / 10);
    putchar(a % 10 + '0');
}

void add_edge(int u, int v) {
    edge[etot].v = v;
    edge[etot].u = u;
    edge[etot].nxt = head[u];
    head[u] = etot++;
}

int n;

int pre[MAXN], low[MAXN], mark[MAXN], dfs_clock, scc_cnt;
stack<int> S;

void dfs(int u) {
    low[u] = pre[u] = ++dfs_clock;
    S.push(u);
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (!pre[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (!mark[v]) {
            low[u] = min(low[u], pre[v]);
        }
    }
    if (low[u] == pre[u]) {
        scc_cnt++;
        int x;
        do {
            x = S.top();
            S.pop();
            mark[x] = scc_cnt;
        } while (x != u);
    }
}

void tarjan() {
    memset(pre, 0, sizeof(pre));
    memset(mark, 0, sizeof(mark));
    for (int i = 1; i <= n; i++) {
        if (!pre[i]) dfs(i);
    }
}

void init() {
    memset(head, -1, sizeof(head));
    etot = 0;
    n = Scan();
    for (int u = 1; u <= n; u++) {
        int k;
        k = Scan();
        while (k--) {
            int v;
            v = Scan();
            add_edge(u, v + n);
        }
    }
    for (int u = 1; u <= n; u++) {
        int v;
        v = Scan();
        add_edge(v + n, u);
    }
}

void solve() {
    tarjan();

    vector<int> data;
    for (int u = 1; u <= n; u++) {
        data.clear();
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].v;
            //如果属于同一强连通分量，那么可以选择
            if (mark[u] == mark[v]) data.push_back(v);
        }
        Out(data.size());
        //对答案排序
        sort(data.begin(), data.end());
        for (int i = 0; i < data.size(); i++) {
            putchar(' ');
            Out(data[i] - n);
        }
        putchar('\n');
    }
}

int main() {
    init();
    solve();
}

####HDU4685

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXM = 500000 + 10;
const int MAXN = 4000 + 10;

struct Edge {
    int u, v, nxt;
} edge[MAXM];

int head[MAXN], etot;
int n, m, Case, tot;

int pre[MAXN], low[MAXN], mark[MAXN], dfs_clock, scc_cnt;
stack<int> S;

int matching[MAXN];

int Scan() {
    int res = 0, ch, flag = 0;
    if ((ch = getchar()) == '-')
        flag = 1;
    else if (ch >= '0' && ch <= '9')
        res = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9')
        res = res * 10 + ch - '0';
    return flag ? -res : res;
}

void Out(int a) {
    if (a > 9)
        Out(a / 10);
    putchar(a % 10 + '0');
}

void add_edge(int u, int v) {
    edge[etot].v = v;
    edge[etot].u = u;
    edge[etot].nxt = head[u];
    head[u] = etot++;
}

void dfs(int u) {
    low[u] = pre[u] = ++dfs_clock;
    S.push(u);
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (!pre[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (!mark[v]) {
            low[u] = min(low[u], pre[v]);
        }
    }
    if (low[u] == pre[u]) {
        scc_cnt++;
        int x;
        do {
            x = S.top();
            S.pop();
            mark[x] = scc_cnt;
        } while (x != u);
    }
}

void tarjan() {
    memset(pre, 0, sizeof(pre));
    memset(mark, 0, sizeof(mark));
    for (int i = 1; i <= tot; i++) {
        if (!pre[i]) dfs(i);
    }
}

bool find(int u) {
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (pre[v]) continue;
        pre[v] = true;
        if (matching[v] == -1 || find(matching[v])) {
            matching[v] = u;
            matching[u] = v;
            return true;
        }
    }
    return false;
}

void match() {
    memset(matching, -1, sizeof(matching));
    for (int i = 1; i <= n; i++) {
        memset(pre, 0, sizeof(pre));
        find(i);
    }
}

void init() {
    memset(head, -1, sizeof(head));
    etot = 0;
    n = Scan();
    m = Scan();
    for (int u = 1; u <= n; u++) {
        int k;
        k = Scan();
        while (k--) {
            int v;
            v = Scan();
            add_edge(u, v + n);
        }
    }
}

void solve() {
    match();

    tot = n + m;
    for (int i = 1; i <= n; i++) {
        //如果当前节点未匹配
        if (matching[i] == -1) {
            //增加一个虚拟公主，并建边
            ++tot;
            add_edge(tot, i);
            for (int j = 1; j <= n; j++) {
                add_edge(j, tot);
            }
        } else {
            //如果已匹配，建一条反向边
            add_edge(matching[i], i);
        }
    }
    for (int i = n + 1; i <= n + m; i++) {
        //同理增加一个虚拟公主
        if (matching[i] == -1) {
            ++tot;
            add_edge(i, tot);
            for (int j = n + 1; j <= n + m; j++) {
                add_edge(tot, j);
            }
        }
    }

    tarjan();

    printf("Case #%d:\n", ++Case);
    vector<int> data;
    for (int u = 1; u <= n; u++) {
        data.clear();
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].v;
            //如果是虚拟节点就忽略
            if (v > n + m) continue;
            //如果和公主属于同一强连通分量，那么可以选择
            if (mark[u] == mark[v]) data.push_back(v);
        }
        Out(data.size());
        sort(data.begin(), data.end());
        for (int i = 0; i < data.size(); i++) {
            putchar(' ');
            Out(data[i] - n);
        }
        putchar('\n');
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        init();
        solve();
    }
}
ACM►图论►匹配

HDU3829 - Cat VS Dog（二分图匹配）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3829

题目大意：

有 N 条狗， M 只猫和 P 个人。

每个人会喜欢一条狗讨厌一只猫或喜欢一只猫讨厌一条狗。

现在可以将一些狗或猫移除。如果一个人喜欢的动物被保留，并且讨厌的动物被移除，那么称这个人是开心的。现在求最多可以使多少人开心。

解题过程：

刚开始一直想的是狗和猫之间建图，然后怎么想都不好解决，因为狗和猫没有直接的关系…

然后这个题放了挺久的，直到后来才想起来补题，不错的题，感觉匹配问题主要是要将原问题如何转化到图论模型上。

题目分析：

首先我们对人建图。如果一个人喜欢的动物是另一个人讨厌的，那么这两个人是矛盾的，对所有矛盾的人之间建一条边。

这时候会发现，如果这样建图的话，不会出现长度为奇数的环，因为一个人只能如果喜欢猫了不能再讨厌猫。

所以这样建的图是一个二分图。对于矛盾的人，他们是不可能同时高兴的，也就是我们要尽量多的找出来一堆的人，他们之间不能有边。然后这就是最大独立集了。

对于二分图:

  • 最大匹配 = 最小点覆盖
  • 最小点覆盖 + 最大独立集 = |V|

那么跑一边二分图最大匹配就出来答案了。

AC代码：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>

using namespace std;

const int MAX = 2000 + 10;

struct Node {
    char like[112], dislike[112];
} data[MAX];

struct Edge {
    int u, v, nxt;
} edge[MAX * MAX * 10];

int head[MAX], etot;
int n, m, p;
int matching[MAX], vis[MAX];

void add_edge(int u, int v) {
    edge[etot].u = u;
    edge[etot].v = v;
    edge[etot].nxt = head[u];
    head[u] = etot++;
}

bool find(int u) {
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (vis[v]) continue;
        vis[v] = true;
        if (matching[v] == -1 || find(matching[v])) {
            matching[v] = u;
            matching[u] = v;
            return true;
        }
    }
    return false;
}

int main() {
    while (~scanf("%d %d %d", &n, &m, &p)) {
        memset(head, -1, sizeof(head));
        etot = 0;
        for (int i = 0; i < p; i++) {
            scanf("%s %s", data[i].like, data[i].dislike);
        }

        for (int i = 0; i < p; i++) {
            for (int j = i + 1; j < p; j++) {
                if (strcmp(data[i].like, data[j].dislike) == 0 ||
                    strcmp(data[i].dislike, data[j].like) == 0) {
                    add_edge(i, j);
                    add_edge(j, i);
                }
            }
        }

        int ans = 0;

        memset(matching, -1, sizeof(matching));
        for (int i = 0; i < p; i++) {
            if (matching[i] != -1) continue;
            memset(vis, 0, sizeof(vis));
            if (find(i)) ans++;
        }

        printf("%d\n", p - ans);
    }
}
ACM►DP►状压DP

CodeForces743E - Vladik and cards（状压DP + 二分）

题目链接：

http://codeforces.com/problemset/problem/743/E

题目大意：

给出一个只含数字 1~8 序列，找出一个符合下面条件的最长子序列。

  1. 选出的子序列，每种数字出现的次数差不能超过，没选视为出现 0 次。
  2. 选出的子序列中，相同数字出现的位置要连续。

解题过程：

补的好久之前的题，一开始题意都没看懂，然后去搜了下题意，顺便看到了二分+状压dp的标签，不过还是不会做。刚开始做的时候漏掉了第二个条件….

最后翻到了两个博客：

题目分析：

首先因为每种序列的差最大不会超过 1，那么我们可以二分答案，枚举较长的连续数字长度 L 。

然后用 DP 判断一个解是否可行，并且算出来最优的答案。

假设我们现在限制最长的长度为 L，那么对于每种数字有 L 和 L-1 两种长度可选，显然选长度为 L 是比 L-1 更优的，现在我们要知道最多能选多少个长度为 L 的。

首先用一个集合记录那些数已经选完，那些还没选，由于只有 8 个数字，所以可以用状态压缩。

设二维的 DP 数组 $dp[i][j]$ 的含义是，只考虑序列里前 i 个数字，选取的状态为 j 的时，最多能选几个长度为 L 的连续数字。

这时候有状态转移方程：

$$dp[next(i, L-1)][s \cup k] = max(itself, dp[i][s]) $$

$$ dp[next(i, L)][s \cup k] = max(itself, dp[i][s])$$

$next(i, L)$ 表示从当前位置开始往后第 L 个数字 k 的位置，这个可以通过预处理获得。

这样就得出了当最长的连续数字长度为 L 时可以选多少个长度为 L 的连续数字。

设上面结果为 sum，那么 $sum \cdot L + (8 - sum) \cdot (L - 1)$ 就是原问题的答案。

不过二分枚举 L 的时候 L 最小为 2，因为我们默认长度为 L-1 的连续数字是合法的。

我们特殊处理一下 L = 1 的情况，判断下有多少个数字至少出现了一次即可。

AC代码：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1123;
const int INF = 0x3f3f3f3f;

vector<int> pos[10];

int n, ans;
int a[MAX], dp[MAX][1 << 8], cur[10];

bool ok(int L) {
    memset(cur, 0, sizeof(cur));
    memset(dp, -1, sizeof(dp));
    //初始合法的状态只有在字符串开始并且一个没放的情况
    dp[1][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < (1 << 8); j++) {
            if (dp[i][j] < 0) continue;
            for (int k = 1; k <= 8; k++) {
                //如果当前 dp 数组的值为负数，说明当前状态是不可到达的，不进行往后转移
                if (j & (1 << (k - 1))) continue;
                if (pos[k].size() - cur[k] < L - 1) continue;
                dp[pos[k][cur[k] + L - 2]][j | (1 << (k - 1))] = max(dp[pos[k][cur[k] + L - 2]][j | (1 << (k - 1))],
                                                                     dp[i][j]);
                if (pos[k].size() - cur[k] < L) continue;
                dp[pos[k][cur[k] + L - 1]][j | (1 << (k - 1))] = max(dp[pos[k][cur[k] + L - 1]][j | (1 << (k - 1))],
                                                                     dp[i][j] + 1);
            }
        }
        //cur记录每个数字出现了多少次
        cur[a[i]]++;
    }
    int sum = -INF;
    for (int i = 1; i <= n; i++) sum = max(sum, dp[i][(1 << 8) - 1]);
    if (sum <= 0) return 0;
    ans = max(ans, sum * L + (8 - sum) * (L - 1));
    return 1;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    //记录每个出现的数字对应的下标，转移可以通过 vector 下标直接访问某个数字第 i 次出现的位置
    for (int i = 1; i <= n; i++) pos[a[i]].push_back(i);

    //二分枚举 L 且 L 至少为 2
    int l = 2, r = n;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (ok(mid)) l = mid + 1;
        else r = mid - 1;
    }

    //当答案为 0 的时候，考虑 L = 1 的情况
    if (ans == 0) {
        for (int i = 1; i <= 8; i++) {
            if (pos[i].size() > 0) ans++;
        }
    }
    cout << ans;
}