ComplexPug

未归档

做题记录(1)

/ 注册

全部文章 / 未归档（共273篇）

CF375D Tree and Queries

题目 luogu 思路唯有水题暖人心只用子树的树，当然dfs序列区间查询出现k次的数字的个数 nub[i]记录出现次数大于i的数字个数发现只是O(1)的转移，想想就OK了代码 ps:为了更好地阅读，我加一段cpp吧 void add(int x) { hav[x]...

dfs序莫队

2018-10-18

0 500

P3709 大爷的字符串题

题意询问区间众数出现的次数思路唯有水题快人心离散化+莫队莫队一定要先加后减，有事会出错的莫队维护区间众数: 维护两个数组，一个数组记录权值为x的出现次数，一个记录出现次数为x的数的个数 add很简单，更新ans delete的时候，删除的是ans话，查看出现次数为x的个数是否为1，...

离散化莫队

2018-10-18

0 452

CF873B Balanced Substring

1到n内0,1个数相同的个数的最长字串 \(i>=j\) \[1的个数=0的个数\] \[sum[i]-sum[j-1]=i-(j-1) - (sum[i]-sum[j-1])\] 这里把\((j-1)\)替换为\(j\) \[2*sum[i]-2*sum[j]=i-j\] \[2*sum[i...

hash

2018-10-17

0 475

bzoj 3791 作业

思路重要信息是区间m次修改最多能产生2*m-1个区间然后就成了简单dp了代码 //f[j][i][0/1]表示到j这个点分了i段，这一段染色的是0/1的作业数 #include <bits/stdc++.h> using namespace std; #define ll ...

DP

2018-10-16

0 426

bzoj1055 ||P4290 [HAOI2008]玩具取名

目录链接思路代码链接 luogu bzoj 思路区间dp 然后\(f[i][j][k]\) 区间\([i,j]\)能否变成\(k\)字符（字符当然得转化一下）字符的个数不多，直接暴力\(check\)，暴力转移就行，\(%...

DP

2018-10-15

1 496

loj 诗歌

链接链接思路好久之前的考试题了吧，之前貌似抄的题解现在理解了怕忘了,就写个题解记录一下吧，题目还是不错的枚举中间点j \[H_{i}-H_{j}=H_{j}-H_{k}\] \[H_{k}+H_{i}=2*H_{j}\] 由于H是一种n的排列，所以取值就是\([1,n]\) 那就可以...

树状数组

2018-10-14

1 489

hdu 3698 UVA1490 Let the light guide us 线段树优化DP

题目链接 and 题目大意 hdu3698 但是 hdu的数据比较弱，所以在这luogu提交吧UVA1490 Let the light guide us 有一个\(n*m\)的平原，要求每行选一个点，选\(n\)个点建造塔楼。平原上每个点都有他自己的花费时间和魔法值。为了正确控制塔楼，我们...

线段树 DP

2018-10-12

1 504

#10078. 「一本通 3.2 练习 4」新年好

题目链接 loj 思路亲戚很少，可以每个点都算一遍单源最短路然后dfs 错误原因算错复杂度 #include <iostream> #include <cstring> #include <queue> #include <cstdio&g...

2018-10-10

0 515

#10178. 「一本通 5.5 例 4」旅行问题

题目 loj链接思路 ***写，考试最后5min找到bug，考玩10minAC，成功GG 这题没啥算法(感觉跟dp有点关系?) 他们说正解是单调队列，鬼知道咋用，反正我是O(n) 题目数据最大好像是1e5，大家也可以写个O(nlogn)的水一水拉就是预处理个 f1 ,f2，代码里的...

2018-10-10

0 624

luoguP2572 [SCOI2010]序列操作

题目&&链接反正数据都是一样的，luogu比较友好 luogu bzoj lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作： 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a,...

线段树

2018-10-10

1 464