Q779’s Blog

洛谷P1817 棋盘染色 题解 题目链接：P1817 棋盘染色 题意： 给定一个 \(N \times M\) 的网格，每个格子可以染成黑色或者白色，要求所有黑色格子连通，所有白色格子连通，并且至少有一个黑色格子贴边，至少有一个白色格子贴边。问有多少种染色方法？ 输入格式： 第一行有两个正整数 \(N, M\)。 输出格式： 只有一个正整数表示答案。 数据范围： \(1 \le N \le 7\)，\(1 \le M \le 8\)。 暴力打表即可。代码如下： #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; } void down(int &x, int y) { x > y ? x = y : 0; } #define rep(i, a, b) for(int i = (a...

洛谷P1285 队员分组 题解 题目链接：P1285 队员分组 题意： 有 \(n\) 个人从 \(1\) 至 \(n\) 编号，相互之间有一些认识关系，你的任务是把这些人分成两组，使得： 每个人都被分到其中一组。 每个组都至少有一个人。 一组中的每个人都认识其他同组成员。 在满足上述条件的基础上，要求两组成员的人数之差（绝对值）尽可能小。请构造一种可行的方案。 请注意，\(x\) 认识 \(y\) 不一定说明 \(y\) 认识 \(x\)；\(x\) 认识 \(y\) 且 \(y\) 认识 \(z\) 不一定说明 \(x\) 认识 \(z\)。即认识关系是单向且不可传递的。 输入格式： 输入的第一行是一个整数，代表总人数 \(n\)。 第 \(2\) 到第 \((n + 1)\) 行，每行有若干个互不相同的整数，以 \(0\) 结尾，第 \((i + 1)\) 行的第 \(j\) 个整数 \(a_{i, j}\)（\(0\) 除外）代表第 \(i\) 个人认识 \(a_{i, j}\)。 输出格式： 本题存在 Special Judge。 如果无解，请输出一行一个字符串 ...

SP19985 GCDEX2 - GCD Extreme (hard) 题解 题目链接：GCDEX2 - GCD Extreme (hard) 题意： 给定 \(n~(1\le n\le 235711131719)\) ，计算 \[ G(n)=\sum_{i=1}^n\sum_{j=i+1}^n\gcd(i,j) \] 答案对 \(2^{64}\) 取模。有多组询问 \((T\le10^4)\)。本题时限 20s 。 貌似写过这题的弱化版 UVA11424 GCD - Extreme (I) ，是一道 7 倍经验题。 不过之前的做法都不行了，现在我们来重新考察这个式子怎么做。 推式子，启动！ \[ \begin{aligned} \mathrm{Ans}&= \sum_{i=1}^n \sum_{j=i+1}^n \operatorname{gcd}(i, j) \\[6pt]& =\sum_{i=1}^n \sum_{j=1}^{i-1} \operatorname{gcd}(i, j) \\[6pt]& =\sum_{d=1}^n d \sum_{...

洛谷P2714 四元组统计 题解 题目链接：P2714 四元组统计 题意： 有 \(n\) 个正整数 \(a _ i\)，你要统计有多少个四元组满足 \(\gcd(a _ i, a _ j, a _ k, a _ l) = 1\)。 输入格式： 输入包含多组数据。 对于每组数据：第一行一个正整数 \(n\)，接下来一行 \(n\) 个正整数 \(a _ i\)。 输出格式： 若干行，每行对应一个输入数据，表示满足要求的四元组的个数。 数据范围： \(4 ≤ n ≤ 10000\)，\(1 ≤ a _ i≤ 10000\)，且数据组数不超过 \(100\)。 设 \(f(n)\) 表示 \(n\) 的倍数的出现次数。 初值 \(f(a_i)=k_i\) ，其中 \(k_i\) 表示 \(a_i\) 的出现次数（这里其实是等于 \(n\) 的情况）。 考虑转移，有 \[ f(n) \gets f(n) + \sum_{n \mid d} f(d) \] 这其实是以质因数及其幂次为坐标的 \(\pi(n)\) 维向量上的高维前缀和，参考 Dirichlet 前缀和。 考虑令 \[...

树状数组 Python实现 具体原理参考 浅谈树状数组 区间修改&区间查询 这里直接给出 区间修改 + 区间查询 的代码 常数超级无敌巨大。 import sys # sys.stdin = open('check.in', 'r') # sys.stdout = open('check.out', 'w') N = int(1e6 + 15) tr1 = [0] * N tr2 = [0] * N def read(): return [int(x) for x in input().split()] def lowbit(x): return x & (-x) def _add(tr, x, v): i = x while(i <= n): tr[i] += v; i += lowbit(i) def add(x, v): _add(tr1, x, v); _add(tr2, x, v * x) def _qry(tr, x): r = 0; i = x while(...

洛谷P7219 [JOISC2020] 星座 3 题解 题目链接：P7219 [JOISC2020] 星座 3 题意： JOI 君去拍照，拍了一张大小为 \(N \times N\) 的图片，第 \(i\) 列第 \(j\) 行的格子称为格子 \((i,j)\)。 图里有白色的小白船，黄色的星星（天知道为啥星星是黄色的），黑色的空格（天知道这空格是啥），第 \(i\) 列自下往上数到第 \(A_i\) 行的格子里都是小白船，另外有 \(M\) 颗星星，第 \(i\) 颗星星在格子 \((X_i,Y_i)\)，除了小白船和星星，其他格子都是空格。 现在 JOI 君定义满足下面的一个矩阵为星座： 不包含小白船 至少包含 \(2\) 颗星星 JOI 君已经看星座看了 114514 年了，他厌烦了，所以他要把图片中的一些星星涂黑变成黑色空格，涂黑第 \(i\) 颗星星会让图片增加 \(C_i\) 的不自然度。求不存在星座的最小不自然度。 输入格式 第一行一个整数 \(N\) 代表图片的大小。 第二行 \(N\) 个整数第 \(i\) 个整数 \(A_i\) 代表小白船的位置。 第三...

CF103E Buying Sets 题解 题目链接：Buying Sets 题意： 有一个大小为 \(n~(1 \le n \le 300)\) 的全集，每个元素是一个数 现在有 \(n\) 个子集，大小分别为 \(m_i\) ，题目保证任意 \(k\) 个子集的并的大小 \(\ge k\) 。 每个子集有一个可正可负的权值，你需要选出一些子集使得这些子集并的大小等于子集个数， 且所选子集的权值和最小。可以为空集。保证 \(\sum m_i \le 10^6\) 。 输入格式： 第一行 \(n\) ，接下来 \(n\) 行：每行第一个数是 \(m_i\) ，接下来 \(m_i\) 个数是集合中的数。 最后一行 \(n\) 个数，表示每个子集 输出格式 一行，即权值和的最小值。 考虑将权值取反，这样只需要求最大权值。 注意到，如果我们将集合看作一些点，\(n\) 个数看作 \(n\) 个点，将集合与其中的点连边 那么，不考虑「子集并的大小等于子集个数」这个限制的话，这就是一个经典的最大权闭合子图问题。 最大权闭合子图问题，就是给定一张有向图，每个点有点权（可能为负）。 现在...

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」卡牌 题意： 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 题解 题目链接：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 题解 题目链接：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\) 的所有质因子，那么...

[AGC058F] Authentic Tree DP 题解 题目链接：[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}\) ，那么它的组合意义是： 将一棵树随机删除一条边，再分为两棵子树分别进行...