标签题解下的文章 - YBAGGIO

CF1902D题解

题意有一个无限的 $2$ 维网格。一开始，机器人站在 $(0, 0)$ 点。机器人可以执行四条指令：U：从点 $(x, y)$ 移动到 $(x, y + 1)$ ；D：从点 $(x, y)$ 移动到 $(x, y - 1)$ ；L：从点 $(x, y)$ 移动到 $(x - 1, y)$ ；R：从点 $(x, y)$ 移动到 $(x + 1, y)$ 。给你一串长度为 $n$ 的命令 $s$ 。您的任务是回答 $q$ 独立的查询：给定四个整数 $x$ 、 $y$ 、 $l$ 和 $r$ ；判断机器人在执行命令序列 $s$ 时是否访问了点 $(x, y)$ ，但 $l$ 到 $r$ 的子串是相反的（即机器人执行命令的顺序是 $s_1 s_2 s_3 \dots s_{l-1} s_r s_{r-1} s_{r-2} \dots s_l s_{r+1} s_{r+2} \dots s_n$ ）。题解每次查询，机器人的路径分为三个部分：$[1, l - 1]$；$[l, r - 1]$；$[r, n]$。我们可以开个map，记录下每个点分别在第几步之后到达，于是第一三部分就很容易做掉了。对于

题解 · 2023-12-10

CF1902C

题意给你一个整数数组 $a_1, a_2, \dots, a_n$ ，它的所有元素都是不同的。首先，要求你在这个数组中再插入一个整数 $a_{n+1}$ 。 $a_{n+1}$ 不应等于 $a_1, a_2, \dots, a_n$ 中的任何一个。然后，您必须使数组中的所有元素相等。开始时，您选择一个正整数 $x$。在一次操作中，你将 $x$ 恰好添加到数组的一个元素中。注意 $x$ 在所有操作中都是一样的。在你选择了 $a_{n+1}$ 和 $x$ 之后，要使所有元素相等所需的最小运算次数是多少？题解由于 $x$ 只能是正值，所以我们只能使所有元素等于数组中当前的最大值。考虑不添加 $a_{n + 1}$。我们设 $a$ 中最大值为 $M$，则要想要运算次数最少，则需要使 $x$ 尽可能大，所以 $x$ 应该取 $gcd\{a_n -a_1, a_n-a_2, \dots, a_n-a_{n-1}\}$，然后直接枚举统计答案即可。考虑添加 $a_{n+1}$。我们不希望改变 $x$（将会增加至少 $n$ 的答案），所以我们选择当 $a_{n+1} = M - k \cdot x$ 时

题解 · 2023-12-10

CF1902B题解

题意每学期为 $n$ 天，莫诺卡普必须在这 $n$ 天内获得至少 $P$ 分。获得分数有两种途径——完成实践任务或上课。每完成一项实践任务，蒙诺卡普就能获得 $t$ 分；每上一堂课，他就能获得 $l$ 分。实践任务每七天解锁一个：第一个任务在第 $1$ 天解锁（可以在 $1$ 到 $n$ 的任何一天完成），第二个任务在 $8$ 天解锁（可以在 $8$ 到 $n$ 的任何一天完成），第三个任务在 $15$ 天解锁，以此类推。从 $1$ 到 $n$ ，每天都有一堂课可以让莫诺卡普参加。每天，莫诺卡普都可以选择是学习还是休息一整天。当蒙诺卡普决定学习时，他可以上一堂课，并完成不超过 $2$ 个解锁了但未完成的任务。如果莫诺卡普全天休息，他将跳过一堂课，并不做任何任务。求莫诺卡可以休息的最大天数。$1 \le n, l, t \le 10^9$ ；$1 \le P \le 10^{18}$。题解要求休息的最大天数，等于求不休息的最小天数，显然不休息的天数越多，所获得的学分也越多，所以我们可以二分不休息的天数，设为 $m$。然后我们计算不休息 $m$ 天所能获得的最大学分。学分由两部分组成——课

题解 · 2023-12-10

CF1882D

传送门CF1882D题意给出一颗树，节点编号为 $1 ... n$，每个点有一个权值 $a_i$。你可以执行任意次操作：选择一个 $x$ 满足 $1 \le i \le n$，和一个正整数 $c$。并将 $x$ 子树中所有点的权值异或上 $c$，这次操作的代价为 $u \cdot c$，其中 $u$ 为子树 $x$ 的节点个数。现在需要你求出，对于每个 $r,1 \le r \le n$，以 $r$ 为根时，让所有 $a_i$ 相等的最小代价。$1 \le n \le 2 \cdot 10 ^ 5,1 \le a_i \le 2 ^ {20}$题解我们首先考虑，只需要求出以 $1$ 为根时的答案。看到异或操作，而且 $a \le 2 ^ {20}$，可以想到对每一位分别处理。接下来我们考虑树形DP，设 $f_{x,j,k}$ 表示将子树 $x$ 所有点权值的第 $j$ 位均变成 $k$ 的方案数，那么答案就是 $\sum_{j=0}^{20} {\min \{f_{1,j,0},f_{1,j,1}\}}$。对于一个叶子节点，可以很容易地求出它的 $f$ 值。对于任意非叶子节点 $x$。

题解 · 2023-09-26

CF1862E 题解

题意有 $n$ 场电影，第 $i$ 场电影能够带来 $a_i$ 的快乐值，但是当距离上一次观看电影 $cnt$ 天后观看一场电影，这场电影带来的欢乐值会减少 $d \cdot cnt$（可能减少至负数）。现在我们可以去选择观看 $n$ 场电影中的不大于 $m$ 场，使得最终所获得的欢乐值最大。题解假设我们观看了第 $i_1, i_2 ... i_s$ 这 $s$ 场电影，那么我们获得的欢乐值表示为$a_{i_1} - i_1 \cdot d + a_{i_2} - (i_2 - i_1) \cdot d + ... + a_{i_s} - (i_s - i_{s - 1}) \cdot d$将 $d$ 提取出来得到：$a_{i_1} + a_{i_2} + ... + a_{i_s} - i_s \cdot d$由此可见，$d$ 的系数仅与看的最后一场 $i_s$ 有关，因此我们可以枚举看的最后一场电影，得到 $- i_s \cdot d$ 的取值，随后贪心选择第 $i_1 ... i_{s-1}$ 场电影。Code#include <iostream> #include

题解 · 2023-08-26

ARC127B 题解

题意给出 $n$ 和 $l$，要你构造 $3n$ 个长度为 $l$ 字符串，使得字符串都是由 0,1,2 组成且字符串两两不同，每个字符在每个字符串的同一位的出现次数都是 $n$ 次。要你最小化你构造出来的字典序最大的字符串的字典序，输出 $3n$ 个字符串。题解我们可以将 $3n$ 个字符串分为0开头的，1开头的，2开头的。对于前两种字符串，它们的字典序显然不是最大的，因此既然要求最大字典序最小，我们就要考虑构造2开头的字符串，使得其最大字典序最小。我们可以这样按照3进制下的 $[0,n)$ 贪心构造出 $n$ 个字符串，即可满足最小：200...00000 200...00001 200...00002 200...00010 200...00011 200...00012 200...00020 ...而对于1开头和0开头的字符串，我们直接从2开头的置换而来即可。#include<iostream> using namespace std; const int maxn=50010,maxl=20; int n,l,a[maxn][maxl],b[maxn][maxl

题解 · 2023-04-06

ABC294D 题解

题意有 $N$ 个人，他们的编号分别为 $1 ... N$。现在有三种操作：柜台呼叫尚未被呼叫的编号最小的人。表示编号为 $x$ 的人来到了柜台（保证 $x$ 已经被呼叫过一次及以上）询问已经被呼叫但是没有来到柜台的人中的最小编号。题解我们发现一个人有三种状态：没有被呼叫，呼叫了但没来，被呼叫且来了。因此我们用两个小根堆维护前两个状态的人（最后一个状态的人相当于不会在被操作或询问了，所以不用维护）。因此对于操作1，我们询问状态1的人中编号最小的人，将其变成状态2，对于操作2，我们直接将指定的 $x$ 从状态2堆中删除。#include <iostream> #include <queue> using namespace std; int n, m; priority_queue <int, vector<int>, greater<int>> q1, q2, d; int main () { ios::sync_with_stdio (false), cin.tie (0); cin >> n >&

题解 · 2023-03-21

ABC291E Find Permutation 题解

传送门题意有一个长度为 $N$ 的排列 $A_1 \dots A_N$，然后给出 $M$ 对大小关系：输入 $i,j$ 表示 $A_i<A_j$。问 $A$ 是否只有一种可能，若是，输出Yes然后输出 $A$，如果不是输出No。题解如果要 $A$ 只要一种可能，则必须要求每两个数的大小关系都确定，因此我们对每一对输入的 $(i,j)$ 建边 $i->j$，然后跑拓扑排序，如果有环（大小关系矛盾）或者队列里同时有两个数（这两个数可以调换位置）则输出No，否则按照拓扑排序的序列得出答案。#include <map> #include <iostream> #include <vector> #include <queue> using namespace std; const int maxn = 200010; int n, m, tot, tp[maxn], rd[maxn], a[maxn]; map <pair<int, int>, bool> p; queue <int> q; vec

题解 · 2023-02-27

Theme Jasmine by Kent Liao