吴国庆

acm

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

/ 注册

全部文章 / acm （共50篇）

Divide Points siwei

链接题意：平面上有n个点（互不相同）现要把所有点分成两部分A，B 并对两点P，Q之间 Euclidean distance 染***r> 当点p，q属于同一部分时染成黄色否则染整蓝***r> 输出满足使所有相同距离的颜色不同的集合A Euclidean distance：（...

2020-05-04

0 423

线性预处理逆元

2020-05-04

0 435

Codeforces Round #612(Div. 2) D. Numbers on Tree 思维

传送门题意：现在有一棵树每个点有一个ci和ai ai为点权，ci代表i的子树中点权aj <ai 的个数现在给你这棵树的形状和每个点的ci 构造所有点的ai n<2000 思路： ci大于子节点个数时显然不能构造出解；假设当前节点有m个子节点该点的Ci为k；那么就相当于将该...

2020-05-04

0 443

Codeforces Round #613 (Div. 2)D. Dr. Evil Underscores Trie树上的简单dp

链接题意：给n个数求x与a[i]异或的最大值最小思路：每个数拆成2进制数建立一个trie树，在trie树上dp即可难点主要是实现方面对trie树建边的思想没有理解很到位 #include<bits/stdc++.h> #define warn printf("...

2020-05-04

0 534

poj3486分块实现

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

2020-05-04

0 516

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 393

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 484

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

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

2020-05-04

0 429

洛谷P5357 AC自动机模板题

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

2020-05-04

0 408

nefu 2027Ac自动机 + 状压dp

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

2020-05-04

0 376