Ptilopsis_w's little blog

Boring Queries 考虑 lcm 的求法，一个求法是将所有质因子的质数取 max 再乘起来。 因为没有修改操作，可以考虑分解质因数然后用 ST 表求区间 max。 但是数据范围中 ai≤2×105a_i \le 2 \times 10^5ai​≤2×105，很明显不能把每个质因子都用 ST 表处理，时间空间都不允许。 考虑每个数 xxx 最多有一个大于 x\sqrt{x}x​ 的质因子，所以我们可以用 ST 表处理 2×105\sqrt{2 \times 10^5}2×105​ 以内的质数，共 868686 个，不会超出空间限制。 然后就是大于根号的质因子的去重问题，其实就是变相询问区间内不同数字个数，只不过带个权而已，可以仿照 HH 的项链这道题。 具体就是求一个 ∏i=lri [lasti<l]\prod\limits_{i=l}^{r} i \, [last_i < l]i=l∏r​i[lasti​<l]，这个可以主席树解决。 #include <algorithm>#include <cmath>#include <cs ...

Ribbons on Tree 树形 DP，定义 gig_igi​ 表示 iii 个点两两配对的方案数（奇数为 000），否则方案数就是小于 iii 的奇数的积，比较好算。 然后容斥一下就可以 DP 了。 #include <iostream>#include <cstdio>#include <cstring>using namespace std;typedef long long ll;const int N = 5005;const int P = 1e9+7;namespace graph { struct edge { int to, next; }e[N*2]; int head[N], ecnt; void insert(int u, int v) { e[++ecnt] = {v, head[u]}; head[u] = ecnt; e[++ecnt] = {u, head[v]}; ...

排列 因为可以任意排列，所以我们可以想到尽量把大于 000 的数放到一起。所以我们可以先把大于 000 的全加起来，再进行一些取舍。 对于一个形如 a→b→ca \rightarrow b \rightarrow ca→b→c 的限制，也就是如果选了 a,ca,ca,c 就必须选 bbb。 如果 xb<0x_b < 0xb​<0 的话，要么就选上 bbb ，要么就不选 aaa 或不选 ccc，而我们需要一种代价最小的方案，可以想到最小割（一条链的模型）。 而这种情况只有在 xa>0,xb<0,xc>0x_a > 0, x_b < 0, x_c > 0xa​>0,xb​<0,xc​>0 时才需要取舍，所以我们可以拆点。 如果 ai>0a_i > 0ai​>0，就连两条边: S⟶xiiS \stackrel{x_i}{\longrightarrow} iS⟶xi​​i 和 i′⟶xiTi' \stackrel{x_i}{\longrightarrow} Ti′⟶xi​​T，如果 xi< ...

Or Plus Max 需要求 ior⁡j≤k,i≠ji \operatorname{or} j \le k, i \not= jiorj≤k,i=j 条件下 max⁡{Ai+Aj}\max\{A_i+A_j\}max{Ai​+Aj​}，我们可以找出 kkk 的二进制子集内的最大值和次大值。 暴力枚举子集肯定会超时，所以我们可以利用已有的子集信息进行转移，具体就是尝试抠掉 kkk 的某一个 111，从这个子集转移一下最大值和次大值。 因为抠掉 111 之后的那个子集也是用同样的方法转移过来的，所以就相当于枚举子集了。 可以看代码实现，更好理解一些。 #include <algorithm>#include <cstdio>using namespace std; const int N = 300005; int n;int a[N];int f[N], g[N], id[N]; // id记录最大值的位置int main(){ scanf("%d", &n); for(int i = 0; i < ( ...

A 传球 原题ARC124E 一个比较难的DP 首先可以发现必定有一个人没有传球，因为每个人都少传一个球的话状态不变。 然后考虑式子的实际含义，即为每个人在自己手中选一个球的方案数。 所以我们可以对着实际含义来做，每个人手上的球的来源只有原来没有传出去的球和上一个人传过来的球，所以我们可以将球的来源记录在DP状态里。 设 fi,0f_{i,0}fi,0​ 表示 第 i−1i-1i−1 个人从自己手里选球时前 i−1i-1i−1 个人的选球方案数， fi,1f_{i,1}fi,1​ 表示 第 iii 个人从传过来的球中选球时前 iii 个人的选球方案数。(将两个状态错开一个是为了方便转移) 转移就分 444 中情况: 从 fi,0f_{i,0}fi,0​ 转移到 fi+1,0f_{i+1,0}fi+1,0​ : 自己和下一个人都不选被传的球，所以剩下几个球就有几种方案，方案数 ∑i=1aii\sum\limits _{i=1}^{a_i} ii=1∑ai​​i 。 从 fi,0f_{i,0}fi,0​ 转移到 fi+1,1f_{i+1,1}fi+1,1​ : 有两个人没有计算，且 ...

低仿机器人(robo) 一个纯模拟题，没什么好说的。 有一些坑点需要注意: 不要出现 END 或 ERROR 后就退出循环，要把当前数据点的输入全读取完再跑下一个数据点。 指令中可能存在小数，判一下是否有小数点就行了。 机器人不会执行发生 ERROR 的那条指令，需要输出发出这条指令前的状态. #include <cstdio>#include <cstring>#include <iostream>#include <stack>using namespace std;struct Rhine_Lab { Rhine_Lab() { freopen("robo.in", "r", stdin); freopen("robo.out", "w", stdout); }};Rhine_Lab Ptilopsis_w;const int dx[] = { ...

trees 一个简单的数学题，只需要将树按高度排序，计算以 iii 为最大值时选取的方案数即可。 #include <bits/stdc++.h>using namespace std;struct Rhine_Lab { Rhine_Lab() { freopen("trees.in", "r", stdin); freopen("trees.out", "w", stdout); }};Rhine_Lab Ptilopsis_w;typedef long long ll;const int N = 100005;const int P = 1e9+7;int n, k;ll val[N];ll fact[N], finv[N];void prework(int n);ll qpow(ll a, ll b);ll C(ll n, ll m);int main(){ scanf("%d ...

技术有限，常数较大，但是方便（ 重载了加减乘，写了求逆元、求ln，求exp、求sqrt、求幂(普通)。 #include <vector>#include <stack>using namespace std;namespace polynomial { typedef long long ll; const int P = 998244353; const int g = 3, gi = 332748118; int lim, bit; vector<int> r; struct poly : vector<ll> { poly() {}; poly(ll a) { resize(1); (*this)[0] = (a%P+P)%P; } poly& modx(int n) { ...

并查集 这个没什么好讲的，带权和扩展域相信大家都会，这里就给一道有意思的题吧 link 这个题并查集显然不能直接做，因为修改一个节点也会影响它的儿子，我们要想办法对他儿子的影响给去掉。 于是我们可以借鉴扩展域并查集的思想，新开一倍的节点，用 i+n 来代表合并并查集时用的节点，这样我们修改 i 时，不会影响 i+n 的父亲，达到了单点修改的目的。 二分图 二分图最大匹配 貌似大家只会敲dinic的样子，我给大家讲讲匈牙利算法解决二分图匹配吧，虽然整体时间复杂度不如dinic，但在使用增量法时匈牙利算法有时间复杂度保证而dinic不太行。 算法流程 : 我们从一个未匹配的左部点开始搜索，寻找与之相连的右部点。 如果找到一个未匹配的右部点，则与之匹配，匹配数+1，结束此次增广。 如果找到一个已匹配的右部点，我们可以去搜索 与这个右部点匹配的左部点2 ，让 左部点2 换一个右部点去匹配，这样就能将这个右部点让出来，匹配数+1，结束此次增广。 如果无 2,3 情况，则这个点匹配失败， 结束此次增广。 正确性证明 : 可以看出匈牙利算法基于一个贪心思想：尽量匹配当前的左部 ...

Windows+VSCode 中使用 clangd 安装 LLVM clangd 属于 LLVM 的一部分， 如果您想要使用 clangd， 首先需要 安装LLVM。 因为是 windows 系统所以需要下载 LLVM-版本号-win32/64.exe 这个安装包（取决于您的系统是32/64位）。 安装您的 LLVM ，然后将 \LLVM\bin\ 添加到环境变量 Path 里。 安装mingw64 如果您已有 mingw64，则可跳过这一步。 可以下载编译好的mingw64压缩包。 如果你的电脑是32位windows就下载i686的版本，64位windows下载x86_64版本，后米娜的就选-posix-sjlj就行了。 将压缩包解压到一个合适的路径，然后将 \mingw64\bin\ 这个路径添加到环境变量 Path 里。 安装clangd插件 直接在VSCode的插件中搜索 clangd，第一个带着LLVM认证的就是需要的插件。 安装好之后右下角会弹出弹窗询问您是否安装 clang，但是我们已经安装过了，所以忽略它，去插件设置里配置您的 clangd 路径。 您的 clangd ...