1 codancer

尚未进行身份认证

为信仰而战斗

等级
TA的排名 2w+

【LOJ 网络流24题】方格取数

方格取数题解按照顺序对应不同的格子染色,相邻的染不同的颜色,从SSS向所有的黑色的点建流量为对应权值的边,从所有的白点向TTT建流量为对应权值的边。对于有冲突的黑点和白点之间建流量为infinfinf的边,跑最小割,所有点的和减去最小割即为答案(最大权独立子集)代码:#include<bits/stdc++.h>usingnamespacestd;constint...

2019-10-11 17:51:26

【LOJ 网络流24题】试题库

试题库题解:SSS向mmm中类型连接容量为对应需求量的边,题目种类和对应的属于该种类的题目连流量为1的边,每道题和TTT连流量为111的边,跑最大流即可。#include<bits/stdc++.h>usingnamespacestd;constintN=80000;constintmaxn=2000;constintINF=0x3f3f3f...

2019-10-11 17:46:03

【LOJ 网络流24题】最长递增子序列

最长递增子序列题解:对于第一个查询直接dpdpdp即可,dpidp_{i}dpi​代表以iii结尾的最长上升子序列的最大长度,计算出sss。对于第二个查询,对于每个点拆分成两个点i1,i2i_1,i_2i1​,i2​,如果dpidp_idpi​为111,则SSS向i1i_1i1​连接流量为111的边,如果dpidp_idpi​为sss,则i2i_2i2​向TTT连接流量为111的边,对于每...

2019-10-11 14:53:57

【LOJ 网络流24题】圆桌聚餐

圆桌聚餐题解:从SSS向每个单位连接流量为rir_iri​的边,每个单位向每个桌子连接流量为111的边,每个桌子向TTT连接流量为cic_ici​的边,跑最大流即可。如果满流,即maxflow=maxflow=maxflow=人数,则存在方案。对于方案的输出:对于每个单位,记录下向哪些桌子流出了流量即可。代码:#include<bits/stdc++.h>usingnam...

2019-10-11 14:48:12

【LOJ 网络流24题】魔术球

魔术球题解:考虑如果i+ji+ji+j为完全平方数,则iii和jjj之间连一条边,那么最后构成一个图GGG,那么问题即可转化为寻找一个最大的数字mmm,使得按照上述方法构成的图的最小路径覆盖数小于等于nnn,我们二分mmm即可,构造方案同最小路径覆盖一题。#include<bits/stdc++.h>usingnamespacestd;constintN=100...

2019-10-10 18:48:29

【LOJ 网络流24题】最小路径覆盖

最小路径覆盖题解:假设x,yx,yx,y之间有一条边,则把xxx和yyy分别拆成x1,x2,y1,y2x_1,x_2,y_1,y_2x1​,x2​,y1​,y2​。在x1x_1x1​和y2y_2y2​之间连接一条流量为111的边,构造好二分图后答案即为n−maxmatchn-maxmatchn−maxmatch。对于方案的输出,可以利用并查集,对于xxx和yyy,如果流量流经x−>yx-...

2019-10-10 16:47:38

【LOJ 网络流24题】太空飞行计划

太空飞行计划题解:最大权闭合子图,设V′V'V′为G(V,E)G(V,E)G(V,E)的一个点集,如果VVV中对于每个点的所有的出边所到达的点也∈V′\inV'∈V′,那么V′V'V′即为一个闭合子图,最大权闭合子图即为所有的闭合子图中权值和最大的。定理:从SSS向所有权值为正数的点增加一条等于该点点权的流量的边,从所有权值为负数的点向TTT增加一条等于该点权绝对值流量的边,对于u(wu&...

2019-10-10 16:46:13

【codeforces 590div3】F.Yet Another Substring Reverse

题意:现在有一个字符串sss(1≤∣s∣≤1061\leq|s|\leq10^61≤∣s∣≤106),现在选择一个区间[l,r][l,r][l,r],反转一次或者不反转。若某区间的字母各不相同,则该区间为完美区间。你要做的就是执行完操作后使完美区间的长度最大。(整个字符串的字母种类数不超过202020)题解:这个问题可以转换为寻找两个不相交的完美区间使得他们的长度和最大。首先枚举...

2019-10-02 12:13:10

codancer的图论训练(updating...)

2019.9.12580C.KefaandParktags:简单DFS1081D.MaximumDistancetags:带点思维的MST,学会了只联通某些点的并查集

2019-09-12 19:01:14

JSOI2007:字符加密(后缀数组)

题意:将长度为nnn的字符串排成一圈,对于nnn种排列方式构成的字符串按字典序从小到大输出最后一位。题解:1.将原串扩展成2倍(避免有些没有遍历到)。2.建立后缀数组,对于saisa_{i}sai​小于nnn的输出第sai+n−1sa_i+n-1sai​+n−1位即可。代码://luogu-judger-enable-o2#include<bits/stdc++.h>...

2019-09-12 11:11:00

The Preliminary Contest for ICPC Asia Xuzhou 2019

B.soeasy并查集,可能会卡掉map,建议使用unordered_map。#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+100;constintmod=1e9+7;typedeflonglongll;constintINF=0x3f3f3f3f;constllll...

2019-09-09 17:23:38

The Preliminary Contest for ICPC Asia Nanjing 2019

A.Thebeautifulvaluesofthepalace首先对于每个(x,y)(x,y)(x,y),我们可以O(1)O(1)O(1)的查询出这个坐标的值。接下来就将问题转化为了一个106⋅10610^6\cdot10^6106⋅106的矩阵,每次查询子矩阵内的点的和。考虑将所有的yyy离散化,计mpi,jmp_{i,j}mpi,j​表示(1,1)−(i,j)(1,1)-(i...

2019-09-04 11:08:33

AtCoder Beginner Contest 139

A#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+100;constintmod=1e9+7;typedeflonglongll;constintINF=0x3f3f3f3f;constllllINF=0x3f3f3f3f3f3f3f3f;#definerep(i,...

2019-09-01 22:14:48

【codeforces 1026 D】 Shortest Cycle(最小环)

题面题意:一个长度为nnn的数组,如果ai&aj!=0a_{i}\&a_{j}!=0ai​&aj​!=0,那么iii和jjj之间就有一条边,计算所构成图的最小环。(1≤n≤100000,1≤ai≤1018)(1\leqn\leq100000,1\leqa_i\leq10^{18})(1≤n≤100000,1≤ai​≤1018)思路...

2019-08-28 17:43:37

【codeforces 1208D】 Restore Permutation(线段树)

题面题意:一个长度为nnn的排列aaa,现在定义pip_ipi​为数组aaa中下标小于等于iii并且小于aia_iai​的数字的和。现在给定ppp,求aaa。思路:首先可以肯定的是,ppp中最后一个000出现的位置pospospos在aaa中一定是111。我们可以反证:假设aposa_{pos}apos​不为111,假设111在pospospos之前,那么ppos≥1p_{pos}\g...

2019-08-27 11:30:20

【HDU 6714】最短路2(Dijkstra)

题面题意:对于floyedfloyedfloyed算法,Di,jD_{i,j}Di,j​表示最外层循环最小的能够求出来disi,jdis_{i,j}disi,j​的循环次数,计算∑i=1n∑j=1nDi,j\sum_{i=1}^{n}{\sum_{j=1}^{n}{D_{i,j}}}∑i=1n​∑j=1n​Di,j​思路其实Di,jD_{i,j}Di,j​即为iii到jjj的最短路路径上最...

2019-08-25 08:53:39

【HDU 6638】Snowy Smile(线段树求区间连续最大和)

题面题意平面坐标系有nnn个点,第iii个点的坐标为(xi,yi)(x_i,y_i)(xi​,yi​),每个点有个权值wiw_iwi​,现在你需要寻找一个矩形把某些点圈起来使得他们的权值和最大。思路先把各点的纵坐标离散化,然后把所有的点按照横坐标从小到大排序,枚举矩形的左边界,每加入一个新的点,就把它对应纵坐标yyy的权值和w[y]w[y]w[y]更新并更改右边界,当左右边界都确定以后,利...

2019-08-10 10:56:47

【HDU 6627】equation(分段函数求值)

题目链接题意:两个长度为nnn的数组aaa和bbb和一个正整数CCC,计算有多少个xxx满足:∑i=1n∣ai⋅x+bi∣=C\sum_{i=1}^n|a_i\cdotx+b_i|=Ci=1∑n​∣ai​⋅x+bi​∣=C思路:该函数为分段函数,每段的转折点为−biai-\frac{b_i}{a_i}−ai​bi​​,先把转折点排序,计最开始的函数值为x⋅suma+sumbx\...

2019-08-06 10:57:12

2019牛客暑期多校D.Big Integer

题面题意:定义A(n)A(n)A(n)为nnn个1构成的数字,如A(3)=111A(3)=111A(3)=111,计算有多少对(i,j)(i,j)(i,j)使得A(ij)%p=0A(i^j)\%p=0A(ij)%p=0。思路:通过枚举发现是有上面的等式是有循环节的,而且循环节是p−1p-1p−1的因子,因此暴力枚举计算出循环节ddd,接下来就是求有多少对ij%d=0i^j\%d...

2019-08-05 20:32:49

【HDU 6621】 K-th Closest Distance(主席树+二分)

题面题意:一个长度为nnn的数组,有mmm次查询,对于每次查询,查询[l,r][l,r][l,r]内距离ppp第kkk近的距离。强制在线。思路考虑二分距离disdisdis,对于每次的disdisdis,判断在[l,r][l,r][l,r]内在区间[p−dis,p+dis][p-dis,p+dis][p−dis,p+dis]内的数是否超过了kkk个,该操作可以利用主席树来实现,复杂度O(n...

2019-08-05 19:40:16

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。