- 博客(315)
- 收藏
- 关注
RSS订阅
原创 特殊代码使用（自用）
测试数据是否越界。struct node{ int & operator[](int idx){ if(idx>=maxn||idx<0)while(1); return a[idx]; } int operator[](int idx)const{ if(idx>=maxn||idx<0)w...
2019-08-13 18:33:01
237
原创 dinic 最大流费用流模板
dinic最大流：#include<bits/stdc++.h>#define rep(i,a,b) for(int i = (int)a;i<=(int)b;i++)#define pb push_back#define lson rt<<1#define rson rt<<1|1#define mid (l+r)/2using ...
2018-09-07 09:36:43
700
原创 线性求逆元等 数论板子
#pragma GCC optimize(2)逆元板子块先来一个线性求逆元#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=100005;const int mod=(int)1e9+7;ll inv[maxn],a[maxn],n;int m...
2018-08-14 13:27:59
445
原创 P3690 【模板】Link Cut Tree （动态树）
给定 n 个点以及每个点的权值，要你处理接下来的 m 个操作。操作有四种，操作从 0 到 3 编号。点从 1 到 n 编号。0 x y 代表询问从 x 到 y 的路径上的点的权值的 xor 和。保证 x 到 y 是联通的。1 x y 代表连接 x 到y，若 x 到 y 已经联通则无需连接。2 x y 代表删除边 (x,y)，不保证边 (x,y) 存在。3 x y 代表将点 x 上的权值变成 y。#include <bits/stdc++.h>#define rep(i, a, b
2020-08-14 16:00:50
235
原创 Android Studio无法连接上蓝叠模拟器问题
本文是自己在安装安卓环境时一直无法成功运行的原因，仅供参考。在按照网上大部分人提供的安装流程走下来之后，我碰到了最后装模拟器的问题，关于模拟器，很多人推荐的是Genymotion模拟器，那本人由于经济实力原因还是选择了之前就有用过的蓝叠模拟器。在成功adb connect 127.0.0.1:5555之后，首次运行安装过程中还是无法运行，出现Session’app’:Installation did not secceed.The application could not be installed的问
2020-07-29 13:18:17
2314
原创 [COCI2015]BNE 最大全1子矩阵
题意你有一个1000*1000的矩阵，现在定义一个矩阵 $A_{x,y} $ 是酷的当且仅当 a1,1+ax,y<=ax,1+a1,ya_{1,1}+a_{x,y}<= a_{x,1}+a_{1,y}a1,1+ax,y<=ax,1+a1,y 且 x>1,y>1x>1,y>1x>1,y>1 条件成立时。 而一个矩阵是非常酷的当且仅当它的所有子矩阵都是酷的。现在问你，非常酷的矩阵的最大的元素个数有多少。做法我们证明一下，假设有如下图，两边的矩
2020-07-10 20:15:57
278
原创 图论总结
因为图论的知识点是真的杂，稍微写一点东西帮助记忆。后续会慢慢补充。一、最短路DijkstraFloydSPFAK短路差分约束系统二、最小生成树PrmieKruskal三、二分图定义设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。定理最小点覆盖数 = 最大匹配数 （这是 Konig 定理）最大独立集 = 顶点数 - 最大匹配数最小路径覆盖数 = 顶点数 – 最大匹配数3.1
2020-07-03 12:04:43
348
原创 C. Johnny and Megans Necklace 欧拉回路
题目链接 https://codeforces.ml/contest/1361题意给你 nnn 段线段，每个线段的两端都有一个权值，现在要你将所有的线段相连成一个环，两个线段相连时会产生一个权值 val=log2(aval=log_2(aval=log2(a xor b)b)b)，即两个值能够相连必须在二进制的val位之后所有值相等，如果两个值相等，那么这个 valvalval 默认为20。这个环的值等于所有连接节点的最小值，要你求这个环的最大值。做法自己想还是一下子做不出来，参考了别人的做法敲
2020-06-30 11:14:22
131
原创 Gym 102419H In-degree 费用流or最大匹配
题目链接： http://codeforces.com/gym/102419/problem/H题意：2000个点，2000条边，无重边无自环的无向图，现在要你把这些无向边变成有向边，使得每个点的入度为给你的数组 AAA ,如果为 −1-1−1 则任意入度即可。做法：两种做法，第一种是费用流做法， 1−n1-n1−n 表示点， 1−m1-m1−m 表示边，我们将边也看成点，从原点到所有点...
2020-03-30 15:24:44
196
原创 Gym 101655D Delta Quadrant 树形dp
题目链接https://codeforces.com/gym/101655/attachments题意一棵有着 1e41e41e4 个结点的树，树的边上有权值，你现在可以任意选择从某一个起点开始，遍历 n−kn-kn−k (k<=20)(k<=20)(k<=20)个不同的结点并返回，问经过的路径长度最短为多少。做法看到 kkk 的个数其实心里就有点谱了，并且 nnn ...
2020-03-23 15:09:50
204
原创 CF932 D. Tree 倍增
题目链接： https://codeforces.com/contest/932/problem/D题意4e5次操作，每次操作有两种不同内容111 fff www 表示新增加一个结点，以 fff 作为其父节点，新结点权值为 www222 uuu sumsumsum 表示以结点 uuu 为第一个元素找到一个序列，要求：① 序列中靠后的点必须是前面的点的父亲。② 序列所有结点的和不能...
2020-03-17 20:46:48
184
原创 竞赛图 哈密顿图
竞赛图竞赛图是通过在无向完整图中为每个边缘分配方向而获得的有向图（有向图）。 也就是说，它是一个完整图形的方向，等价于一个有向图，其中每对不同的顶点通过单个有向边连接，即每对顶点之间都有一条边相连的有向图称为竞赛图。总的概括就是一个有向完全图。与哈密顿路径的关系任何有限数量n个顶点的竞赛图都包含一个哈密尔顿路径，即所有n个顶点上的直线路径。假设该语句适用于n，并考虑n + 1个顶点上的...
2020-02-27 16:07:59
3312
原创 Running Routes 区间dp
题目链接 https://open.kattis.com/problems/runningroutes题意给你一个正 nnn 边多边形，告诉你所有点和点之间是否可以连线，现在要你选出最多的连线，使得所有线之前两两不相交，问最多能选出多少条线。做法其实能感觉出来是区间 dpdpdp ，因为如果一个 888 边形，3和6连上后，7~2 和 4~5两个区间都是一个新的状态，但是emmm，原来自...
2020-02-07 19:00:44
326
原创 UFPE Starters Final Try-Outs 2020 J.Jingle Bells 树形dp
题目链接 http://codeforces.com/gym/102448/problem/J题意你现在有一棵树，5种颜色 (1,2,3,4,5)(1,2,3,4,5)(1,2,3,4,5) ，树的边会有一种颜色或者没有被染色。现在要你给树染上颜色，让每一个顶点的所有边都带有不同的颜色，问你有多少中方案。做法树形 dpdpdp ，（赛上并没有时间想，挺神奇的一道我应该是做不出来的一道题）。...
2020-02-05 20:45:37
560
原创 cf #616 (Div. 2) E. Prefix Enlightenment 拆点并查集
题目链接： http://codeforces.com/contest/1291/problem/E题意：你现在有一个 nnn 位的 010101 串 SSS ，和 kkk 个集合，每个集合里会有 1,2,3,4,.....,n{1,2,3,4,.....,n}1,2,3,4,.....,n 中的若干个数字，并且保证每个数字只会在最多两个集合中出现。当你某次选择某一个集合 xxx 时，串 S...
2020-02-03 20:05:22
339
原创 617.E . XOR and Favorite Number 莫队+异或前缀和
题目链接： https://codeforces.com/contest/617/problem/E题意：长为 1e51e51e5 的数组 aaa ，和 1e51e51e5 个查询，每次查询要求出区间 [li,ri][l_i,r_i][li,ri] 中有多少 个子区间使得该区间内的异或和为 kkk。做法：因为我们要快速求得一个区间 [li,ri][l_i,r_i][li,ri] 中...
2019-11-20 15:16:57
111
原创 605D A. Board Game set+树状数组思想
题目链接： https://codeforces.com/gym/260204/problem/A题意：你现在有 nnn 种魔法，每种魔法 iii 都有四个数值 a[i],b[i],c[i],d[i]a[i],b[i],c[i],d[i]a[i],b[i],c[i],d[i] ， 现在你有初值 x=0,y=0x=0,y=0x=0,y=0 ，一个魔法 iii 能被使用当且仅当满足 a[i]<...
2019-11-20 14:06:08
349
原创 D1. Constrained Tree 构造+dfs
题目链接：https://codeforces.com/contest/513/problem/D1
2019-11-18 10:52:41
226
原创 Fabricating Sculptures dp+前缀和优化
题目链接： https://codeforces.com/gym/102428/problem/F题意：你现在有 mmm 个方块，要搭建一个以 sss 为底的一个模型，这个模型是不能储水的结构，即不存在一列，其左边和右边的俩均比它高，问你有多少种搭建的方法。做法：dp[i][j]dp[i][j]dp[i][j] 表示以 iii 为底的时候，还有 jjj 个方块时的方案数。这个时候 dp[i...
2019-11-18 10:33:50
668
原创 Codeforces 549B. Looksery Party 构造
题目链接： http://codeforces.com/problemset/problem/549/B题意：你现在拥有一个 n∗nn*nn∗n 的 010101 数组 aaa ，和一个长为 nnn 的数组 bbb，现在要你选出一些行的集合 XXX，使得对于每一列 jjj 所有行的和 ∑a[i][j](i∈X)\sum a[i][j] (i\in X)∑a[i][j](i∈X) 不等于 bj...
2019-11-12 15:57:35
131
原创 CF551D GukiZ and Binary Operations 矩阵快速幂
题目链接： http://codeforces.com/problemset/problem/551/D题意：你现在需要构造一个长为 nnn 的数组 aaa ，使得 (a1anda2)∣((a2anda3)∣...∣(an−1andan))=k(a_1and a_2)|((a_2and a_3)|...|(a_{n-1}and a_n))=k(a1anda2)∣((a2anda3)∣....
2019-11-12 15:09:14
122
原创 E. Little Elephant and Tree dfs序+线段树
题目链接： http://codeforces.com/contest/258/problem/E题意：你现在做法：代码#include <bits/stdc++.h>#define lson rt<<1#define rson rt<<1|1#define mid (l+r)/2#define rep(i,a,b) for(int i = ...
2019-11-10 10:59:01
114
原创 cf 246 E. Blood Cousins Return 二分+主席树
题目链接： http://codeforces.com/problemset/problem/246/E题意：你现在有一棵 1e51e51e5 个结点的树，每个结点有一个权值。你现在有 1e51e51e5 个询问，每个询问会有两个值 v,kv,kv,k ，询问的是结点 vvv 的往下第 kkk 代所有结点中有多少个不同的权值。做法：因为每一层的结点都已经固定了，所以我们可以按照层序遍历来...
2019-11-04 10:03:52
246
原创 2014-2015 ACM-ICPC, NEERC L. Useful Roads 支配树
题目链接： 我是链接题意：一个 2e52e52e5 个点， 2e52e52e5条边的有向图。我们定义一条简单路径为，没有一个结点被走过超过一次的路径。现在我们从结点 111 出发走简单路径，如果到达某一个点 xxx 的路径上如果经过 u→vu\rightarrow vu→v ，那么这条路径要被保留。现在要你输出所有要被保留的路径编号。做法：可能题目里面有点绕，对于一条路径是否被保留的说法...
2019-11-03 20:29:06
158
原创 cf 231 E. Cactus 仙人掌图圆方树
题目链接： http://codeforces.com/problemset/problem/231/E题意：你现在有一个 1e51e51e5 个点的仙人掌图（每个边最多只属于一个简单环），定义一条简单路径为一条边最多只被走过一次的路径。你现在有 1e51e51e5 个询问，每次询问从 a−>ba->ba−>b 有多少条简单路径，答案 modmodmod 1e9+71e9+...
2019-11-02 09:54:51
197
原创 Codeforces Round #587 (Div. 3) F. Wi-Fi dp+线段树维护
题目链接： http://codeforces.com/contest/1216/problem/F题意：nnn 户人家要联网，第 iii 家用户联网的成本为 iii ，其中有一些人家家中有 wifiwifiwifi ，这使得如果这些人家里联了网，那么 [max(i−k,1),min(i+k,n)][max(i-k,1),min(i+k,n)][max(i−k,1),min(i+k,n)] 范...
2019-11-02 09:28:50
158
原创 Gym 101161H Witcher Potion 状压dp
题目链接： http://codeforces.com/gym/101161/attachments题意：你在初始状态下有 100100100 点能量， 000 点毒素值，你现在要连续的打小怪兽，打每只小怪兽需要花费你 KKK 点能量和 MMM 单位时间。你现在有 n(n<=8)n(n<=8)n(n<=8) 瓶药水，每瓶药水只能喝一次，并且在打一只小怪兽时最多喝一瓶，每瓶药水...
2019-10-26 20:15:35
152
原创 2-sat 小结
定义简略的说， nnn 个变量 aia_iai，且 ai∈[0,1]a_i\in[0,1]ai∈[0,1]。给出一些条件，形式如下：aia_iai opopop aj=0/1(op∈[and,or,xor])a_j =0/1(op\in[and,or,xor])aj=0/1(op∈[and,or,xor])求解 2−SAT2-SAT2−SAT 即找到一组合法的 aaa 满足所有限...
2019-10-25 10:54:06
130
原创 316C Tidying Up 费用流的完美匹配
题目链接： http://codeforces.com/gym/257279/problem/C题意：你有一个 n∗mn*mn∗m 的矩阵，这些方格中有数字 1−n∗m/21-n*m/21−n∗m/2 每个数字出现两次，现在要你选出最少的方格个数，使得在这些方格内数字可以任意交换的情况下，可以实现两个相同的数字邻接。做法：感觉就是用图论做，就是网络流建不出图来…和队友综合一下应该就能过了…...
2019-10-24 10:04:15
194
原创 差分约束小结
背景果然还是要吃个亏摔一下才会知道做点什么，之前一直挺忽视这个知识点的（毕竟是大一下开始学了算法之后就没碰到过的题型），直到今年CCPC在哈尔滨碰到了一道现在被队友吐槽是模板题的题目。当引起重视，在借鉴大佬的博客的前提下写一些小结，以示警戒。正题一、差分约束的概念如果一个系统由 nnn 个变量和 mmm 个约束条件组成，形成 mmm 个形如ai−aj≤ka_i-a_j≤kai−aj≤k...
2019-10-16 20:49:55
114
原创 Manthan, Codefest 19 E. Let Them Slide
题目链接： http://codeforces.com/contest/1208/problem/E题意：你现在有 nnn 行数组，他们被放在一个 mmm 列的箱子中，数组的长度如果不到 mmm 则可以左右移动，现在问你对于每一列 xxx ，经过数组移动后这一列可以达到的最大值为多少。做法：对于不出现负数的情况：前 LLL 个位置，每个位置上只能取到区间 [max(1,i−(w−L))...
2019-10-15 15:30:27
116
原创 2014-2015 ACM-ICPC Moscow Subregional H - Holes 思维
题目链接： https://codeforces.com/gym/100519/problem/H题意：你现在有一个特殊的无向图，这个图除了最多某一个点外，其余的点的度数均为二，每个点上都有一只兔子，现在灾难要来了，你可以在 kkk 个点上打洞，每只兔子会往最近的洞跑，问你跑的最远的兔子的最短距离是多少。做法：二分距离，重点是在已知当前距离 LLL 情况下的判断。很明显我们可以知道距离 ...
2019-10-09 21:53:31
174
原创 P5236 【模板】静态仙人掌圆方树模板
链接： https://www.luogu.org/problem/P5236题意：你有一个 n(n<=10000)n(n<=10000)n(n<=10000) 个点 m(m<=20000)m(m<=20000)m(m<=20000) 条边的仙人掌，有 q(q<=10000)q(q<=10000)q(q<=10000) 个询问，每次询问两个...
2019-10-08 17:01:04
160
原创 H - Binary Tree Gym - 100443H 网络流
题目链接： https://codeforces.com/gym/100443/attachments题意：你现在有 n(n<=100)n(n<=100)n(n<=100) 节课要上，每节课 xxx 有一个上课区间 [lx,rx][l_x,r_x][lx,rx] 和这堂课的学生数量 sxs_xsx ，每间教室最多可容纳 MMM 个学生，一节课 uuu 在结束后如果想要...
2019-10-06 18:57:20
520
1
原创 poj 4006 Genghis Khan the Conqueror 树形dp
题目链接： http://poj.org/problem?id=4006题意：你现在有一个 nnn 个结点 mmm 条边的无向带权连通图，现在你有 qqq 个等概率发生的改变，每次会将原图中某一条原先存在的边权变大，但只会改变其中的一条，问你在这样的情况下，图中生成最小生成树权值的期望是多少。做法：先对原图中的点做最小生成树，如果改变的边不在这棵树上，那么直接加上最小生成树的值即可。重要...
2019-10-05 20:42:27
138
原创 2019牛客国庆one D.Modulo Nine dp
题目链接： https://ac.nowcoder.com/acm/contest/1099/D题意：你要构造一个长为 nnn 的数字串 a1a2a3a4....ana_1a_2a_3a_4....a_na1a2a3a4....an，使得其满足 mmm 个条件，每个条件为一个区间 [li,ri][l_i,r_i][li,ri] 要求 ali∗ali+1∗...∗aria_{l_i...
2019-10-01 19:53:27
351
原创 洛谷 P4244 [SHOI2008]仙人掌图 II
题目链接： https://www.luogu.org/problem/P4244题意：无向图仙人掌求直径，即这张图相距最远的两个点的距离，距离为两个点之间的最短路长度。做法：必要的过程解释都已经写在代码里了。简单来说，如果是一棵树，那么直接用 d[x]d[x]d[x] 来表示点 xxx 往下的儿子到 xxx 的最长距离，每次用最长和次长距离更新答案即可。但是因为仙人掌图是存在环的，所...
2019-10-01 19:11:40
167
原创 Educational Codeforces Round 34 G. Yet Another Maxflow Problem 线段树实现最小割
题目链接： https://codeforces.com/contest/903/problem/G题意：在理解网络流的前提下简化的题目大概是，源点向 A1A_{1}A1 连流量 infinfinf , BnB_nBn 向汇点连流量 infinfinf，对于每个 i∈[1,n−1]i\in[1,n-1]i∈[1,n−1] 都有一条 Ai→Ai+1A_i\rightarrow A_{i+1...
2019-09-30 20:09:17
138
原创 CF Round #589 (Div. 2)E. Another Filling the Grid 组合数学dp
题目链接： https://codeforces.com/contest/1228/problem/E题意：你现在有个 n∗nn*nn∗n 的矩阵，现在要你给每个格子填上一个数字 x(x∈[1,k])x(x\in[1,k])x(x∈[1,k]) ，并且要求每一行以及每一列的最小值是 111 ，问你有多少种填数字的方法。做法：只会 O(n3)O(n^3)O(n3) 的做法，果然还是太菜了...
2019-09-30 19:46:02
275
原创 Codeforces Round 73F. Choose a Square 线段树
题目链接： https://codeforces.com/contest/1221/problem/F题意：二维平面上有 nnn 个带权值的点，选择一个 [(a,a),(b,b)](a<=b)[(a,a),(b,b)] (a<=b)[(a,a),(b,b)](a<=b) 的一个正方形区域获得的权值是该区域内点权的和减去正方形边长。 现在要你选择一个值最大的区域，输出最大权值 ...
2019-09-29 12:54:10
72
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人