CF1995C Squaring 题解
CF1995C Squaring 题解 题目链接:Squaring 题意: 多组数据,给定长度为 \(n\) 的序列 \(a\) 每次可以让一个 \(a_i \gets a_i^2\) ,其中 \(1 \le i \le n\) 。 求使得序列 \(a\) 单调不降的最小操作数。 数据范围: \(1 \le \sum n \le 2\times 10^5,~1 \le a_i \le 10^6\) 。 显然我们不能直接计算出操作后的数有多大 但是可以发现,如果 \(a_i < a_{i+1}\) ,后者的操作数肯定是不超过前者的 因此我们可以计算每个位置相对于前者的增量,然后求一遍前缀和就可以了 时间复杂度 \(\mathcal{O}(n)\) 代码: #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f void up(int &x, int y) { x < y ? x = y : 0; ...
洛谷P10800 「CZOI-R1」卡牌 题解
洛谷P10800 「CZOI-R1」卡牌 题解 题目链接:P10800 「CZOI-R1」卡牌 题目描述: Alice 和 Bob 正在玩卡牌游戏。 每张卡牌有四个属性:攻击、防御、速度、血量。 我们称一张卡牌能胜过另一张卡牌,当且仅当其至少有三个属性都大于另一张卡牌。 Bob 拥有 \(m\) 张卡牌,而 Alice 拥有每个属性值在 \([1, n]\) 的所有 \(n^4\) 张卡牌。 现在 Alice 想知道:她有多少张卡牌可以胜过所有 Bob 的卡牌? 输入格式: 第一行包含两个整数 \(n, m\),分别表示属性值上限和 Bob 的卡牌数量。 接下来 \(m\) 行,每行四个整数 \(a_i, b_i, c_i, d_i\),表示 Bob 一张卡牌的属性。 输出格式: 输出一行一个整数,表示答案对 \(2^{32}\) 取模后的结果。 数据范围: 对于所有测试数据,\(1 \le n, m \le 5 \times 10^5\),\(1 \le a_i, b_i, c_i, d_i \le n\)。 因为参考文献1写的非常清楚,并不需要补充过多废话,所以本文大部分...
CF815D Karen and Cards 题解
CF815D Karen and Cards 题解 题目链接:Karen and Cards 题意: 有 \(n\) 张卡牌,每张卡牌都有三个属性,第 \(i\) 张卡牌的三个属性记作 \(a_i,b_i,c_i\)。卡牌 \(x\) 可以打败卡牌 \(y\) 当且仅当 \(x\) 至少有两个属性值比 \(y\) 对应的属性值大。如卡牌 \((1,2,3)\) 可以打败卡牌 \((3,1,2)\),因为 \(2>1,3>2\)。 现在请你判断满足 \(a\leq A,b\leq B, c\leq C\) 的卡牌中,可以打败给定的所有 \(n\) 张卡牌的有多少张。 数据范围: \(1 \le n,A,B,C \le 5\times 10^5\) 。 九条可怜镇楼 这里讲讲 \(\mathcal{O}(n \log n)\) 的更好想的解法。(其实是我的思路和这个解法比较接近) 方便起见,记当前考察的三元组为 \((x,y,z)\) 。 首先考虑所有的 \(c_i\) 相等时(设为 \(c\) )怎么做。正难则反,考虑计算不可行解的数量。 分类讨论一下 \(z\)...
CF1406E Deleting Numbers 题解
CF1406E Deleting Numbers 题解 题目链接:Deleting Numbers 题意: 这是一道交互题。 已知 \(n\), 有一个未知数 \(x\) \((1\le x\le n)\),你需要求出 \(x\) 的值。 一开始,你有一个集合 \(S=\{x\mid x\le n,x\in \mathbb{N^+}\}\) 你可以对这个集合执行不超过 \(10000\) 次 A、B、C 操作(总和不超过)。 A \(a\),表示求出 \(S\) 中 \(a\) 的倍数的个数 \((1\le a\le n)\) B \(a\),表示求出 \(S\) 中 \(a\) 的倍数的个数, 并将这些 \(a\) 的倍数从 \(S\) 中删去(\(x\) 是不会被删掉的) \((2\le a\le n)\) C \(a\),表示你知道了 \(x=a\) \((1\le a\le n)\) 所有的 \(a\) 均为整数。数据范围 \(1 \le n \le 10^5\) 。 由于本题和整除有关,所以很容易想到特殊考虑质因子。 假设我们知道 \(x\) 的所有质因子,那么...
AT_agc058_f [AGC058F] Authentic Tree DP 题解
AT_agc058_f [AGC058F] Authentic Tree DP 题解 题目链接:AT_agc058_f [AGC058F] Authentic Tree DP 题意: 对于一棵 \(n\) 个节点的无根树 \(T\),我们按如下方式定义函数 \(f(T)\) : 若 \(n=1\) ,定义 \(f(T) = 1\)。 若 \(n>1\) ,定义 \[ f(T) = \frac{\sum_{e\in T} f(T_1(e)) \times f(T_2(e))}{n} \] 其中 \(e\) 是 \(T\) 中的一条边,\(T_1(e),T_2(e)\) 表示 \(T\) 切断 \(e\) 后分裂成的两棵新的树。 现在给定一棵 \(n~(2\le n\le 5000)\) 个节点的树 \(T\),编号从 \(1\) 到 \(n\) 。 请输出 \(f(T) \bmod 998244353\) 的值。 非常喵喵的思维+dp题。 注意到这个奇怪的定义式,如果把 \(\frac{1}{n}\) 改成 \(\frac{1}{n-1}\) ,那么它的组合意义是: ...
洛谷P2569 [SCOI2010] 股票交易 题解
洛谷P2569 [SCOI2010] 股票交易 题解 题目链接:P2569 [SCOI2010] 股票交易 题意: 最近 \(\text{lxhgww}\) 又迷上了投资股票,通过一段时间的观察和学习,他总结出了股票行情的一些规律。 通过一段时间的观察,\(\text{lxhgww}\) 预测到了未来 \(T\) 天内某只股票的走势,第 \(i\) 天的股票买入价为每股 \(AP_i\),第 \(i\) 天的股票卖出价为每股 \(BP_i\)(数据保证对于每个 \(i\),都有 \(AP_i \geq BP_i\)),但是每天不能无限制地交易,于是股票交易所规定第 \(i\) 天的一次买入至多只能购买 \(AS_i\) 股,一次卖出至多只能卖出 \(BS_i\) 股。 另外,股票交易所还制定了两个规定。为了避免大家疯狂交易,股票交易所规定在两次交易(某一天的买入或者卖出均算是一次交易)之间,至少要间隔 \(W\) 天,也就是说如果在第 \(i\) 天发生了交易,那么从第 \(i+1\) 天到第 \(i+W\) 天,均不能发生交易。同时,为了避免垄断,股票交易所还规定在任何时间,...
CF1808E3 Minibuses on Venus (hard version) 题解
CF1808E3 Minibuses on Venus (hard version) 题解 题目链接:Minibuses on Venus (hard version) 题意: 给定 \(n,k,m\) ,定义序列 \(\{a_i\}_{i=1}^n\) 的值域为 \([0,k)\) ,即 \(\forall i, ~a_i \in[0,k)\) 。 称一个序列 \(a\) 是幸运的,当且仅当存在至少一个 \(p~(1\le p \le n)\) 使得 \[ \sum_{i=1}^na_i - a_p\equiv a_p \pmod{k} \] 求幸运序列的总方案数模 \(m\) 的结果。 输入格式: 一行,三个整数 \(n,k,m\) 。 输出格式: 一行,即答案。 数据范围: \(1 \le n \le 10^{18},~1\le k \le 2000,~10^8 \le m \le 10^9\) 。 记 \(s = \sum_{i=1}^n a_i\) ,考虑问题的反面,即 \(s \not\equiv 2a_i \pmod{k}\) 的序列 考虑枚举 \(s \in ...
同余的基本性质
同余的基本性质 一、定义 设整数 \(m \ne 0\) 。若 \(m \mid (a - b)\) ,则称 \(m\) 为模数(模), \(a\) 同余于 \(b\) 模 \(m\) ,\(b\) 是 \(a\) 对模 \(m\) 的剩余,记作 \(a \equiv b \pmod{m}\) 。 否则 \(a\) 不同余 \(b\) 模 \(m\) ,\(b\) 不是 \(a\) 对模 \(m\) 的剩余,记作 \(a \not\equiv b \pmod{m}\) 。 这样的等式称为模 \(m\) 的同余式,简称同余式。 根据整除的性质,上述同余式也等价于 \(a \equiv b \pmod{(-m)}\) 故未特别注明的情况,默认模数为正整数。 二、性质 同余是等价关系,即同余具有 自反性:\(a\equiv a\pmod m\) 对称性:若 \(a\equiv b\pmod m\),则 \(b\equiv a\pmod m\) 传递性:若 \(a\equiv b\pmod m,b\equiv c\pmod m\),则 \(a\equiv c\pmod m\) ...
【生物】纺锤丝和星射线的区别
【生物】纺锤丝和星射线的区别 纺锤体在动物细胞和高等植物细胞中有差异。 动物细胞的纺锤体两端有星状体,每个星状体的中间有中心体,称为有星纺锤体。 高等植物细胞的纺锤体两端没有星状体,呈桶状,称为无星纺锤体。 组成纺锤体的丝状结构称为纺锤丝。 纺锤丝共四种,即连续丝、牵引丝、中间丝和星体丝(即星射线)。 连续丝是由一极与另一极相连的纺锤丝。 牵引丝又称染色体丝,是着丝点与一极相连的纺锤丝。 中间丝不与两极相连,也不与着丝点相连,是在后期于两组染色体之间出现的纺锤丝 星体丝又称星射线,由两极的中心体射出,它只存在于有星纺锤体的细胞内。 各种纺锤丝都由微管蛋白组成。 动/植物细胞共有的纺锤丝是染色体丝和连续丝,动物细胞特有的是中间丝和星射线。 题外话: 因为找不到翻译所以直接翻译了维基百科的图。
洛谷P4721 【模板】分治 FFT 题解
洛谷P4721 【模板】分治 FFT 题解 题目链接:P4721 【模板】分治 FFT 题意: 给定序列 \(g_{1\dots n - 1}\),求序列 \(f_{0\dots n - 1}\)。 其中 \[ f_i=\sum_{j=1}^if_{i-j}g_j \] 边界为 \(f_0=1\)。 答案对 \(998244353\) 取模。 输入格式: 第一行一个整数 \(n\) 。 第二行 \(n-1\) 个整数 \(g_{1\dots n - 1}\)。 输出格式: 一行 \(n\) 个整数,表示 \(f_{0\dots n - 1}\) 对 \(998244353\) 取模后的值。 数据范围: \(2\leq n\leq 10^5\),\(0\leq g_i<998244353\)。 本题可以通过多项式求逆解决,不过这就体现不出「分治 FFT 模板题」的意义了。 分治 FFT/分治NTT 主要利用的是 CDQ 分治的思想。 先求出 \([l,\,\mathrm{mid}-1)\) 的答案(即 \(f\) ),可以发现这部分对于 \([\mathrm{mid},r...
洛谷P5787 【模板】线段树分治 题解
洛谷P5787 【模板】线段树分治 题解 题目链接:P5787 二分图 /【模板】线段树分治 题意: qry 有一个 \(n\) 个节点的图。 因为 qry 是 qry,所以在 \(k\) 时间内有 \(m\) 条边会出现后消失。 qry 要求出每一时间段内这个图是否是二分图。 这么简单的问题 qry 当然会做了,于是她想考考你。 输入格式: 第一行三个整数 \(n,m,k\)。 接下来 \(m\) 行,每行四个整数 \(x,y,l,r\),表示有一条连接 \(x,y\) 的边在 \(l\) 时刻出现 \(r\) 时刻消失。 输出格式: 共 \(k\) 行,第 \(i\) 行一个字符串 Yes 或 No,表示在第 \(i\) 时间段内这个图是否是二分图。 数据范围: \(1\le n,k \le 10^5,~1 \le m \le 2\times 10^5,~1 \le x,y \le n,~0 \le l \le r \le k\)。 本题是线段树分治的模板题。 线段树分治其实非常简单。考虑对时间轴建立线段树,每个节点维护这段区间存在的边集。 因为如果区间 \([l,r]\...
洛谷P5495 【模板】Dirichlet 前缀和 题解
洛谷P5495 【模板】Dirichlet 前缀和 题解 题目链接:P5495 【模板】Dirichlet 前缀和 题意: 给定一个长度为 \(n\) 的数列 \(a_1,a_2,a_3,\dots,a_n\)。 现在你要求出一个长度为 \(n\) 的数列 \(b_1,b_2,b_3,\dots,b_n\),满足 \[ b_k=\sum_{i\mid k}a_i \] 由于某些神秘原因,这里的 \(b_k\) 要对 \(2^{32}\) 取模。 输入格式: 为了避免过大的输入,本题的输入使用随机数生成器。 输入中只有一行两个整数 \(n,\mathrm{seed}\)。其中 \(\mathrm{seed}\) 为 \(32\) 位无符号整数,用来生成数据。 接下来,你要调用 \(n\) 次随机数生成器,分别生成 \(a_1\sim a_n\)。随机生成器见原题链接。 输出格式: 为了避免过大的输出,你只需输出一个 \(32\) 位无符号整数,表示所有 \(b_i\) 的异或和。 数据范围: \(1\leq n\leq 2\times 10^7\),\(0\leq \mathrm...




![AT_agc058_f [AGC058F] Authentic Tree DP 题解](/qwq/img/p159.webp)
![洛谷P2569 [SCOI2010] 股票交易 题解](/qwq/img/p187.webp)







![洛谷B3869 [GESP202309 四级] 进制转换 题解](/qwq/img/p184.webp)

![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p214.webp)
![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p230.webp)