题解atcoder agc 004

前言 本文中 $S[i,j]$ 表示取 $S$ 中 $i$ 到 $j$ 位置连接成的子串。 补充知识：本原平方串 定义：一个字符串 $S$ 是本原平方串，当且仅当其循环节长度为 $\frac{|s|}{2}$。 性质：字符串 $S$ 的子串中本原平方串的个数至多为 $n \log n$。 不会 $\ ......

一、题目描述： n 个点，m 条边，带边权。起点为 1，终点为 n。 求最小割以及在最小割的情况下的最少割的边数。 2<=n<=32,1<=m<=1e3。 二、解题思路： 第一问很好求解，直接最大流即可。 第二问想不出来，看了题解把我震惊了！ 设边 i 原本的边权为 w[i]，现在我们令新边权 v[ ......

~~谨以此题解纪念我的20次提交~~。 题目大意 给一个整数 $x$ 和 进位次数 $k$，求一个数 $y$ 使得列竖式计算 $x+y$ 时正好产生 $k$ 次进位。 思路 ~~（最开始是想正着搞的，但是怎么也调不出来）~~提供一种倒着做的做法。 首先有几个结论： 产生进位 $=$ 给前一位 $+1 ......

前言 数学符号约定 $a,b,p$：表示任意自然数。 $F_x$：表示广义斐波那契数列的第 $x$ 项。 $f_x$：表示普通斐波那契数列的第 $x$ 项. 如非特殊说明，将会按照上述约定书写符号。 题目分析 首先引入一条定理： 普通斐波那契数列在模 $m$ 意义下纯循环，且循环节为 $O(m)$。 ......

一、题目描述： 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 ......

P3185 [HNOI2007]分裂游戏 题目描述 聪聪和睿睿最近迷上了一款叫做分裂的游戏。 该游戏的规则是： 共有 $n$ 个瓶子， 标号为 $0, 1, \ldots, n-1$，第 $i$ 个瓶子中装有 $p_i$ 颗巧克力豆，两个人轮流取豆子，每一轮每人选择 $3$ 个瓶子，标号为 $i,j ......

原题链接 题目描述 菲菲和牛牛在一块 $n$ 行 $m$ 列的棋盘上下棋，菲菲执黑棋先手，牛牛执白棋后手。 棋局开始时，棋盘上没有任何棋子，两人轮流在格子上落子，直到填满棋盘时结束。 落子的规则是：一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。 棋盘的每个格子 ......

~~想了一会然后看题解，翻到日文题解然后又关了，然后突然会了，怎么回事~~ 第一眼生成函数！做不了。 考虑经典拆贡献方法，把平方的贡献变成从区间中选两个数的方案数。这样我们可以用一个 DP 来计数。 设 $f_{i, j}$ 表示到了第 $i$ 格，已经选了 $j$ 个数的方案数。如果没有限制，那么 ......

题目链接 分析 首先考虑哪些串能被删空。下面只考虑长度为偶数的串。考虑这样一个（错误的）算法：从左往右依次加入串中的字符，然后能删则删。这个算法对于结尾为 A 的串一定能删空。对称地，开头为 B 的串也一定能被删空。 现在只需要考虑开头为 A 结尾为 B 的串。如果它能被删空，则一定存在最早的一个时 ......

洛谷传送门 AtCoder 传送门 算是对这篇博客的补充吧。 设 $a_1 \le a_2 \le \cdots \le a_n$。 发现最优操作中一定是对相邻的数进行操作，因为如果 $a_j$ 想把 $x$ 给 $a_i$（$i < j$），最优是依次操作 $(j-1,j,x),(j-2,j-1, ......

洛谷传送门 AtCoder 传送门 感觉太人类智慧了。 设 $A = (c_1,c_2,...,c_n)$ 表示当前每种牌的数量，$f(A)$ 为状态 $A$ 只进行换牌操作最终最少剩下几张牌。 $f(A)$ 是可以贪心求出的，因为策略必然是能换则换。 并且我们发现依次换 $2,3,...,n,1$ ......

BUAACTF2023 Writeup by Joooook 目录 Misc Which Element chatgpt zhuzhu zhuzhu's revenge Screenshot carzymaze MC Crypto Block Cipher Math KeyExchange Web ......

笑了，题意转换的思路大致都是对的，不知道为啥猜成与题解结论完全相反的结论了。 首先考虑将这个过程看做是一棵满 $k$ 叉树，其中有 $n + m$ 个叶子，$n$ 个叶子为 $0$，$m$ 个叶子为 $1$。不难发现，如果一个 $1$ 的深度为 $x$，那么它对最后的数造成的贡献为 $\frac{1 ......

试题A：2022 解题思路： 有2022个物品，它们的编号分别是1到2022，它们的价值分别等于它们的编号。也就是说，有2022种物品，物品价值等于物品编号。 从2022个物品种选取10个物品，满足10个物品的价值之和为2022，用f[i][j][k]表示前i个物品里选择j个物品，价值之和为k的方案 ......

// created on 23.03.26 A. Alice and Bob 对于链上的情况，异色点是一定不会选择走进同色段的（长度不小于 $2$），因为一定不优。所以，可以倒着 DP，求助每个点的优势步数（即走多少到同色段的最后，然后接下来是黑白相间的链；链过后如果还是同色，就再 $+1$，表示 ......

// created on 23.04.18 A. Ascending Matrix 先不考虑 $a_{R,C}=V$ 的限制，考虑原问题，我们要找到 $k-1$ 条值域轮廓线（起点 $(n,0)$ 终点 $(0,m)$），使相互不越过。将第 $i$ 条向下、右平移 $i-1$ 格，变成了路径不交问 ......

​ 【关键字】 AGC、质量、数据分析 【问题描述】 开发者反馈在应用中集成了AGC的相关服务，在查看平台数据时遇到了一些问题。具体如下所述： 我发现平台的App卸载量每个月都非常高，卸载量/新下载量近80%，很异常，所以想要咨询两个问题： 1、中国的电商行业平均的卸载率 benchmark 是多少 ......

本来想写一个有关思维过程的题解，写出来却成了这样一个怪胎，大家当个乐子看。 最近回顾了一下 Picks loves segment tree IX，然后终于会做这题了，其实两题在思维上有很大的相似之处。 核心思想是划分阶段的问题。 分析一下 $+1$ 的操作，应该怎么考虑： 看作 bitxor 一段 ......

Hackpack2023-2023/4/15 https://ctf2023.hackpack.club/challenges 做了2题出来，其实是一题，第一题是手动逆向，第二题是脚本自动逆向 主要是学习到了nclib包使用 使用说明 https://nclib.readthedocs.io/en/ ......

洛谷传送门 AtCoder 传送门 从低位往高位考虑。设当前个位为 $k$，暴力搜索这一位向上进 $i$ 位，设 $\left\lfloor\frac{n}{10}\right\rfloor - i$ 的答案为 $t$。 若 $t > 10i + k$ 显然就不可行，因为就算个位全部填 $1$ 也不 ......

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 ......

仍然是没有做通信题。 JOISC2016 Day1 Matryoshka 俄罗斯套娃 转化错了，转化成上升子序列了，然后就变成了区间 LIS。 实际上是 LDS，那么就可以直接做了。 https://qoj.ac/submission/99648 JOISC2016 Day1 Memory2 神经衰 ......

洛谷传送门 AtCoder 传送门 Hint 如果是一个环怎么做？ Answer 由于是一个环，因此环上每个点对最终答案造成的贡献都相同。设 $f_{i,j}$ 为长度为 $i$ 的序列选 $j$ 个不相邻的点的方案数，则 $f_{i,j} = \binom{i-j+1}{j}$。应该很好理解，考虑 ......

题意 传送门 给定一张有向图，每条边上有一个边权以及一个字符串。 一条有向路径的长度为这条路径上每条边的边权之和+按照路径的顺序将这些边上的字符串排成一列，相邻两个串的 $\text{lcp}$ 长度之和。 求 $1$ 号点到其他店的最短路。 用所有边上的字符串构造字典树，保证其大小 $\le 2\ ......

T1签到题。 [AGC030B] Tree Burning 高桥湖是周长为 $L$ 的一个首尾相接的圆，圆上整点标为$0, 1, 2, ..., L-1$. 在湖边有 $N$ 颗树，分别在距离起点顺时针数 $X_1, X_2,...,X_n$ 的位置上。保证位置 $0$ 没有树。 高桥君初始在位置 ......

洛谷传送门 AtCoder 传送门 很棒的 flow 题，考虑建二分图。 源点向每种零食连边权为 $a_i$ 的边，每种零食向每个孩子连边权为 $b_j$ 的边，每个孩子向汇点连边权为 $c_j$ 的边，这个图的最大流就是答案。 直接跑最大流肯定 T，考虑最大流等价于求这个图的最小割，因此转而求最小 ......

洛谷传送门 AtCoder 传送门 很不错的状压。 考虑先把最后作为答案的数聚到一起，再算它们的逆序对个数。 设 $f_S$ 为当前选的数集合为 $S$ 的答案。有转移： 选 $a_i$，答案加上之前选的比它大的数； 不选 $a_i$，此时需要把左边的数或者右边的数往中间挪一个，答案加上左右两端的最 ......

A. Burglar and Matches - 900 题目大意 一个窃贼要去偷火柴，最多偷 $n$ 盒，店里有 $m$ 种火柴，每种火柴有 $a_i$ 盒， 每盒有 $b_i$ 根火柴，问最多能偷走多少根火柴， 解题思路 贪心签到题，按照每盒的火柴数排序，优先偷火柴多的盒即可。 AC Code ......