Asahi 的博客

Solution:本题需要模拟一个链表，考虑需要加入时需要知道一个点的后继，删除时需要知道一个点的前驱和后继，所以我们采用双向链表维护。用数组维护每个点的前驱和后继。由于值域是 $10^9$ 的，所以我们采用map维护。 首先考虑构建链表。我们把序列中的点顺次放入链表中，具体地说，对于每个点 $a_i$，它的前驱是 $a_{i-1}$，后继是 $a_{i+1}$。特别地，我们建立两个虚拟节点，分别作为 $a_1$ 的前驱和 $a_n$ 的后继。 考虑添加点。我们很容易得知要添加点的左右两个点 $L$ 和 $R$，设添加的点为 $X$，对于后继，把 $L$ 的后继连向 $X$，$X$ 的后继连向 $R$，前驱同理，如图所示： 考虑删除。我们很容易得知要删除点的左右两个点 $L$ 和 $R$，把 $L$ 的后继连向 $R$，$R$ 的前驱连向 $L$ 如图所示： 最后从最左边的虚拟点开始，向右寻找后继输出，直至寻找到最右边的点，输出结束。 时间复杂度 $O(n \log n)$。 Code:12345678910111213141516171819202122232425262...

Solution:首先转换一下题意。 对于 $a_i$ 和 $a_j$，满足 $a_i + a_j$ 可被 $x$ 整除，也就是满足 $a_i + a_j \equiv 0 \pmod{x}$，两边同时减 $a_j$，得 $a_i \equiv -a_j \pmod{x}$，即 $a_j \equiv -a_i \pmod{x}$；满足 $a_i - a_j$ 可被 $y$ 整除，也就是满足 $a_i - a_j \equiv 0 \pmod{y}$，两边同时加 $a_j$，得 $a_i \equiv a_j \pmod{y}$。 有一个问题，就是处理 $-a_i \mod x$ 的方法。显然 $a_i \equiv x-a_i \mod x \pmod{x}$，所以使用 $(x-a_i \mod x) \mod x$ 来处理。 开个map数组，以每个数模 $x$ 和模 $i$ 的值作为下标，对于每个数 $a_i$，其对应的答案就是 $mp_{-a_i \mod x,a_i \mod y}$。 Code:12345678910111213141516171819202122232...

想到一种和其他题解不一样的做法，就写一下吧。 Solution：设设个序列为 $S$，如果有一个位置 $i$ 满足 $S_i=S_{i-1}$，那么把 $i$ 的位置记录下来（也就是说记录两个数相同的位置），由于数据范围是 $5 \times 10^5$ 的，所以把位置可以用bool数组存下来，查询时如果 $[l+1,r]$ 内没有被标记的位置，就是合法的，否则是不合法的，我们可以用线段树维护这个数组。 对于修改，显然修改后区间内数的相对关系是不会改变的，修改区间外数的相对关系当然也不会改变，可能改变的只有 $[l-1,l]$ 和 $[r,r+1]$，所以我们只需要从新判断这两个位置的数的关系是相同的还是不同的，并作出修改就好了。 如何得知修改后每个数是 $0$ 还是 $1$？我们可以维护一下每个数字被取反了几次，修改时区间加上 $1$，设这个数被取反了 $k$ 次，原始的值是 $0/1$，那么查询就是 $(k\mod 2 + 0/1) \mod 2$。区间加、单点查询用差分就可以维护。 时间复杂度 $O(Q \log N)$。 Code:12345...

本题考虑使用二分答案。 思路关于本题单调性的证明：因为显示器的宽度越大，一行能显示的宽度越多，所以显示需要的行数越少（单词总量不变）。所以显示器的宽度和显示需要的行数具有单调递减的关系，所以可以使用二分。 二分枚举显示器的宽度 $w$，然后计算以 $w$ 为宽度显示单词需要的最少行数，如果需要的行数小于等于 $m$，则符合要求，否则不符合要求。 怎么计算呢？ 如果显示器的宽度 $w$ 小于单词的最大宽度 $mw$，说明一个单词都无法放进显示器中，显然是不符合要求的。 令 $sum$ 表示当前行已经用了多少宽度，$cnt$ 表示当前用了多少行，一次枚举单词的长度 $l_i$，如果当前宽度加上一个空格和 $l_i$ 的长度大于 $w$，说明当前行已经放不下这个单词了，需要新开一行，让 $cnt$ 加 $1$，并且让 $sum$ 等于 $l_i$，否则 $sum$ 加上 $l_i$ 和一个空格的长度。 时间复杂度：二分的复杂度是 $O(\log n)$，计算一遍的复杂度是 $O(n)$，整体时间复杂度 $O(n \log n)$。 代码123456789101112131415161...

我提供一种奇特的解法。 思路暴力枚举左上角坐标 $(x_1,y_1)$ 和右上角坐标 $(x_2,y_2)$ ，然后用二维前缀和判断一下有没有沼泽地，最后算一下面积，取最大值 就是答案。 时间复杂度 $O(n^4)$ ，很明显会超时。 暴力代码： 123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>using namespace std;int sum[1145][1145];int query(int x1,int y1,int x2,int y2){ return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];}int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ char s; cin>>s; ...

思路首先我们思考朴素的 dp 方程。 定义状态首先定义 $dp_i$，表示当前最后一个分区是以 $i$ 结尾时均势区和更赛牛较多区的和的最小值。 然后我们定义 $cnt_i$ 表示 $[1,i]$ 范围内更赛牛减荷斯坦牛的数量，所以 $[l,r]$ 范围内更赛牛减荷斯坦牛的数量就是 $cnt_r - cnt_{l-1}$，在读入时只需要碰到字符 G 加 $1$，碰到字符 H 减 $1$ 就可以了。 转移方程我们假设倒数第二个区间是以 $j$ 结尾的，则最后一个区间的范围是 $[j+1,i]$。由于一个区间的长度大于 $1$ 小于 $k$，所以 $j$ 的范围是从 $i-k$ 到 $i-1$。枚举每一个 $j$，如果 $sum_i-sum_j\geqslant0$，也就是说 $[j+1,i]$ 这个区间是一个均势区或更赛牛较多区，$dp_i=dp_j+1$，否则这不是均势区或更赛牛较多区，$dp_i=dp_j$，最后对所有的 $j$ 转移来的情况区最小值，方程如下： $$ dp_i=\min\limits_{j=i-k}^{i-1} \beg...

题目中 你需要求出有多少整数可能成为 $b$ 的众数。 想表达的意思应该是 你需要求出有多少种数可能成为 $b$ 的众数。 吧。 所以你输出的是能成为众数的种类数，而不是个数。 解法：这里我提供一种贪心的做法。 首先只需维护出每一种数出现的次数（因为题目只关心可能成为众数的数的数量）。 接下来我们思考怎样一种数才可能成为众数。 经过 $k$ 次修改以后，一种数只有在被修改后出现次数大于等于被修改后出现次数最大的那种数的出现次数时才可以成为众数。 那么每一次修改是什么呢？ 想要让第 $i$ 种数成为众数，对于每一次修改，我们将除了第 $i$ 种数外的一个数修改为第 $i$ 种数。这样就让第 $i$ 种数出现的次数 $+1$ ，让除了第 $i$ 种数外的一种数出现的次数 $-1$ 。不难想到，这样可以让第 $i$ 种数出现的次数最大。 具体来说，设第 $i$ 种数出现的次数为 $v_i$ ，那么它在被操作 $k$ 次后出现的次数为 $v_i+k$ ，设经过操作后的最大出现次数为 $x$ ，那么第 $i$ 种数能成为众数的条件是： $$v_i+k \geq x$$ 因为 $v_...

这是一道很简单的模拟。 解题思路：我们定义两个变量 $cnt1$ $cnt2$，分别用于记录上一个连续 $0/1$ 区间的长度和这一个连续 $0/1$ 区间的长度。只要这个连续区间的长度不等于上个区间的长度，那么直接输出NO，然后return 0就可以了(因为这里不一样后面就无需判断，这是一个小优化)。如果相等，那么 $cnt2$ 清零，重新计算新的连续区间的长度，以此类推计算就可以了。 那么这个过程怎么实现呢？ 对于代码实现来说，对于当前的 $a_i$ 来说，分两种情况： 如果 $a_i$ 等于 $a_{i-1}$ ，那么说明还在当前的区间中，那么 $cnt2+1$ ，长度加 $1$ 。 如果 $a_i$ 不等于 $a_{i-1}$ ，那么按照上面的思路判断就可以了。 这里需要注意一些细节：加一个特判，判断 $cnt1$ 是不是 $0$ ，并在cnt2=1前面把 $cnt1$ 修改为 $cnt2$ ，就可以了。然后把 $a_{n+1}$ 赋值为 $2$ ，循环到 $n+1$ 就可以处理最后一次的问题。 ps：一定要从 $2$ 开始循环，要不然会出问题...

update：有一个图挂了，我重新补上，管理求过 这道题不难，主要考察的是数学知识。 前铺：欧几里得距离首先我们都知道，两点之间线段最短，如下图所示： 这个距离很好求，我们把 $A$ 点和 $B$ 所在的轴画出来，如下图所示： 很容易看出来这三条线构成了一个直角三角形。根据勾股定理，我们就求出了距离公式，如下： $$\large{dis(i,j)=\sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}}$$ 这个距离公式也是现在最常用的距离公式。 切比雪夫距离切比雪夫距离用于解决格点上的距离问题。这类问题只能向自己点的上、下、左、右、左上、左下、右上、右下方向走。 在这个问题中，每走一个斜线和走一个直线的距离相同。那我们想要距离最短，那就按照欧几里得距离的思想，尽量先走斜线到对方的横坐标上，在走直线到达对方的点，如下图所示： 这就是当前问题下的最短距离。 那么怎么算出距离呢？ 因为棋盘的性质，走一个斜线等于走一个直线的距离，所以只需要求出两边距离的最大值就可以了。公式如下： $$\large{dis(i,j)=\max(|x_i-x_j|,|y...

回文数判断前面几位大佬已经讲的很清楚了，我讲一种新的 STL 做法。 这里介绍两个函数，reverse()和to_string()。 to_string()函数to_string()是在 C++11 中新加入的函数，定义于<string>头文件中。用法为to_string(val)，其中val可以是int,long,long long,unsigned int,unsigned long long,fload,double,long double类型。其作用是将数字转换成字符串。 reverse()函数reverse()函数是一个可以翻转数组，string，vector等数据结构的函数，定义于<algorithm>头文件中。用法为reverse(p1,p2)，p1为前指针，p2为后指针。 123reverse(array,array+a_length) //数组reverse(str.begin(),str.end()) //stringreverse(v.begin(),v.end()) //vector 明白之后代码就简单多了。 Code：12345...