- 博客(74)
- 收藏
- 关注
RSS订阅原创 error while loading shared libraries: libpython3.9.so.1.0
类似这种找不到共享库的问题一般都是本地有，但安装的时候只安装在了下载的目录下，感觉都可以这样操作，目前还没发现有什么副作用。中寻找，所以需要在该文件夹中添加路径文件指导编译的时候寻找链接库。查询动态链接库时也会查看缓存的路径，在。所在文件夹的位置即可。文件夹里面应该就有这个文件。等等默认文件夹中找不到。，只要把搜索路径加上。
2023-05-29 19:34:53
2866
原创 Codeforces Round #767 (Div. 1) E. Groceries in Meteor Town
题解还是妙啊。考虑每条边在什么时候成为答案，可以把边按照权值排序，从大到小枚举，对于当前枚举的边，它能将树分成两部分，只要路径的起点和终点分别在这两部分，当前边就成为答案。然后可以删掉这条边，递归子部分操作。如何快速求两个点路径之间的边权最大值呢？这里真的很妙，将每条边看作一个节点，按照上面的方法，每次删掉一条边，就将这条边所代表的节点和他分开的这两部分下一步要删的边分别连边，递归操作就可以形成一颗二叉树，而这个二叉树具有第一个极好的性质：我们将原树中每个点挂在他所连边代表的节点中深度最大的节点上，此时
2022-01-26 14:31:59
252
原创 Codeforces Round #728 (Div. 2) D. Tree Array
一道概率题。题意不再赘述。讲一讲思路。由于题目的图形为一棵树，而初始节点为随机的，所以第一步需要枚举根节点，由题意得每个点为根的概率为1/n。题目求逆序对的期望，稍作思考，此题如果考虑序列对结果的贡献会非常复杂，因而转换思路，考虑将考虑范围缩小，直接考虑任意两点对结果的影响，这就用到了数据结构课上所经常提到的指示器变量的思想，很多时候能够巧妙化简问题。两个点的贡献就是一个指示器变量，对于任意两点x,y，不妨设x<y。如果先访问y，那么这对节点的贡献即为1，否则为0。所以要求期望，我们只需要求出先
2021-07-20 10:55:30
73
原创 记扩展欧几里得算法的学习
为了解决形如ax+by=c的方程求解问题而应运而生的算法就是扩展欧几里得算法，没想到学了高等代数相关知识后温习这个的证明也变得简单多了。完全可以将其的某些性质和多项式的那些定理等价，证明什么的也都如出一辙。而其求解与辗转相除法密不可分。首先如何证明辗转相除法的正确性呢？a = bq + r，那么若x = gcd(a, b), y = gcd(b, r)即证x=y; 由等式易知x|a&&...
2020-03-28 17:18:36
125
原创 2019-ICPC沈阳J题Graph
写这篇博客也是为了方便自己以后能够快速回顾LCT，再探索其其他的用途以后回顾LCT可以参考这篇博客：写的很清楚题目如下Rose would like to find whether they truly love each other.Rose lets Jack draw a graph of N vertices, and Rose herself writes a set of ve...
2020-03-12 18:29:18
209
原创 [NOI2016]优秀的拆分
题目实际上要求我们求从每个点出发的AA串的数量考虑点i的答案，发现如果前缀i与前缀j(j<=i)的最长公共后缀>=i-j，那么i点出发向前就存在一个长度为i-j的AA串，题目即求对于每个前缀，有多少个在他之前的前缀满足条件考虑后缀自动机，由于每个前缀都是后缀自动机parent树上的一点，即两个前缀的最长公共后缀为两个前缀点在parent树上的lca的len长度。考虑在lca处统...
2020-02-23 22:25:32
104
原创 BZOJ 4560 [JLOI2016]字符串覆盖
这是一道如果没想清楚就不要乱打的题目， 否则就像我一样～～题目描述字符串A有N个子串B1,B2,…,Bn。如果将这n个子串分别放在恰好一个它在A中出现的位置上（子串之间可以重叠）这样A中的若干字符就被这N个子串覆盖了。问A中能被覆盖字符个数的最小值和最大值。 输入输出格式 输入格式：第一行包含一个正整数T，表示数据组数。保证T接下来依次描述T组数据，每组数据中：第一行包含
2018-01-08 14:57:44
510
原创 HNOI2017 spaly题解
终于调过了，决定把这份巨屎无比的冗长代码贴上来 解题思路： 主要在于发现两个题目的性质： 1.对于插入操作，插入的元素只可能作为他前驱的右儿子或者后继的左儿子 2.旋转最大最小值，并不会改变树的结构，实质上就是把要删除的那个元素直接提到根节点（模拟即可证明）有了这两条性质，我们可以发现只需要维护这棵树的形态并能够在log内的复杂度求树上某个点的深度 于是我们就可以想
2017-12-17 09:24:36
238
转载 清华月赛 Yazid的新生舞会题解
算法一（针对n≤300n\leq 300的测试点）考虑枚举所有区间，然后求其众数及出现次数，并判断是否超过区间总长的一半，统计答案即可。时间复杂度O(n3)O\left( n^3\right)算法二（针对n≤2,000n\leq 2,000的测试点）考虑先枚举区间的左端点ll，再从左到右枚举右端点rr并用数组维护每个数的出现次数，同时使用变量维护当前众数、众数的出现次数。不难发现，当右端点向右移动时
2017-11-27 10:10:14
951
转载 清华月赛 大吉大利晚上吃鸡题解
《大吉大利，晚上吃鸡！》题解出题人：陈宇验题人：刑健开(jkxing)题目简述给定一张有边权（边权全为正）的无向图， nn 个点 mm 条边，给定起点 SS 和终点 TT ，问有多少对 AA 和 BB 满足从 SS 到 TT 的任意最短路一定经过 AA 或者 BB ，但是不存在某条最短路同时经过 AA 和 BB 。解法一首先是最暴力的解法，枚举任意点对 AA 和 BB ，然后删掉 AA 和 BB ，
2017-11-27 09:23:41
784
原创 NOIP2017滚粗记
落榜后 【唐】ergeda 昔日龌龊不足夸，今朝郁闷思无涯 欲哭无泪马失蹄，摔在地上摩擦我此时的心情，大约的确是如此吧*****游记的分割线*****Day0 不知道该干什么。 早上拉着脑普文比赛打模板被吊虐（果然还是比不过某键盘侠）中午吃了一顿饱的休养生息，下午脑煜勋开始疯狂立flag “今年肯定又要考树了”， “NOIP什么时候考过图论啊”， 我居然还
2017-11-24 13:45:55
300
原创 多重背包的优化
好久没写博客，今天认真写一波～ 多重背包问题： 有N种物品和容量为V的背包，若第i种物品，容量为v[i]，价值为w[i]，共有num[i]件。怎样装才能使背包内的物品总价值最大？ 复杂度O(n * V * sigma(num[i]))的算法大家学完01背包应该就会了 dp[j] = max(dp[j], dp[j - k*v[i]] + k * w[i]);(0<=k<=min(num[i]
2017-10-12 19:13:18
326
原创 [SDOI2011]消防
题目描述某个国家有n个城市，这n个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为zi(zi这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。现在这个国家的经费足以在一条边长度和不超过s的路径（两端都是城市）上建立消防枢纽，为
2017-09-14 22:09:03
307
原创 后缀数组
好多年一直听到这个东西，不久前还研究过一次，但始终没有真正理解，短短的二十行代码，每次都是无功而返，就算打了模板最后还是忘得一干二净，今天难得大花了一比时间先把get_sa给稍微弄清楚了，这里仅对于代码谈谈自己的理解（至于大部分的思想可以参照网上其他的博客和罗穗骞的论文）。后缀数组，我们要做的第一步也就是给后缀排名，但为了优化复杂度，代码还是大有讲究的，利用倍增的思想以及基数排序，妙哉！首
2017-06-22 21:10:48
428
2
原创 bzoj 1901 && P2617 Dynamic Ranking
题目描述给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对
2017-06-14 22:12:03
362
原创 分块【线段树模板】
线段树的一些操作其实用分块也可以很方便就做掉，至于时间效率也不会慢很多，主要是好写对于区间加法一样用lazy数组标记，如果区间覆盖整块，则把块给标记上，否则暴力加减，维护sum和lazy数组#include "cmath"#include "cstdio"#include "cstdlib"#include "cstring"#include "iostream"#inclu
2017-06-08 14:17:05
358
原创 P1351 联合权值 noip提高组2014
题目描述无向连通图G 有n 个点，n - 1 条边。点从1 到n 依次编号，编号为 i 的点的权值为W i ，每条边的长度均为1 。图上两点( u , v ) 的距离定义为u 点到v 点的最短距离。对于图G 上的点对( u, v) ，若它们的距离为2 ，则它们之间会产生Wu×Wv 的联合权值。请问图G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？输入
2017-06-08 12:19:52
502
原创 P3329 [ZJOI2011]最小割
题目描述小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话： ”对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t不在同一个部分中，则称这个划分是关于s,t的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而s,t的最小割指的是在关于s,t的割中容量最小的割“现给定一张无向图，小白有若干个形如”
2017-06-05 11:16:46
418
原创 P2738 [USACO4.1]篱笆回路Fence Loops
题目描述农夫布朗的牧场上的篱笆已经失去控制了。它们分成了1~200英尺长的线段。只有在线段的端点处才能连接两个线段，有时给定的一个端点上会有两个以上的篱笆。结果篱笆形成了一张网分割了布朗的牧场。布朗想将牧场恢复原样，出于这个考虑，他首先得知道牧场上哪一块区域的周长最小。 布朗将他的每段篱笆从1到N进行了标号（N=线段的总数）。他知道每段篱笆有如下属性：该段篱笆的长度该段篱笆的一端所连接
2017-05-06 10:36:17
486
1
转载 莫队算法——解决序列上询问的利器
问题： 有一个长为N序列，有M个询问：在区间[L,R]内，出现了多少个不同的数字。（序列中所有数字均小于K）。题目会给出K。莫队算法就是滋磁解决这类问题的离线算法。（其实很简单）首先来看看暴力： 由于暴力还是比较水的，所以直接上：#include using namespace std ;const int maxn = 50010 ;int n, m, a[maxn]
2017-03-29 19:20:02
347
原创 P1519 穿越栅栏 Overfencing
题目描述描述 农夫John在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。幸运的是，他在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是，他所建造的迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。给定迷宫的宽度W(1+-+-+-+-+-+| |+-+ +-+ + +| | | |+-+-+ + +| | |+-+ +-+-+-+（
2017-03-22 22:19:43
656
原创 P2737 [USACO4.1]麦香牛块Beef McNuggets
题目描述农夫布朗的奶牛们正在进行斗争，因为它们听说麦当劳正在考虑引进一种新产品：麦香牛块。奶牛们正在想尽一切办法让这种可怕的设想泡汤。奶牛们进行斗争的策略之一是“劣质的包装”。“看，”奶牛们说，“如果你只用一次能装3块、6块或者10块的三种包装盒包装麦香牛块，你就不可能满足一次只想买1、2、4、5、7、8、11、14或者17块麦香牛块的顾客了。劣质的包装意味着劣质的产品。”你的任务是帮助这
2017-03-21 21:48:26
1161
原创 P2750 [USACO5.5]贰五语言Two Five
题目描述有一种奇怪的语言叫做“贰五语言”。它的每个单词都由A～Y这25个字母各一个组成。但是，并不是任何一种排列都是一个合法的贰五语言单词。贰五语言的单词必须满足这样一个条件：把它的25个字母排成一个5*5的矩阵，它的每一行和每一列都必须是递增的。比如单词ACEPTBDHQUFJMRWGKNSXILOVY，它排成的矩阵如下所示：A C E P TB D H Q UF J M R W
2017-03-21 20:37:20
617
原创 （bzoj 1082）（SCOI2005）栅栏
题目描述农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为10的木板可以切成长度为8和2的两个木板。你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木
2017-03-17 14:47:33
387
转载 floyed详解
显然Floyed算法是一个简短而好理解的算法，这里指的好理解是 因为Floyed的代码长度不大，实在没理解都可以背下来，所以说是好理解，实际上是真的好理解吗？我们来看看最基础的FloyedFloyed是什么？自然是用来求多源最短路的啦，时间效率是O(n^3)，有人会问那我不对每个点做一遍SPFA或dijkstra堆优化，时间效率是O(n^2logn)那不是快很多？实际上因为Floyed
2017-03-16 16:43:29
688
原创 bzoj 2824: [AHOI2012]铁盘整理
题目描述输入输出格式输入格式：共两行。第一行为铁盘个数N（1输出格式：一个正整数，表示使铁盘从小到大有序需要的最少翻转次数。输入输出样例输入样例#1：52 4 3 5 1输出样例#1：5此题乍一看数据范围极小，自然以为是水题，便想用bfs直接水过去，结果很满意的得了10分，以下是暴力程序：#include#incl
2017-03-16 10:41:12
845
原创 noip2009靶形数独
题目描述小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有
2017-03-11 09:10:51
375
转载 单调队列
单调队列今天问了长者有关单调队列的知识，单调队列这种东西其实用途并不是特别的广泛，只是在处理区间上询问的时候比较管用，而且这种询问有限制，比如： 一个含有n项的数列(n这种类似的题目，每次询问前m个数中最小的，显然暴力的话是O（n * m）的每个点枚举一遍m，就是这样，但是暴力显然会TLE，那有什么办法呢？ RMQ是可以的，但是有一个问题，就是MLE，2000000 * 20，
2017-03-04 11:25:47
315
转载 网络流详解（好文章啊）
网络流最近在学习二分图匹配，网络流和博弈论(%eazy,miaomiao,lsr_dalao,zyh,zlt),感谢诸位牛犇给蒟蒻的讲课，让我受益匪浅，PPT就不放上来了，有版权问题，下面我给大家谈谈我近期学习网络流的心得。（因为前几天感冒落了些进度，感谢ergeda和脑屁股的细心辅导）。微笑吐舌头一：what is 网络流？？？根据lsr_dalao的ppt上所言： 定义：
2017-02-12 15:35:30
655
1
原创 小玉买文具
题目描述班主任给小玉一个任务，到文具店里买尽量多的签字笔。已知一只签字笔的价格是1元9角，而班主任给小玉的钱是a元b角，小玉想知道，她最多能买多少只签字笔呢。 输入输出格式 输入格式：输入的数据，在一行内，包括两个整数，依次表示a和b，a<=10000,b<=9。输出格式：输出一个整数，表示小玉最多能买多少只签字笔。输入输出样例 输入样例#1：10 3输出样例#1：5直接根据实际知识运用一下就
2017-02-12 14:59:29
573
转载 poj 2449 A*
题意：大意是 有N个station 要求从s点到t点 的第k短路 （不过我看题意说的好像是从t到s 可能是出题人写错了）思路： 这是一道 经典的第k短路算法，只要你会就能过。PS：这也是我第一k短路题 学到了很多新的东西 因为没学过A* 算法 所以在网上找了好久，但讲了都不是清楚 解题报告也都不带注释的 这里我就附上详细的解题报告 也好给以后要学的人 一点帮助。从这题中还真的学到了很多 1.第k短
2017-02-10 14:49:10
210
原创 USACO P1457 城堡 The Castle
//代码虽然长了点，但应该相当清楚吧~~~ //考虑一二问，只需dfs一遍即可求出答案(根据8>4+2+1,4>2+1,2>1，可以判断哪边有墙)#include<cmath>#include<algorithm> #include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>using namespace st
2017-02-05 15:54:49
473
原创 spoj 375 Query on a tree——(树链剖分orLCT动态树)
You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.We will ask you to perfrom some instructions of the following form:CHANGE i ti : chang
2017-01-21 22:22:44
369
1
原创 Corn fields poj 3254 （状压dp入门）
状态压缩动态规划： 动态规划的状态有时候比较恶心，不容易表示出来，需要用一些编码技术，把状态压缩的用简单的方式表示出来。典型方式：当需要表示一个集合有哪些元素时，往往利用2进制用一个整数表示。再普及一下位运算：& 按位与 如果两个相应的二进制位都为1，则该位的 结果值为1，否则为0| 按位或 两个相应的二进制位中只
2017-01-21 16:53:53
290
原创 食物链（并查集）
题意题目描述动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B吃 C，C 吃 A。现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这 N 个动物所构成的食物链关系进行描述：第一种说法是“1 X Y”，表示 X 和 Y 是同类。第二种说法是“2 X Y”，表示 X 吃 Y 。此人对 N 个动物
2017-01-21 16:40:43
472
原创 近日计划
现在欠下的任务还是很多，主要必须在近期解决的有： 1.左偏树第二题； 2.毫无头绪的后缀树 3.要把LCT写几篇博客，并写一道跟边修改权值，求边权和有关的题目 若还有时间要把凸包的代码给禡一遍。 跟上每天的讲课，至少每个专题做一道题~~~
2017-01-19 16:46:41
360
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人