YBAGGIO
题意有一个无限的 $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，记录下每个点分别在第几步之后到达，于是第一三部分就很容易做掉了。对于
题意给你一个整数数组 $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$ 时
题意每学期为 $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$ 天所能获得的最大学分。学分由两部分组成——课
转载自ZYXB220226，查看请输入密码ZYXB220226诗歌报汇总.pdf
传送门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$。
下载方式在vscode中搜索Meogi Theme即可介绍其中深色主题的代码高亮非常“花哨”，浅色很典雅，个人推荐 moegi-black。此外，高亮适合各种语言。一共有 8 种主题：1.moegi-black-zen2.meogi-black3.moegi-dark-vitesse4.moegi-dark5.moegi-dawn6.moegi-light-vitesse7.moegi-light8.moegi-space
备注：此做法来自nzq巨佬题意：FJ 有一个边长为 $n (n \leq 500)$， 共有 $n^2$ 个格子的正方形草地，每一个格子有一个 $1...200$ 的绿度值。对于 FJ 的这个草地，有很多个子矩阵。现在需要你求出子矩阵中所有格子的最小值是 $100$ 的子矩阵的个数。样例:输入3 57 120 87 200 100 150 2 141 135输出8_思路我们可以发现答案显然等于最小值小于 $100$ 的矩阵的个数减去最小值小于等于 $100$ 的个数。如何计算这两个值呢？我们设函数 query(m) 为最小值小于 $m$ 的子矩阵个数，那么答案就等于 query(100)-query(101) 。这个函数怎么写呢，我们将所有小于 $m$ 的格子设为 $1$, 将所有大于等于 $m$ 的格子设为 $0$， 我们对于每一行记一个 $sum_{i,j}$。代码如下:for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(a[i][j]<maxx)b[i][j]=1,sum[i][j]=0;
题意有 $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
ybaggio
