2 litmxs

尚未进行身份认证

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

等级
TA的排名 4w+

上下界网络流

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

2018-09-15 18:19:38

线性素数筛 模板

const int MAXN = 1e8+1000;int prime[MAXN/10];bool is_prime[MAXN+1] = {0};int getprime(int n){ int tot = 1; prime[0] = 2; is_prime[2] = true; for(int i=3; i<=n; i+=2) is_prime[i...

2018-09-15 18:14:24

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

题目链接:Jiu Yuan Wants to Eat题目大意一颗树,n各节点(n≤105n≤105n \leq 10^5)每个节点上有一个值aiaia_i(ai≤264)ai≤264)a_i \leq 2^{64}) 有四种操作 1. 将u到v路径上所有节点值乘以x(x≤264)x≤264)x \leq 2^{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

题目链接:Problem E. 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>using namespace std;const int maxn = 1e5 + 100;struct Node{ Node * ch[2]; int r, v, s; Node (int v = 0): v(v) { ch[0] = ch[1] = nullptr; ...

2018-08-20 11:29:35

差分标记

次数 a1a1a_1 a2a2a_2 a3a3a_3 a4a4a_4 a5a5a_5 通项 一次 1 1 1 1 1 an=1an=1a_n = 1 二次 1 2 3 4 5 an=nan=na_n = n 三次 1 3 6 10 15 an=n(n+1)2an=...

2018-08-05 12:28:47

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

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

2018-08-02 19:03:39

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

题目链接: E room题目大意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 组合数学 莫队算法

题目链接:HDU 6333 Harvest of Apples题目大意T组询问(T≤105T≤105T \leq 10^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 拓扑排序 线段树

题目链接: J Hash Function题目大意一张hash表,长度为n,哈希函数为hash(x) = x mod n,如果有冲突,则位置向后移一位(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 图论 欧拉通路

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

2018-07-26 09:55:44

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

题目链接:1007 Naive Operations题目大意两个数组a和b, 长度为n,a一开始全都是0,b里面是1-n的排列 有两两种操作 add l, r : 将a数组[l, r]内所有元素+1 query l, 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

题目链接:1004 Distinct Values题目大意一个数列, 长度为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 贪心 排序

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

2018-07-23 19:17:12

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

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

2018-07-21 09:55:54

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

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

2018-07-19 19:09:03

查看更多

勋章 我的勋章
    暂无奖章