1 ordinarv

尚未进行身份认证

努力才是人生的常态

等级
TA的排名 4w+

洛谷P2580 于是他错误的点名开始了(Trie树板子)

字典树空间一般开n*maxLen(n为字符串数量,maxLen为字符串最大长度,最大情况n个串都不相同)#include<bits/stdc++.h>usingnamespacestd;constintmaxnode=5e5+5;//n*maxlenconstintmaxn=5e3+5;inttrie[maxnode][26],val[maxnode...

2019-11-06 23:57:41

2019CCPC-Harbin E(拓扑排序)

Note:T很大,初始化就容易超时。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<int,ll>piir;constintmaxn=1e6+5;vector<int>s[maxn];vector<int>G[...

2019-11-03 18:25:30

牛客假日团队赛19 D-Chocolate Milk(拓扑排序+树)

传送门思路:给每个入度为零的点一些流量,其流量等于该点的出度值。然后拓扑排序,如果某个点的流量等于全部流量,即为答案点(除起点)。因为题目给的是一颗树,所以不用考虑流量分流后在聚集到一点上。也就是说,除入度为零的点以外,出度大于1的点及其后面的点都不会是答案。#include<bits/stdc++.h>usingnamespacestd;typedefpai...

2019-11-01 14:27:36

2016第十二届湖南省赛 B-有向无环图(拓扑排序)

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=1e5+5;constintmod=1e9+7;lla[maxn],b[maxn];vector<int>G[maxn];queue<int>q;intin...

2019-10-31 15:05:03

UVA - 10305 Ordering Tasks (拓扑排序)

水题#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>piir;typedeflonglongll;constintmaxn=1e2+5;constintINF=0x3f3f3f3f;intn,m;intin[maxn];vector<i...

2019-10-31 15:06:37

UVALive - 4255(拓扑排序+构造)

传送门思路:连续和转化为前缀和之差。可以将问题转化为已知序列a1,a2,...,an的大小关系,求出任意一组满足条件的序列。拓扑排序即可。我是以sum大指向sum小的方向建边。假设入度为零的点即最大值点的值为0,那么后面的点比它小就小1。注意sum[0]=0,0也要跑。#include<bits/stdc++.h>usingnamespacestd;typ...

2019-10-31 13:49:51

UVA11624 Fire! (BFS)

思路:两遍BFS即可,先跑Fire,再跑J。貌似写过stp数组没有考虑初始INF!#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>piir;typedeflonglongll;constintmaxn=1e3+5;constintINF=0x3f3f...

2019-10-31 11:03:29

区间贪心

51nod1091线段的重叠#include<bits/stdc++.h>usingnamespacestd;constintmaxn=5e4+5;structnode{intl,r;}a[maxn];boolcmp(nodea,nodeb){if(a.l==b.l)returna.r>b.r;re...

2019-10-21 22:17:41

Gym-101741C Cover the Paths(LCA贪心)

传送门题意:给你一颗n个结点的无向树,然后给你m条路径(a,b),让你求最小的点集,满足这些路径上至少有一点在这个点集上。输出点集的大小和点。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=1e5+5;intn,m;vector<int&gt...

2019-10-25 16:00:05

「BZOJ1483」[HNOI2009] 梦幻布丁 (启发式合并)

传送门这题没有数据范围可怎么写啊!#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constllsetoff=1e9;constintmaxn=1e6+5;vector<int>v[maxn];intf[maxn],c[maxn],ans,n,m;//...

2019-10-22 21:53:52

Codeforces 161D Distance in Tree(点分治)

题意:求distance(u,v)==k的点对数。思路:统计距离root距离之和为k的对数-距离root儿子节点中距离儿子节点距离之和为k-2的对数。因为每对算了两边除二即可。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=1e6+5;constint...

2019-10-10 22:32:21

点分治

#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintmaxn=1e5+5;/* sz[x]表示以x为根的子树的size使多少 son[x]表示x的儿子中size最大的是 rt是我们要找的重心 all当前子...

2019-10-10 22:27:01

__int128

voidscan(__int128&x){x=0;intf=1;charch;if((ch=getchar())=='-')f=-f;elsex=x*10+ch-'0';while((ch=getchar())>='0'&&ch<='9')...

2019-10-05 23:19:49

2018 Hunan province E

动态开点#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>piir;typedeflonglongll;constintmaxn=1e6+5;constintINF=0x3f3f3f3f;intsum1[maxn],ls1[maxn],rs1[max...

2019-10-05 10:28:47

2017xiangtan H

#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>piir;typedeflonglongll;constintmaxn=1e5+5;constintINF=0x3f3f3f3f;intn;boolvis[maxn];lldist1[maxn],di...

2019-10-05 09:52:56

2019 Shanghai Online Substring

传送门题意给定一个主串S,m个模式串T,问主串中有多少个字串与模式串T比配这里的匹配指首尾字符相同,中间部分可以乱序(可以理解为相同字母个数相同)。思路整体思路就是,将T个模式串按照长度排序,相同长度的模式串一起处理。对于每一种长度len,求一次主串S长度为len的子串哈希值。考虑到空间问题,我们只存储有贡献的子串,即出现过的。赛时维护的位置前缀和应该是会冲突的,所以这里用哈希和来维...

2019-09-20 18:48:44

卡常数!!!

RT

2019-09-12 20:44:07

GDKOI2016Day1T1-魔卡少女

题目描述君君是中山大学的四年级学生。有一天在家不小心开启了放置在爸爸书房中的一本古书。于是,君君把放在书中最上面的一张牌拿出来观摩了一下,突然掀起一阵大风把书中的其她所有牌吹散到各地。这时一只看上去四不像的可爱生物“封印之兽”可鲁贝洛斯从书中钻了出来,它告诉君君书中的牌叫“库洛牌”,现在散落各地已实体化,要君君将它们全部再次封印起来,以免危害世界,于是君君开始过上了收服“库洛牌”的旅程。经...

2019-09-11 15:40:09

51Nod 1391 01串(思维+前缀和)

传送门题意:思路:预处理出每个点向左和向右分别最远能扩展多远。处理完后O(n)扫一遍串即可。很常规的0->-1,1->1维护一个【0,i】的前缀和cur,当cur<0表示[0,i]区间0的个数大于1的个数,即当前长度为最长的,否则判断cur+1是否出现过,如果cur+1这个数值没有出现过,则向左扩展最大长度为0,如果曾经出现过,则两点间的串0比1多,因为有前缀和可知,...

2019-09-11 15:08:26

Dinic模板

#include<bits/stdc++.h>#definemkmake_pairusingnamespacestd;typedeflonglongll;constdoublePI=acos(-1.0);constdoubleeps=1.0e-8;constintINF=0x3f3f3f3f;constintmaxn=1...

2019-09-06 22:04:34

查看更多

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