LowestJN-CSDN博客

原创【Note】The Power of Grids

Reference: Geometric Approximation Algorithms, Sariel Har-Peled, Chapter 1.回来写点看书的note，主要是简单整理一下看过的内容。看的第一本书是导师推荐的 Geometric Approximation Algorithms，里面介绍了一些几何问题的经典的techniques.第一章介绍了网格化（Grid），利用网格坐标点离散的性质，可以设计一些运行时间为 poly(m)\mathrm{poly}(m)poly(m)（mmm 为网

2022-02-22 01:08:20 624

原创 AFO

2018.7.20苟不下去了。下午查成绩T1炸成50分的时候就知道自己已经翻不了盘了。最后知道队线452的时候真是绝望。要是day1T2写了卡特兰数或者day2T1对拍一下就稳了吧。…...

2018-07-20 22:51:14 1911 5

原创 [Min-Max 容斥] LOJ#2542. 「PKUWC 2018」随机游走

这题我原来使用 O(2nn3)O(2nn3)O(2^n n^3) 暴力过的…跑的还贼快可以用Min-Max 容斥设 Max(S)Max(S)Max(S) 表示集合里最晚被访问的节点被访问的期望步数（也就是访问所有节点的期望步数）。设 Min(S)Min(S)Min(S) 表示集合里最早被访问的节点被访问的期望步数（也就是第一次访问到集合里的节点的期望步数）那么 Max(S)=∑T∈...

2018-05-24 18:29:11 1483

原创 [容斥 NTT] LOJ#2541. 「PKUWC 2018」猎人杀

很妙的题这题其实如果不考虑攻击的限制，也就是不管猎人死没死，他都能被当作攻击的目标，一个猎人被攻击到的概率是一样的。设 A=∑wiA=∑wiA=\sum w_i ， BBB 为以及死的猎人的 wiwiw_i 的和，设 PiPiP_i 为 iii 是下一个被杀死的概率（iii 之前还活着）那么 Pi=wiA−BPi=wiA−BP_i={w_i\over A-B}，如果不考虑攻击的限制，...

2018-05-13 10:39:01 1555

原创 [DP] LOJ#2473. 「九省联考 2018」秘密袭击

设 fifif_i 表示选出的联通块第 kkk 大的值大于等于 iii 的方案数那么答案就是 ∑wi=1i(fi−fi+1)=∑wi=1fi∑i=1wi(fi−fi+1)=∑i=1wfi\sum_{i=1}^w i(f_i-f_{i+1})=\sum_{i=1}^w f_i枚举 iii，把权值大于等于 iii 的点标记为 111，否则标记为 000，那么 fifif_i 就是树上包含至少 ...

2018-04-07 21:36:23 624

原创 [贪心线段树] LOJ#2472. 「九省联考 2018」IIIDX

从1到n枚举，逐位确定。首先可以把关系树建出来，一个点的权值要大于等于父节点的权值。如果没有相同数字的，第 iii 以及它子树种的点会选择 [n−sizei+1,n][n−sizei+1,n][n-size_i+1,n] 这个区间里的数，选完后把这个区间删去，继续考虑 i+1i+1i+1如果有重复的数字，那么第 iii 个点会选择第 n−sizei+1n−sizei+1n-size_i...

2018-04-07 21:29:41 564

原创 [博弈] LOJ#2471. 「九省联考 2018」一双木棋

考虑暴力。每次枚举放哪个位置，设已经放了棋子的位置集合为 SSS，fSfSf_S 表示当前放置情况为 SSS 时，双方采用最优策略后，两个人的权值和的差。那么如果是菲菲，会选择 fS+ai,jfS+ai,jf_S+a_{i,j} 最大的，牛牛会选择 fS−bi,jfS−bi,jf_S-b_{i,j} 最小的，然后跑dfs实际上如果记忆化一下就能过了。考虑每一种合法的状态，棋子都是放...

2018-04-07 21:16:17 430

原创 [杂题] hihocode1715. 树联通问题

考虑计算每条树边出现在哪些区间了，但是这样不太好统计，补集转换一下计算每条树边没有出现的区间的个数那么用set维护一下每棵子树中的点的标号，如果一个区间里的元素都不在这个set里或者都在这个set里，那么这个点到父亲的边都不在这个区间里启发式合并一下就可以了#include <cstdio>#include <iostream>#include <al...

2018-03-28 22:08:02 387

原创 [容斥状压DP] Atcoder ARC093 F - Dark Horse

wwwww比赛的时候题目看错了假设我们确定的1的位置，那么接下来的每一轮，1都会和一段长度为2的幂的区间里，标号最小的人pk。把1固定在1位置（求出最终方案数后乘上 2n2n2^n 就是答案），那么就相当于区间 [2,2][2,2][2,2]，[3,4][3,4][3,4]，[5,8][5,8][5,8]…[2n−1+1,2n][2n−1+1,2n][2^{n-1}+1,2^n] 里的最小...

2018-03-26 08:32:51 704

原创 [补集转换] Topcoder SRM563 DIV1. CoinsGame

枚举两个点，如果经过一系列操作使得一个留在棋盘上一个不在，那么这个点对是有价值的那么合法的放棋子的方案一定包含至少一个有价值的点对但是点对个数是 O((nm)2)O((nm)2)O((nm)^2) 的，直接容斥不行补集转化一下，可以发现如果点对 (a,b)(a,b)(a,b) 和点对 (b,c)(b,c)(b,c) 是没有价值的，那么点对 (a,c)(a,c)(a,c) 也是没有价值的...

2018-03-24 13:58:12 686

原创 [DP] Topcoder SRM 562 DIV1. InducedSubgraphs

分类讨论当 2k≤n2k≤n2k\le n 时，两边是树中间是一条链，枚举链然后DP当 2k>n2k>n2k>n 时，中间部分为一个联通块，这个联通块一定过重心，求出重心后DP#include <cstdio>#include <iostream>#include <algorithm>#include <vector>...

2018-03-24 13:51:31 429

原创 [树的直径] Codechef March Cook-Off 2018. Maximum Tree Path

这个套路好像是计蒜之道里的一题考虑枚举gcd把两端点都是gcd的倍数的边存下来，按照两段点较小值从大到小排序枚举每一条边，把这条边加入图中，可以用并查集维护出所有联通块的直径，然后就好了#include <cstdio>#include <iostream>#include <algorithm>#include <vector&...

2018-03-23 21:14:30 381

原创 [期望] Topcoder SRM561 Div1 1000. Orienteering

首先每条边至多走两遍，可以选出一条最长的链，这条链上的所有边走一遍，其他边走两边。那么答案就是 2|E|−|P|2|E|−|P|2|E|-|P| 其中 EEE 是边集，PPP 是最长的链这个的期望就是 2E(|E|)−E(|P|)2E(|E|)−E(|P|)2E(|E|)-E(|P|)E(|E|)E(|E|)E(|E|) 可以枚举每条边，求这条边存在的概率E(|P|)E(|P|)E...

2018-03-23 14:49:58 344

原创 [数学] Topcoder SRM560 Div1 1000. BoundedOptimization

可以枚举每个元素的值是上界、下界还是中间值，总共有 3n3n3^n 种情况若存在两个元素 xi,xjxi,xjx_i,x_j，它们都取中间值，且xixjxixjx_ix_j 不在式子中，那么设表达式为 axi+bxj+caxi+bxj+cax_i+bx_j+c，可以发现最有情况肯定是 xixix_i 或 xjxjx_j 达到边界值设 kkk 为取中间值的元素的个数所以表达式可以写作...

2018-03-23 11:59:49 345

原创 [DP] LOJ#6307. 「雅礼国庆 2017 Day1」Clique

假设 xi>xjxi>xjx_i>x_j那么 iii 和 jjj 之间有边的条件是 xi−xj≥wi+wjxi−xj≥wi+wjx_i-x_j\ge w_i+w_j把一个点看作一个区间 (xi−wi,xi+wi)(xi−wi,xi+wi)(x_i-w_i,x_i+w_i)那么两个点有边的条件就是两个点代表的区间不重叠这题就转化成选出最多从区间使得这些区间两两不重叠这...

2018-03-20 11:02:59 308

原创 [二分 bfs] UOJ#371. 【UR #17】滑稽树下你和我

二分答案用点对 (x,y)(x,y)(x,y) 表示一个人在 xxx，另一个在 yyy 的状态，当 xxx 和 yyy 的距离小于等于二分的答案时，这个状态合法。两个状态 (x1,y1)(x1,y1)(x1,y1) 和 (x2,y2)(x2,y2)(x2,y2) 直接相连，当且仅当 x1x1x1 和 x2x2x2 之间有边或者 y1y1y1 和 y2y2y2 有边那么只要用bfs判断一...

2018-03-19 12:27:18 561 1

原创 [Contest] CodeChef March Challenge 2018

听说CC也分div1 div2了Mix the Colors如果有重复的数，就把最大的数加到这个数上，所以答案是n减去不同的数的个数Chef and Easy Problem从高到低枚举贪心。 Minions and Voting对每个人二分一下它能投票的区间Chef and Gcd Queries对每个质因数开线段树记录一下它的倍数出现的情况莫比乌斯反演就...

2018-03-15 13:22:09 351 2

原创 [线段树博弈] 一道博弈题

障碍点数和询问点数都是1e5 坐标范围为1e9（实际数据既然有大于1e9的）一个点的下方或左边存在必败点，则为必胜点，否则为必败点同一行的障碍会把这一行分成很多段，段与段之间是互不影响的。考虑同一段的点，若其中一个点为必败点，则之后的点一定是必胜点，也就是说要找到第一个必败点扫描线枚举每一行，用线段树维护每个位置是否有必败点，每一段的询问相当于在线段树上二分找到第一个没有必败点...

2018-03-15 10:41:14 354

原创 [数位DP] 【UNR #2】梦中的题面

当 c=1c=1c=1 的时候，很容易想到转成 bbb 进制每一位独立考虑，就可以数位DP了当 c=0c=0c=0 的时候，再加一维表示之前满足 xi=bixi=bix_i=b^i 的个数就可以了#include <cstdio>#include <iostream>#include <algorithm>#include <cst...

2018-03-14 10:04:26 640

原创 [DP] 【UNR #2】积劳成疾

fi,jfi,jf_{i,j} 表示长度为 iii 最大值为 jjj 的序列的答案枚举最大值的位置转移就好了#include <cstdio>#include <iostream>#include <algorithm>using namespace std;const int N=410,P=998244353;int n,k,an...

2018-03-14 09:58:48 393

原创 [回文串线段树] Codeforces Gym100032 ICL Cup 2012 K. Subpalindromes

题意是求一个区间里回文串的个数（出现位置不同的回文串算不同）用马拉车算出以每个点为中心的最长回文串长度考虑点 iii，iii点到以它为中点的最长的回文串的端点长度为 xxx那么它对一个询问的贡献是 min{i−L,R−i,x}min{i−L,R−i,x}\min\{i-L,R-i,x\}把询问的区间分成两部分 [L,mid][L,mid][L,mid]，[mid,R][mid,R]...

2018-03-11 19:14:16 454 1

原创 [随机构造] UOJ#76. 【UR #6】智商锁

随机1000张25个点的图，two-points枚举所有情况#include <cstdio>#include <iostream>#include <algorithm>#include <cstdlib>#include <map>#define fi first#define se secondusing n...

2018-03-10 15:54:17 575 1

原创 [决策单调分治] LOJ#535. 「LibreOJ Round #6」花火

如果 i&lt;ji&lt;jiai&gt;ajai&gt;aja_i>a_j 那么 iii 作为左端点比 jjj 优，右端点同理那么搞出两个上升序列，发现右端点递增的时候左端点也是单调上升的，也就是gjghfd和vector说的具有决策单调分治就好了#include &lt;cstdio&gt;#include &lt;iostream&gt;#in

2018-03-09 13:30:13 859 2

原创 [三元环] BZOJ5206: [Jsoi2017]原力

活那么久竟然都不会找三元环…https://www.cnblogs.com/jiachinzhao/p/7474761.html这题的话，颜色相同且两端点相同的边权值可以加在一起，然后找三元环就好了#include <cstdio>#include <iostream>#include <algorithm>using namespace s...

2018-03-09 09:03:50 728

原创 [最小割] Topcoder SRM558Div1. SurroundingGame

对网格黑白染色黑的格子和源点连边，白的格子和汇点连边因为如果保留benefit就必去删去cost或者所以和他相连的格子的cost大概是这样跑最小割#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#include &l...

2018-03-08 18:40:45 534

原创 [网络流] BZOJ3894 文理分科

经典模型我都不会每个点拆成三个点，分别表示“选文理”“周围的人都选文科”“周围的人都选理科”然后根据关系连边#include <cstdio>#include <iostream>#include <algorithm>#include <queue>using namespace std;const int N=10001...

2018-03-08 18:29:14 353

原创 [线性基贪心] Topcoder SRM557Div1. XorAndSum

对数列建线性基，求出最大异或值那么不在线性基里面的元素可以把它变成最大异或值在线性基里的元素，可以把最高位的元素变成最大值，然后把其他数异或上最大值#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#include <vec...

2018-03-08 15:45:00 634

原创 [网络流] Topcoder SRM556DIV. OldBridges

只有一个人的时候，可以把图建出来看是否满流但是两个人的时候会出现特殊情况把b1和b2反过来在跑一遍就好了#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#include <vector>#include &lt...

2018-03-08 14:51:58 704

原创 [容斥] Topcoder SRM555DIV1. MapGuessing

经典题了枚举初始状态的磁头位置，求出哪些位置可以随意改动，然后大力容斥#include <cstdio>#include <iostream>#include <algorithm>#include <vector>#include <cstring>using namespace std;typedef lo...

2018-03-08 07:53:42 407

原创 [Tarjan] BZOJ5201: [NEERC2017]Connections

tarjan的时候每次每次加入一条返祖边，都会至少缩去一个点，那么只要记录一下遍历过的边以及返祖边就可以了#include <cstdio>#include <iostream>#include <algorithm>using namespace std;const int N=100010;inline char nc(){ st...

2018-03-07 19:59:35 536

原创 [矩阵乘法优化DP] Topcoder SRM554. TheBrickTowerHardDivOne

dpfi,sfi,sf_{i,s} 表示第 iii 层的状态为 sss 的方案数转移是一个矩乘的形式用矩乘快速幂优化#include <cstdio>#include <iostream>#include <algorithm>using namespace std;const int P=1234567891;typedef...

2018-03-07 18:58:39 408

原创 [差分约束] Topcoder SRM553 Div1 Hard. YamanoteLine

可行的长度肯定是一个区间约束条件可以建城差分约束系统，那么判无解就是判是否有负环记一下负环上关于总长度的系数，二分就可以了#include <cstdio>#include <iostream>#include <algorithm>#include <vector>using namespace std;const i...

2018-03-07 13:23:13 493

原创 [启发式分裂] BZOJ5200 [NWERC2017]Factor-Free Tree

当找到一个根的时候会把区间分成两个部分，然后递归做问题就是怎么找根了可以用bzoj4059那种思路，大概叫启发式分裂吧对每个数，可以预处理一下在它左边第一个与他不互质的数和在它右边第一个与它不互质的数然后就 O(nlogn)O(nlog⁡n)\mathcal{O}(n\log n) 搞就可以了#include <cstdio>#include <iost...

2018-03-07 08:28:27 811

原创 [多项式exp] LOJ#556. 「Antileaf's Round」咱们去烧菜吧

学一发分治FFT求多项式exp感觉这种打法应该比牛顿迭代好打多了#include <cstdio>#include <iostream>#include <algorithm>using namespace std;const int N=1000010,P=998244353;inline void add(int &x,int...

2018-03-06 10:47:33 534

原创 [二分图] 【JOI2017春季合宿】Port Facility

T2比T1可做多了…每个玩具相当于一条线段，交叉的线段之间连边，就变成求二分图染色的方案数考虑怎么建边把左端点排序，右端点用set维护，假设现在加入的线段为(l,r)因为有三元环就直接无解了，所以当前所有右端点比r小的线段都是相互包含的，否则就无解而这时候这些线段之后染色的颜色都是一样的，所以可以缩起来我的做法是把右端点最小的加入set，当它被弹出set的时候把右端点第二小...

2018-03-06 09:04:40 604

原创 [DP] Codeforces 936D. World of Tank

令 fi,jfi,jf_{i,j} 表示走到 (i,j)(i,j)(i,j) 时的最大充能坐标离散后 O(n)O(n)O(n) DP一下就好了#include <cstdio>#include <iostream>#include <algorithm>#include <vector>#define all(x) x.begin()...

2018-03-05 16:55:12 485

原创 [链剖 FFT] LOJ#6289. 花朵

树形DP的转移是一个卷积的转移形式可以先链剖，一个点的轻儿子先合并，然后一条重链用分治FFT合并#include <cstdio>#include <iostream>#include <algorithm>#include <vector>#include <queue>using namespace std;...

2018-03-05 10:34:14 565

原创 [eertree] Codeforces 932G. Palindrome Partition

http://codeforces.com/blog/entry/19193不是很懂证明#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>using namespace std;const int N=1000010,P=1e9+7...

2018-03-05 10:31:47 672

原创 [Bluestein's Algorithm DFT] Codechef REALSET. Petya and Sequence

A和B的运算是卷积形式考虑把A和B DFTD(A)∗D(B)=0,D(B)≠0D(A)∗D(B)=0,D(B)≠0D(A)*D(B)=0 , D(B)\neq0也就是 A DFT后至少有一个0求出模某个质数意义下的 2n2n2n 次单位根用Bluestein’s Algorithm DFT#include <cstdio>#include <iost...

2018-03-01 16:46:25 422

原创 [DP 博弈] Topcoder SRM579 Div1. RockPaperScissors

每一轮的策略跟之前出现过的剪刀石头布的数量有关另 fi,a,b,cfi,a,b,cf_{i,a,b,c} 表示之前出现了 aaa 次石头， bbb 次剪刀，ccc 次布，然后第 iii 个筛子没用过的概率DP一下，每一轮独立算贡献// BEGIN CUT HERE // END CUT HERE #include <vector> #include <...

2018-02-28 11:12:04 316

空空如也

空空如也