题解product dice abc

总结题意 显然可以转化为序列问题嘛。 给出序列 \(A\{a_i\}\)，你需要通过若干次操作使其归零。 操作： 选定 \(d | n\)、\(k\)、\(r\)，对于序列中所有满足 \(i \bmod d = r\) 的位置加上 \(k\)。 题解 很明显，加减相互抵消，对于所有 \(d\)、\( ......

USACO 铂金题解 USACO 2018 Platium B. Sort It Out 很巧妙的转换 注意到操作并不会影响没有被选中的牛的相对顺序 所以没有被选中的一定单调递增 要使得选中的尽可能少，就要选尽可能长的没有被选中的序列，即原序列的 \(LIS\) 所以原题等价于求原序列第 \(k\) ......

分析 自然，我们可以想到利用贪心去解题。 我们可以证明，$\texttt{ARC}$ 左右两边 $\texttt{A}$ 和 $\texttt{C}$ 个数多的比少的变为 $\texttt{R}$ 贡献能更多，第奇数次操作比第偶数次能使操作次数更多。 于是，我们可以得出这样的一个算法： 若为奇数次操 ......

一道比较简单的爆搜题。虽然在考场上没写出来。 分析 我们可以直接枚举每个人加入哪个团队（如果团队中没有与他相斥的人）。然后答案加一就可以了。 为了是答案更优，我们可以小小地剪一剪枝。 如果剩下的不能满足每一组都有人，就新建一个组，不考虑加入新组。 如果当前组数与要求组数相同就不新建小组了。 但其实， ......

前情提要 本题解重在使大家理解。 本题需要 KMP，相信阅读本篇的大佬都会吧。 没学过也没关系，点这里。这是一篇我喜欢的讲解，不喜勿喷。 分析 看见本题的第一感就是会与 KMP 中的 $next$ 数组有关。 我们通过下面证明可以得出：满足 $i \bmod len = 0$，且 $S[1 \sim ......

A小亮的睡眠时间 思路：求一下一共花了多少时间思考，注意思考时间大于睡觉时间上限的特殊情况。 #include <iostream> using namespace std; int main() { int n; scanf("%d", &n); int sum = 0; int cur; int ......

题目传送门 前置知识 线段树 解法 第一眼感觉和 luogu P1083 [NOIP2012 提高组] 借教室 很像。本题同样采用线段树维护，\(sum_{l,r}(1 \le l \le r \le 10^6)\) 表示从 \(l \sim r\) 时刻内骑士拜访的总时间，\(maxx_{l,r} ......

blog。简单最小割。 发现 \(L_{i,j}\le5\)，所以对 Level 拆点。初始源点 \(S\xrightarrow{0} \text{Lvl}1_i, S\xrightarrow{c_i} \text{Lvl}2_i,\text{Lvl}3_i,\text{Lvl}4_i,\text{ ......

题意 对于一对长度均为 \(M\) 且元素值在 \(\left[1, N\right]\) 之间的序列 \((S, T)\)，定义其为好的当且仅当： 存在一个长度为 \(N\) 的 \(01\) 序列 \(X\)，使得其满足如下条件： 对于任意 \(i \in \left[1, M\right]\) ......

转裁自我的洛谷博客：https://www.luogu.com.cn/blog/653832/Code-of-CF1721A-Image 题意简述 给你一个2×2的矩阵，每次可以将一个或两个字母变成任意的其他字母，问最少用几步能将矩阵中的字母变成一样的。 思路 可以先分类讨论可能会出现的情况（如下表 ......

A 傻逼题，降智吃了一发罚时。 B 依旧是傻逼题，std::pow 炸精度又吃了一发罚时。 C 傻逼题，切了 D 发现就是个判断二分图，切了。 E 一眼丁真，感觉最后一个一定是最大的，然后就是求以最大的结尾的 LIS。 交上去，喜提 WA29。 转变思路，考虑 dp。 设 \(f_{i,j}\) 表 ......

题目传送门 前言 本题解内容均摘自我的 Tarjan 学习笔记 。 解法 Tarjan 与无向图 无向图与割点（割顶） 在一个无向图中，不存在横叉边（因为边是双向的）。 一个无向图中，可能不止存在一个割点。 割点（割顶）：在一个无向图中，若删除节点 \(x\) 以及所有与 \(x\) 相关联的边之后 ......

A. 2UP3DOWN 直接模拟即可。 Code B. 326-like Numbers 枚举，每次拆除百、十、个位，再判断。 Code C. Peak Description 数字线上放置了 \(N\) 个礼物。第 \(i\) 个礼物放置在坐标 \(A_i\) 处。 可以在数轴上选择长度为 \(M ......

帽儿山奇怪的棋盘 题目： Time Limit:1000ms Memory Limit:65535K Description 军哥来到了帽儿山，发现有两位神人在顶上对弈。棋盘长成下图的模样： 每个点都有一个编号：由上到下，由左到右，依次编号为 1、2……12。两位神人轮流博 弈，每一轮操作的一方可以 ......

题目描述 要求有多少个序列满足： 令 \(v=1\sim n\) 从 \(v\) 号点开始，走到 \(p_v\)，…，最后走回 \(v\) 记录每个点被走到的次数（起点算，终点不算，反正只算一次） \(i\) 号点走到的次数恰好是 \(i\) 答案对 \(998,244,353\) 取模 Solut ......

Problem - 1866D - Codeforces Digital Wallet - 洛谷 不妨为选数钦定一个顺序：不同行之间无影响，列从左到右取一定不劣。 设计状态：设 \(dp_{i,j}\) 表示前 \(i\) 次操作操作到第 \(j\) 列的最大答案 转移：因为对于同一列不互相影响， ......

B - The Middle Day 难度: ⭐ 题目大意 在某颗星球上一年有n个月, 给定每个月的天数, 设一年的总天数是m, 请问第m/2(小数向上取整)天是第几个月的第几天; 解题思路 数据不大, 暴力即可; 神秘代码 #include<bits/stdc++.h> #define int l ......

AGC037F 题目传送门 第一步，考虑判断序列是否合法。 通过对于属于等级 $k$ 的定义将定义反推：$s$ 中最小的元素 $x$，找到所有 $x$ 的连续段。设一个连续段的长度是 $len$，若 $len < l$ 则不合法，否则将这一段合并为 $\lfloor \frac {len}l \rf ......

这里提供一个非常暴力但是期望复杂度很低的算法。 不难想到要么就是全部放 \(1\)，要么就是取出一个最大的质数，然后对于剩下的部分继续按照这样的策略求答案。 因为质数间隔不大，然后暴力判断质数复杂度是 \(O(\sqrt n)\) 的，再加上 IOI 的 buff，我们可以直接考虑从大到小枚举质数， ......

题意 对于一个长度为 \(N\) 的序列 \(H\)，可以通过如下方式构造一个序列 \(P\)： 若存在 \(j \in \left[1, i\right)\)，使得 \(H_j > H_i\)，则 \(P_i = \max\limits_{j \in \left[1, i\right) \land ......

Problem - 1866M - Codeforces Mighty Rock Tower - 洛谷 先考虑一个 \(O(n^2)\) 的 dp 设计状态： \(dp_i\) 表示搭 \(i\) 层的期望 转移：\(dp_i=dp_{i-1}\times(1-P_i)+\sum\limits_{j ......

题意 给定一个长度为 \(N\) 的序列 \(A\)，按照下列方式生成一个长度为 \(N\) 的序列 \(X\)： \(\forall i\in[1,n]\)，\(X_i\) 在 \([1,A_i]\) 中的整数中均匀随机生成。 求其最长上升子序列长度的期望，对 \(10^9+7\) 取模。 \(1 ......

[ARC098F] Donation 题解 题目描述 给定一张 \(n\) 点，\(m\) 边的无向图，到达一个点需要拥有 \(a_i\) 的权值，对于一个点操作需要消耗 \(b_i\) 的权值，询问最少需要多少权值才能够对每个点都进行一次操作（权值在任何时候都不能小于 \(0\)）。 题目分析 提 ......

Problem - D - Codeforces Shichikuji and Power Grid - 洛谷 首先这题显然不可能是 dp 我们发现第二个式子是困难的，但题目竟然给 \(n \leq 2000\) ，因此我们考虑抽象建图。我们把两个点的贡献两两建成一张图，最终的答案显然是把这个图划分 ......

lock 这题就是个模拟吧，赛时被迷惑了以为是什么不可做题，仔细看只有 \(10^5\) 种状态，那就枚举好了。 我们分别从状态串出发，枚举它能达到的答案，加到 set 取个并集，不过注意给定的状态不能是密码，要减掉。注意不要直接计数器减减，不然如果有相同的算在状态里面的会多减，我考场代码就这么被 ......

NOIST2023 涂色游戏 对于每一行每一列记录一个时间戳，对于每个格子颜色即为时间戳较大的颜色。 幂次 考虑暴力，我们发现 \(O(\sqrt[3]{n})\) 的复杂度是可以接受的，所以可以枚举 \(\sqrt[3]{n}\) 内的数然后暴力往上乘，可以用一个 unordered_map 判重 ......

Problem - 1867D - Codeforces Cyclic Operations - 洛谷 差一点就想出来了 首先 \(b_i\) 构建出来的肯定是一个章鱼森林，而且手玩一下样例就会发现我们每次要找到一个大小为 \(K\) 的环后让里面的点重新指向，一直重复这些操作直到所有点都被找到。 ......

B - Roulette 难度: ⭐ 题目大意 有一个猜数字的游戏, 有n个人参加, 每人都猜了若干个数; 最后给出答案数字; 在所有猜中数字的人中输出猜数数量最少的人的编号;(可能不止一个); 解题思路 数据不大, 暴力即可; 神秘代码 #include<bits/stdc++.h> #defin ......

题意 对于一个只含有 A，C，T，G 的字符串 \(s\), 定义其为匹配的当且仅当其中 A 的数量和 T 的数量相等，C 的数量和 G 的数量相等。 给定一个长度为 \(N\) 的字符串 \(S\)，求其有多少个非空子串是匹配的。 \(1 \le N \le 5000\)。 题解 \(\mathc ......

题意 有 \(N\) 个区间 \([a_i,b_i](a_i<b_i)\)，都是 \([1,2n]\) 内的整数且互不相同（\(a_i\ne b_j,a_i\ne a_j,b_i\ne b_j\)）。 现在给定一些 \(a\) 和 \(b\) 的值，剩下不知道的用 \(-1\) 表示。问是否存在一种 ......