Q779’s Blog

洛谷P2657 [SCOI2009] windy 数 题解 题目链接：P2657 [SCOI2009] windy 数 题意： 不含前导零且相邻两个数字之差至少为 \(2\) 的正整数被称为 windy 数。windy 想知道，在 \(a\) 和 \(b\) 之间，包括 \(a\) 和 \(b\) ，总共有多少个 windy 数？ 对于全部的测试点，保证 \(1 \leq a \leq b \leq 2 \times 10^9\)。 常规的数位dp，只需要记录上一位的数字即可 但是注意，最高位是不需要限制的 具体的，我们是从高位往低位做dp的 至于为什么高位往低位做dp，可以看下面的解释 因为低位开始会导致无法判断是否超过了当前的限制 例如 \(4234\) ，假设我们从高位开始做 如果以 \(4\) 开始，可以发现接下来一位不能超过 \(3\) 如果用 \(0 \sim 3\) ，则接下来没有任何限制 但是如果我们从低位开始做，比如填了一个 \(8\) 那么最后我们有可能推出来个 \(4238\) 之类的 因为无法判断 回到刚刚的问题，我们从高位往低位做数位dp 那么第...

洛谷P1410 子序列 题解 题目链接：P1410 子序列 题意： 给定一个长度为 \(N\)（\(N\) 为偶数）的序列，问能否将其划分为两个长度为 \(N / 2\) 的严格递增子序列。 【数据范围】 共三组数据，每组数据行数<=50，0 <= 输入的所有数 <= 10^9 第一组(30%)：N <= 20 第二组(30%)：N <= 100 第三组(40%)：N <= 2000 首先可以有个原始的思路 设 \(f_{i,j,k}\) 表示前 \(i\) 位，以 \(i\) 结尾的上升子序列长度为 \(j\) ，另一个上升子序列以 \(k\) 结尾是否可行。 如果仅仅用是否可行去做，比较浪费。 注意到我们一定希望 \(a_k\) 尽可能小，这个很好用dp去算 考虑把 \(k\) 这一维去掉，移到 \(f\) 里让它算。 设 \(f_{i,j}\) 表示以 \(i\) 结尾的上升子序列长度为 \(j\) ，不以 \(i\) 结尾的另一条上升子序列的结尾的最小值。 如果 \(a_i < a_{i+1}\) ，那么 \(a_{i+1}\...

CF914D Bash and a Tough Math Puzzle 题解 题目链接：CF914D Bash and a Tough Math Puzzle 题意： 给定长度为 \(n\) 的序列 \(a\)。\(m\) 次操作。操作有两种： 1 l r x：若能在 \(a_l\sim a_r\) 中 至多 修改一个数，使得 \(\gcd(a_l,a_{l+1},\cdots,a_r)=x\)，输出 YES，否则输出 NO。注意：我们不需要进行实际的改动。 2 i y：将 \(a_i\) 修改为 \(y\)。 \(1\le n\le 5\times 10^5\)，\(1\le m\le 4\times 10^5\)，\(1\le a_i,x,y\le 10^9\)。 设区间内不能被 \(x\) 整除的数的个数为 \(\text{cnt}\) 若 \(\text{cnt}=0\) ，则改不改无所谓 若 \(\text{cnt}=1\) ，则直接把那个数修改为 \(x\) 即可 若 \(\text{cnt}>1\) ，则无解，输出NO 考虑用线段树维护区间 \...

CF475D CGCDSSQ 题解 题目链接：CF475D CGCDSSQ 题意： 给出一个长度为 \(n\) 的序列和 \(q\) 个询问， 每个询问输出一行，询问满足 \(\gcd\{a_l,a_{l+1},\dots,a_r\}=x\) 的 \([l,r]\) 的对数 \(1 \le n \le 10^5,~1 \le q \le 3 \times 10^5,~1 \le a_i,x_i \le 10^9\) 这题有一个很有趣的结论。 区间 \(\gcd\) 最多有 \(\mathcal{O}(n\log \omega)\) 种可能的值（记 \(\omega = \max\{a_i\}\)） 即 \(l\) 固定时，\([l,r]\) 的区间 \(\gcd\) 至多有 \(\mathcal{O}(\log \omega)\) 种取值。 证明： 假设区间 \(\gcd\) 在 \(i\) 处发生了变化，此时新的 \(\gcd\) 一定是原 \(\gcd\) 的因数 因此新的 \(\gcd\) 至少缩小了一半，则至多有 \(\mathcal{O}(\log \omega)\...

洛谷P6225 [eJOI2019] 异或橙子 题解 题目链接：P6225 [eJOI2019] 异或橙子 题意： 序列上有n个值，第i个值为Ai 一段区间[l,r]的异或和为 A(l)^..^A(r) 一段区间[l,r]的答案是把所有区间[i,j]的异或和结果异或起来(l<=i<=j<=r) 例如 区间[2,4]的答案为 A2^A3^A4^(A2^A3)^(A3^A4)^(A2^A3^A4) 现在给定m次操作： 第一种操作输入i,j,将Ai值修改为j 第二种操作输入i,j,求区间[i,j]的答案 输入第一行为n,m 第二行n个值，为A1,...An 之后m行， 每一行输入操作的类型和对应的i,j 对于每个第二类操作，输出区间答案 n,m<=2e5 其实就是单点修改+查询下面这个柿子 \[ \bigoplus_{i=l}^{r}\bigoplus_{j=i}^{r}a_j \] 考虑区间中一个数的出现次数 设 \(l \le i \le r\) ，则 \(i\) 在区间 \([l,r]\) 的异或和的异...

CF877E Danil and a Part-time Job 题解 题目链接：CF877E Danil and a Part-time Job 题意： 一棵树有n个点，根结点编号为1，每个点的权值都是1或0 m次操作： 操作1(get)：询问一个点x的子树里有多少个1 操作2(pow)：将一个点x的子树中所有节点的权值取反 对于每一个操作1，输出答案 输入格式： 第一行一个整数n 第二行共n−1个整数，第i个数xi表示xi是i+1的父亲， 第三行给出n个点的初始权值 第四行一个整数m 接下来m行输入操作的类型和对应的节点遍号 对于每个操作1，输出1的个数 n,m<=2e5 询问&修改子树，显然需要用dfs序，然后用线段树维护 取反操作其实就是把区间和变成区间长度减区间和 而两次取反操作等于啥也没干 因此下传懒标记的时候，直接加个 \(1\) 就好了 时间复杂度 \(O(m \log n)\) 代码： #include <iostream> #include <string> #include <vector> #includ...

时间戳优化树状数组的频繁清空 来自@zx2017老师的ppt Orz 适用场景： 给定 \(T\) 组数据，每组数据有 \(Q\) 个询问，询问给定 \(n\) 个数的区间和 数据范围：\(T\le 2\times 10^5,~\sum Q \le 2\times 10^5,~n\le 5\times 10^5\) 注意，这里只限制了 \(\sum Q\) ，并没有限制 \(\sum n\) 对于每组数据不能直接去清空数组，因为 \(T \times n\) 肯定爆炸 考虑维护一个时间戳now，也就是现在是第几组数据 对于是这组数据的，也就是t[i]==now的情况，直接用 如果不是这组数据的，我们要先清零，再加。 注意到 tree[i]=0,tree[i]+=v 其实等价于 tree[i]=v 由于我们只有查询到一个树上结点，才会去判断它的时间戳 因此这类题目的时间复杂度可以控制在 \(O(\sum Q \log \sum Q)\) 修改部分的代码： int tree[N],t[N],now=0; void add(int x,int v) { for(int...

洛谷P5142 区间方差 题解 题目链接：P5142 区间方差 题意： 对于一个长度为 \(n\) 的序列 \(a_1,a_2,a_3\cdots a_n\)，我们定义它的平均数 \(a\) 为: \[ a=\frac{1}{n}\sum_{i=1}^{n}a_i \] 并定义它的方差 \(d\) 为: \[ d=\frac{1}{n}\sum_{i=1}^{n}(a_i-a)^2 \] 现在给定一个长度为 \(n\) 的序列 \(a_1,a_2\cdots a_n\)。你需要支持两种操作。每种操作的格式为 c x y。 若 \(c=1\)，为修改操作，代表将 \(a_x\) 赋值为 \(y\)。 若 \(c=2\)，为查询操作，代表查询 \(a_x\) 到 \(a_y\) 的方差。 为了避免浮点数误差，请以分数取模形式输出结果（对 1000000007（\(10^9+7\)）取模）。 对于 \(100\%\) 的数据，\(1\leq n,m\leq 1\times 10^5\)，\(1\leq a_i\leq 1\times 10^9\)，\(1\leq x\leq n\)。...

OI模板-其他 快读快写 测试 T256742 快读测试 稳定版： namespace FastIO { #define gc() readchar() #define pc(a) putchar(a) #define SIZ (int)(1e6+15) char buf1[SIZ],*p1,*p2; char readchar() { if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin); return p1==p2?EOF:*p1++; } template<typename T>void read(T &k) { char ch=gc();T x=0,f=1; while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();} while(isdigit(ch)){x=(x...

OI模板-图论 最短路算法 dijkstra P4779 【模板】单源最短路径（标准版） 优先队列优化 \(O((n+m)\log m)\) #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> #include <random> #include <queue> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(1e5+15) #define M (int)(2e5+15) int n,m,pos=1,d[N],vis[N],head[N]; struct Edge{int u,v,w,next...

OI模板-字符串 字符串哈希 单哈希 给定 \(N\) 个字符串（第 \(i\) 个字符串长度为 \(M_i\)，字符串内包含数字、大小写字母，大小写敏感），请求出 \(N\) 个字符串中共有多少个不同的字符串。 P3370 【模板】字符串哈希 #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> #include <random> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(1e4+15) #define M (int)(1515) const int hash_base=31; const int has...

OI模板-数据结构 笛卡尔树 笛卡尔树满足 每个节点的编号满足二叉搜索树的性质。 节点 \(i\) 的权值为 \(p_i\)，每个节点的权值满足小根堆的性质。 构建的复杂度为 \(\mathcal{O}(n)\) // 2024年06月13日 22:24:45 #include <bits/stdc++.h> using namespace std; // #define int long long // #define INF 0x3f3f3f3f3f3f3f3f typedef long long ll; void up(int &x, int y) { x < y ? x = y : 0; } void down(int &x, int y) { x > y ? x = y : 0; } #define N ((int)(1e7 + 15)) int n, top, a[N], ls[N], rs[N], stk[N]; void build() { for(int i = 1; i...