题解small 254e abc
[ABC136E] Max GCD
2023-02-02 题目传送门 翻译 难度&重要性(1~10):4 题目来源 AtCoder 题目算法 数学，贪心 解题思路 记这个数列的和为 $sum$。那么对于每一次操作，$sum$ 的值都不会改变。最后的答案，也一定是 $sum$ 的因数。 那么我们枚举一下 $sum$ 的因数，然后判断一下 ......
「集训队作业2018」串串划分 题解
前言 本文中 $S[i,j]$ 表示取 $S$ 中 $i$ 到 $j$ 位置连接成的子串。 补充知识：本原平方串 定义：一个字符串 $S$ 是本原平方串，当且仅当其循环节长度为 $\frac{|s|}{2}$。 性质：字符串 $S$ 的子串中本原平方串的个数至多为 $n \log n$。 不会 $\ ......
P1344 [USACO4.4] 追查坏牛奶 Pollutant Control 题解
一、题目描述： n 个点，m 条边，带边权。起点为 1，终点为 n。 求最小割以及在最小割的情况下的最少割的边数。 2<=n<=32,1<=m<=1e3。 二、解题思路： 第一问很好求解，直接最大流即可。 第二问想不出来，看了题解把我震惊了！ 设边 i 原本的边权为 w[i]，现在我们令新边权 v[ ......
[题解] P9215 [入门赛 #11] [yLOI2021] 扶苏与 1 (Hard Version)
~~谨以此题解纪念我的20次提交~~。 题目大意 给一个整数 $x$ 和 进位次数 $k$，求一个数 $y$ 使得列竖式计算 $x+y$ 时正好产生 $k$ 次进位。 思路 ~~（最开始是想正着搞的，但是怎么也调不出来）~~提供一种倒着做的做法。 首先有几个结论： 产生进位 $=$ 给前一位 $+1 ......
题解 P7325
前言 数学符号约定 $a,b,p$：表示任意自然数。 $F_x$：表示广义斐波那契数列的第 $x$ 项。 $f_x$：表示普通斐波那契数列的第 $x$ 项. 如非特殊说明，将会按照上述约定书写符号。 题目分析 首先引入一条定理： 普通斐波那契数列在模 $m$ 意义下纯循环，且循环节为 $O(m)$。 ......
P1345 [USACO5.4]奶牛的电信Telecowmunication 题解
一、题目描述： n 个点，m 条边，给定起点 s 和终点 t ，求最少删去几个点后，s 和 t 不连通。 注意，s 和 t 不能删掉。1<=n<=100，1<=m<=600; 二、解题思路： 刚刚学了最大费用流，知道最大流等于最小割。但此题割的不是边，是点。 我们需要将将割点转化为割边。把一个点切成 ......
比赛题解和游记
AtCoder ABC ABC238 Editorial ARC AGC CodeForces Div4 Div3 Div2 Div1 Luogu GF 模拟赛 游记 GDOI2023 游记 ......
题解（开始学知识点
D. Frog Traveler 1900 dp gq！ https://codeforces.com/contest/1602/problem/D 题解：我们可以通过类似bfs的过程找到每个点的能到达的所需步数最小的点，完成更新，但每个点能被哪些点到达很难判断，故我们反过来考虑，如果我们能得到从n ......
ABC238 Editorial
A - Exponential or Quadratic 题意 给定一个 $n$，问 $2^n>n^2$ 是否成立。 分析 手搓样例，发现只有 $2,3,4$ 不满足条件，输入输出题。 code #include <bits/stdc++.h> #pragma GCC target("sse,sse ......
【题解】P3185 [HNOI2007]分裂游戏
P3185 [HNOI2007]分裂游戏 题目描述 聪聪和睿睿最近迷上了一款叫做分裂的游戏。 该游戏的规则是： 共有 $n$ 个瓶子， 标号为 $0, 1, \ldots, n-1$，第 $i$ 个瓶子中装有 $p_i$ 颗巧克力豆，两个人轮流取豆子，每一轮每人选择 $3$ 个瓶子，标号为 $i,j ......
【题解】P4363 [九省联考 2018] 一双木棋 chess
原题链接 题目描述 菲菲和牛牛在一块 $n$ 行 $m$ 列的棋盘上下棋，菲菲执黑棋先手，牛牛执白棋后手。 棋局开始时，棋盘上没有任何棋子，两人轮流在格子上落子，直到填满棋盘时结束。 落子的规则是：一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。 棋盘的每个格子 ......
BUAACTF2023 Writeup题解 by Joooook
BUAACTF2023 Writeup by Joooook 目录 Misc Which Element chatgpt zhuzhu zhuzhu's revenge Screenshot carzymaze MC Crypto Block Cipher Math KeyExchange Web ......
第十三届蓝桥杯c++b组国赛题解（还在持续更新中...）
试题A：2022 解题思路： 有2022个物品，它们的编号分别是1到2022，它们的价值分别等于它们的编号。也就是说，有2022种物品，物品价值等于物品编号。 从2022个物品种选取10个物品，满足10个物品的价值之和为2022，用f[i][j][k]表示前i个物品里选择j个物品，价值之和为k的方案 ......
【题解】XX Open Cup, GP of Moscow
// created on 23.03.26 A. Alice and Bob 对于链上的情况，异色点是一定不会选择走进同色段的（长度不小于 $2$），因为一定不优。所以，可以倒着 DP，求助每个点的优势步数（即走多少到同色段的最后，然后接下来是黑白相间的链；链过后如果还是同色，就再 $+1$，表示 ......
【题解】XXI Open Cup. GP of Tokyo
// created on 23.04.18 A. Ascending Matrix 先不考虑 $a_{R,C}=V$ 的限制，考虑原问题，我们要找到 $k-1$ 条值域轮廓线（起点 $(n,0)$ 终点 $(0,m)$），使相互不越过。将第 $i$ 条向下、右平移 $i-1$ 格，变成了路径不交问 ......
Hackpack 2023 逆向Re部分题解
Hackpack2023-2023/4/15 https://ctf2023.hackpack.club/challenges 做了2题出来，其实是一题，第一题是手动逆向，第二题是脚本自动逆向 主要是学习到了nclib包使用 使用说明 https://nclib.readthedocs.io/en/ ......
2022CCPC威海站 铜牌题解 A C D E G I J 补题
A //木桶效应 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 10; map<string, int> cham; pair<string, int> player[N ......
[ABC131E] Friendships
2023-01-30 题目传送门 翻译 难度&重要性(1~10): 题目来源 AtCoder 题目算法 找规律，构造 解题思路 先构造一个菊花图为最大边的图，再依次连边减小k。 完成状态 已完成 ......
JOISC2016 题解
仍然是没有做通信题。 JOISC2016 Day1 Matryoshka 俄罗斯套娃 转化错了，转化成上升子序列了，然后就变成了区间 LIS。 实际上是 LDS，那么就可以直接做了。 https://qoj.ac/submission/99648 JOISC2016 Day1 Memory2 神经衰 ......
[ABC213E] Stronger Takahashi
2023-01-17 题目传送门 翻译 难度&重要性(1~10):4 题目来源 AtCoder 题目算法 bfs 解题思路 首先，这道题的问题是从家到鱼市摧毁障碍物的最少次数。我们很容易想到用广搜的方法来做。因为 $2 \le H,W \le 500$，数据很小，理论上我们可以对于每个障碍物都进行一 ......
LG3783 题解
题意 传送门 给定一张有向图，每条边上有一个边权以及一个字符串。 一条有向路径的长度为这条路径上每条边的边权之和+按照路径的顺序将这些边上的字符串排成一列，相邻两个串的 $\text{lcp}$ 长度之和。 求 $1$ 号点到其他店的最短路。 用所有边上的字符串构造字典树，保证其大小 $\le 2\ ......
[ABC132D] Blue and Red Balls
2023-01-16 题目传送门 翻译 难度&重要性(1~10):3 题目来源 AtCoder 题目算法 dp 解题思路 因为蓝球的数量是固定的，题目让我们求，在取 $i$ 次的情况下，有几种方案，首先我们肯定要枚举 $i$，范围就是 $\sum_{i=1}^{k}$ 了，然后因为他每次只能取连续的 ......
[ABC129E] Sum Equals Xor
2023-01-15 题目传送门 翻译 难度&重要性(1~10):4 题目来源 AtCoder 题目算法 dp/模拟 解题思路 我们都知道，异或是一种不进位的加法，而要想 $ a + b = a \oplus b $ 就不能进位，也就是说每一位不能是 $ ( 1,1 ) $ 就有 $ ( 0,1 ) ......
[ABC128F] Frog Jump
2023-01-14 题目传送门 翻译 难度&重要性(1~10):5 题目来源 AtCoder 题目算法 数学，模拟 解题思路 把(A-B)看为一步。应为最后必须落在N-1，所以可以将其分为两个序列： $(A+B),2\times(A+B),3\times(A+B),\cdots N-1-2\tim ......
[ABC128E] Roadwork
2023-01-14 题目传送门 翻译 难度&重要性(1~10): 题目来源 AtCoder 题目算法 区间覆盖，线段树，双堆 解题思路 可以将问题转化为区间覆盖问题和单点查询问题。 一共会有 $3$ 种操作： $1.$ 插入一个区间。 $2.$ 删除一个区间。 $3.$ 查询一个区间。 想到这我是 ......
[ABC128D] equeue
2023-01-14 题目传送门 翻译 难度&重要性(1~10): 题目来源 AtCoder 题目算法 暴力，贪心 解题思路 由题意可以得出，数据只有 $n \leq 50,k \leq 100$。所以，可以使用暴力，枚举从左右两边取的个数（只能从两边取），用一个数组记录下负数，去玩两边之后，将负数 ......
DfC 专项训练题解1
A. Burglar and Matches - 900 题目大意 一个窃贼要去偷火柴，最多偷 $n$ 盒，店里有 $m$ 种火柴，每种火柴有 $a_i$ 盒， 每盒有 $b_i$ 根火柴，问最多能偷走多少根火柴， 解题思路 贪心签到题，按照每盒的火柴数排序，优先偷火柴多的盒即可。 AC Code ......
ABC267G Increasing K Times 题解
做这道题，很有感悟，发篇文。 先给数列从小到大排个序。 接下来设 $f_{i,j}$ 表示前 $i$ 个数的排列形成 $j$ 个上坡的方案数。 接下来考虑转移，分为插入第 $i$ 个数后增加上坡和不增加上坡两种情况。 对于不增加的情况，有三种可能： 第 $i$ 个数插入在了数列的最前端，有 $1$ ......
2021牛客OI赛前集训营-提高组（第二场）第三题 树数树题解
题目描述 牛牛有一棵 $n$ 个点的有根树，根为 $1$。 我们称一个长度为 $m$ 的序列 $a$ 是好的，当且仅当： $\forall i \in (1,m]$，$a_i$为 $a_{i−1}$的祖先或 $a_{i−1}$是 $ai$的祖先 $\forall 1 \leq i \lt j \le ......
2021牛客OI赛前集训营-提高组（第三场） 第二题 交替 题解与结论证明
题目描述 一个长度为 $n$ 的数组$A$，每秒都会变成一个长度为 $n − 1$ 新数组 $A'$，其变化规 则如下： 若当前数组 $A$ 的长度 $n$ 为偶数，则对于新数组 $A'$ 的每一个位置 $i(1 ≤ i < n)$来说，$A'[i]=A[i]+A[i+1]$ 若当前数组 $A$ 的 ......