- 博客(235)
- 收藏
- 关注
RSS订阅原创 SPOJ - LIS2 Another Longest Increasing Subsequence Problem（CDQ分治维护三维LIS）
题解：先考虑暴力的O(n ^ 2)的dp，那么有dp[i]=max(dp[j]+1)dp[i] = max(dp[j] + 1)dp[i]=max(dp[j]+1) if(j<i && x[j]<x[i] && y[j]<y[i])if(j < i \ \&\& \ \ x[j] < x[i] \ \&\& \ \ y[j] < y[i])if
2020-12-24 21:11:23
189
原创 UVA - 1234 Dynamic len(set(a[L:R]))（带修莫队）
题解：板子题代码：/* * @Author : Nightmare */#include <bits/stdc++.h>using namespace std;#define ll long long#define ull unsigned long long#define ld long double#define ls 2 * rt#define rs 2 * rt + 1#define PII pair<int,int>#define PDD pai
2020-12-24 18:37:07
219
1
原创 HDU - 5052 Yaoge’s maximum profit（树剖 + 线段树维护上下最值）
题解：将u -> v的有向路径拆成 u -> lca 和 lca -> v的有向路径，那么答案一定是三种情况之一：u -> lca路径上买，u -> lca路径上卖u -> lca路径上买，lca -> v路径上卖lca -> v路径上买，lca -> v路径上卖利用树链剖分将u -> lca 和 lca -> v的路径拆成一段一段的链，现在考虑怎样合并两条链假设从上到下的路径 a -> b -> c，那么a -&
2020-12-24 16:36:31
165
1
原创 ZOJ - 2112 Dynamic Rankings（带修莫队 + 权值线段树）
题解：对于区间询问，能够很快的转移，考虑莫队，因为带修改，所以加一维修改时间做带修莫队，至于区间第k小，考虑权值线段树或者主席树，这里带修改，所以我们选择将所有值离散化，用权值线段树求区间第k小即可代码：/* * @Author : Nightmare */#include <bits/stdc++.h>using namespace std;#define ll long long#define ull unsigned long long#define ld long d
2020-12-24 00:35:26
187
原创 qko 吃串
题解：考虑离线然后一个一个添加字符，这样问题就转化成了字符串T在字符串S[1, i]中出现了多少次，直接对S串建SAM，然后询问只需要拓扑排序然后求字符串T走过去的子树大小即可，但是这样很明显过于暴力了。因此我们可以利用LCT来帮助我们快速求出子树大小以达到O(nlogn)O(nlogn)O(nlogn)代码：/* * @Author : Nightmare */#include <bits/stdc++.h>using namespace std;#define ll long
2020-11-25 19:17:12
156
原创 Codeforces Round #684 (Div. 2)题解
A. Buy the String题解：循环一遍判断是否转换哪个更便宜即可代码：/* * @Author : Nightmare */#include <bits/stdc++.h>using namespace std;#define ll long long#define ull unsigned long long#define PII pair<int,int>#define ls 2 * rt#define rs 2 * rt + 1#defin
2020-11-18 19:59:13
217
原创 牛客小白月赛29 F 项链
题解：双向链表模拟即可代码：/* * @Author : Nightmare */#include <bits/stdc++.h>using namespace std;#define int long long#define ull unsigned long long#define PII pair<int,int>#define ls 2 * rt#define rs 2 * rt + 1#define gcd(a,b) __gcd(a,b)#def
2020-11-16 17:37:23
113
原创 Codeforces Round #683 (Div. 2, by Meet IT)题解
A. Add Candies题解：让所有数被加成 n * (n + 1) / 2即可代码：/* * @Author : Nightmare */#include <bits/stdc++.h>using namespace std;#define ll long long#define ull unsigned long long#define PII pair<int,int>#define ls 2 * rt#define rs 2 * rt + 1#
2020-11-16 17:16:03
244
原创 牛客小白月赛29 B 二进制
题解：因为二进制中每一位都是相互独立的，所以我们用全为0的二进制数和全为1的二进制数模拟过程，得到每一位最后变化成了0还是1即可。如果初始为0，最后为1，并且初始为1，最后为0，很显然一个异或就能解决。如果初始为0，最后为1，并且初始为1，最后为1，只需要一个或运算即可。如果初始为0，最后为0，并且初始为1，最后为0，只需要一个与运算与上一个0即可如果初始为0，最后为0，并且初始为1，最后为1，不用操作。代码：/* * @Author : Nightmare */#include <
2020-11-14 20:37:54
226
原创 Codeforces Round #682 (Div. 2)题解
A. Specific Tastes of Andre题解：全输出一样的数即可代码：/* * @Author : Nightmare */#include <bits/stdc++.h>using namespace std;#define ll long long#define ull unsigned long long#define PII pair<int,int>#define ls 2 * rt#define rs 2 * rt + 1#defi
2020-11-14 13:21:20
385
原创 Codeforces - 620E. New Year Tree
题目链接题解：颜色数比较少，考虑用二进制表示颜色，对于重复颜色的处理，直接按位与当成一种颜色就行了，询问就是答案的二进制中有多少个1就有多少中颜色了。代码：/* * @Author : Nightmare */#include <bits/stdc++.h>using namespace std;#define ll long long#define ull unsigned long long#define PII pair<int,int>#define
2020-11-12 14:45:21
88
原创 Codeforces - 1428E. Carrots for Rabbits
题目链接题解：考虑将一个胡萝卜分成K段，那么这个胡萝卜肯定是尽可能的均分才能贡献最小因为一个胡萝卜切的次数越多，x / cnt下降的越少，因此胡萝卜切的次数越多，它的平方和减少的越少那么可以用优先队列维护平方和下降的值，每次减去贡献平方和减少最多的胡萝卜即可代码：/* * @Author : Nightmare */#include <bits/stdc++.h>using namespace std;#define int long long#define ull un
2020-11-12 13:46:00
252
原创 Codeforces - 1303E. Erase Subsequences
题意：给出两个字符串S和T，最多对S串操作两次，每次操作从S串中选择一个子序列加到字符串P中，并将该子序列从S中删去，P最初为空串，问能否让P = T？题解：将T串切成两段A和B段，因为可能只需要一次操作，所以A串可以为空然后考虑dp判断让dp[i][j]表示现在已经匹配完成了A串的前i个字符，B串的前j个字符，当前在S串的哪个位置，如果选择字符与A[i + 1]相等，那么转移到S串的下一个与A[i + 1]相等字符的下标即可，B串同理，如果选择字符与B[j + 1]相等，那么转移到S串的下一个与
2020-11-11 21:44:21
139
原创 True Liars POJ - 1417
题意：有 p 个好人和 q 个坏人，好人永远说真话，坏人永远说假话。现给出一组话，问能否唯一确定每个人是好人还是坏人。题解：当 a 说 b 是好人时，如果 a 是好人，那么 b 也应该是好人，如果 a 是坏人，那么 b 也应该是坏人当 a 说 b 是坏人时，如果 a 是好人，那么 b 就应该是坏人，如果 a 是坏人，那么 b 就应该是好人那么输入的 opt = "yes"的时候，a 和 b 就应该属于同一个阵营的，否则 a 和 b 应该不属于同一阵营，用并查集维护每个集合中的人即可，但是我们还
2020-10-30 18:11:53
86
原创 Caocao‘s Bridges HDU - 4738
题意：在赤壁之战中，曹操被诸葛亮和周瑜击败。但他不会放弃。曹操的军队仍然不善于水战，所以他提出了另一个想法。他在长江建造了许多岛屿，在这些岛屿的基础上，曹操的军队很容易攻击周瑜的部队。曹操还建造了连接岛屿的桥梁。如果所有岛屿都通过桥梁相连，那么曹操的军队可以在这些岛屿中非常方便地部署。周瑜无法忍受，所以他想要摧毁一些曹操的桥梁，这样一个或多个岛屿就会与其他岛屿分开。但周瑜只有一枚由诸葛亮留下的炸弹，所以他只能摧毁一座桥。周瑜必须派人携带炸弹来摧毁这座桥。桥上可能有守卫。轰炸队的士兵数量不能低于桥梁的守卫数
2020-10-30 15:21:00
187
原创 Prince and Princess HDU - 4685
题意：有 n 个王子和 m 个公主，每个王子有 kik_iki 个喜欢的公主，每个公主都喜欢所有的王子，询问每个王子可能会和哪些公主匹配。题解：首先 n 个王子 和 m 个公主做一次二分匹配，得到匹配数最大为res，相当于右边有 m - res 个点没有匹配，左边有 n - res 个点没有匹配。所以可以加入 m - res 个王子喜欢所有的公主，加入 n - res 个公主被所有的王子喜欢，加入后的新图一定是一个完美匹配。然后跑一次强连通如果u，v属于同一连通块，那么相当于连通块中的王子公主
2020-10-30 14:45:01
95
原创 Strongly connected HDU - 4635
题意：给定一个有向图，求最大可以增加多少条边使得这个仍然不是强连通。题解：考虑逆向思维我们知道一个有向完全图的边数为 n * (n - 1)比如现在有k(k >= 2)个连通块，其中一个连通块的点数为 x那么我们将这 x 个点和其他 n - x 个点的边删掉，删掉后的图一定不是强连通的因此我们只需要考虑让需要删掉的边 x * (n - x) 最少，那最后留下的边就越多所以我们只需要使 n * (n - 1) - x * (n - x) - m 最小即可因为n, m都是定值，这其实也就
2020-10-29 21:37:33
73
原创 Warm up HDU - 4612
题意：给出一个n个点m条边的无向图，询问添加一条边后图中最少有多少个桥？题解：对无向图缩点，缩点后的DAG有多少条边即有多少个桥。很明显添加一条边(u, v)后，DAG中的(u, v)路径上的桥都会失效。那么我们直接找一条最长的路径即直径即可。代码：/* * @Author : Nightmare */#include <bits/stdc++.h>using namespace std;#define ll long long#define ull unsigned
2020-10-29 19:41:05
83
原创 PowerOJ 2904: kmlver的子串plus
题意：kmlver有一个字符串S， 该字符串仅由小写字母组成，你需要分别回答Q次询问，每次询问由4个整数组成：l1,r1,l2,r2(1≤l1≤r1≤∣S∣，1≤l2≤r2≤∣S∣)l1, r1, l2, r2 (1 ≤ l1 ≤ r1 ≤ |S|， 1 ≤ l2 ≤ r2 ≤ |S|)l1,r1,l2,r2(1≤l1≤r1≤∣S∣，1≤l2≤r2≤∣S∣)，你需要统计子串Sl1S_{l_1}Sl1Sl1+1S_{l_1+1}Sl1+1Sl1+2S_{l_1+2}Sl1+2…Sr1S_{r1}
2020-10-27 19:02:08
164
原创 安装eclipse时弹出网页Java Missing解决方法
最近一直因为这个问题，导致Java实验一直做不了，尝试过很多次，反复安装配置又卸载jdk14，jdk11，jdk8，以及用别人传的jdk进行安装配置又卸载，并且看到很多网上都方法都是说jdk和eclipse的安装位数不同导致的，但是我的jdk和eclipse的安装位数都是和电脑一样是64位数的，这就导致我这几天一直在折腾eclipse的安装…其实只需要去官网eclipse压缩安装包下载然后点...
2020-04-30 01:58:19
2383
2
原创 CF327E Axis Walking
题意翻译给你一个长度为n(1<=n<=24)的正整数序列S，再有k(0<=k<=2)个正整数。求有多少种S的排列方式使得其前缀和不会成为那k个数里的任意一个。 答案对1e9+7取模。题解：n<=24，考虑状压DP设dp[S]表示当前已选的集合为S,sum[S]为当前集合的数的和sum很好得到，sum[i]=sum[isum[i]=sum[isum[i]=...
2020-02-22 16:56:50
107
原创 P2114 [NOI2014]起床困难综合症
题目描述每扇防御门包括一个运算op和一个参数t，其中运算一定是OR,XOR,AND中的一种，参数则一定为非负整数。如果还未通过防御门时攻击力为x，则其通过这扇防御门后攻击力将变为x op t。最终drd受到的伤害为对方初始攻击力x依次经过所有n扇防御门后转变得到的攻击力。由于atm水平有限，他的初始攻击力只能为0到m之间的一个整数（即他的初始攻击力只能在 0, 1, … , m中任选，但在通过...
2020-02-22 16:16:38
192
原创 可达性
题目描述给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图，输出一个尽可能小的点集，使得从这些点出发能够到达任意一点，如果有多个这样的集合，输出这些集合升序排序后字典序最小的。输入描述:第一行为两个整数 1 ≤ n, m ≤ 105，接下来 M 行，每行两个整数 1 ≤ u, v ≤ 105 表示从点 u 至点 v 有一条有向边。数据保证没有重边、自环。输出...
2020-02-20 14:07:07
694
原创 P1407 [国家集训队]稳定婚姻
题目描述：现代生活给人们施加的压力越来越大，离婚率的不断升高已成为现代社会的一大问题。而其中有许许多多的个案是由婚姻中的“不安定因素”引起的。妻子与丈夫吵架后，心如绞痛，于是寻求前男友的安慰，进而夫妻矛盾激化，最终以离婚收场，类似上述的案例数不胜数。我们已知n对夫妻的婚姻状况，称第i对夫妻的男方为Bi，女方为Gi。若某男Bi与某女Gj曾经交往过（无论是大学，高中，亦或是幼儿园阶段，i≠j），则...
2020-02-17 16:30:21
174
原创 P3398 仓鼠找sugar
题目描述小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a）到餐厅（b），而他的基友同时要从他的卧室（c）到图书馆（d）。他们都会走最短路径。现在小仓鼠希望知道，有没有可能在某个地方，可以碰到他的基友？小仓鼠那么弱，还要天天被zzq大爷虐，请你快来救救他吧！输入格式第一行两个正整数n和q，表示这棵树...
2020-02-17 15:35:42
99
原创 Stammering Aliens
题意：输入一个k，和一个字符串，询问是否存在出现次数>=k的子串，若存在，输出长度最长的子串和这些子串中起始下标最靠右的（下标从0开始），否则输出"none"；例如：3baaaababababbababbab其中babab出现了3次，长度为5，起始下标分别出现在5,7,12，输出最靠右的也就是12题解：先用SA对所有后缀排序，由于一段区间的LCP表示的子串一定出现在每个后缀里...
2020-02-14 17:15:21
89
原创 Trick or Treat
题意：多组数据，每组数据给出n，表示n个点的坐标，然后从x轴上选择一点，使得所有点到该点的最大值最小，并输出该点在x轴上的位置和所有点到该点的最大值题解：很明显dis(xi)=max((xi−x)2+(yi−y)2)dis(x_i)=max((x_i-x)^2+(y_i-y)^2)dis(xi)=max((xi−x)2+(yi−y)2)，要求min_dis，容易看出是一个关于x的下凹...
2020-02-14 16:57:25
237
原创 Gym - 102219 F - Military Class
There is a military class of 2∗n soldiers, and the commander wants all of them to get partnered into n pairs. He divides the soldiers into two lines of length n, and numbers the soldiers in both lines...
2020-02-12 21:19:46
244
原创 P3388 割点（割顶）
题目描述给出一个 nn 个点，mm 条边的无向图，求图的割点。输入格式第一行输入两个正整数 n,mn,m。下面 mm 行每行输入两个正整数 x,yx,y 表示 xx 到 yy 有一条边。输出格式第一行输出割点个数。第二行按照节点编号从小到大输出节点，用空格隔开。题解：Tarjan求割点模板题AC代码：#pragma GCC optimize(2)#include<...
2020-02-11 23:50:11
268
原创 P3387 缩点
题目描述给定一个 n 个点 m 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。输入格式第一行两个正整数 n,m第二行 n 个整数，依次代表点权第三至 m+2 行，每行两个整数 u,v，表示一条 u→vu\rightarrow vu→v 的有向边。输出格式共一行，最大的点...
2020-02-11 23:06:37
125
原创 P2746 [USACO5.3]校园网Network of Schools
题目描述一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 BB 在 AA 学校的分发列表中，AA 也不一定在 BB 学校的列表中。你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校...
2020-02-11 22:35:51
118
原创 P1656 炸铁路
题目描述因为某国被某红色政权残酷的高压暴力统治。美国派出将军uim，对该国进行战略性措施，以解救涂炭的生灵。该国有n个城市，这些城市以铁路相连。任意两个城市都可以通过铁路直接或者间接到达。uim发现有些铁路被毁坏之后，某两个城市无法互相通过铁路到达。这样的铁路就被称为key road。uim为了尽快使该国的物流系统瘫痪，希望炸毁铁路，以达到存在某两个城市无法互相通过铁路到达的效果。然而，...
2020-02-11 21:58:13
143
原创 P2341 [HAOI2006]受欢迎的牛
题目描述每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 AA 喜欢 BB，BB 喜欢 CC，那么 AA 也喜欢 CC。牛栏里共有 NN 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。输入格式第一行：两个用空格分开的整数：NN 和 MM。接下来 MM 行：每行两个用...
2020-02-10 17:29:39
80
原创 P3916 图的遍历
题目描述给出N个点，M条边的有向图，对于每个点v，求A(v)表示从点v出发，能到达的编号最大的点。输出格式N 个整数A(1),A(2),⋯A(N)A(1),A(2),\cdots A(N)A(1),A(2),⋯A(N)。题解：本来想直接dfs遍历的，但是图里有环，所以直接dfs只拿了40，所以考虑用tarjan缩点，然后再dfs就OK了，建议用记忆化搜索AC代码：#pragma ...
2020-02-10 16:36:16
341
原创 P2835 刻录光盘
题目描述在JSOI2005夏令营快要结束的时候，很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家，以便大家回去后继续学习。组委会觉得这个主意不错！可是组委会一时没有足够的空光盘，没法保证每个人都能拿到刻录上资料的光盘，又来不及去买了，怎么办呢？！组委会把这个难题交给了LHC，LHC分析了一下所有营员的地域关系，发现有些营员是一个城市的，其实他们只需要一张就可以了，因为一个人拿到光盘后...
2020-02-10 15:50:11
107
原创 P2863 [USACO06JAN]牛的舞会The Cow Prom
题目描述：约翰的N (2 <= N <= 10,000)只奶牛非常兴奋，因为这是舞会之夜！她们穿上礼服和新鞋子，别 上鲜花，她们要表演圆舞.只有奶牛才能表演这种圆舞.圆舞需要一些绳索和一个圆形的水池.奶牛们围在池边站好， 顺时针顺序由1到N编号.每只奶牛都面对水池，这样她就能看到其他的每一只奶牛.为了跳这种圆舞，她们找了 M(2<M< 50000)条绳索.若干只奶牛的...
2020-02-10 15:16:56
124
原创 P3872 [TJOI2010]电影迷
题目描述小A是一个电影迷，他收集了上百部的电影，打算从中挑出若干部在假期看完。他根据自己的口味和网上的介绍，对每部电影X都打了一个分数vX，表示自己喜欢的程度。这个分数的范围在-1000至1000之间，越大表示越喜欢。小A每看一部电影X，他的体验值就会加上vX。另外，因为某些电影是组成一个系列的，比如著名的《终结者》系列、《黑客帝国》系列等等，如果小A只看了前一部而没有看后一部的话，他就会觉得...
2020-02-04 23:24:08
173
1
原创 P4251 [SCOI2015]小凸玩矩阵
题目描述小凸和小方是好朋友，小方给了小凸一个 n×m(n≤m)n × m (n \leq m)n×m(n≤m)的矩阵 AA，并且要求小凸从矩阵中选出 n 个数，其中任意两个数都不能在同一行或者同一列。现在小凸想知道，选出的 n 个数中第 k 大的数的最小值是多少。输入格式第 1 行读入 3 个整数 n,m,k。接下来 n 行，每一行有 m 个数字，第 i 行第 j 个数字代表矩阵中第 i ...
2020-02-04 17:52:54
135
原创 P3171 [CQOI2015]网络吞吐量
题目描述路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中，路由器会使用经典的Dijkstra算法计算最短路径，然后尽量沿最短路径转发数据包。现在，若已知一个计算机网络中各路由器间的连接情况，以及各...
2020-02-04 17:01:00
233
原创 P4174 [NOI2006]最大获利
题目链接题解：算法合集之《最小割模型在信息学竞赛中的应用》经典的最大流模型，最大权闭合子图将用户放在左边，基站放在右边，连边容易看出是一个二分图那么根据题意，选择左边的点，就一定要选择右边和它相连的两个点，从而有互相依赖的关系，所以可以利用最大权闭合子图来求将正权点连向源点S，也就是左边的点，也就是收益，负权点连向汇点T，也就是右边的点，也就是成本，中间的点根据关系相连，流量为INF...
2020-02-03 20:44:23
140
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人