吴国庆

分类

acm(50) Codeforces(6) Xcpc(4) 未归档(2) 算法学习(6) 题解(38)

/ 注册

全部文章（共106篇）

poj3486分块实现

传送门区间加和区间查询分块实现(是真慢。。。) #include<cstdio> #include<cmath> #include<iostream> #define ls rt<<1 #define rs rt<<1|1 #defi...

2020-05-04

0 622

bzoj 2038 经典莫队小z的袜子

莫队入门小z的袜子题意：n个数记ai，ai<=n m次询问：l~r区间内任意选两个数求其相同的概率稍微化简为求区间内每个数出现次数的平方和 #include<bits/stdc++.h> using namespace std; typedef long long LL...

2020-05-04

0 508

莫队

bzoj2038莫队入门题目目前没有理解的几点就是当前区间L R的初始化问题，为什么要L=1，R=0? 还有在更新过程中出现了cnt《0的情况？ hdu6483莫队求区间不同数字种类数当题目要求的区间操作满足以下条件时可以应用莫队 1）已知L，R区间答案可以O1求出【L-1，R】【L，R-1】...

2020-05-04

0 625

2018 黑龙江省赛A Sequence Game 莫队+ST表

A Sequence Game 大意：求区间内的最大值与最小值中的数是否都出现过看max-min+1是否等于区间数字种类数即可前者预处理ST表后者可用两种方法求出 1）莫队 #include<bits/stdc++.h> using namespace std; typedef ...

2020-05-04

0 584

2016 CCPC长春Sequence II 主席树 OR 分块

题目链接求L,R内所有数字第一次出现的下标的中位数区间第一次出现即倒着的最后一次出现所以我们倒着更新一个主席树如果位置 I 的数字第一次出现那么直接在第I颗树上的第I个位置加一即可否则在加完1后再在该数字的原位置减一找BUG真的好难啊 ✔ #include<bits/s...

2020-05-04

0 550

洛谷P5357 AC自动机模板题

P5357 对应输出n个模式串在文本串中出现的次数 AC自动机😳 坑点：可能出现重复模板串，所以标记结尾时做相应的修改即可这里的写法是把fail树对应的图建出来了，其实不需要建也可以求出(这不重要) void getans(void){ for(int i=1;i<=tot;i...

2020-05-04

0 545

AC自动机

洛谷P5357模板题 CodeForces 727E Games on a CD补 HDU – 2243 poj2778 nefuoj2027 在写AC自动机相关题目时要注意一下几点避免浪费时间 1）使用邻接矩阵建图时要注意将head 清空为-1 2）解决计数问题时mod运算比较费时，少用 3...

2020-05-04

0 700

nefu 2027Ac自动机 + 状压dp

想不出来啊想不出来😟（全局变量数组开大还会RE。。。。。）官方题解:**多模式串匹配的问题用 AC 自动机来解决。**首先用输入的这些串构建出 AC 自动机，然后用状压在 AC 自动机上对答案进行搜索。设 res[now][S][l]，表示的意思是在自动机上当前节点为 now，状态是 S，已经...

2020-05-04

0 497

HDU-2243考研路茫茫 AC自动机 + 矩阵快速幂

hdu-2243 n个模式串，求满足长度小于等于k且至少包含其中一种模式串的串数（只包含小写字母） k<2^31-1 多模式串的计数问题，我们用AC自动机来解决那么问题来了 1）怎么求至少包含一种的串数？正难则反，我们用所有串数减去一种都不含的就是至少包含一种的方案 2）所有长度小于等...

2020-05-04

0 526

Codeforces Round #618 E. Water Balance 贪心

Water Balance 题意: n个数可进行以下操作任意次：选择区间【l，r】其中的A【i】都变成这个区间的平均数，要求最小字典序思路：由于最后答案使单调不减的那假设前i个元素答案以求出，看当前位置的元素能否对当前答案优化，即前面元素的个区间答案加上当前元素能否使区间均值变小，一...

2020-05-04

0 539