pubgoso_2024

分类

acm(131) atcoder(1) bfs(3) cf(14) clion(2) dfs(15) dp(33) KMP(3) segement tree beats(1) wannafly(7) 主席树(2) 二分(10) 匹配(2) 单调栈(2) 大数(2) 字典树(1) 字符串(3) 思维(6) 数学(50) 暴力(2) 最小生成树(7) 最短路(8) 未归档(45) 构造(1) 树(4) 树状数组(11) 树链剖分(1) 模拟(3) 矩阵(2) 离散化(5) 线段树(16) 莫队(4) 记录(3) 贪心(20)

/ 注册

全部文章（共420篇）

2019icpc沈阳网络赛 D. Fish eating fruit （点分治）

题目链接大意：让你求树上%3后分别为0，1，2的所有路径之和。思路：树上路径分为两种，过根节点的，和在子树的，所以直接点分治，在计算每个根节点的贡献的时候，统计一下%3分别为0 1 2 的路径数，和路径和，然后每次直接算一下贡献就好了。细节见代码： #include<bits/...

2020-05-06

0 502

2019icpc沈阳网络赛 B. Dudu's maze(dfs)

题目链接大意：有个无向图，你从1出发，可以到任意联通的非怪物点，你至多可以选择一个可达的怪物房间使用魔法，传送到随机一个与怪物点相邻的点上，问你取得糖果的期望值（操作者足够聪明）。思路：我们先dfs记录一下，不到怪物房间就能取到的糖果数量，这一部分肯定是可以直接拿的，剩下就是从那些相邻（意为不用...

2020-05-06

0 425

大数全能版（转）

本文原地址 const int MAXN=150; struct bign { int len, s[MAXN]; bign () { memset(s, 0, sizeof(s)); len = 1; } bign (int...

2020-05-06

0 455

2019icpc上海网络赛 F. Rhyme scheme

题目链接预处理： d p [ i ]...

2020-05-06

0 429

luogu3806 点分治模板

题目链接每次找重心，然后处理每个子树。 // luogu-judger-enable-o2 #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define mp mak...

2020-05-06

0 418

Educational Codeforces Round 36 (Rated for Div. 2) E. Physical Education Lessons

题目链接大意：初始n天都是工作日，给你q个操作，分别是把l,r变成工作日或者非工作日。让你求出工作日的天数。思路：n很大，但操作数不大，所以我们要动态开点线段数来解决这个问题，算是裸题了。记录每个点和左右儿子节点的编号，如果是新的点就新开一个节点。其他的操作都是根普通线段树一样拉细节见...

2020-05-06

0 380

Educational Codeforces Round 72 (Rated for Div. 2) E. Sum Queries? (线段树)

题目链接大意：给你n个数，支持修改和查询操作查询一个和最小的集合，使得该集合不平衡(就是不满足：集合的和的所有位上的数字等于集合中的至少一个数的同位) 思路：显然我们要找到某一位上存在两个不为0的最小数，这两个数加起来就是答案。显然我们要拆分每一位建10颗线段树。具体做法：把每个数拆开，看每...

2020-05-06

0 399

Educational Codeforces Round 50 (Rated for Div. 2) B. Diagonal Walking v.2 （思维）

题目链接大意：给你一个目标点，让你从(0,0)出发走k步到(n,m)，（8个方向），问你最多能走几次斜着的，或者不能到思路：我们思考一下我们该怎么走，显然我们上来先斜着走到一个坐标为0，（从(n,m)到(0,0) ），然后我们看剩余的步数last和剩下的k，的奇偶关系。（首先要满足能走到的条件...

2020-05-06

0 386

VK Cup 2012 Round 1 D.Distance in Tree（点分治）

题目链接大意：给你一棵树，问你树上距离等于x的无序点对个数点分治模板题，直接做 #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define mp make_pai...

2020-05-06

0 515

Educational Codeforces Round 46 (Rated for Div. 2) F. One Occurrence(线段树)

题目链接大意：给你一个数组，询问一个区间仅出现一次的数。思路：我们记录每个位置x左边的第一个相同数的位置y，记为这个x的值为y，如果左边没数的话就是0，然后询问的区间必然是满足存在一个 t ...

2020-05-06

0 435