题解atcoder agc 004

> 咕咕咕，总力战还没打，凹不过卷狗，躺了.jpg ## [A - Full Moon (abc318 A)](https://atcoder.jp/contests/abc318/tasks/abc318_a) ### 题目大意 给定$n, m, p$，问有多少个 $i$满足 $0 神奇的代码 ` ......

[题目传送门](https://www.luogu.com.cn/problem/AT_dp_j) 一道 dp 题。 发现以前课上讲的题能水题解。 在 `dp` 之前，我们需要明确以下几个东西： **状态的表示**，**状态转移方程**，**边界条件**跟**答案的表示**。 ### 状态的表示 $ ......

[题目传送门](https://www.luogu.com.cn/problem/B3608) 一道网络流题。 费用流板子题。费用流实际上是在给最大流套个最短路，而费用流一般边权会有负数，所以用 SPFA 算法，~~关于 SPFA，它复活了~~。 可以在最大流做 bfs 的时候将 SPFA 套上去。 ......

## A - Full Moon ### Problem Statement Takahashi likes full moons. Let today be day $1$. The first day on or after today on which he can see a full mo ......

我直接从第三题开始讲了。 [T3](https://atcoder.jp/contests/abc318/tasks/abc318_c) 把数组 $A$ 从大到小排序。 然后从前往后把前 $q$ 个数加起来，然后判断这 $q$ 个数的和与 $d$ 的大小关系，如果大了就变成 $d$。 然后有些细节就 ......

咕咕咕的东西总是要补的。 ## A.报数 ### 题目描述： 报数游戏是一个广为流传的休闲小游戏。参加游戏的每个人要按一定顺序轮流报数，但如果下一个报的数是 $7$ 的倍数，或十进制表示中含有数字 $7$，就必须跳过这个数，否则就输掉了游戏。 在一个风和日丽的下午，刚刚结束 SPC20nn 比赛的小 ......

[Link](https://www.luogu.com.cn/problem/P7706) 一道很有意思的线段树题。 **第一步分析**，我们要求最大的 $a_i+a_k-\min{(b_j)}$，事实上我们可以直接省去这个 $\min$ 因为要最大化这个东西，选出来的 $b_j$ 必然是最小的， ......

每次打都想感叹一句，Educational 名不虚传。 ## A.Not a Substring ### 题目描述： 有 $t$ 组数据，对于每一组数据，你需要判断能否构造一个只由左右括号组成且长度为已经给定字符串的 $2$ 倍且已经给定的字符串不是子串的合法字符串。注：合法的字符串是左右括号能完全 ......

写了 $358$ 行，$11.94 \mathrm{KB}$，有这么几个地方写挂了： - 反猪决斗一定选主猪。 - 游戏结束判定是主猪死亡或全部反猪死亡。 - 决斗可能被反杀，之后不能再出牌。 点击查看代码 ```cpp #include using namespace std; int n,m; ......

# CF1863B Split Sort 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1863B) [Codeforces](https://codeforces.com/problemset/problem/1863/B) ## Desc ......

# CF1863C MEX Repetition 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1863C) [Codeforces](https://codeforces.com/problemset/problem/1863/C) ## ......

# P1463 [POI2001] [HAOI2007] 反素数 题解 可以发现，最大的不超过 $n$ 的反素数就是 $1\sim n$ 中因数最多的数字。 > 证明： > > 设 $x, x\in[1, n]$ 为 $1\sim n$ 中因数最多的数字，则 $x #define x first # ......

# CF1863D Two-Colored Dominoes 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1863D) [Codeforces](https://codeforces.com/problemset/problem/1863/ ......

之前整理的时候忘记写，现在补上。 # 思路 拉插求自然数幂和。 关于自然数幂和 $\sum\limits_{i = 1}^n i^k$，已知是关于 $n$ 的 $k + 1$ 次多项式，可以用伯努利数 $O(k \log k)$ 求，也可以直接拉插 $O(k)$ 求。 拉插结论：若一个 $n$ 次多 ......

[题目链接](https://www.luogu.com.cn/problem/AT_agc004_d) 躺在床上想到重要性质的题目。。。 首先，由于每个城市只有一个可以直接到达的城市，所以 $n$ 个城市就有 $n$ 条边，容易发现这是一棵基环树，那么我们先从普通树的角度考虑，若要求每个点走 $k ......

## 题意 有一棵有 $n$ 个节点的树，第 $i$ 个节点有点权 $a_i$。 定义 $g(x,y)$ 为 $x$ 到 $y$ 的树上路径所经过的点的点权 $\gcd$。 对于每一个正整数 $k\in[1,2\times 10^5]$ 求出满足以下条件的 $x,y$ 的对数: + $1\le x\ ......

## 题意 给定 $n, k$，对于所有的 $m \in \left[1, k\right]$，求长度为 $n$，值域为 $\left[1,m \right]$ 且最大公约数为 $1$ 的序列种数，对 $10^9 + 7$ 取模。 （$1 \le n,k \le 2 \times 10^6$）。 # ......

[题目传送门](https://www.luogu.com.cn/problem/P7735) 一眼数据结构 考虑树上有什么数据结构支持 $x$ 到 $y$ 节点的修改和查询，那就是：树链剖分。 那么这道树链剖分的题有个 $trick$：**边点转换&染色法，对于每次修改，考虑将修改路径上的点全部染 ......

**不要相信这篇题解的任何一个字，包括标题和这句话。** 省流-恶搞题目：A，B，C，M，Q。 [题目](https://vjudge.net/contest/578685) # [A](https://vjudge.net/contest/578685#problem/A) ## 思路 这道题实在 ......

# E - Xor Distances [原题链接](https://atcoder.jp/contests/abc201/tasks/abc201_e) 题意：设dist(i,j)即i到j之间路径的异或和，求树上所有两点之间dist（i，j)的和 思路：dist(i,j) = dist(i,1)^ ......

# D - Game in Momotetsu World [原题链接](https://atcoder.jp/contests/abc201/tasks/abc201_d) 题意 有一个 H×W 的方格，每个方格里写着 '+' 或 '-' 有一个初始在 (1,1),（也就是左上角)的棋子， Tak ......

# D - President [原题链接](https://atcoder.jp/contests/abc317/tasks/abc317_d) 题意：一共n轮，每一轮Xi > Yi （票数）时，X可以获得Zi 张席位，反之亦然；最终席位总和多的就获胜；因此要使X获胜，求Y至少要给X多少个票 思路 ......

# P1450 [HAOI2008] 硬币购物 题解 首先考虑只有一种硬币的情况。 如果取的数量没有限制，就是一个完全背包，$f_i$ 表示背包体积为 $i$ 的选择方案数，显然 $f_j = f_{j - v}$。 如果取的数量有限制，用多重背包做一遍会超时，考虑以下思路：所有方案数 - 不合法方 ......

原：[CF652F. Ants on a Circle](https://codeforces.com/problemset/problem/652/F) 太摆了！不能摆了！不会写题！来写博客！ 首先套路的，蚂蚁相遇时我们可以看作他们的编号交换后继续往前走，可以求出最后的所有位置。同时，显然最早和最 ......

[题目链接](https://www.luogu.com.cn/problem/P2431) 由于每个质量的月饼只有一个，并且质量恰好是2的整数倍，所以考虑将一个质量看成一个二进制位。 那么也就是说，我们要构造一个二进制数 $x$，使得 $x$ 的 $1$ 的个数最多，且满足 $a\le x \le ......

## Description 有一天 Masha 回到家，发现有 $n$ 只老鼠在它公寓的走廊上，她大声呼叫，所以老鼠们都跑进了走廊的洞中。 这个走廊可以用一个数轴来表示，上面有 $n$ 只老鼠和 $m$ 个老鼠洞。第 $i$ 只老鼠有一个坐标 $x_i$ ，第 $j$ 个洞有一个坐标 $y_j$ ......

[原题链接](https://ac.nowcoder.com/acm/contest/64384/C) 先不考虑车子的容量问题，因为结束位置保证是在起始位置之后的，那我们从前往后扫，发现是可以知道每个点时的车内的商品。 但是现在有了容量限制，我们怎么办呢，如果对于一段，k 都是大于每个点的货物量时， ......

## 题意 给定长度为 $n$ 的数组 $a$ 和一个整数 $k$ ，执行下面的代码： ```cpp long long ans = 0; //定义一个初始值为0的长整型变量 for(int i = 1; i typedef long long valueType; typedef std::vec ......

[Maximum Diameter](https://www.luogu.com.cn/problem/AT_abc290_f) ### 题目大意 定义长度为 $n$ 的序列 $a$ 的权值为： - 所有的 $n$ 个点的第 $i$ 个点的度数为 $a_i$ 的树的直径最大值，如果不存在这样的树，其 ......

## D.Matrix Cascade ### 题目描述： 有一个大小为$n \times n$的矩阵，由 0 和 1 组成。行的编号从上到下依次为$1$到$n$，列的编号从左到右依次为$1$到$n$。第$x$行与第$y$列交叉处的单元格记为$(x, y)$。 水月想把矩阵的所有元素都变成 0。她可 ......