ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共277篇）

luoguP2826 LJJ的数学课

思路把公式拆开维护两个值，一个a[i]的总和，一个a[i]*i的总和也可以用树状数组维护，模板题代码 #include <iostream> #include <vector> #include <cstdio> #include <cstrin...

线段树

2018-10-30

1 456

noip2017列队

目录 #2319. 「NOIP2017」列队链接思路代码思路代码 #2319. 「NOIP2017」列队链接 loj 思路动态开点线段树，详见代码。代...

暴力动态开点线段树

2018-10-30

0 650

bzoj3289 Mato的文件管理

题目 bzoj3289 思路区间求逆序对离散化+莫队+树状数组修改代码 /************************************************************** Problem: 3289 User: 3010651817 ...

莫队离散化暴力

2018-10-22

0 488

P4396 [AHOI2013]作业

题目链接 luogu4396 思路唯有水题暖人心咕了4天，今天跟着std对拍才做出来不得不说题解真的水的一批先离散化一下第一问差分询问，权值树状数组套一套就好了 \(nlog_{n}\) 第二问，Emma 莫队，加上树状数组维护修改 \(nlog_{n}sqrt_{n}\) \(3s\...

莫队树状数组暴力离散化

2018-10-22

0 420

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 503

P3709 大爷的字符串题

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

离散化莫队

2018-10-18

0 460

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 479

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 431

bzoj1055 ||P4290 [HAOI2008]玩具取名

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

DP

2018-10-15

1 499

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 495