周一 3.8 （KMP+AC自动机）
昨天又打了一场积分赛
心态上比第一场好了很多，继续保持
但是做题策略就不是很好己哪里写了bug
C题是最难的，我因为按顺序做题就在这浪费了很长时间
我剩下一个小时在刚E题
E题我以为很简单，但我犯了一个关键的错误而我不知道
然后就剩下一半时间都在debug，还是没找出错误
其实F题我应该是可以做出来的
所以之后做题策略要注意，遇到题目卡住不要死磕及时跳过
所以比赛就2点，心态和策略
「CF471D」MUH and Cube Walls(kmp）
昨天校赛就死在这道题上了，其实不难，但我犯了一个很关键的错误
我第一个感觉是让它们都在同一水平线上，也就是都减去第一个数
所以我在kmp的过程中a[i] == b[j] 我改成了a[i - j] == b[j]
但是我在求Next数组的时候还是写b[i] == b[j]，应该写b[i - j] == b[j]
说到底还是做题少了经验不够，要独立做大量大量的题目
正解是另外一种思路，就是匹配的话差分一定是一样的
也就是每个数和后面的数的差值是一样的，那么就处理成差值做kmp就好
注意这时两个数组的最后一位都没有意义了，差值包含了最后一位信息，可以直接把两个数组的长度都-1
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e5 + 10;
int a[N], b[N], Next[N], n, w, ans;void get_next()
{Next[0] = -1;int i = 0, j = -1, len = w;while(i < len){if(j == -1 || b[i] - b[i - j] == b[j]) //kmp和求Next数组一起改 {i++; j++;Next[i] = j;}else j = Next[j];}
}int main()
{scanf("%d%d", &n, &w);REP(i, 0, n) scanf("%d", &a[i]);REP(i, 0, w) scanf("%d", &b[i]);int t = b[0];REP(i, 0, w) b[i] -= t;get_next();int i = 0, j = 0, len = n;while(i < len){if(j == -1 || a[i] - a[i - j] == b[j]){i++; j++;if(j == w) {ans++;j = Next[j]; //这种求匹配次数的，匹配完成ans++然后直接j = Next[j] }}else j = Next[j];}printf("%d\n", ans);return 0;
}P5357 【模板】AC自动机（二次加强版）
昨天做了加强版
发现我的做法一样适用于二次加强版，改了一下就AC了
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e5 + 10;
int t[N][26], fail[N], End[N], num[N], len, n, cnt = 1;
string s[N], T;
vector<int> ve[N];void add(string str, int i)
{int p = 1, h = 0; len = str.size();REP(i, 0, len){h++;int id = str[i] - 'a';if(!t[p][id]) {t[p][id] = ++cnt;ve[h].push_back(t[p][id]);}p = t[p][id];}End[i] = p;
}void get_fail()
{_for(i, 0, 25) t[0][i] = 1;fail[1] = 0;queue<int> q;q.push(1);while(!q.empty()){int u = q.front(); q.pop();_for(i, 0, 25){if(t[u][i]){q.push(t[u][i]);fail[t[u][i]] = t[fail[u]][i];}else t[u][i] = t[fail[u]][i];}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cin >> n;_for(i, 1, n) cin >> s[i], add(s[i], i);get_fail();cin >> T;len = T.size();int p = 1;REP(i, 0, len){p = t[p][T[i] - 'a'];num[p]++;}for(int i = 2e5; i >= 1; i--)for(auto u: ve[i])num[fail[u]] += num[u];_for(i, 1, n)cout << num[End[i]] << endl;return 0;
}我看很多做法是建立fail树，统计子树和
我按照这个思路写了
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e5 + 10;
int t[N][26], fail[N], End[N], num[N], len, n, cnt = 1;
vector<int> g[N];
string s, T;void add(string str, int i)
{int p = 1; len = str.size();REP(i, 0, len){int id = str[i] - 'a';if(!t[p][id]) t[p][id] = ++cnt;p = t[p][id];}End[i] = p;
}void get_fail()
{_for(i, 0, 25) t[0][i] = 1;fail[1] = 0;queue<int> q;q.push(1);while(!q.empty()){int u = q.front(); q.pop();_for(i, 0, 25){if(t[u][i]){q.push(t[u][i]);fail[t[u][i]] = t[fail[u]][i];}else t[u][i] = t[fail[u]][i];}}
}void dfs(int u)
{for(auto v: g[u]){dfs(v);num[u] += num[v];}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cin >> n;_for(i, 1, n) cin >> s, add(s, i);get_fail();cin >> T;len = T.size();int p = 1;REP(i, 0, len){p = t[p][T[i] - 'a'];num[p]++;}_for(i, 2, cnt)g[fail[i]].push_back(i);dfs(1);_for(i, 1, n) printf("%d\n", num[End[i]]);return 0;
}周二 3.9 （二维前缀和）
计蒜客 - T2185
这题思路太骚了，真的想不到
把矩阵旋转一下就可以转化为二维前缀和了
顺便复习一下二维前缀和把
转化的时候坐标要改变，列几个坐标找一下规律就好
然后n和k都乘以2-1
但是这题数据是错的，太坑了，另一个写了关于这道题的博客也说了，浪费了我挺多的时间了
肯定存在锤子一部分在原来矩形外面而答案更优的情况，但是考虑了这种情况反而WA了
我写的是考虑的情况
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 4000 + 10;
int s[N][N], n, k;int cal(int x1, int y1, int x2, int y2)
{return s[x1][y1] - s[x2-1][y1] - s[x1][y2-1] + s[x2-1][y2-1];
}int main()
{scanf("%d%d", &n, &k);_for(i, 1, n)_for(j, 1, n)scanf("%d", &s[i - j + n][i + j - 1]);k = 2 * k - 1;n = 2 * n - 1; _for(i, 1, n)_for(j, 1, n)s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];int ans = 0;_for(i, 1, n)_for(j, 1, n){if(i + k - 1 > n || j + k - 1 > n) continue;ans = max(ans, cal(i + k - 1, j + k - 1, i, j));}printf("%d\n", ans);return 0;
}CodeForces - 930A（思维）
这道题没做出来
但是一想通了却非常简单
我一直按照题目的思路，一秒一秒来思考问题，就发现很难模拟这个过程，肯定超时
这题的关键在于，同一时间落在一起的苹果，后面苹果的去向是一样的
所以在1消掉苹果和在过程中消掉的苹果的个数是一样的
所以可以直接在1一起消掉苹果
那就要求每个时间内落到1的苹果个数，跳同样次数到1的苹果会消掉
其实我有想到建图，但是画的时候点排成了一排，没有把其画成树的形状。建图的时候要把其画成树的形状
要专题和杂题相结合，刷杂题可以刷div1，AB，C尽量。可以每周至少给自己安排一套杂题，比如周末。算是对其他知识点的巩固
最近在选拔赛，所以可以多做一些杂题，专题放一放。其实都是一样的，反正就是做题提升嘛
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e5 + 10;
int d[N], n;
vector<int> g[N];void dfs(int u, int depth)
{d[depth]++;for(auto v: g[u])dfs(v, depth + 1);
}int main()
{scanf("%d", &n);_for(i, 2, n){int x; scanf("%d", &x);g[x].push_back(i);}dfs(1, 1);int ans = 0;_for(i, 1, n)ans += d[i] % 2;printf("%d\n", ans);return 0;
}周三 3.10 （杂题）
A. k-Amazing Numbers（逆向思维）
这道题挺不错的
我一开始一直卡住，因为一直在想k越来越多时会怎么变化
其实应该逆向思维
就是看某一个值要覆盖所有片段，k的最小值是多少
不要想片段来覆盖数，想数来覆盖片段
所以做题卡住时告诉自己反过来想
所以答案就是最左端需要的长度，最右端需要的长度，中间需要的长度取最大值就好了
其中中间需要的长度，点与点之间都是取最大值
然后有个加1减1的可以总结一下
一个片段，一端i，一端j
求长度，也就是包含i，j，那长度是i - j + 1
一个端点不包含就是i - j
所以一个点加上x，那么就是跳x个点，不包括本身
加x-1就是跳x个点，包括本身
看了题解，看到了一个输出的骚操作
如果特地要求行末没有空格这样写很方便
这道题还是学到挺多的
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 3e5 + 10;
int fi[N], pre[N], ans[N], t[N], n;int main()
{int T; scanf("%d", &T);while(T--){memset(fi, 0, sizeof(fi)); memset(ans, 0, sizeof(ans));scanf("%d", &n);_for(i, 1, n) {int x; scanf("%d", &x);if(!fi[x]) fi[x] = i;else ans[x] = max(ans[x], i - pre[x]);pre[x] = i;}_for(i, 1, n) if(fi[i])ans[i] = max(ans[i], max(fi[i], n - pre[i] + 1));_for(i, 1, n) t[i] = 1e9;_for(i, 1, n) t[ans[i]] = min(t[ans[i]], i);int now = -1;_for(k, 1, n){if(t[k] != 1e9) {if(now == -1) now = t[k];else now = min(now, t[k]);}printf("%d%c", now, " \n"[k == n]);}}return 0;
}CF702C Cellular Network（思维）
不知道为什么是蓝题……挺水的
第一反应二分答案，结果超时了，算了一下复杂度没问题啊
然后就换了个思路，其实很简单，就是每一个a都算一下和它相邻的两个b就好了
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e5 + 10;
int a[N], b[N], Next[N << 1], n, m, cnt;
struct node
{int v, id;
}c[N << 1];bool cmp(node x, node y)
{return x.v < y.v;
}int main()
{scanf("%d%d", &n, &m);_for(i, 1, n) {scanf("%d", &a[i]);c[++cnt] = node{a[i], 1};}_for(i, 1, m) {scanf("%d", &b[i]);c[++cnt] = node{b[i], 2};}sort(c + 1, c + cnt + 1, cmp);int p = 0;_for(i, 1, cnt)if(c[i].id == 2){Next[p] = i;p = i;}int ans = 0; p = 0;_for(i, 1, cnt){if(c[i].id == 1){if(p == 0) ans = max(ans, c[Next[p]].v - c[i].v);else if(Next[p] == 0) ans = max(ans, c[i].v - c[p].v);else ans = max(ans, min(c[i].v - c[p].v, c[Next[p]].v - c[i].v));}else p = i;}printf("%d\n", ans);return 0;
}周四 3.11（杂题）
CF915E Physical Education Lessons（线段树+离散化）
做完看了洛谷题解，貌似和他们的解法都不太一样
本来以为线段树改改就好，然后看到n可以到10的9次方
那么显然就要离散化一些了，我把一个区间离散化成三个点，两个端点值为1，区间值为区间长度
然后线段树就好了
线段树除了维护本来的值，还要多维护一个val
表示真正的值，操作的时候val就改变
然后区间修改打懒标记我有点遗忘了，一开始写竟然忘记了
区间修改要写个lazy函数
离散化要两次sort，去重前要sort
这道题最慢的点0.9s，太惊险了
#include<bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 3e5 + 10;
struct node
{int l, r, w, f, val;int m() { return (l + r) >> 1; }
}t[N << 4];
int ll[N], rr[N], k[N], lsh[N << 1];
int v[N << 2], cnt, m, n, q;
unordered_map<int, int> id;void init()
{_for(i, 1, q) lsh[i] = ll[i];_for(i, 1, q) lsh[q + i] = rr[i];lsh[2 * q + 1] = 1; lsh[2 * q + 2] = n; sort(lsh + 1, lsh + 2 * q + 3); //去重前先sort m = unique(lsh + 1, lsh + 2 * q + 3) - (lsh + 1);sort(lsh + 1, lsh + m + 1);
}void up(int k)
{t[k].w = t[l(k)].w + t[r(k)].w;t[k].val = t[l(k)].val + t[r(k)].val;
}void lazy(int k, int op) //区间修改需要懒标记，回忆
{t[k].f = op;if(t[k].f) t[k].val = t[k].w;else t[k].val = 0;
}void down(int k)
{lazy(l(k), t[k].f);lazy(r(k), t[k].f);t[k].f = -1;
}void build(int k, int l, int r)
{t[k].l = l; t[k].r = r; t[k].f = -1;if(t[k].l == t[k].r){t[k].val = t[k].w = v[++cnt];return;}int m = t[k].m();build(l(k), l, m);build(r(k), m + 1, r);up(k);
}void change(int k, int L, int R, int op)
{if(L <= t[k].l && t[k].r <= R){lazy(k, op);return;}if(t[k].f != -1) down(k);int m = t[k].m();if(L <= m) change(l(k), L, R, op);if(R > m) change(r(k), L, R, op);up(k);
}int main()
{scanf("%d%d", &n, &q);_for(i, 1, q) scanf("%d%d%d", &ll[i], &rr[i], &k[i]);init();cnt = 0;_for(i, 1, m){if(i > 1 && lsh[i] - lsh[i - 1] - 1 > 0) v[++cnt] = lsh[i] - lsh[i - 1] - 1;v[++cnt] = 1;id[lsh[i]] = cnt;}n = cnt; cnt = 0;build(1, 1, n);_for(i, 1, q){change(1, id[ll[i]], id[rr[i]], k[i] - 1);printf("%d\n", t[1].val);}return 0;
}CF915E Physical Education Lessons（线段树+动态开点）
看到题解发现还可以动态开点，知识盲区，就去学习了一下
当区间端点很大的时候，开这么大空间肯定炸，这时有两种方法，动态开点和离散化
离散化是离线的，写起来比动态开点多一些
动态开点可以是在线的，代码会少一些
动态开点的作用就是省空间
原本的线段树是左端点乘2，右端点乘2加1，动态开点不这样，用数组存左右儿子，用到了就给一个编号
在区间修改和懒标记下传的时候也会动态开点。up的时候左右儿子一定是已经开过的了
动态开点记得要引用
理论上空间复杂度和时间复杂度都是qlogN
我以前都是用结构体写线段树，写得都挺长
这次用数组写线段树，代码少了许多，挺好。不过函数中的参数要一直写l和r
以后就用数组写了
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1.5e7+ 10; //qlogN 但不知道为什么这题要开更大一些，可能数据不对
int t[N], f[N], ls[N], rs[N]; // 用数组写代码少一些，但就是参数一直要写l， r
int cnt, n, q;void up(int k) { t[k] = t[ls[k]] + t[rs[k]]; } //一定左右儿子都开过点了 void lazy(int& k, int l, int r, int op) //下传懒标记也会开点。开点都要引用
{if(!k) k = ++cnt;t[k] = (r - l + 1) * op;f[k] = op;
}void down(int k, int l, int r)
{int m = (l + r) >> 1;lazy(ls[k], l, m, f[k]);lazy(rs[k], m + 1, r, f[k]);f[k] = -1;
}void change(int& k, int l, int r, int L, int R, int op)
{if(!k) k = ++cnt;if(L <= l && r <= R){lazy(k, l, r, op);return;}if(f[k] != -1) down(k, l, r);int m = (l + r) >> 1;if(L <= m) change(ls[k], l, m, L, R, op);if(R > m) change(rs[k], m + 1, r, L, R, op);up(k);
}int main()
{scanf("%d%d", &n, &q);memset(f, -1, sizeof(f)); //初始化为-1 int root = 0; //要写个root，因为要引用 change(root, 1, n, 1, n, 1);_for(i, 1, q) {int l, r, k;scanf("%d%d%d", &l, &r, &k);if(k == 2) change(root, 1, n, l, r, 1);else change(root, 1, n, l, r, 0);printf("%d\n", t[root]);}return 0;
}P3372 【模板】线段树 1 (数组写法 + 标记结合)
我用数组写了一下这道题
其实差不多吧，数组的话就一直要写l,r,m
然后注意标记直接会结合。这里加法我直接写=了应该写+=
所以要考虑到旧标记。上一道题是直接覆盖了，就不用考虑。这道题新标记与旧标记有关系
在lazy函数那里体现
#include<bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e5 + 10;
ll t[N << 2], f[N << 2];
int n, m;void up(int k) { t[k] = t[l(k)] + t[r(k)]; }void lazy(int k, int l, int r, ll p)
{t[k] += (r - l + 1) * p;f[k] += p;
}void down(int k, int l, int r)
{int m = (l + r) >> 1;lazy(l(k), l, m, f[k]);lazy(r(k), m + 1, r, f[k]);f[k] = 0;
}void build(int k, int l, int r)
{if(l == r){scanf("%lld", &t[k]);return;}int m = (l + r) >> 1;build(l(k), l, m);build(r(k), m + 1, r);up(k);
}void change(int k, int l, int r, int L, int R, ll p)
{if(L <= l && r <= R){lazy(k, l, r, p);return;}if(f[k]) down(k, l, r);int m = (l + r) >> 1;if(L <= m) change(l(k), l, m, L, R, p);if(R > m) change(r(k), m + 1, r, L, R, p);up(k);
}ll sum(int k, int l, int r, int L, int R)
{if(L <= l && r <= R) return t[k];if(f[k]) down(k, l, r);ll res = 0; int m = (l + r) >> 1;if(L <= m) res += sum(l(k), l, m, L, R);if(R > m) res += sum(r(k), m + 1, r, L, R);return res;
}int main()
{scanf("%d%d", &n, &m);build(1, 1, n);while(m--){int op, l, r; ll k;scanf("%d%d%d", &op, &l, &r);if(op == 1){scanf("%lld", &k);change(1, 1, n, l, r, k);}else printf("%lld\n", sum(1, 1, n, l, r));}return 0;
}周五六日 打了两场比赛以及社团轰趴。算是休息一下