3 LowestJN

尚未进行身份认证

强省弱OIer

等级
TA的排名 1w+

AFO

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

2018-07-20 22:51:14

[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

[容斥 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

[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

[贪心 线段树] 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

[博弈] 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

[杂题] hihocode1715. 树联通问题

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

2018-03-28 22:08:02

[容斥 状压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

[补集转换] 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

[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

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

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

2018-03-23 21:14:30

[期望] 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

[数学] 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

[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

[二分 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

[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

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

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

2018-03-15 10:41:14

[数位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

[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

[回文串 线段树] 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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!