1 codancer

尚未进行身份认证

为信仰而战斗

等级
TA的排名 2w+

SQL学习笔记------基础语法

创建数据库:CREATEDATABASE<数据库名>创建表:usestudentcreatetablestudentinfo( namevarchar(20), idchar(10), scoreintnotnull);use<数据库名>指定数据库char是固定字节长度,varchar是可变的字节长度,后面的数字是最大字...

2019-11-09 14:46:47

【codeforces 1243】D. 0-1 MST(补图的连通块计数)

题意:给你一个图,求补图的联通块个数。题解:考虑用使用并查集,用set存已经被放入并查集的点,对于没有放入的点,计算该点和联通块相连的点的个数,如果相连的点的个数小于联通块大小,则直接连进去即可。时间复杂度O(n+m∗log)O(n+m*log)O(n+m∗log)。代码:#include<bits/stdc++.h>usingnamespacestd;const...

2019-11-07 10:12:02

【AtCoder Grand Contest 040】B.Two Contests

题意nnn段区间,要把他们分到两个不同的集合S,TS,TS,T中,不能有剩余,每个区间只能在一个集合里,令SSS中所有区间的交的长度为lslsls,TTT中所有区间的交为ltltlt,求max{ls+lt}max\{ls+lt\}max{ls+lt}。题解找到LLL最大的区间ppp和rrr最小的区间qqq,那么只有两种情况:1.1.1.p,qp,qp,q在同一个集合内,那么...

2019-11-04 10:32:28

【HDU 3622】 Bomb Game(2-SAT)

题意:一个游戏有nnn轮,每轮提供给你两个坐标,你选择其中一个放置炸弹,到最后会放置nnn个炸弹,要保证任意两个炸弹的爆炸区域不会相交,每个炸弹的爆炸半径由你来决定,你的目的是使最小的半径最大。题解:考虑二分半径,对于半径rrr,O(n2)O(n^2)O(n2)的建立约束关系,利用2−SAT2-SAT2−SAT判断可行性。时间复杂度O(n2log(n))O(n^2log(n))O(n2log...

2019-10-30 15:25:53

【codeforces 1225D】Power Products

题意计算满足ai∗aj=xk,i<ja_{i}*a_{j}=x^k,i<jai​∗aj​=xk,i<j的对数。思路考虑x∗y=pkx*y=p^kx∗y=pk,将xxx和yyy进行质因子分解可得:x=p1m1p2m2p3m3...pnmnx=p_1^{m_1}p_2^{m_2}p_3^{m_3}...p_n^{m_n}x=p1m1​​p2m2​​p3m3​​...pnm...

2019-10-27 22:20:47

Educational Codeforces Round 75 (Rated for Div. 2)

A如果某个字母连续出现的次数是奇数,那么这个键一定是好的,遍历一遍即可。#include<bits/stdc++.h>usingnamespacestd;intmain(){intT;cin>>T;while(T--){strings;cin>>s;set&l...

2019-10-25 19:45:29

Codeforces Round #595 (Div. 3)

A对数组排序,如果存在相邻两项为1,则最少可以分成两组,否则分成1组。#include<bits/stdc++.h>usingnamespacestd;inta[200];intmain(){intT;cin>>T;while(T--){intn;cin>>n;...

2019-10-23 16:48:34

【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

查看更多

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