uoj专题
Uoj #179 线性规划 单纯形算法
这是一道模板题。 （这个题现在标程挂了。。哪位哥哥愿意提供一下靠谱的标程呀？） 本题中你需要求解一个标准型线性规划： 有 n n 个实数变量 x 1 , x 2 ,…, x n x1,x2,…,xn 和 m m 条约束，其中第 i i 条约束形如 ∑ n j=1 a ij x j ≤ b i ∑j=1naijxj≤bi 。 此外
uoj 117 欧拉回路
1.判断是否为欧拉存在欧拉回路---裸的判断 欧拉回路就是看一笔能不能把途中所有的边跑完没得重复 对于无向边----建立双向边判断每个点的入度是否为2的倍数 1.1 对于有向边---建立单向边判断每个点的入度与出度是否相等 1.2 然后就是看一下是否所有的点是否连接----可以用并查集或者dfs判断，具体看情况来定。 2 判断是否存在欧拉回路，就是同时满足上边的1，2两个条件
UOJ #131 BZOJ 4199 luogu P2178【NOI2015】品酒大会 (后缀自动机、树形DP)
UOJ #131 BZOJ 4199 luogu P2178【NOI2015】品酒大会 (后缀自动机、树形DP) 水是水，但是写出了不少问题，因此写一发博客。 https://www.luogu.org/problemnew/show/P2178https://www.lydsy.com/JudgeOnline/problem.php?id=4199http://uoj.ac/probl
BZOJ 3218 UOJ #77 A+B Problem (主席树、最小割)
BZOJ 3218 UOJ #77 A+B Problem (主席树、最小割) 大名鼎鼎的A+B Problem, 主席树优化最小割…… 调题死活调不对，一怒之下改了一种写法交上去A了，但是改写法之后第4,5个点常数变大很多，于是喜提UOJ全站倒数第三 目前还不知道原来的写法为什么是错的，暂时先写一下A掉的那种写法的题解。 题目链接: (BZOJ) https://www.lydsy.c
UOJ #395 BZOJ 5417 Luogu P4770 [NOI2018]你的名字 (后缀自动机、线段树合并)
NOI2019考前做NOI2018题。。 题目链接: (bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=5417 (luogu) https://www.luogu.org/problemnew/show/P4770 (uoj) http://uoj.ac/problem/395 题解: 其实非常水，转化成\(S[l,r]\)和\(T
[UOJ 3]【NOI2014】魔法森林：LCT
点击这里查看原题 将所有路径按a升序排序，用LCT维护路径上最大的b，将边权化为点权，如果加入一条边x，其两端点分别为u,v，那么将u与i+x连边，v与i+x连边。 如果(u,v)路径最大的b值大于当前边的b，那么删去b最大的边。 注意：access操作中必须pushup，因为这个调了好久 /*User:SmallLanguage:C++Problem No.:3*/#inclu
[UOJ 5]【NOI2014】动物园：KMP
点击这里查看原题 cnt[i]表示从i出发，经过cnt[i]次nex[i]到达0。于是做两次KMP，第一次求nex[i]和cnt[i]，第二次求i一直nex[i]到达的第一个≤i/2的位置 /*User:SmallLanguage:C++Problem No.:5*/#include<bits/stdc++.h>#define ll long long#define inf ((
[UOJ 130]【NOI2015】荷马史诗：哈夫曼树
点击这里查看原题 二叉哈夫曼树教程：http://blog.csdn.net/shuangde800/article/details/7341289 这里是k叉哈夫曼树，依然采取贪心策略，不过需要注意的是首先要判断(n-1)%(k-1)是否为0，不为0则要添加权值为0的节点直到(n-1)%(k-1)=0 这是因为，每次合并操作会取出k个点，放进1个点，即每次减少k-1个点。而最终目标是使n个
UOJ 176 新年的繁荣
挺妙的解法。 发现边权很小，我们可以考虑从大到小枚举边权来进行$kruskal$算法，这样子对于每一个边权$i$，我们只要枚举$0 \leq j < m$，找到一个点使它的点权为$i | 2^j$，尝试连边即可。 另外，如果同一个点权重复出现，一定有办法使这个边权连满，这样子直接累加到答案里就可以了。 时间复杂度$O(m * 2^m)$，再套一个并查集的复杂度。 Code： #inclu
【bzoj 4326】【codevs 4632】【UOJ #150】[NOIP 2015]运输计划（dfs+lca+二分答案+差分）
4326: NOIP2015 运输计划 Time Limit: 30 Sec Memory Limit: 128 MB Submit: 789 Solved: 520 [ Submit][ Status][ Discuss] Description 公元 2044 年，人类进入了宇宙纪元。L 国有 n 个星球，还有 n−1 条双向航道，每条航道建立在两个星球之间，这 n−1
【UOJ 测试】B. 【#245 UER #7】天路（近似算法+RMQ）
245. 【UER #7】天路 隆冬将至，几天后跳蚤国便会迎来寒冬，这对于以血肉之躯和飞机搏斗的跳蚤们来说并不是件好事……然而在悠悠历史岁月中，跳蚤国早已有了应对严寒的应急措施方案！ 在跳蚤国王的带领下，跳蚤们准备启动天路热能塔 —— 红米 note7（红米 note7 为发烧而生）。这座热能塔高耸入云，直接穿出大气层从太空中直接吸收太阳光，垂直向下将热能送往跳蚤国各个角落。热
【UOJ 测试】C. 【#246 UER #7】套路（乱搞+枚举）
C. 【UER #7】套路 反攻正在进行中，按照套路，跳蚤国将会很快获得最终的胜利。跳蚤国的情报局也没闲下来，他们正打算派遣一批“菲克蚤”前往跳晚国窃取有关三星 note7 的资料。 Fake Yang 是这批“菲克蚤”的教练，他教会他们各种 Fake 的技术，以便更好混入敌方内部。共 n n 只菲克蚤，由 1 1 到 n n 编号。Fake Ya
【UOJ 测试】A. 【#244 UER #7】短路（贪心（模拟+枚举））
A. 【UER #7】短路 “第七套广播体操，原地踏步——走！” 众所周知，跳蚤们最喜欢每天早起做早操，经常天还没亮就齐刷刷地站在操场做着反复纵跳热热身。跳晚国在研制三星 note7 的时候注意到了这点，于是他们打算让炸弹更快地引爆，这样就可以消灭更多早起的跳蚤。 三星 note7 的主板可以看作是由 (2n+1)×(2n+1) (2n+1)×(2n+1)