ABC200 题解 [toc] AC代码 A - Century B - 200th ABC-200 C - Ringo's Favorite Numbers 2 D - Happy Birthday! 2 给定一个大小为 $N$ 的数组 $A$ ，找出两个长度分别为 $x,y$ 的递增序列 $B,C$ 使得： $$ \begin{aligned}…

CF720 (Div. 2) 题解 [toc] AC代码 A. Nastia and Nearly Good Numbers 给定正整数 $A,B$ ，询问能否构造一个互不相同的三元组满足：$x+y=z$ 且其中两个数只是 $A,B$ 其中之一的倍数，另一个数则同时为 $A,B$ 的倍数。 $A,B\leq 10^6$ 。 $x=A,y=(2B-1…

CF719 (Div. 3) 题解 [toc] AC代码 A. Do Not Be Distracted! B. Ordinary Numbers 定义普通数为：数位上所有数字相同的数。多组询问，询问 $N$ 以内的普通数数量。 $N\leq 10^9$ 。 这样的数字显然很少，直接暴搜出数据范围内的所有普通数，每个询问二分查找即可。 C. Not…

HHKB2020 [toc] AC代码 A - Keyboard B - Futon C - Neq Min 给定一个数组 $P_N$ ，对于每一位 $i$ 求 $MEX(P_1,P_2,\cdots,P_N)$ 。 $N,P_i\leq 2\times 10^5$ 。 显然前缀 $MEX$ 是单调不减的，考虑到数据范围直接模拟就行。 D - Sq…

CF Global Round 14 题解 [toc] AC代码 A. Phoenix and Gold 给定 $N$ 个不同权值的物品和一个整数 $x$，物品的权值分别为 $w_i$，能否给出一种 $w_i$ 的排列使得不存在 $j$ 使得 $\sum_{i=0}^{j}w_i=x$ 。 至多 $1000$ 组询问，$n\leq 100,1\le…

CF EDU108 题解 [toc] AC代码 A. Red and Blue Beans B. The Cake Is a Lie C. Berland Regional 有 $N$ 个人分别来自学校 $U_i$ ，能力值为 $S_i$ ，要求每个学校组成几支人数恰好为 $K$ 的队伍（不满 $K$ 不能组队）去参加比赛，所有参赛选手的能力值之和…

图论模板 并查集 struct dsu { private: // number of nodes int n; // root node: -1 * component size // otherwise: parent std::vector<int> pa; public: dsu(int n_ = 0) : n(n_), pa(n_,…

FFT解决字符串匹配问题 朴素的字符串匹配 设有两个字符串 $a,b$ 长度分别为 $n,m(n\geq m)$ ，询问字符串 $b$ 在 $a$ 中出现了几次。 这是一个最基础的字符串匹配问题，显然我们容易想到 $O(nm)$ 的暴力匹配方法，同时也可以使用 $KMP$ 算法在 $O(n+m)$ 的复杂度下解决该问题。实际上，我们还可以利用 $F…

ZONe Energy Programming Contest 题解 [toc] AC代码 A - UFO Invasion B - Sign of Friendship C - MAD TEAM 有 $N$ 个人，每个人有 $A,B,C,D,E$ 五个属性，选择 $3$ 个人组成一个团队去参加比赛，这个团队的五项属性定义为每项属性中三个人的最大值…

线性代数模板 高斯消元法 /* * 高斯-约旦消元法 * 可以修改为解异或方程组 修改策略为 * a+b -> a^b * a-b -> a^b * a*b -> a&b * a/b -> a*(b==1) * */ void gauss(int n) { vector<bool> vis(n, fals…