2021.7.3

Exam

早上考的是非常基础的算法知识，应该说没有什么难度。

T1就是非常经典的错排问题，容易想到递推式
$$
D_n=(n-1)(D_{n-1}+D_{n-2})
$$
直接递推就好了，复杂度$O(n)$，完全没有问题。

T2二分答案没有什么可说的。

T3要求出一个序列中长度大于$k$的子序列所有元素平均值的最大值，考场上没有想出正解比较可惜，实际上也是二分答案。

这里对原序列做一次前缀和得到$\{S_n\}$，我们二分一个答案，接下来就是要检查是否存在$l,r(l<r)$使得
$$
\frac{S_r-S_{l-1}}{r-l+1}\ge mid
$$
这个式子可以化简
$$
\begin{aligned}
S_r-S_{l-1}&\ge r\cdot mid - l\cdot mid + mid \\
S_r-r\cdot mid &\ge S_{l-1}-(l-1)mid
\end{aligned}
$$
所以我们只要对于所有$S_k$计算出$A_k=S_k-k\cdot mid$，然后检查$\{A_n\}$是否单减即可。

看到分数就要想到二分答案然后把分母扔到式子的另一边乘开，然后看看能不能发现什么性质。

T4填数独，直接一个启发式搜索就结束了。数独从空少的行开始填，非常常见的trick。

Practice

主要是学了一下随机增量法。

随机增量法用于解决平面上最小圆覆盖问题。

具体操作流程：

1. 取当前圆外一点$A$，将这一点作为圆心
2. 取当前圆外一点$B$，将$AB$作为圆的直径
3. 取当前圆外一点$C$，将当前圆设为$\triangle ABC$的外接圆

模板（Luogu P1742 最小圆覆盖）

namespace Main{
    int n;
    double r;
    struct point{
        double x, y;
        point() {}
        point(double x, double y): x(x), y(y) {}
    }a[N], o;
    inline double dis(point a, point b){
        return sqrt((a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y));
    }
    inline pair<point, double> getCircle(point a, point b, point c){
        double a1 = 2 * (b.x - a.x), a2 = 2 * (c.x - a.x);
        double b1 = 2 * (b.y - a.y), b2 = 2 * (c.y - a.y);
        double c1 = b.x*b.x - a.x*a.x + b.y*b.y - a.y*a.y;
        double c2 = c.x*c.x - a.x*a.x + c.y*c.y - a.y*a.y;
        double x = (b1 * c2 - b2 * c1) / (b1 * a2 - b2 * a1);
        double y = (a1 * c2 - a2 * c1) / (a1 * b2 - a2 * b1);
        double r = dis(a, point(x, y));
        return make_pair(point(x, y), r);
    }
    Bool inCircle(point a){
        return dis(a, o) <= r;
    }
    void Main(){
        input(n);
        for(ri i = 0; i < n; i++) cin >> a[i].x >> a[i].y;
        random_shuffle(a, a + n);
        for(ri i = 0; i < n; i++) if(!inCircle(a[i])){
            o = a[i];
            for(ri j = 0; j < i; j++) if(!inCircle(a[j])){
                o = point((a[i].x + a[j].x) / 2, (a[i].y + a[j].y) / 2);
                r = dis(o, a[j]);
                for(ri k = 0; k < j; k++) if(!inCircle(a[k])){
                    pair<point, double> res = getCircle(a[i], a[j] ,a[k]);
                    o = res.first;
                    r = res.second;
                }
            }
        }
        cout << fixed << setprecision(10) << r << endl << o.x << ' ' << o.y;
        return;
    }
} // namespace

2021.7.4

Exam

同样考基础算法，但是感觉并不基础。

T1是一个三角形计数题，讲真如果是我自己想这个题真的不一定能够想出来。

懒得在华一高搭我的PicGo就先将就着洛谷图床用吧。

以图中的端点为三角形的顶点，求共能组成多少个正三角形。显然这个正三角形可以是斜着的。

我们可以考虑从递推式开始。

从这个图中往下拓展一层，然后考虑新的一层中的端点能与原图中哪些点构成正三角形。

这里我们两点确定正三角形的规则是这样的：以这两点确定的线段为一条边，向右作正三角形，我们需要保证另一个顶点也落在图中的端点上。

对原图中每个端点计算贡献可以得到这样一个数阵

1
2 1
3 2 1
4 3 2 1

记这个数阵中所有数的和为$S_4$，我们不难得到原题的递推式
$$
T_n=T_{n-1}+S_{n-1}
$$
这样直接做复杂度是线性的，但题目期望一个常数级别复杂度的算法。

观察这个数阵，我们发现每行都是一个一维前缀和，所以$\{S_n\}$实际上是一个二维前缀和，$\{T_n\}$就应该是一个三维前缀和，事实也确实如此。

1   1   1   1   1   1   1   1   1   1
1   2   3   4   5   6   7   8   9   10
1   3   6   10  15  21  28  36  45  55
1   4   10  20  35  56  84  120 165 220 
1   5   15  35  70  126 210 330 495 715 (Answer)

更进一步我们可以发现，这个高维前缀和和数表中，每个数实际上都对应从左上角走到当前位置的方案数，我们就可以直接得到$\{T_n\}$的通项
$$
T_n=C_{n+4}^4
$$
这样T1就能够$O(1)$解决了。

T2感觉不是很难，考场上打了一个暴力水过去了，数据并没有出的特别强，我这个暴力也稍微比较难卡。

简述题意，一棵$n$个结点的树，第$i$个结点的权值为$2^i$，现在要在树上去掉$k$个点使得剩下部分仍然联通且权值和最大。

首先容易想到一个贪心思路，因为$2^k>\sum\limits_{i=0}^{k-1}2^i$，所以留下编号大的点永远比编号小的点优，于是我们需要以$n\to1$这样的顺序来选择留下哪些点。

这里我们不考虑删去哪些点，而是考虑留下哪些点。

不妨直接把$n$设为根，我们接下来每选一个点$u$，为了保证连通性，都一定得把$u\to root$路径上的点全部留下。

但是这里出现了一个问题，我们无法确定$u\to root$路径上还有多少点没有被选过。

我的解决方案是每次选一条路径都对路径上每个点进行一次$dfs$，动态更新其他点到根的距离。这样做的均摊复杂度实际上很低，足以通过考试数据，但最劣仍能够达到$O(n^2)$。

我们可以用倍增来优化这个过程。考虑在$u\to root$路径上通过倍增跳一个指针，如果当前指向的点没有被选过就向上跳，否则向下跳，这样做复杂度为$O(n\log n)$。

T3有一个很有意思的trick，如果遇到反弹相关的问题，可以考虑将图形对称无限延伸，这样就可以认为物体是在延直线运动。

T4仍然是数独，也是通过搜索解决，但是代码又难写又难调，考试基本上时间都花在了T1上，所以没人打T4。

Practice

主要做了几道极角排序题。

atan2(y, x)可以直接获得$(x,y)$的极角，这样做第一、二象限极角为负，三、四象限极角为正，所以排完序后的顺序为$3\to4\to1\to2$。

另外一种方式是使用叉积来进行极角排序，这样做精度要高于atan2，$x_1y_2-x_2y_1$为正说明$(x_1,y_1)$在$(x_2,y_2)$的逆时针方向，否则在顺时针方向。（这里方向的角度在$(0,\pi)$范围内）

struct point{
    int x, y;
    double angle;
    point() {}
    point(int x, int y): x(x), y(y) { angle = atan2(y, x); }
    Void calc() { angle = atan2(y, x); }
}; 
Bool cmp(point a, point b){
    return a.angle < b.angle;
}

2021.7.5

Exam

考字符串。

恶心到爆炸。

还是简单写一写每一道题思路和解法。

T1，对序列重复执行以下操作$k$次：

• 找到一个最小的$i$使得$a_i=4$且$a_{i+1}=7$
• 如果找不到就直接结束
• 如果$i$为奇数，令$a_{i+1}=a_i$，否则令$a_i=a_{i+1}$

序列从1开始编号

很容易想到只有出现$4,7,7$或$4,4,7$才会对一段区间进行重复操作，否则只要从头往后扫一遍就能够完成所有操作，重复操作的话就判断一下剩余操作次数的奇偶性就可以了，复杂度线性。

T2，询问母串$S$中有多少个子串满足前缀为$A$，后缀为$B$。

由于$len(S)\le2000$，所以我们直接暴力枚举$S$的所有子串，然后使用$hash$判断是否满足条件即可。

暴力枚举复杂度$O(len(S)^2)$，$hash$预处理$O(len(S))$，$hash$判断合法$O(1)$，所以说总复杂度是平方级的。

T3，首先令$r(str)$表示翻转字符串$str$，$f(s,l,r)=s_{i+1...j-1}+r(s_{j...n-1})+r(s_{0...i})$，给定$A$，$B$，求一对$i,j$使得$f(A,i,j)=B$。

这个题的数据水的离谱，你其实只需要打一个较为优秀的$O(len^3)$暴力就足以切掉这道题，我就是是用这种方式。

实际上对于这道题而言，暴力算法只要处理好细节，在随机数据下表现无比优秀。你也可以使用$hash$优化这个暴力的过程，但是实测比我的暴力跑起来要更慢（有可能是$hash$的实现不太好）。

正解是$exKMP$，预处理$A$的每个后缀与$B$匹配的$LCP$，这是用来处理$s_{i+1...j-1}$这一段，预处理$B$的每个后缀与$r(A)$匹配的$LCP$，这是用来处理$r(s_{0...i})$这一段。然后同样是枚举。没有实现这种做法。

T4不是字符串题，而且个人认为像是一道观赏题，但是可以写一写基础思想。

在一个号码中，限制了每个数字后面可以接的数字，比如说如果出现$1$后面就只能接$3,7,9$这种。

现在要求你构造字典序第$k$小的号码。

根据题目给的限制， 我们可以构造一个$10$行$10$列的矩阵，初始矩阵中如果$i$后面能够接$j$，那么$(i,j)$为$1$，否则为$0$，然后我们只要对这个矩阵取$k$次幂就能够得到长度为$\le k$的号码共有多少个，这样我们就能够确定最后答案的位数。

这是这题的核心思路，后面还需要通过二分和矩乘判断每一位上的数字。

Practise

晚上上了字符串的课，讲的内容比较基础，学了一下$ACAM$，另外$exKMP$的板子以及题目还没打。个人认为把概念弄清楚无比重要。

AC自动机是一个接受且仅接受以指定的字符串集合中的某个元素为后缀的字符串的$DFA$（确定有限状态自动机）。也就是$Trie+KMP$。

（LuoguP3808 AC自动机 简单版）

const int ACAM_SIZE = 2000005;
struct ACAM{
    int cnt, num[ACAM_SIZE], fail[ACAM_SIZE], ch[ACAM_SIZE][30];
    ACAM(){
        cnt = 0;
        memset(ch, 0, sizeof(ch));
        memset(num, 0, sizeof(num));
    }
    void build(char *s){
        int len = strlen(s), p = 0;
        for(ri i = 0; i < len; i++){
            if(!ch[p][s[i]-'a']) ch[p][s[i]-'a'] = ++cnt;
            p = ch[p][s[i]-'a'];
        }
        num[p]++;
    }
    void getfail(){
        queue<int> q;
        for(ri i = 0; i < 26; i++){
            if(ch[0][i]){
                q.push(ch[0][i]);
                fail[ch[0][i]] = 0;
            }
        }
        while(!q.empty()){
            int now = q.front(); q.pop();
            for(ri i = 0; i < 26; i++){
                int p = ch[now][i];
                if(p){
                    fail[p] = ch[fail[now]][i];
                    q.push(p);
                }
                else ch[now][i] = ch[fail[now]][i];
            }
        }
    }
    int solve(char *s){
        int len = strlen(s), p = 0, ans = 0;;
        for(ri i = 0; i < len; i++){
            p = ch[p][s[i]-'a'];
            for(ri j = p; j && num[j] != -1; j = fail[j]) ans += num[j], num[j] = -1;
        }
        return ans;
    }
}AC;

另外AC自动机的$fail$边可以连成一棵树的，我们每次把文本串放到AC自动机上跑一遍，走到一个状态上之后，就顺着$fail$边一直往上跑直到跑到根为止统计答案，所以对于一个模式串而言，要想知道其被匹配了多少次，我们只需要在$fail$树上统计其终止结点的子树内结点一共被走了多少次即可。

（LuoguP5357 AC自动机 二次加强版）

namespace Main{
    const int N = 200005;
    const int L = 2000005;
    const int ACAM_SIZE = 200005;
    struct ACAM{
        int cnt, match[ACAM_SIZE], ch[ACAM_SIZE][30], fail[ACAM_SIZE];
        void clear(){
            cnt = 0;
            memset(ch, 0, sizeof(ch));
        }
        void build(char *s, int k){
            int len = strlen(s), p = 0;
            for(ri i = 0; i < len; i++){
                if(!ch[p][s[i]-'a']) ch[p][s[i]-'a'] = ++cnt;
                p = ch[p][s[i]-'a'];
            }
            match[k] = p;
        }
        void getfail(){
            queue<int> q;
            for(ri i = 0; i < 26; i++){
                if(ch[0][i]) fail[ch[0][i]] = 0, q.push(ch[0][i]);
                else fail[ch[0][i]] = 0;
            }
            while(!q.empty()){
                int now = q.front(); q.pop();
                for(ri i = 0; i < 26; i++){
                    if(ch[now][i]){
                        fail[ch[now][i]] = ch[fail[now]][i];
                        q.push(ch[now][i]);
                    }
                    else ch[now][i] = ch[fail[now]][i];
                }
            }
        }
    }AC;
    int n, siz[N];
    char s[L];
    vector<int> g[N];
    void dfs(int u){
        for(ri i = 0; i < g[u].size(); i++){
            int v = g[u][i];
            dfs(v);
            siz[u] += siz[v];
        }
    }
    void Main(){
        AC.clear();
        input(n);
        for(ri i = 0; i < n; i++) scanf("%s", s), AC.build(s, i);
        AC.getfail();
        for(ri i = 1; i <= AC.cnt; i++) g[AC.fail[i]].push_back(i);
        scanf("%s", s);
        int len = strlen(s);
        for(ri i = 0, p = 0; i < len; i++){
            p = AC.ch[p][s[i]-'a'];
            siz[p]++;
        } 
        dfs(0);
        for(ri i = 0; i < n; i++) write(siz[AC.match[i]]), puts("");
        return;
    }
} // namespace

2021.7.6 & 2021.7.7

Exam - 7.6

今天考的字符串就涉及到昨天上课讲的知识了。

T1是一个简单的$kmp$性质题，有原题（LuoguP2375 [NOI2014] 动物园）。

$kmp$是可以看做自动机的，nxt[]就相当于fail[]，我们同样可以将nxt[]看作一个树形结构，对于$s$的一个子串$s_{0...i}$，我们可以通过nxt[i] nxt[nxt[i]] nxt[nxt[nxt[i]]]等获得其所有border。

知道这个性质然后再注意一下跳nxt时的细节，这题就结束了。

T2同样是原题，CodeForces 235C，只不过作了一些修改，原题是一个$SAM$性质题，而这一题是能够使用$hash$通过的。

简述题意，给定一个模式串$s$和$n$个文本串，求模式串的所有循环同构在文本串中出现次数之和。

$hash$做法自然就十分暴力，枚举模式串的所有循环同构，然后再与文本串匹配即可，复杂度显然是$O(len(s)^2)$的，只有$10^8$级别。

T3阅读理解题，原题面直接放在这里：

描述
When the son was in high school, he didn’t like exams. As a none famous writer, he wanted to write a long novel and declared that it’s his own work. But his father doesn’t trust his son because his son is a punk.The father embedded “text finger prints” in all the novels and articles. If the son treats him badly,the father will stand out and declare that his son is a fake writer. The father can prove that he actually is the author.He points out some words that come from his book and these words have been copyed by his son.
输入
There are multiple test cases. The first line in the input is an integer $T$ indicating the number of test cases. For each test case: The first line if a integer n indicatding the number of father’s words. Then $n$ lines follows, each represents a text finger print. It’s guaranteed that these $n$ strings are at least consists of one letter. The last line of a text case is the article. All letters of INPUT may be described in a compressed format. A compressed string consists of capital letters and “compressors”. A “compressor” is in the follow format: [qx] $q$ is a number and $x$ is a capital letter. It means $q$ consecutive letter $x$s in the original uncompressed string. For example, [6K] means KKKKKKin the original string. So, if a compressed string is like: AB[2D]E[7K]G It actually is ABDDEKKKKKKKG after decompressed to original format. If some of the $n$ works are the same, please only leave one word and others are useless.
输出
For each case, print an integer $k$ in a line meaning that the article includes $k$ text finger prints. PLEASE NOTE: If finger print $s1$ is a sub string of finger print $s2$ and $s2$ is included in the article, then $s1$ doesn't count ($s1$ can be regarded as doesn't exists). Multiple appearances of a finger print in the article are just counted as one.

题目读完你就会发现这直接用$ACAM$做就可以了。暴力将每个模式串拆开丢到自动机里去，文本串在匹配的时候有一些细节，最重要的是这个：

If finger print $s1$ is a sub string of finger print $s2$ and $s2$ is included in the article, then $s1$ doesn't count.

子串其实可以看做是一个前缀的后缀，所以这个时候我们考虑建出$fail$树，匹配统计答案时我们只考虑树上深度较低的结点即可。

T4观赏题，用$SA$做，跳了。

Practice

$exKMP$的坑填上了，同样的思想，用已经求出的$lcp$来辅助更新当前的答案，画个图就很好理解了。

LuoguP5410 扩展 KMP（Z 函数）

namespace Main{
    int len1, len2, nxt[N], ext[N];
    ll ans;
    char a[N], b[N];
    void Main(){
        scanf("%s%s", a, b);
        len1 = strlen(a);
        len2 = strlen(b);

        nxt[0] = len2;
        for(ri i = 1, l = 0, r = 0; i < len2; i++){
            if(i <= r && nxt[i - l] < r - i + 1) nxt[i] = nxt[i - l];
            else{
                nxt[i] = max(0, r - i + 1);
                while(i + nxt[i] < len2 && b[i + nxt[i]] == b[nxt[i]]) nxt[i]++;
            }
            if(i + nxt[i] - 1 > r) l = i, r = i + nxt[i] - 1;
        }
        for(ri i = 0; i < len2; i++) ans ^= (ll)(i + 1) * (nxt[i] + 1);
        write(ans); puts("");

        while(ext[0] < len1 && a[ext[0]] == b[ext[0]]) ext[0]++;
        for(ri i = 1, l = 0, r = 0; i < len1; i++){
            if(i <= r && nxt[i - l] < r - i + 1) ext[i] = nxt[i - l];
            else{
                ext[i] = max(0, r - i + 1);
                while(i + ext[i] < len1 && a[i + ext[i]] == b[ext[i]]) ext[i]++;
            }
            if(i + ext[i] - 1 > r) l = i, r = i + ext[i] - 1;
        }
        ans = 0;
        for(ri i = 0; i < len1; i++) ans ^= (ll)(i + 1) * (ext[i] + 1);
        write(ans);

        return;
    }
} // namespace

$ACAM$又刷了几道题，至少现在已经把$ACAM$玩得比较熟了。

但是又多了两个坑，$SA$和$SAM$，后面找时间再说，七月集训这段时间大概都没时间学。

2021.7.8

Exam

T1在题意简化后可看做是一次必须走两步的一个最短路问题，具体地说，你的一步都需要借助一个途经点，当然，并且你只能经过这个途经点，而不能真正到达途经点，$u\to a\to v$的权值为$(w_{u\to a}+w_{a\to v})^2$。

最直接的想法当然还是直接跑$dijkstra$，由于一次必须走两步，在枚举$v$的时候我们必须套两层循环，很显然这样做的最高复杂度可以达到$O(|V|^2)$。

但是可以注意到一点， 原题目中$w$的数据范围很小，所以我们可以考虑拆点。对于一个点$u$，我们将其拆成$u_0,u_1,u_2\dots u_{50}$共51个点，其中，$u_0$表示停留在$u$点的状态，$u_i(1\le i\le 50)$表示途径$u$点，并且有一条权值为$i$的边到达$u$点。这样的话， 原来的$u\xrightarrow{w_0} a\xrightarrow{w_1} v$就可以被拆成$u_0\xrightarrow1 a_{w_0}$和$a_{w_0}\xrightarrow{(w_0+w_1)^2} v_0$两条边，然后再跑最短路就可以了。可以证明此时实际点数并不会达到$Wn$，由于每条边最多新增一个途经点，所以新图中点数最多为$n+m$。

T2给你了一张无向图，其中每个点为黑点或者白点，第$i$条边的权值为$2^i$，现在要求所有黑电到白点的最短距离之和。

首先在这道题目里面看到$2^i$肯定应该最先想到$2^0+2^1+\dots+2^{k-1}<2^k$这个性质，所以我们直接在原图上跑最小生成树，这样可以保证任意两点间的最短路一定在生成树上。

这样的话图上问题就被转化为了树上问题，接下来我们只需要通过一次$dfs$统计出每个子树中黑点与白点的个数，然后就可以$O(n)$的统计出最短距离之和。

T3，对于$n$个点$(x_i,y_i)$，现在要求至少需要多少条形如$y=x+d$或$y=-x+d$的直线能够穿过所有点。可以发现，两点能够共用一条直线当且仅当$x_1+y_1=x_2+y_2$或$x_1-y_1=x_2+y_2$，那么，问题就被转化为了一个求一个二分图的最小点覆盖，对于一个点$(x_i,y_i)$，我们将$x_i+y_i$与$x_i-y_i$连边，建超级源点以及超级汇点然后跑$dinic$即可， 复杂度显然应该是$O(n\sqrt n)$。

T4是一个矩阵数定理模板题，还没有学所以暂且放着。

Practice

为了学矩阵数定理，肯定得先学行列式。由于我并没有上线性代数的课，所以说行列式我得从零开始学。

首先，行列式有这样几个性质：

• 行列互换，行列式值不变。
• 行列式的一行乘上$k$，行列式值也乘$k$。
• 如果行列式的一行是两组数之和，那么这个行列式可以被表示为两个行列式之和，这两个行列式的其他行都与原行列式相同，该行分别为两组数。
• 对换行列式两行位置，行列式反号。
• 如果行列式两行成比例，行列式值为0。
• 把行列式中某一行乘上$k$加到另一行，行列式值不变。

那么，接下来考虑如何求一个行列式的值。

首先对于一种特殊的行列式
$$
\begin{vmatrix}
a_{11} & a_{12} & a_{13} & \cdots & a_{1n} \\
0 & a_{22} & a_{23} & \cdots & a_{2n} \\
0 & 0 & a_{33} & \cdots & a_{3n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & a_{nn}
\end{vmatrix}
$$
很容易发现行列式的值就是
$$
\prod_{i=1}^n a_{ii}
$$
所以说我们现在的目标就是把一个普通行列式转化为这样一个特殊的行列式。

这里直接使用辗转相除即可，具体地，我们考虑这样一个行列式
$$
\begin{vmatrix}
10 & a_{12} & a_{13} & \cdots & a_{1n} \\
3 & a_{22} & a_{23} & \cdots & a_{2n} \\
a_{31} & a_{32} & a_{33} & \cdots & a_{3n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & a_{n3} & \cdots & a_{nn}
\end{vmatrix}
$$
我们将第一行所有数减去$A=\lfloor\frac{10}3\rfloor\times3$，这样，行列式就变成了
$$
\begin{vmatrix}
1 & a_{12}-A & a_{13}-A & \cdots & a_{1n}-A \\
3 & a_{22} & a_{23} & \cdots & a_{2n} \\
a_{31} & a_{32} & a_{33} & \cdots & a_{3n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & a_{n3} & \cdots & a_{nn}
\end{vmatrix}
$$
然后，交换第一行与第二行
$$
\begin{vmatrix}
3 & a_{22} & a_{23} & \cdots & a_{2n} \\
1 & a_{12}-A & a_{13}-A & \cdots & a_{1n}-A \\
a_{31} & a_{32} & a_{33} & \cdots & a_{3n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & a_{n3} & \cdots & a_{nn}
\end{vmatrix}
$$
接下来重复一样的操作，第一行所有数减去$B=\lfloor\frac3 1\rfloor\times 1$
$$
\begin{vmatrix}
0 & a_{22}-B & a_{23}-B & \cdots & a_{2n}-B \\
1 & a_{12}-A & a_{13}-A & \cdots & a_{1n}-A \\
a_{31} & a_{32} & a_{33} & \cdots & a_{3n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & a_{n3} & \cdots & a_{nn}
\end{vmatrix}
$$
可以发现已经出现$0$了，同样交换第一行与第二行
$$
\begin{vmatrix}
1 & a_{12}-A & a_{13}-A & \cdots & a_{1n}-A \\
0 & a_{22}-B & a_{23}-B & \cdots & a_{2n}-B \\
a_{31} & a_{32} & a_{33} & \cdots & a_{3n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & a_{n3} & \cdots & a_{nn}
\end{vmatrix}
$$
这样，我们就已经将下三角的其中一个位置变为了$0$，其他位置同理。

这里注意每次交换行要反号。

ll a[N][N];
int gauss(){
    ll res = 1;
    for(ri i = 0; i < n; i++){
        for(ri j = i + 1; j < n; j++){
            if(a[j][i] > a[i][i]) swap(a[i], a[j]), res = p - res;
            while(a[j][i]){
                ll x = a[i][i] / a[j][i] % p;
                for(ri k = i; k < n; k++) a[i][k] = (a[i][k] - a[j][k] * x % p + p) % p;
                swap(a[i], a[j]);
                res = p - res;
            }
        }
    }
    for(ri i = 0; i < n; i++) res = res * a[i][i] % p;
    return res;
}

2021.7.9

Exam

T1是$DAG$支配树的模板。

T2是一个比较简单的费用流，但是考场上压根没看出来是费用流，同时费用流板子也记得不熟，那就没办法了。

T3有原题，LuoguP5025 炸弹。

$solution$给的是一个线段树优化建图的做法，但是这样做复杂度是$O(n\log n)$的，同时也很难写。

实际上这道题有一个十分精妙的线性做法。

首先，我们可以维护一个单调栈，求出每个点只向左炸能够炸多远，右边同理，但是我们还需要考虑一些特殊情况，炸弹还能够先向右炸再向左炸，反之亦然，我考场上就是在这里被卡住了。

我们其实可以在第一次维护向左炸的距离时顺带维护炸弹向右的最大爆炸范围，然后第二次维护向右最大距离是顺带更新向左的最大距离。

这样做表面上处理不了先向左再向右再向左再向右这样的套娃情况，实际上是可以的。

考虑一下为什么正确性成立，因为我们第二次维护向右最大距离时，一次性向左炸的最大距离已经维护好了，如果是套娃情况，由于爆炸距离一定是一次比一次远，所以我们的更新顺序自然是从外层套外开始的，不知道能不能明白我的意思，也就是说如果先左后右再左再右，我们首先会更新“再左再右”这一层，然后再处理“先左后右”这一层。

最好的理解方式就是把单调栈打出来之后调试，一步一步看执行过程，真的无敌精妙。

看起来假的做法实际上是真的。

namespace Main{
    int L[N], R[N];
    ll n, ans, x[N], r[N], tl[N], tr[N];
    ll stk[N], top; 
    void Main(){
        input(n);
        for(ri i = 0; i < n; i++){
            input(x[i], r[i]);
            tl[i] = x[i] - r[i];
            tr[i] = x[i] + r[i];
            L[i] = R[i] = i;
        }
        for(ri i = 0; i < n; i++){
            while(top > 0 && tl[i] <= x[stk[top-1]])
                L[i] = L[stk[--top]], tr[i] = max(tr[i], tr[stk[top]]);
            stk[top++] = i;
        }
        top = 0;
        for(ri i = n - 1; i >= 0; i--){
            while(top > 0 && tr[i] >= x[stk[top-1]])
                R[i] = R[stk[--top]], L[i] = min(L[i], L[stk[top]]);
            stk[top++] = i;
        }
        for(ri i = 0; i < n; i++)
            ans = (ans + 1ll * (i + 1) * (R[i] - L[i] + 1) % MOD) % MOD;
        write(ans);
        return;
    }
} // namespace

T4网络流建模至今不会。

Practise

无向图上的矩阵树定理

首先对无向图定义$Laplace$矩阵，$L_{ii}(G)=\deg(i)$，$L_{ij}(G)=-e_{ij}(i\ne j)$，其中$e_{ij}$表示$ij$之间相连的边数。

那么$G$的最小生成树个数就是将$Laplace$矩阵抽掉任意一行一列后构成行列式的值。

2021.7.12

Exam

数据结构这种东西考场上乱糊是不现实的，这种东西就能够真正看出人与人的差距了。

orz红太阳$\mathrm{\color{black}{h}\color{red}{uangyikun}}$和神$\mathrm{\color{black}{F}\color{red}{Zzzz}}$。

由于今天的题目都不会写所以不太好总结。

首先四道题都有原题，分别是P5089，P4428，P5305，P4425。

T1还算挺简单的，就是给你了一个网格，里面有些格子已经被标记了，如果$(r_0,c_0)$，$(r_0,c_1)$和$(r_1,c_0)$三个格子被标记，那么我们就可以以$0$的花费直接标记$(r_1,c_1)$，也可以以$1$的花费任意标记一个格子，求标记所有格子的最小花费。

我们可以把这个网格转化为一个二分图，对于一个已经被标记的格子$(r,c)$，我们在二分图上连一条$r\to c$的边，可以发现$0$花费的标记方式不会改变二分图的连通性，另一方面，二分图的一个连通块中是可以任意连边的，也就是说，对于一个连通块而言，我们可以以$0$的花费连完里面所有的边，于是我们只需要在连通块之间连边即可，显然如果二分图上有$k$个连通块，我们只需要$k-1$的花费就可以连完所有边，于是答案就为$k-1$。

另外T3大概能搞懂是怎么做的，代码还没有实现。

对于一棵$n$个结点的有根数，给定常数$k$，$q$次询问，每次给出$(x,y)$，求
$$
\sum_{i\le x}\mathrm{dep}(\mathrm{lca}(i,y))^k
$$
这个东西其实有一个很神奇的性质，我们把$k$次方丢掉，式子就变成了对$\mathrm{dep(lca)}$求和，一次性求多个$\mathrm{lca}$显然不现实，所以我们换个方式考虑。$\mathrm{dep(lca(}x,y\mathrm{))}$实际上就是$root\to x$与$root\to y$两条路径的交集大小，所以我们考虑每次查询，在树剖之后，对于每一个$\mathrm{lca}(i,y)$，在线段树上将$root\to i$区间$+1$，最后直接区间查询$root\to y$即可。

那么现在加上了一个$k$次方，考虑刚才操作的实质，其实我们做的就是一个树上差分，加上$k$次方后我们只需要给线段树上每个点赋一个权值即可，具体的，对于结点$u$，其权值就为$\mathrm{dep}(u)^k-\mathrm{dep}(fa_u)^k$。

然后还要注意的就是离线处理询问，按照$x$排序，避免每次清空线段树，复杂度就可以降掉一个$q$。

T3超级无敌细节题，用一个线段树容斥一下就能做，但是极其复杂。

具体可以参考神$\mathrm{\color{black}{2}\color{red}{5917921qiu}}$的提交R52922804。

T4不会。

Practise

得规划一下DS的学习，目前来讲，优先熟练线段树，树剖，点分治，左偏树这种简单内容，要学的主要就是主席树，莫队，$KDT$，$LCT$，平衡树（无旋$treap$和$Splay$）。显然优先级按照我列出的顺序排序。

有多的时间就去搞替罪羊树，李超树这种，不可能有多的时间的。

2021.7.13 & 2021.7.14

Exam - 2021.7.13

依然是阴间的数据结构考试。

T1是[JOI 2019 Final]珍しい都市，据说做法是长剖，写起来不难，就是把重剖更新son[u]的方式改为按照maxdep[v]更新即可，但是不知道这玩意具体怎么用。

T2是对于一个序列，每次操作对区间$[l,r]$内的任一元素$x$，将其变为$ax+b\mod m$。正解是二进制分组，但是这题大概是数据给的太水，实现较为优秀的暴力即可拿到60到70pts的高分。

我是真的想不明白我的暴力为什么跑的比别人快那么多。代码贴在这里。

#include<bits/stdc++.h>
#define File(name) freopen(#name".in", "r", stdin); freopen(#name".out", "w", stdout);
#define ri register int
using namespace std;
typedef long long ll;
const int N = 100005;
int n, m, q, op, task, cnt, a[N];
ll lastans;
struct handle{
    int i, j, a, b;
}h[N]; 
template<typename T>
T read(){
    T n = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        n = n * 10 + ch - '0';
        ch = getchar();
    }
    return f * n;
}
template<typename T>
void write(T n){
    if(n/10) write(n/10);
    putchar(n%10+'0');
}
int main(){
    File(metaphysics)
    task = read<int>();
    n = read<int>(), m = read<int>();
    for(ri i = 1; i <= n; i++) a[i] = read<int>();
    q = read<int>();
    while(q--){
        op = read<int>();
        if(op == 1){
            h[++cnt].i = read<int>() ^ lastans;
            h[  cnt].j = read<int>() ^ lastans;
            h[  cnt].a = read<int>();
            h[  cnt].b = read<int>();
        }
        else{
            int s = read<int>() ^ lastans, e = read<int>() ^ lastans, k = read<int>() ^ lastans;
            lastans = a[k];
            for(ri i = s; i <= e; i++){
                if(h[i].i > k || h[i].j < k) continue;
                lastans = (h[i].a * lastans + h[i].b + m) % m; 
            }
            write(lastans); puts("");
            if(~task&1) lastans = 0;
        }
    }
    return 0;
}

按道理说$n=10^5,q=10^5$，这个时候$O(nq)$的算法是拿命跑也跑不过去的，但是这份代码居然能卡过去？

时限$8s$

T3不会，但是由于题目涉及到莫比乌斯函数结果我连莫比乌斯函数是什么都不知道，甚至认不出来$\mu(x)$，在这里记录一下关于莫比乌斯函数的内容。
$$
\mu(x)=
\begin{cases}
1 & x = 1\\
(-1)^k & x=p_1p_2p_3\dots p_k(p_1\ne p_2\ne \dots\ne p_k)\\
0 & otherwise
\end{cases}
$$
简单的性质：

• 莫比乌斯函数是积性函数，$\mu(a)\mu(b)=\mu(ab)$
• $\sum\limits_{d|n}\mu(d)=[n=1]$

T4有一个和昨天T3一样的树剖+差分的$O(n\log\log n)$做法，如果实现的常数小就能够通过本题，另外有一个$O(n\log n)$的线段树合并做法，不太会。

Practise

主要做的是树剖的题目，打了两道比较难码的题目，感觉自己树剖的掌握程度要高了很多，至少在考场上打出来是没什么问题的。

集训给的时间还是太少了，三天一个专题还有高强度的考试和讲课，基本没什么时间学东西，所以说数据结构这块还是有大量东西没有学。

感觉自己因为时间还算挺多的，就应该在一个专题上多花费一些时间精力，长时间专攻一个版块，而不是三四天一换的这种像赶时间一样的学习节奏。。。

2021.7.15

Exam

非常重要的$dp$， 但是考的实在是太差了，简直直接自闭。

实际上我的问题主要出在做题策略上，今天考试正常来讲最好拿分的应该在T1和T3，但是由于T3是一个树上问题我基本上直接就给跳掉了，按照142的顺序开的题，最后结果奇差无比。

首先T1是一道比较水的$dp$，要求在一个$n\times m$的矩阵$a$中取出部分元素使得元素和$\mod p=0$，要求每行取出的元素个数不超过$\lfloor\frac m2\rfloor$，同时最大化元素和。

容易想到设$f_{i,j,k,l}$表示当前已经取到了第$i$行第$j$列，此时元素和$\mod p=k$，当前行已经取出了$l$个数。

转移方程很好写，对于一般情况
$$
\large{f_{i,j,k,l}=\max\{f_{i,j-1,k,l},f_{i,j-1,(k-a_{i,j})\ \mathrm{mod}\ p,l-1}\}}
$$
换行的时候要特殊考虑
$$
\large{
\begin{aligned}
f_{i,0,k,0}&=\max\{f_{i-1,m,k,l}\}\\
f_{i,0,k,1}&=\max\{f_{i-1,m,(k-a_{i,j})\ \mathrm{mod}\ p,l}\}
\end{aligned}
}
$$
T2，对于一个$1,2,\dots,n$的排列$\{a_n\}$，定义
$$
b_i=
\begin{cases}
0 & a_i<a_{i+1} \\
1 & a_i>a_{i+1}
\end{cases}
$$
给定$\{b_n\}$，问有多少个$\{a_n\}$与其匹配。

这题拿到手的时候，我认为$dp$非常难写，并且也不好打记搜，因为我认为对于$a_{i\dots n}$的方案数而言，$a_{1\dots i-1}$是会对其有影响的，如果这样的话，一方面空间不够，另一方面复杂度也直接原地裂开，所以考场上直接用next_permutation打了个暴力，也没有想过优化搜索什么的。

但是如果你打了一个记搜上去，你会发现这样做能够通过所有样例，这么做确实是正确的，$a_{1\dots i-1}$实际上没有后效性。

我们考虑这样一种情况，我们已经对于$b_{1\dots i-1}$构造出了一个满足条件的$1,2,\dots i$的排列，比如是$\{4,3,1,2\}$，这个时候，我们希望将其向后拓展，我们$\forall x\in[1,5]$将其加入到序列末尾，你会发现$x$可能与序列中的元素重复，我们只需要对于原序列中$\ge x$的元素$+1$即可，这样我们就保证了直接顺序枚举不存在后效性。

如果这样的话，$dp$就非常显然了，设$dp_{i,j}$表示已经填好前$i$个数并且第$i$个数填$j$的方案数，通过一个前缀和和后缀和就能够进行转移。

T3是树形$dp$的典题，对于一棵$n$和结点，边有边权的树，希望最大化连通块内的边权和，要求连通块内度数$> k$的点不超过一个。

任选树根，设$dp_{u,0}$表示以$u$为根的子树内所有点度数都不超过$k-1$的连通块的最大边权和， $dp_{u,1}$则要求连通块内有且仅有一个点的度数超过$k-1$，特别的，对于根节点， 限制更改为$k$。

显然，$dp_{u,0}=\sum\limits_{i=0}^{k-1}dp_{son_i,0}+w_{u,son_i}$，这里$son_i$按照$dp_{son_i,0}+w_{u,son_i}$排序。

$dp_{u,1}$需要考虑三种情况：

• 如果度数超过$k-1$的结点就是$u$，则$dp_{u,1}=\sum\limits_idp_{son_i,0}+w_{u,son_i}$
• 如果度数超过$k-1$的结点是$dp_{u,0}$所选取的$k-1$个结点之一，则$dp_{u,1}=\sum\limits_{i=0}^{k-1}\left(dp_{son_i,0}+w_{u,son_i}\right)+\max\limits_{i=0}^{k-1}\{dp_{son_i,1}-dp_{son_i,0}\}$
• 如果度数超过$k-1$的结点在所选$k-1$个结点之外，则$dp_{u,1}=\sum\limits_{i=0}^{k-2}(dp_{son_i,0}+w_{u,son_i})+\max\{dp_{son_i,1}\}$

关于这最后一种情况其实还有一些争议，$\mathrm{\color{black}{F}\color{red}{rSmT}}$在考场代码中并没有考虑最后一种情况，并且顺利通过了本题， 由于无法证明直接舍弃最后一种情况的正确性，所以我们暂且认为最后一种情况的出现概率极小，但仍然应该考虑。

总复杂度为$O(n\log n)$。

T4，要求最小化序列分割为$k$段后每段和的最大值，可以不分完。

使最大值最小，很容易想到二分。

实际上包括我在内的部分人因为这是$dp$考试所以压根没想着用二分。

考虑现在二分到了一个最大值$mid$，我们尝试判断其是否合法。

设$dp_i=x$表示序列中前$i$个数最多能够被分为满足条件的$x$段，容易想到转移方程
$$
dp_i=\max\{dp_j\}+1\ (j<i,\sum\limits_{k=j+1}^ik\le mid)
$$
直接枚举是$O(n^2)$的，考虑怎么优化。

首先做一次前缀和，对$j$的限制可以改为
$$
S_i-S_j\le mid \Longrightarrow S_j\ge S_i-mid
$$
可以发现我们现在只需要求区间最大值即可，这个可以用线段树维护。

总复杂度$O(n\log n\log|V|)$。

Practise

$dp$太差，先主要以练思维为主，刷$\mathrm{CodeForces}$上的题，大概按照$\mathrm{Luogu}$上2100分的$\mathrm{CF}\ dp$题单刷。之后再去学$dp$的优化以及$ddp$那些东西。

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。