题解atcoder agc 004
AT_arc157_a 题解
## 思路 看数据范围时能发现，这 $N$ 啥用也没有，因为 $A+B+C+D=N-1$。 首先，$B$，$D$ 为 $0$ 且 $A$，$C$ 为 $0$ 的情况是不可能有的，因为既然有 `XX` 和 `YY` 字符串，那么一定会至少组成一个 `XY` 或 `YX`，输出 `No`； 然后，$\l ......
AT_past202005_d 题解
## 思路 每 $4$ 列字符为一组，判断每一组，输出就可以了。 我有一个可能比较好的判断方法，就是先判断第三行——第一列一定是 `.`，所以我判断是都是**从第二个开始，请牢记**——有以下这 $4$ 种可能： - 为 `#.#`，这种只有一个——$0$，直接输出 $0$ 就可以了。 - 为 `. ......
[ABC267F] Exactly K Steps题解
### [ABC267F] Exactly K Steps ### 题意 有一颗 $n$ 个点，$n - 1$ 条边的树，找到任意一个离结点 $u$ 的距离恰好为 $k$ 的点，或报告无解。 定义两点 $u, v$ 间的距离为这两个点之间的最短路径所包含的边数。 ### 思路 考虑无解，显然如果从 ......
题解 BZOJ4543【[POI2014] HOT-Hotels】
长链剖分优化 DP 板子题了，但是虽然是板子这个转移方程也很难想。 ## problem 树。求 $\sum_{1\leq i 点击查看代码 Rename $height,len\to hei$，$g\to h$。 ``` #include #include #include #include us ......
AGC006F Blackout
## **AGC006F** Blackout 如果一个格子 $(x, y)$ 是黑色的，那么构建边 $x\rightarrow y$，接下来对于每个弱连通块分类讨论： 1. 图中有自环 则弱连通块必然形成一个完全图 > 证明： > > 从自环开始归纳，将自环视为一个点数为 $1$ 的完全图，接下来 ......
Codeforces 1852A Ntarsis' Set 题解
题目传送门：[Codeforces 1852A Ntarsis' Set](https://codeforces.com/contest/1852/problem/A) # 题意 给定一个集合，里面初始有 $1,2,3...10^{1000}$，告诉你每天会拿掉其中的第 $a_1, a_2, a_3 ......
CF1776M Parmigiana With Seafood 题解
先将所有的叶子取 $\max$ 贡献给答案，以下讨论的所有点中不考虑叶子。 首先可以考虑先手能否删到 $n$：不难发现当 $2 \mid n$ 的时候可以，然后我们就排除了一半的 $n$，于是以下令 $2 \not \mid n$。接下来，考虑先手能否删掉 $n-1$，那么把 $n-1 \to n$ ......
洛谷 P9221 「TAOI-1」Pentiment 题解
给定带障碍的矩阵，每次向下、左、有走一步，求从第一行出发走到最后一行方案。列出 DP 式子，用珂朵莉树与光速幂优化做到线性。 ......
题解 CF1844G【Tree Weights】
## problem 一棵树边带正整数权，给出所有 $dis(i,i+1)$，还原树的边权，或者无解。$n\leq 10^5,V\leq 10^{12}$。 ## solution 首先很容易得到 $n$ 个方程形如 $dep_1=0,dep_i+dep_{i+1}-2dep_{lca(i,i+1) ......
题解 CF1601C【Optimal Insertion】
特别鸣谢： ## problem 两个数组 $a,b$ 长度分别为 $n,m$。将 $b$ 的所有元素以任意顺序插入 $a$ 的任意位置，使最终序列逆序对数量最小，并输出这个值。$n,m\leq 10^6$。 ## solution $b$ 明显是排序成不降的最优，$a$ 原来的逆序对个数无法改变， ......
题解 P8819 星战
生日，感慨万千。 我们废话不多说看题，这道题让我们对于一张图维护四个操作 1. 删一条边。 2. 删一点的所有入边。 3. 加入一条被删除的边。 4. 加入原图中一个点的所有入边。 每次都要问你一下这个图是不是所有点的出度都是 1。 动态维护一张图是肯定不可能的，可以肯定地说，所有让你动态维护图的题 ......
AtCoder Beginner Contest 311
AtCoder Beginner Contest 311 First ABC 思路：找到第一个a，b，c都出现的位置 #include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 t ......
题解 LGP2300【合并神犇】
## Problem 随机 $n$ 个正整数组成序列。将序列分尽量多的段数，使得前一段的和不大于后一段的和。求能分成多少段。输出 $n-ans$。$n\leq 10^5$，值域不重要。 ## Solution 状态设计为：$f_i=1+\min_{sum_i-sum_j\geq g_j}f_j$ 表 ......
AtCoder Beginner Contest 311
# A - First ABC ```cpp #include using namespace std; #define int long long int32_t main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nu ......
洛谷P3629 [APIO2010] 巡逻题解
题目链接 P3629 [APIO2010] 巡逻 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路 n个村庄，n-1条道路，原图为树 1.若k=0（不修建道路）那么答案为（n-1）*2 每个道路会走两遍 2.若k为1（修建一条道路） 设修建的道路（r1）所在的环长度为L 那么答 ......
题解 P1532 【卡布列克圆舞曲】
posted on 2021-02-05 12:19:34 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/310534) 这道题有一个很坑的地方： >差不够四位数时补零。 但实际上我们并不需要补零。举个例子，$45$ 是这样变化的 ......
题解 P1008 【三连击】
posted on 2020-11-12 17:25:10 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/287646) 2023 编者注：请尊重历史。 # 本题正解是暴力枚举 先引用我们老师的一句话：(**无恶意**) >不会吧 ......
题解 P1150 【Peter的烟】
posted on 2020-11-14 10:00:20 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/288276) 2023 编者注：本篇题解的方法过于暴力，但是尊重历史。请不要太在意。 —- # 教你们用栈做这道题 [原题 ......
题解 CF1501B 【Napoleon Cake】
posted on 2021-03-16 17:42:06 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/319814) 题目可以转化一下：给一个长为 $n$ 的数组 $a$，请求出一个长为 $n$ 的数组 $b$。要求若 $a_ ......
题解 CF1501A 【Alexey and Train】
posted on 2021-03-13 21:57:02 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/319230) 简单模拟题，考验选手的读题能力~~和使用谷歌翻译的能力~~。 先定义一个 $now=0$，我们最后算出来的结 ......
题解 CF1497C1 【k-LCM (easy version)】
posted on 2021-03-20 08:26:53 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/320621) 看数据范围，$1\leq T\leq10^4$，$1\leq n\leq 10^9$，显然是构造题。 我们分 ......
题解 CF1497C2 【k-LCM (hard version)】
posted on 2021-03-20 09:09:40 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/320635) 2023 编者注：有一些链接点不进去，分别是 cf1497c1 的 cf 页面和 此题与 [CF1497C1 ......
题解 P1538 【迎春舞会之数字舞蹈】
posted on 2021-06-01 13:24:05 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/337514) 给 $0\cdots9$ 每个数字打表，打它在相应的位置有没有一划。 然后把每个数字分成 $5$ 部分，暴力 ......
题解 P2229 【[HNOI2002]沙漠寻宝】
posted on 2021-06-01 12:15:15 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/337504) 这题一看就知道是个模拟。 做模拟题的时候，一定要先确保你的程序能跑出正确的结果，再去想优化时间。 这道题还是 ......
题解 P7679 【[COCI2008-2009#5] JABUKA】
posted on 2021-07-07 17:38:14 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/346961) 设题目中分给每个朋友的苹果数为 $x$，显然有 $x\vert r\land x\vert g$，也就是 $ ......
题解 P2903 【[USACO08MAR]The Loathesome Hay Baler S】
posted on 2021-05-03 20:50:49 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/331434) 首先输入，记录一下哪个齿轮的位置在 $(0,0)$，哪个在 $(x_t,y_t)$。 接着，为了避免多次判断 ......
题解：【ICPC WF 2021 K】 Take On Meme
[题目链接](https://www.luogu.com.cn/problem/P9449) 可以直接求闵可夫斯基和，这里介绍一种官解。 按照题面的两个评分尺度构建坐标系，将所有可能的 $1$ 号节点分值放在平面上，那么最后的答案一定在凸包上。如果我们知道答案的最终方向，那么问题就比较简单了：就是直 ......
题解 [SDOI2009] HH的项链
[题目链接](https://www.luogu.com.cn/problem/P1972) 对于这类问区间不同数的总数，显然是不能用线段树直接维护的，毕竟不符合区间区间可加性。 考虑对于一个右端点固定的询问，哪些数字实际上是有权值的。 比如区间 `1 3 3 2 3 1 2`，显然，实际上对于相同 ......
【大联盟】20230714 T1 三分网络（tri） 题解 CF1666K 【Kingdom Partition】
## 题目描述 [here](https://codeforces.com/problemset/problem/1666/K)。 ## 题解 赛时得分：$30/30$，想了很久网络流最后不会。 感觉这题就纯纯对脑洞，因为把题目中的 $2$ 改成 $3$ 就做不了）））不过还是相当有意思的。 考虑如 ......