题解secret sport 1894

考虑 kruskal 算法的过程。 先将边按边权排序，考虑当加入 \((u,v)\) 时只有 \((u,v)\) 不联通才可能使得其出现在最小生成树中，所以对于所有的边权小于 \(L\) 的边，我们希望去除尽可能少的边使得 \((u,v)\) 不联通。这显然是一个网络流模型。对于每一条边 \((x, ......

非常有意思的思维题。 首先我先瑞平一下翻译，我根本没看懂，还是去看英文题面看懂的。 首先可以发现整个字符串被拆成了若干个奇回文串与偶回文串。现考虑如何判是否合法。可以发现一个回文串就是要求部分位置匹配。我们对这些匹配的位置建边，如果得到的图是联通的，那么就只能填入 \(1\) 种字符，否则就可以填入 ......

首先考虑一些简单的情况，比如 \(m=1\)。 容易发现操作 1 和操作 2 的顺序不会影响结果，于是可以钦定所有操作 1 在操作 2 之前。并且可以发现，进行完所有 1 后 2 的次数即为 \((\text{连续段个数}-1)\)。 然后考虑将 \(m>1\) 的情况。显然最后序列上每 \(m\) ......

[CF1098E] Fedya the Potter 题解 前言 一道类欧好题。 题解 这道题让求 \(c\) 数组的中位数，那么有一个比较套路的方法就是二分答案 \(mid\) 然后计算 \(b\) 数组中区间和小于 \(mid\) 的区间个数进行 \(check\)。但是 \(b\) 数组总共有 ......

CF882E1+CF1882E2 Two Permutations 题解-构造题 哇，人类智慧，太智慧了。。。 此题作为20231010联考的 T3。 感觉赛时根本没有去往这方面想。 CF1882E1 CF1882E2 E1 是简单版，就是没有要求操作数最小化。 E1-Easy Version 方法 ......

[ABC245G] Foreign Friends 题解 想法 考虑所有颜色相同的弱化版。 这种情况下，只需要把所有特殊点都推入队列之后跑多源 Dijkstra 即可。 思路 正解与上述做法大致相同。 如果有颜色限制，那么可以考虑这个神仙思路： 把所有特殊点的颜色用二进制表示，对于每一位，这一位是 ......

[USACO17JAN] Promotion Counting P 题解 前言 好久没写题解了，今天趁我心情好赶紧水一篇。 思路 首先拿到这题，关键词检索：子树，比 \(p_i\) 大的，树状数组！现在考虑如何去掉其他子树的贡献……emm，我直接在算贡献的时候去掉其他子树的贡献不就好了！ 当然，暴力 ......

题目描述 贝茜听说一场特别的流星雨即将到来：这些流星会撞向地球，并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑，发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。 如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。 根据预报，一共有 \(M\) ......

分析 感觉没有蓝题难度 一道 bfs 题目，相较于大部分 bfs 题，它较为复杂，但分析一下还是很好水过的。 建立墙时，可以用三维数组，\(wall_{~i, ~j, ~pos}\) 表示 第 \(i\) 行第 \(j\) 列 \(pos\) 方向有墙。 观察发现，\(8 = 2^3，4 = 2^2 ......

Shuffle 题目大意 给定一个长度为 \(n\) 的 01 序列 \(a\)，你可以进行至多一次以下操作： 选定 \(a\) 的一个连续段，满足连续段内恰好有 \(k\) 个 \(1\)，将该连续段任意排列。 问能产生多少种不同的 01 序列。 思路分析 （这题 \(n\) 完全可以开到 \(1 ......

A. 黑白染色 这类题没有做过，第一次做，很有新意。 染色的时候，如果一个点的出边中有2个同色点，那么就有一条路中有三个同色点，是不合法的。 不妨先把所有点染成一个颜色，然后再选点染成另一个颜色。 使用一个队列，先把所有的点入队。 每次取出队头 \(u\) ，如果发现他不合法： 1.自己颜色取反 2 ......

[POI2015] LOG 题目描述 维护一个长度为 \(n\) 的序列，一开始都是 \(0\)，支持以下两种操作： U k a 将序列中第 \(k\) 个数修改为 \(a\)。 Z c s 在这个序列上，每次选出 \(c\) 个正数，并将它们都减去 \(1\)，询问能否进行 \(s\) 次操作。 ......

题目描述 给你一个 \(n\) 个点 \(n\) 条边的有向图，若选了当前节点，那么当前节点的儿子节点至少有一个不能选。求最多能选多少个点。 具体思路 显然是一棵基环树，因此考虑基环树 dp。 我们先不管环的条件，先考虑朴素的树形 dp。 设 \(f_{x,0}\) 表示 \(x\) 节点不选，最多 ......

easy_RE 先exeinfo 没有壳，直接上ida 看到有关键信息，但没有显示完，按f5反编译一下 拼接一下输入，注意字符串的部分字母由近似数字代替，提交 KE 运行一下，看到是KE，想着可能是壳的意思？exeinfo看一下 upx壳，尝试upx脱壳 呃呃 权限好像不对 尝试了一下用管理员权限打 ......

题目描述 给出一个长度为 \(n\) 的序列 \(a_i\)，求出下列式子的值： \[\sum_{i=1}^n \sum_{j=i}^n (\max \limits_{i \le k \le j} a_k-\min \limits_{i \le k \le j}a_k) \]即定义一个子序列的权值为 ......

题解： CF768D Jon and Orbs 一句话体面：有k种不同的物品,每天等概率任取一种（不一定是新的种类）。q组询问，每组给出一个p，问取完这k件物品的概率不小于\(\frac{p}{2000}\)的最小天数 不用说，肯定是概率DP了 1.定义 :\(f_{i,j}\) 表示前\(i\)天 ......

题意 给定一个长度为 \(n\) 的正整数序列 \(a\)，对该序列进行 \(m\) 次操作，定义每次操作如下： 从 \(\left[1, n\right]\) 中等概率选取一个 \(i\)，对于 \(j \in \left[i, n\right]\)，执行操作 \(a_j \leftarrow a ......

解题思路: 确实是一道很好的贪心，但由于加上了水这个影响因素，使题目复杂度上升了不少。（考虑的东西多了嘛） 输个入。 对饼干温度无脑排序。 求最小值。 求最大值（用双指针做，后面会讲）。 解题过程: 先输入（这个步骤就不用我讲了） int a[1000005]; long long n,ws; lo ......

Party DP 是门艺术。 \(n\leq 22\) 一眼状压。但是怎么状压就比较困难，因为同一个 \(f[x]\) 可以代表成千上万种含义。 这里我们采用，设 \(f[x]\) 表示当 \(x\) 集合中所有的点都处于同一个团内的最小代价。 则我们有 \(f[x \operatorname{or ......

Piling Up 一个很好的思路就是设 \(f[i][j]\) 表示当前进行了 \(i\) 步，并且盒子中剩下了 \(j\) 个白球的方案数，然后直接 DP 即可。 但是这样是有问题的，它没有考虑到重复计算的问题。 我们不妨令 \(+\) 符号表示取出黑球，\(-\)符号表示取出白球。 则一种方式 ......

BubbleSquare Tokens 神仙构造题。 首先，我们令所有点初始都没有放币，所有边上都放了一个币。则此时每个点的权值即为它的度数。 然后，我们考虑从小到大计算每个点的权值。对于每个点 \(i\)，我们枚举它所有相邻且编号比它小的点，假如该点上没有币，就把币从连接两点的边上移到另一端的点上 ......

Connecting Vertices 这个奇怪的限制（两条边不能有交点）让我们想到什么？ 对于任何一种方案，不存在 \(x_0<x_1<y_0<y_1\)，其中连边 \((x_0,y_0),(x_1,y_1)\)。 也就是说，对于任何一段区间 \([i,j]\)，如果里面所有点全都连通： 要么 \ ......

Dead Ends \(n\le10\)，我还是第一次见到这么小的状压 我们设 \(f[S][s]\) 表示：将集合 \(S\) 内的点连成一棵树，且集合 \(s\) 里的节点是叶子节点的方案数。 则有 \[f[S\cup\{j\}][\{s\setminus i\}\cup\{j\}]+=f[S] ......

Long Colorful Strip 中间如果有那些地方看不懂，可以先去看看前面一道，这是我的题解。 首先，每一次染色，最多把一整段连续的同色格子，分成了三段。 并且，明显我们可以把连续的同色格子，直接看作一个。 这就意味着，在这么压缩后，有 \(m<2n\)。 这就意味着 \(O(m^3)\) ......

[ARC143D] Bridges 题意：给定 \(2n\) 个点和 \((u_1,v_1) , \cdots , (u_m,v_m)\)，选择让 \(u_i\) 连 \(v_i+n\) 或 \(v_i\) 连 \(u_i+n\)，以最小化图中桥的个数。 有种技巧叫拆点，把一个点拆成入点和出点，看这 ......

奇怪装置 找到循环就很简单了。 很显然 \(y\) 是每 \(B\) 次一循环的，对于每个相邻的 \(y\) 循环 \(x\) 的值均相差 \(B+1(\bmod A)\)。 因此总的循环就是 \(B+1\) 对于 \(A\) 的循环乘上 \(B\)。 即 \(\frac{A}{\gcd(A,B+1 ......

Short Colorful Strip 考虑设 \(f[i,j]\) 表示：假设区间 \([i,j]\) 里面一开始所有格子的颜色都是相同的，那么，染成目标状态共有多少种染法。 我们找到 \([i,j]\) 中最小的那个颜色，设为 \(mp\)。则显然，我们下一步要染上 \(mp\) 这种颜色。 ......

所有的 \(DP\) ，只要式子一推出来（不管复杂度），那就很简单了，因为优化是成千上万种的…… 思路1: 我们考虑设 \(f[i][j][k]\) 表示：当前 \(DP\) 到第 \(i\) 块木板的第 \(j\) 个位置，共涂了 \(k\) 次，所能获得的最大收益。因为还要枚举当前这次涂是从哪到 ......

[SDOI2013] 城市规划 题意：给你一个 \(6 \times n\) 的网格题，单点修改，询问区间联通块数，\(n \le 10^5\)。 解：看起来就很显然的一道题......线段树每个点用一个 ufs 维护连通性； 我为了方便思考把图转成横着的了。 写起来真是毒瘤...... 重点在于： ......

AtCoder Beginner Contest 320 Problem C - Slot Strategy 2 (Easy) 题解 题目简述 给定 \(3\) 个长度为 \(m\) 的转盘，转动过后三个转盘分别可以在不同的时间停下，求停下时所有转盘都显示相同数字的最小时间。 思路 由于这题 \(m ......