2 litmxs

尚未进行身份认证

博客内容如有错误,还望指正

等级
博文 136
排名 4w+

上下界网络流

来自:https://blog.csdn.net/linkfqy/article/details/74779656无源汇上下界可行流构建虚拟源点SS,虚拟汇点TT若i点原来入>出,则SS向i连一条容量为其差值的边若i点原来出>入,则i向TT连一条容量为其差值的边因为一条边最终流量等于下界+新图对应流量,原来流量不平衡的点需要用虚拟源汇来补偿流量因为...

2018-09-15 18:19:38

线性素数筛 模板

constintMAXN=1e8+1000;intprime[MAXN/10];boolis_prime[MAXN+1]={0};intgetprime(intn){inttot=1;prime[0]=2;is_prime[2]=true;for(inti=3;i<=n;i+=2)is_prime[i...

2018-09-15 18:14:24

ACM-ICPC 2018 焦作赛区网络预赛 E. Jiu Yuan Wants to Eat 树链剖分 线段树

题目链接:JiuYuanWantstoEat题目大意一颗树,n各节点(n≤105n≤105n\leq10^5)每个节点上有一个值aiaia_i(ai≤264)ai≤264)a_i\leq2^{64})有四种操作1.将u到v路径上所有节点值乘以x(x≤264)x≤264)x\leq2^{64})2.将u到v路径上所有节点值加上x(x≤264)x≤264...

2018-09-15 18:07:36

[HDU 6430] 2018 Multi-University Training Contest 10 Problem E. TeaTree 暴力 bitset

题目链接:ProblemE.TeaTree题目大意一颗树,每个节点上有一个小于等于1e5的数字,然后每个节点的值等于所有以它为LCA的节点对(i,j)中gcd(v[i],v[j])的最大值,要求输出所有节点的值思路一开始想到用bitset记录每个节点的所有因数,但TLE了,没想到G++的bitset有一个函数叫做_Find_first()能快速找到为1的最低位,...

2018-08-22 18:35:16

Treap kth rank 模版

#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e5+100;structNode{Node*ch[2];intr,v,s;Node(intv=0):v(v){ch[0]=ch[1]=nullptr;...

2018-08-20 11:29:35

差分标记

次数a1a1a_1a2a2a_2a3a3a_3a4a4a_4a5a5a_5通项一次11111an=1an=1a_n=1二次12345an=nan=na_n=n三次1361015an=n(n+1)2an=...

2018-08-05 12:28:47

牛客网暑期ACM多校训练营(第五场)F take 线段树 概率

题目链接:Ftake题目大意有n个箱子,每个箱子里面有p[i]/100的概率有一个大小为d[i]的钻石一开始你手上的钻石大小为0,你从第一个箱子开始,依次打开每一个箱子,如果箱子里面的钻石大小比你手上的大,那就拿起箱子里的钻石替换自己的,求最后替换次数的期望思路考虑第i次开箱子,箱子里钻石比你手上的大的概率为,当前钻石比d[i]小的概率*开箱子开出钻石的...

2018-08-02 19:03:39

牛客网暑期ACM多校训练营(第五场)E room 费用流

题目链接:Eroom题目大意4n个学生,每四个人一个寝室,告诉你原先每个人在那个寝室,然后告诉你n个小组,每组四个人,要让每个小组的人在同一个寝室,求怎么换寝室使得最少的人需要换寝室n<=100思路很容易看出来是网络流,接下来就是如何建图了把4n个学生每个学生当作一个结点,再拿n个结点当做小组(小组内4个人要在一个宿舍),将四个小组成员向小组连边...

2018-08-02 18:31:40

组合数 模板

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=1e5+100,mod=1e9+7;llinv[maxn],fac[maxn],finv[maxn];//逆元,阶乘,阶乘逆元voidinit(){inv[1]=1;...

2018-08-02 10:09:08

HDU 6333 2018 Multi-University Training Contest 4 1002 Problem B. Harvest of Apples 组合数学 莫队算法

题目链接:HDU6333HarvestofApples题目大意T组询问(T≤105T≤105T\leq10^5),每次询问求S(n,m)=∑mi=0C(n,m)mod(109+7)S(n,m)=∑i=0mC(n,m)mod(109+7)S(n,m)=\sum_{i=0}^{m}C(n,m)mod(10^9+7)思路可以得出:S(n,m)=...

2018-08-02 10:07:27

牛客网暑期ACM多校训练营(第四场)J Hash Function 拓扑排序 线段树

题目链接:JHashFunction题目大意一张hash表,长度为n,哈希函数为hash(x)=xmodn,如果有冲突,则位置向后移一位(n-1的下一位是0)现在给你一张hash表,要求出字典序最小插入顺序思路如果a[i]%n!=i,说明在a[i]插入前,a[i]%n到i-1所在的位置已经被占用了,也就是说区间[a[i]%n,i-1]中的数字必须在a...

2018-07-30 09:58:29

ext/rope和ext/pb_ds库

官方文档堆#include<ext/pb_ds/priority_queue.hpp>usingnamespace__gnu_pbds;__gnu_pbds::priority_queue<node,less<node>,pairing_heap_tag>pq;//如果using了std,必须显示表面名称空间__gnu_pbdsjoin...

2018-07-27 16:37:25

2018 Multi-University Training Contest 2 1003 Cover 图论 欧拉通路

题目链接:1003Cover题目大意一张无向图,n个节点,m条边,没有重边和自环,不一定连通,求最少多少条路径能覆盖这张图所有边,每条边只能被一条路径覆盖思路将图中每个联通块的奇点(度数为奇数的点)找出来,如果有两个或两个以下的奇点,则为欧拉图,可以一笔画,否则将从第三个奇点开始,将奇点们两两连接起来,让这张图变成欧拉图,求其欧拉通路,将后来新增的奇点连边删除后,得到的路径...

2018-07-26 09:55:44

2018 Multi-University Training Contest 2 1007 Naive Operations 线段树 区间更新区间查询

题目链接:1007NaiveOperations题目大意两个数组a和b,长度为n,a一开始全都是0,b里面是1-n的排列有两两种操作addl,r:将a数组[l,r]内所有元素+1queryl,r:求∑ri=l⌊aibi⌋∑i=lr⌊aibi⌋\sum_{i=l}^{r}\lfloor\frac{a_i}{b_i}\rfloor思路线...

2018-07-25 17:33:20

小球和盒子

from:https://blog.csdn.net/jaihk662/article/details/79572685问题列举:把n个不同的小球放在m不同的个盒子里,有空盒把n个不同的小球放在m不同的个盒子里,无空盒把n个不同的小球放在m相同的个盒子里,有空盒把n个不同的小球放在m相同的个盒子里,无空盒把n个相同的小球放在m不同的个盒子里,有空盒把n个相同的小球放在m不同的个...

2018-07-25 09:44:18

2018 Multi-University Training Contest 1 1008 RMQ Similar Sequence 笛卡尔树 概率

题目链接:1008RMQSimilarSequence题目大意rmq(a,l,r)表示a[l-r]中最大值的下标,如果有相同的数字,取下标小的定义rmq相似,如果两个数组a,b长度相同,对于所有[l,r],都有rmq(a,l,r)==rmq(b,l,r)则abrmq相似现在给你一个数组a,有一个数组b长度与a相同,且每一个元素都是从[0,1]之间独...

2018-07-24 13:06:13

2018 Multi-University Training Contest 1 1004 Distinct Values

题目链接:1004DistinctValues题目大意一个数列,长度为n,有m个特征[l,r],表示区间内所有数字都不重复思路用一个数组pre[i],表示上一次数字i在数组中出现的位置将所有特征排序,先按l从小到大排序,如果l相同,按r从大到小排序(这样如果区间相互包含的情况只需要处理一次最大的那个区间,小的区间跳过就好了)然后遍历所有特征,对于...

2018-07-23 22:20:05

Balanced Sequence HDU 6299 2018 Multi-University Training Contest 1 1002 Balanced Sequence 贪心 排序

题目链接:1002BalancedSequence题目大意给你n个括号序列,你可以重新排序这些序列,然后拼接起来,求最大的合法括号子序列思路先将每个序列的可以匹配的括号去掉,最后剩下一个类似”))))(((“的序列,用一个pair保存’)’和’(‘的数量,按照’)’的数量乘以’(‘的乘机从大到小排序,最后从第一个开始,贪心地拼接序列,看放到已有序列的左边还...

2018-07-23 19:17:12

牛客网暑期ACM多校训练营(第一场)E. Removal 动态规划

题目链接:E.Removal题目大意一个数组s,长度为n(n≤105)n≤105)n\leq10^5),数组元素s[i]≤10s[i]≤10s[i]\leq10,要求从中删除m(m≤10)m≤10)m\leq10)个数字,求能得到多少个不重复的结果,mod1e9+7思路动态规划,如果不考虑重复,令dp[i][j]:=前i个数字删除j个后有多少种结果...

2018-07-21 09:55:54

牛客网暑期ACM多校训练营(第一场)D. Two Graphs 图论 枚举全排列

题目链接:D.TwoGraphs题目大意两张图G1和G2,最多只有8个节点,两个节点之间最多有一条边,两张图节点个数都为n,边数为m1和m2求由多少种方案,从G2中选出m1条边,使得G1和G2重构思路枚举n个节点的全排列,就是将G2中节点和G1的节点一一对应起来,一共由n!中对应方案,判断每一种方案是否可行,如果可行,那将方案用一个unsignedl...

2018-07-19 19:09:03
奖章
    暂无奖章