• 等级
  • 113447 访问
  • 721 原创
  • 1 转发
  • 4249 排名
  • 145 评论
  • 34 获赞

洛谷 P3747 [六省联考2017]相逢是问候 线段树+扩展欧拉定理

题目:https://www.luogu.org/problemnew/show/P3747分析:幂次可以考虑扩展欧拉定理。对于一个模数ppp,使得ϕ(ϕ(...ϕ(p)))=1\phi(\phi(...\phi(p)))=1ϕ(ϕ(...ϕ(p)))=1,最少ϕ\phiϕ的个数limlimlim。每次的ccc是一样的,显然当一个位置修改次数大于limlimlim。这个位置就不变了。维...

2019-04-23 20:29:42

洛谷 P3750 [六省联考2017]分手是祝愿 dp

题目:https://www.luogu.org/problemnew/show/P3750分析:显然按一个开关不能使得比他大的数熄灭。所以最优方案一定是每次选出最大的数按掉。可以用枚举倍数,然后用vector存某个数的约数,求出需要按的开关数cntcntcnt。设f[i]f[i]f[i]表示还有iii个开关需要按到还有i−1i-1i−1个开关需要按的情况期望需要多少步,显然f[i]...

2019-04-23 10:56:16

bzoj 3328: PYXFIB 单位根反演

DescriptionInput第一行一个正整数,表示数据组数据,接下来T行每行三个正整数N,K,POutputT行,每行输出一个整数,表示结果SampleInput1123SampleOutput1HINTSourceByWcmg分析:组合数很大,考虑化掉组合数。化简上诉式子得到=∑i=0n[i mod k==0](ni)∗F...

2019-04-23 10:25:57

洛谷 P3746 [六省联考2017]组合数问题 矩阵乘法

题目:https://www.luogu.org/problemnew/show/P3746分析:设f[i][j]f[i][j]f[i][j]表示在m mod k=jm\mod\k=jm mod k=j的(im)\binom{i}{m}(mi​)的和。转移显然,f[i][j]=f[i−1][j]+f[i−1][(j+k−1) mod&n...

2019-04-22 10:30:26

洛谷 P3749 [六省联考2017]寿司餐厅 最小割

题目:https://www.luogu.org/problemnew/show/P3749分析:显然选择了一个区间[l,r][l,r][l,r],那么一定要选他的子区间。因为区间的价值有正负,所以考虑最大权闭合子图。即SSS向每个权值为正区间[l,r][l,r][l,r]连边,[l,r][l,r][l,r]向负区间连边,每个区间[l,r][l,r][l,r]向[l+1,r][l+1,r]...

2019-04-22 10:26:37

洛谷 P5284 [十二省联考2019]字符串问题 后缀数组+主席树优化加边

题目:https://www.luogu.org/problemnew/show/P5284分析:考虑怎样构造一个合法串。我们从每一个AAA类串向他支配的BBB类串连边,BBB类串向以他为前缀的AAA类串连边,形成一个有向图。每一个AAA类串权值设为他的lenlenlen,BBB类串设为0。那么一条路径的权值和就是某个合法串的长度。显然相当于求图最长链,存在环则解无限大,不然可以拓扑排序求...

2019-04-18 18:56:29

jzoj 5062.【GDOI2017第二轮模拟day1】航海舰队 fft

DescriptionByteasar组建了一支舰队!他们现在正在海洋上航行着。海洋可以抽象成一张n×m的网格图,其中有些位置是“.”,表示这一格是海水,可以通过;有些位置是“#”,表示这一格是礁石,不可以通过;有些位置是“o”,表示这一格目前有一艘舰,且舰离开这一格之后,这一格将变为“.”。这些“o”表示Byteasar的舰队,他们每天可以往上下左右中的一个方向移动一格,但不能有任...

2019-04-17 10:40:38

洛谷 P5290 [十二省联考2019]春节十二响 堆+启发式合并

题目:https://www.luogu.org/problemnew/show/P5290分析:考虑一条链且根不为链端的情况。一定是根左儿子的一个数和右儿子的一个数组成一个集合。因为显然两个节点都在一侧显然不行,只选一个太亏。那么就是左边最大匹配右边最大,左边第二匹配右边第二……拓展到任意子树,我们可以合并两个儿子的方案。显然不能选两个集合都在一边(一定会有冲突,不然这两个集合一定...

2019-04-16 20:36:52

洛谷 P5283 [十二省联考2019]异或粽子 字典树+堆

题目大意:https://www.luogu.org/problemnew/show/P5283分析:考虑对数列跑前缀异或和,然后相当于取两个数,把前kkk大的加起来。可以像超级钢琴那道题一样,先把每个位置iii结尾的序列,找到一个j<ij<ij<i且ai xor aja_i\xor\a_jai​ xor aj​...

2019-04-16 18:39:51

洛谷 P3308 [SDOI2014]LIS 最小割

题目描述给定序列A,序列中的每一项Ai有删除代价Bi和附加属性Ci。请删除若干项,使得A的最长上升子序列长度减少至少1,且付出的代价之和最小,并输出方案。如果有多种方案,请输出将删去项的附加属性排序之后,字典序最小的一种。输入输出格式输入格式:输入包含多组数据。输入的第一行包含整数T,表示数据组数。接下来4*T行描述每组数据。每组数据的第一行包含一个整数N,表示A的项数。接下来三行...

2019-04-16 11:06:59

洛谷 P5293 [HNOI2019]白兔之舞 单位根反演+fft

题目:https://www.luogu.org/problemnew/show/P5293分析:设f[t]f[t]f[t]为余数为ttt的答案。考虑走iii步的贡献,f[t]=∑i=0L[i mod k==t](Li)W(x,y)if[t]=\sum_{i=0}^{L}[i\mod\k==t]\binom{L}{i}W^i_{(x,y)}f[t]=i=0∑L​[...

2019-04-16 08:38:30

洛谷 P5280 [ZJOI2019]线段树 dp+线段树

题目描述九条可怜是一个喜欢数据结构的女孩子,在常见的数据结构中,可怜最喜欢的就是线段树。线段树的核心是懒标记,下面是一个带懒标记的线段树的伪代码,其中tagtagtag数组为懒标记:其中函数Lson⁡(Node)\operatorname{Lson}(Node)Lson(Node)表示NodeNodeNode的左儿子,Rson⁡(Node)\operatorname{Rson}(...

2019-04-16 08:12:45

jzoj 5061.【GDOI2017第二轮模拟day1】最长路径 dp

Description在Byteland一共有n个城市,编号依次为1到n,它们之间计划修建n(n-1)/2条单向道路,对于任意两个不同的点i和j,在它们之间有且仅有一条单向道路,方向要么是i到j,要么是j到i。换句话说,这是一个n个点的竞赛图。Byteasar居住在1号城市,他希望从1号城市出发,沿着单向道路不重复地访问一些城市,使得访问的城市数尽可能多。请写一个程序,帮...

2019-04-15 18:28:36

洛谷 P3233 [HNOI2014]世界树 虚树+dp

题目:https://www.luogu.org/problemnew/show/P3233分析:先把虚树建出来,顺便把根节点插入到虚树中。然后进行dp求出虚树上每个节点到最近关键点的编号。可以两次bfs求,因为有可能是他的兄弟最近。我们先求儿子对父亲的影响,再让父亲更新儿子,这样就可以求出来了。考虑怎么求答案。对于每一个虚树节点维护一个sum[x]sum[x]sum[x],先把他赋值成...

2019-04-11 11:49:27

洛谷 P4218 [CTSC2010]珠宝商 后缀自动机+点分治

题目:https://www.luogu.org/problemnew/show/P4218分析:一种显然的暴力就是枚举一个起点,在这个点进行dfs,然后在后缀自动机上跟着跳。跳到的点的right集大小即为这条路径的答案。这样做的复杂度是O(n2)O(n^2)O(n2)。树上的路径问题可以考虑点分治。显然一条路径可以被拆成两段,xxx到根和根到yyy。这条路径的答案就是所有xxx到根路径...

2019-04-08 14:58:46

洛谷 P4324 [JSOI2016]扭动的回文串 manacher+字符串hash

题目描述JYY有两个长度均为NNN的字符串AAA和BBB。一个扭动字符串S(i,j,k)S(i,j,k)S(i,j,k)由AAA中的第iii个字符到第jjj个字符组成的子串与BBB中的第jjj个字符到第kkk个字符组成的子串拼接而成。比如,若A=’XYZ’A=’XYZ’A=’XYZ’,B=’UVW’B=’UVW’B=’UVW’,则扭动字符串S(1,2...

2019-04-04 10:28:23

洛谷 P4323 [JSOI2016]独特的树叶 树hash

题目描述JYY有两棵树AAA和BBB:树AAA有NNN个点,编号为111到NNN;树BBB有N+1N+1N+1个节点,编号为111到N+1N+1N+1。JYY知道树BBB恰好是由树AAA加上一个叶节点,然后将节点的编号打乱后得到的。他想知道,这个多余的叶子到底是树BBB中的哪一个叶节点呢?输入输出格式输入格式:输入一行包含一个正整数NNN...

2019-04-04 07:57:06

洛谷 P5043 【模板】树同构([BJOI2015]树的同构) 树hash

题目描述树是一种很常见的数据结构。我们把NNN个点,N−1N-1N−1条边的连通无向图称为树。若将某个点作为根,从根开始遍历,则其它的点都有一个前驱,这个树就成为有根树。对于两个树T1T1T1和T2T2T2,如果能够把树T1T1T1的所有点重新标号,使得树T1T1T1和树T2T2T2完全相同,那么这两个树是同构的。也就是说,它们具有相同的形态。现在,给你MMM...

2019-04-03 12:06:15

洛谷 P3320 [SDOI2015]寻宝游戏 set

题目描述小B最近正在玩一个寻宝游戏,这个游戏的地图中有N个村庄和N-1条道路,并且任何两个村庄之间有且仅有一条路径可达。游戏开始时,玩家可以任意选择一个村庄,瞬间转移到这个村庄,然后可以任意在地图的道路上行走,若走到某个村庄中有宝物,则视为找到该村庄内的宝物,直到找到所有宝物并返回到最初转移到的村庄为止。小B希望评测一下这个游戏的难度,因此他需要知道玩家找到所有宝物需要行走的最短路程。但是这个...

2019-04-03 09:25:25

洛谷 P4322 [JSOI2016]最佳团体 分数规划+dp

题目大意:给定一棵树,nnn个节点。每个节点有aia_iai​和bib_ibi​两个值。要求选出若干节点,保证某个节点被选,他的父亲一定被选。使∑i=1kai∑i=1kbi\frac{\sum_{i=1}^{k}a_i}{\sum_{i=1}^{k}b_i}∑i=1k​bi​∑i=1k​ai​​最大化。n≤1000n≤1000n≤1000分析:考虑分数规划,二分一个midmidmid,...

2019-03-29 16:17:27

Amber_lylovely

关注
  • 学生
  • 中国 广东省 东莞市
奖章
  • 持之以恒
  • 勤写标兵Lv3