zsyzClb-CSDN博客

原创 CF1841F Monocarp and a Strategic Game

于是，我们把所有的向量挪到原点，并按照极角排序，然后将一条过原点的直线旋转，并不断统计直线一侧的向量之和，答案即使最大值。以内的向量全部做垂线到这个方向上（并且称这些向量为这个方向的集合），然后全部加起来即可。显然，答案即使和最大的方向。然后根据题目的提示，感觉可以转化成一个平面图来做，也就是选择若干个向量使得它们的和的模最大。后面瞄了一眼题解，发现用的是一种叫做闵可夫斯基凸包的做法，但从具体做法来讲和我的差不多。的，对于一个集合并不需要去考虑具体方向的值，只要把向量全部加起来即可。

2024-01-31 10:44:53 545 1

原创欧拉图相关的生成与计数问题探究

最近学了一波国家集训队2018论文的最后一个专题。于是带上了一些我的注解。先放一波这个论文1.基本概念欧拉图问题是图论中的一类特殊的问题。在本文的介绍过程中，我们将会使用一些图论术语。为了使本文叙述准确，本节将给出一些术语的定义。定义 1.1.图 G 中与顶点 v 关联的边数（自环统计两次）称为图 G 中顶点 v 的度。特别地，对于有向图 G ，进入顶点 v 的边的条数称为顶点 v ...

2023-10-25 16:04:50 587 1

原创带你从一个不同的角度体会后缀自动机的从无到有

在网上看了很多后缀自动机的题解，感觉他们都不是真正理解了这个算法。他们大多都喜欢罗列大量的性质和引理，并且对着大量片面、冗杂、令人头晕目眩的实际情况进行不修边幅的分类讨论，最后还要对着原本很简洁的代码进行复杂得令人令人发指的强行解释。我写这个文章的目的就是想揣测一下算法发明者的思想，让大家能更加简单并且全面的理解这个算法。再次声明一下，本人只学习到了parent-tree，并自己根据自己的理解把后缀自动机剩下的部分（构造）完善了出来，能够通过洛谷的模板，所以大家可以相信我的逻辑。

2023-09-26 12:46:13 119

原创 [IOI2019] 天桥

现在考虑正解，由于对称性，这里我们只讨论起点不在边界的其情况，这种情况会多增加三种类型的天桥：全部在在起点左边，包括起点，但起点的建筑够不到/够得到。如果够不到，我们依然要尝试尽可能早的上桥，因此只用取起点建筑左边第一能上桥的建筑和右边第一个能上桥的建筑。根据贪心的策略，高处的天桥一定会优于低处的天桥，因此我们可以对行走方式增加两条法则：1.不提前下天桥（要么上到别的天桥，要么就一直走到头）；总的来说，这道题的思路不算很难，但是代码很难打，每一个板块的细节都很多，调试了很久才过。

2023-07-16 17:50:28 174

原创 TimusOJ 2042.Nikita

题意给你一个字符串sss和一个kkk，有mmm次查询，每次查询以后两种，第一种将字符串的一个区间修改成同一个字符，第二种是查询字符串一个区间内长度不超过k的回文串的个数。其中1<=∣s∣,m<=1051<=|s|,m<=10^51<=∣s∣,m<=105，1<=k<=501<=k<=501<=k<=50。Solution做这个题我真的花了很久，我第一次做这个题实在八月份，没有AC，到了11月份我重新想了一下这个题，用一个更加优秀

2021-11-05 19:50:44 192

原创 2017提高组初赛问题求解2

如图所示，A到B是联通的。假设删除一条细的边的代价是1，删除一条粗边的代价是2，要让A，B不连通，最小的代价是___，最小代价的不同方案数是__。我突然想到了一个很妙的方法。我们把图里面的每个空格都看成一个点，将图形A,B之上的空白部分当作ST，之下的当成ED，然后图就变成这个样子。接着我们对此建一个图，最短路计数一下即可，以下是建出来后的图。(其中粗便以经标注了2，省略了一下一些不需要的边，括号中的数分别表示最短路和最短路的方案数）故答案为:4,9...

2021-09-18 10:09:33 276 1

原创 CF1548D2 Gregor and the Odd Cows (Hard)

题意：网格图上有n个点，不存在三点共线的情况，求面积为整数，内部点的个数为奇数的三角形个数。Solution简单的版本我做出来了，但是难的还差一点，主要是有几个性质没有发现。观摩大佬的做法，结合自己的理解写了一下题解。这道题其实就是一道找性质的题，我们很容易联想到皮克定理，即S=a+b2+1S=a+\frac{b}{2}+1S=a+2b+1。这样就能够把求内部的点转化成求边上的点。然后我们在联系两个公式，一个是S=∣x1∗y2−x2∗y1∣2S=\frac{|x1*y2-x2*y1|}{2}S

2021-09-05 20:52:55 156 1

原创 TimusOJ 1577. E-mail

题意：给你两个字符串，定义第三个字符串是同时包括两个字符串的最短字符串，让你求第三个字符串的个数。Solution这道题我被我自己误导了。以前我貌似做过类似的题，不过当时没有做出来，原因是我不知道怎么处理重复的情况。然后这道题我想了很久处理重复的方法，不过貌似都不行，后面发现我是想复杂了。（注：f[i][j]f[i][j]f[i][j]表示的是最小值，a[i][j]a[i][j]a[i][j]表示的是第三个字符串，sum[i][j]sum[i][j]sum[i][j]表示的是个数）后面我仔细想了

2021-08-28 15:28:58 104

原创 TimusOJ 1476. Lunar Code

题意：给你n,mn,mn,m，让你求满足对于每一列jjj，满足a[i][j]=0,a[i][j+1]=1a[i][j]=0,a[i][j+1]=1a[i][j]=0,a[i][j+1]=1的iii不超过kkk个的01矩阵的个数。Solution我的思路一开始跑偏了。我把满足a[i][j]=0,a[i][j+1]=1a[i][j]=0,a[i][j+1]=1a[i][j]=0,a[i][j+1]=1的点设置为111，其他的点我设置为000，然后我尝试以行为状态，但是这样的状态数高达一亿多，还要记录每一行

2021-08-26 10:33:40 159

原创 TimusOJ 1395. Pascal vs. C++. Version 1，2

题意：给你n个数，让你找最长的等差数列。Solution想了好久，突然想出了一个非常妙的做法。首先用hash来记录每一个数（下标）。然后暴力枚举等差数列的第一项和第二项，假设两个数分别为x,yx,yx,y，判断如果2∗x−y2*x-y2∗x−y存在，就说明这个等差数列已经被找过，就不用管了，如果没有就暴力跳着找，输出的时候再跳一次就好了。Code#include<bits/stdc++.h>#define ll long long#define gc getchar#defin

2021-08-20 16:19:15 102 1

原创 1223. Chernobyl’ Eagle on a Roof

题意：n层楼，m个蛋（一样），每次实验从指定的楼层往下扔一个蛋，用最少的次数测试出最高的能使蛋摔下去不破裂层数。Solution不得不承认，这一道题的思路很妙。首先，不难想到一个O(n3)O(n^3)O(n3)的暴力：枚举楼层扔蛋，所需的实验次数就是max(s1,s2)+1max(s_1,s_2)+1max(s1,s2)+1，其中，s1s_1s1表示蛋破裂后的实验次数，s2s_2s2表示蛋不破裂的实验次数，然后找一个最小的楼层就可以了。#include<bits/stdc++.h&g

2021-08-18 11:48:32 103

原创 1171. Lost in Space

题意：有nnn层4∗44*44∗4的格子，每个格子有一个权值，你要从第111层的起点走到第nnn层的任意一个点，每一从只有一些格子能去到下一层，每个格子不能重复经过，求最大的平均权值。Solution这道题看起来不算难，但做起来会发现挺恶心的，卡空间卡得特别厉害。我花了差不多一个上午的时间AC这一道题。为了节省数组的空间，我们先处理每一层的内部，因为路径的条数十分有限，我们可以直接用暴力来处理。定义f[floor][x1][y1][x2][y2][k]f[floor][x_1][y_1][x_2][

2021-08-17 15:23:40 93

原创 2014. Zhenya moves from parents

这其实是一道傻逼题，但是花了我很多的时间去想。我的思路是根据暴力的做法来优化成正确的做法先给出暴力的代码：int ans=0,now=0;for(int i=1;i<=n;i++){ now+=a[i]; if(now<0)ans+=now,now=0;}很容易发现根据这一段代码可一个把数列分成很多个段，然后我的思路就开始出错了，我尝试用各种办法来维护段，但是每一种想法都会超时。后面我仔细想了想，发现如果从整体来看，结果就是一段前缀和，毕竟最后是要把每一段全部加起来。然

2021-08-11 14:56:54 81

原创 1560. Elementary Symmetric Functions

这是一道很有意思的题目。首先整体上看过去，有单点修改和区间查询的操作，所以基本可以确定用线段树来做。然后仔细观察一下，可以发现一个非常有意思的性质。我们考虑将两个区间合并，s[0/1][5]s[0/1][5]s[0/1][5]表示两个区间的S函数。如果在每一个区间都选择两个数，那么贡献值就是(∑l1<=x1<y1<=r1a[x1]∗a[y1])∗(∑l2<=x2<y2<=r2a[x2]∗a[y2])=s[0][2]∗s[1][2](\sum_{l_1<=x_

2021-08-05 10:19:02 138

原创 AtCoder Grand Contest 001

A很明显排个序就行了。#include<bits/stdc++.h>#define ll long long#define gc getchar#define pc putchar#define pii pair<int,int>#define mp make_pair#define fi first#define se second#define rep(i,x,y) for(int i=x;i<=y;i++)#define dwn(i,x,y) for

2021-04-23 13:05:08 110

原创 CF1470B Strange Definition

先把这个公式变形一下lcm(x,y)gcd(x,y)=xgcd(x,y)∗ygcd(x,y)\frac{lcm(x,y)}{gcd(x,y)}=\frac{x}{gcd(x,y)}*\frac{y}{gcd(x,y)}gcd(x,y)lcm(x,y)=gcd(x,y)x∗gcd(x,y)y。然后我们可以发现右边两项是互质的，但是这两项的乘积是一个完全平方数，这说明这两项都是完全平方数，同时就可以知道x，y的每个质因子的幂奇偶性相同。当w=0，我们就可以试着把奇偶性相同的归为一个集合，所以只用求最大

2021-03-20 16:39:39 102

原创 CF1493E Enormous XOR

神奇的题目。。。首先很明显，如果l，r最高位不全是1，那么答案肯定每个数位都是1，如样例一对于其他的情况，我们尝试着把r中0的位置给变成1。我把二进制列出来以后，发现只有最低位置才有可能从0变成1（只要r-l>=2就可以)#include<bits/stdc++.h>using namespace std;const int N=1e6+10;int n;char s1[N],s2[N];void add(){ s1[1]++; for(int i=1;i<=n

2021-03-20 14:50:11 143

原创 1495D BFS Trees

一道有趣的题目。因为n和m都很小，所以应该是枚举两个点来求方案数。我们先要bfs两次把每个点离i，j的的距离求出来，然后我们可以发现，对于一个点。然后利用转化思想，把两个点变成x和y坐标放到平面直角坐标系上面去。然后自己手玩一下最普遍的生成树，i和j之间有一段路径，这个路径的每个点都有一写子树。把这个图弄到坐标系上面去就是（个数）：i处在5的位置，j处在E的位置，那一段1是他们之间的路径，然后？表示接在路径上面的点（因为个数不确定）。然后我们可以发现，路径上面只能是1，因此要特判这种情况。又很

2021-03-19 13:09:16 131

原创洛谷P5385 [Cnoi2019]须臾幻境

一个挺有意思的题目。先把每一条边用编号当作边权，从第一条边开始扫描，用LCT维护当前的最大生成树。再用主席树记录删除的边即可。我在add函数写错了，调了好久。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#define ll long longusing namespace std;template<

2021-02-24 21:50:48 145

原创 [USACO18FEB]New Barns P

题目的意思是让我们动态维护直径。很容易得到以下两个定理：1.两棵树合并以后的直径端点是原来两棵树的四个直径端点中的两个；2.距离一个点最远的点一定是一个直径的端点。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>using namespace std;template<typename T>inl

2021-02-23 17:19:17 134

原创 [TJOI2015]旅游

很容易想到要用动态树来维护。不过这一道题我被恶心了一下，主要是翻转操作会影响结果，所以应该同时维护从左到右和从右到左的结果。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>using namespace std;template<typename T>inline void qr(T &x){

2021-02-23 16:16:54 100

原创 P5489 EntropyIncreaser 与动态图

题意：动态加边，求两点间割边和割点的个数。我们可以用LCT来做：对于割边，先是要以点代边，边权1，点权0，我们发现在一个环上的边全部都不是割边，所以如果添加的边的两个端点已经联通，我们就把路径上的全部点权值设置为0.对于割点，我们动态维护圆方树，如果加一条边就会形成和环，那么就把环完全断掉，把环上的每一个点（方点和圆点）全部连在一个新的方点上。可以发现原来环上的任意两个点之间的距离都是2，所以能够保证时间复杂度。查询就输出圆点个数。#include<cstdio>#include&lt

2021-02-22 12:47:42 312

原创 [NOI2014]魔法森林

把每条边的ai从小到大排序然后不断插入每一条边，然后就是要维护是的1到n的路径中最大的bi最小首先我们肯定是要把转化成一棵树的，对于新插入的一条边，如果两个点本来就不连通，那么就直接插入，如果联通那么插入以后就会形成一个换，我们只要再把换上的最大的边删掉，这个用动态树维护即可。对于细节的处理，可以采用以点代边的做法，即多开m个点表示边（编号为n+1~n+m），插入一条边就是连接(u,n+i)和(n+i,v)，边权就放在表示边的点上。#include<cstdio>#include&lt

2020-12-25 12:45:21 132

原创 LCT学习笔记（qtree4-7）

洛谷P4115 Qtree4大意：修改颜色，求最远的两个黑点的距离。lct有一个性质，就是对于一个splay辅助树来说，某个点的子树是现实的树上的连续的一段。很明显，首先要边权下放到叶子结点,col表示这个点的颜色，如果是黑色就是0，不是黑色就是负无穷而根据dp的思想，维护lmax表示一段路径到达这个点子树所在链的最下面一个点的最大值，rmax表示一段路径到达这个点子树所在链的最上面一个点的最大值，dat表示最长的路径，sum表示整个子树的边权和。然后我们用两个multiset分别来维护虚儿子的r

2020-12-19 17:14:24 162 1

原创 Codeforces 1452E Two Editorials

看到数据范围可以想到要用来搞。（时限有2s所以可以再加一个log）这道题的难点在于怎么判断一个人听那一个出题人，不妨画一个图。l1，r1，l2，r2表示选的两段区间（我们令l1<=l2）x，y表示当前的人有兴趣的区间如果y<=r1，那么就一定选第一个人如果x>=l2或者x>r1，那么一定选择第二个人剩下的情况（如图所示）需要列一下公式，我们尝试比较没有选的部分的大小，从而求出是选择听哪一个出题热人，选择第二个出题人，当且仅当y−r1>=l2−xy-r_1>=l

2020-12-02 14:48:39 148

原创 Educational Codeforces Round 99 A-G

A这个公式求的是末尾的0不同的个数就是位数#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>using namespace std;void solve() { char s[110]; scanf("%s", s + 1); int ans =

2020-12-02 09:59:58 112

原创 [NOIP2015]运输计划

让我来提供一个与众不同的贪心做法，不需要任何数据结构，O(nlogn)删掉一条边的贡献就是max（不包含这条边的路径的最大值，包含这条边的路径的最大值-这条边的长度）所以我们只需要先将路径长度从大到小排一次序，然后找到前i个路径的交际中的最大边，统计一下即可#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>

2020-11-28 07:36:09 135

原创 [NOIP2015]斗地主

（我成功过了洛谷的加强版）这道题肯定是不能直接贪心的，感觉状压也不是很好，最好的还是搜索。（NOIP居然考了搜索。。。）这道题的搜索只需要调整一下顺序即可。我打了6层搜索，从上往下依次是四带二，三顺子，二顺子，顺子，三带二或者三带一，大王和小王，剩下的牌。其中四带二，三带二和三带一不在搜索的时候处理带了那一张牌，放在最后贪心处理即可。因为大王小王不能放在一对，所以要多打一重搜索判断一下。#include <cstdio>#include <cstring>#incl

2020-11-27 19:11:58 138

原创 [NOIP2017]队列

这题很简单，只是码量大。用平衡树维护每一行的前m-1列，用树状数组维护第m列就行了。用上树状数组的一个优美性质就能优化到nlogn#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#define ls tr[x].son[0]#define rs tr[x].son[1]#define LL long

2020-11-26 19:06:10 134

原创「NOIP2018」旅行

朴素的做法就是删掉环上的一条边然后跑一次。如果想在优化这个代码，就要尝试找到这条删去的边，把每一个点的儿子节点的编号排一个序。对于环上的一个点，如果它想回溯，就必须要把儿子走完（当然不算下一个环上的点），所以如果下一个换上的点是儿子中最劣的，并且回溯比往下走更优，就可以确定删这条边了。#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include

2020-11-23 15:03:05 272 1

原创 loj2040「SHOI2015」零件组装机

（这道题可能是我退役前做的最后一道省选题了。。。）这个零件肯定是合并了n-1次。自己搞一搞可以发现，编号最大的零件在每一次合并都是处在大的那一个零件的，即编号最大的那个零件每次都合并一个比它小的零件。然后我们就可以通过最后一个点找到与该零件合并的所有零件，并对这些零件跑相同的做法。#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include

2020-11-06 15:07:02 187

原创 loj2038「SHOI2015」超能粒子炮・改（卢卡斯的理解和延伸+数位dp）

我们发现暴力+裸的卢卡斯可以骗到50分所以就应该朝卢卡斯的方向去想。卢卡斯是把n,k拆成两个p进制数进行统计的。注意到如果在某一位ai>nia_i>n_iai>ni，a表示当前的数，n就是给定的n，那么这个数就肯定是0。所以在p进制时n就是k的限制。有可以发现这和数位dp很像，所以用数位dp求解就行了。#include <cstdio>#include <cstring>#include <iostream>#include &lt

2020-11-05 16:29:31 136

原创 loj2037「SHOI2015」脑洞治疗仪（又发现了一个新的玄学问题！）

这不就是一个线段树无脑码农题吗？做过can you answer this questions?肯定会觉得这题很简单c:1的个数lm:左边脑洞的大小rm:右边脑洞的大小dat:最大脑洞的大小[l,r]左右区间其他线段树怎么打就怎么打有意思的是，我在loj提交的时候（洛谷不会），把快读的void改成了int就会全部tle，后面改过来就直接a了。#include <cstdio>#include <cstring>#include <iostream>

2020-11-05 10:05:27 166

原创 loj2033「SDOI2016」生成魔咒

答案是所有height之和很容易想到直接用后缀数组暴力骗60分#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#define FOR(i, x, y) for (int i = x; i <= y; i++)#define DOW(i, x, y) for (int i = x; i >=

2020-11-04 10:02:15 110

原创 loj2032.[SDOI2016]游戏（李超线段树）

这道题是裸的熟练剖分+李超线段树（公式改一下就行了）我想手推一波用线段树维护线段，但是实力不够，所以只好去%一波题解。李超线段树的思想就是维护当前区间内当x=mid时最大的线段，修改分成logn个区间每个区间下传logn次，查询nlogn#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#define l

2020-11-02 20:12:22 109

原创如何求1^k+2^k+...+n^k

今天做了一道题，要求连续幂(n<=109n<=10^9n<=109)然后我就学了一下这个做法。我们可以先从一个简单的入手，也就是k=2时，那么就有12+22+...+n2=n(n+1)(2n+1)61^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6}12+22+...+n2=6n(n+1)(2n+1)其中有一种证明, 设Tn=(n+1)3−n3T_n=(n+1)^3-n^3Tn=(n+1)3−n3，则有Tn=3n2+3n+1Tn=3n^2+3n+1T

2020-10-27 12:13:38 3989

原创 loj2018. 「AHOI / HNOI2017」单旋

因为不能直接打spaly，所以我们先手动模拟一次，找找性质。题目说的很明白，旋转的必须是最小的或者最大的。举最小的为例，它旋转到根节点并不会破坏原来的结构，而是将自己的右儿子变为父亲的左儿子，然后认根节点为右儿子，自己成为根节点，那么这个旋转只需要O（1）。对于插入操作，直觉告诉我会和前驱后继有关，后面发现真的是找前驱后继中深度大的那个点认父亲。删除的话就是旋转以后直接删除。还有维护深度，我们发现每次修改都是区间修改，所以对关键值离散化以后用线段树处理（不用管没出现的值），前驱后继就用stl的set

2020-10-14 10:33:33 135

空空如也

空空如也