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篇）

牛客挑战赛46 E.反演

设考虑先枚举得：考虑先枚举：由于莫比乌斯函数的性质，我们只需要枚举所有莫比乌斯函数非零的因子d（即质因子最高幂次为1）。函数的答案可以分块计算。而所有倍数的因子个数和可以在dfs的过程中计算出来。 #pragma GCC optimize(2) #pragma GCC optimi...

2020-12-15

0 499

牛客练习赛62 D.brz的函数

本题可能有更简单的做法,下面是我自己的做法:可能需要的一些前置知识: 下面是推导: for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ ans[i]+=mu[j]*S(j,i/j)*S(j,i/j); } } 细心...

牛客练习赛62

2020-11-06

1 812

【每日一题】Steps to One （容斥+错位相减）

前置推论：1.长度为1的序列只可能是一个1。2.假设当前的序列长度为，且前个数的不为1的话，那么第位的数必然与a互质，所以第个数选择的方案为[1,m]中与a互质的数的个数,记为中与a互质的数的个数，可以通过容斥计算。那么我们需要统计的就是所有长度>=2的期望。我们从大到小遍历，设当前枚举到的数...

2020-06-08

2 918

出题人的手环(牛客练习赛38D 离散化+树状数组)

题目链接(https://ac.nowcoder.com/acm/contest/358/D) 题目描述出题人的妹子送了出题人一个手环，这个手环上有 n 个珠子，每个珠子上有一个数。有一天，出题人和妹子分手了，想把这个手环从两个珠子间切开，并按顺时针顺序展开成一条链。可以发现，这条链一共有...

2020-05-06

0 581

洛谷P2699小浩的幂次运算

二分走一波，没想到题解的大佬做法 p_q 注意爆long long，所以先对数取一下上限二分确定下限，然后输出 #include<stdio.h> #include<math.h> #include<string.h> #include<stack&...

2020-05-06

0 467

洛谷P2251 【质量检测】

无意中刷st表题看到的题目（抄模板），一看到题目，，，没想用st表，直接莫队？？？？？跑起来也不是特别慢。。。这里用flag数组记录出现次数，set维护最小值，用的时候直接取头部。代码也很短 #include<bits/stdc++.h> #define swap(a,b) {a^...

2020-05-06

0 553

洛谷 P1032 【字串变换】

感觉这个题用一些常用的stl和string函数会非常简单。。（难道就是考这两个的吗？ vector<pair<string,string>>pos//用于变化 map<string,int>bj//用于判重然后字串变化操作用 string的find+sub...

2020-05-06

0 532

洛谷P1494 【[国家集训队]小Z的袜子】

纪念自己独立完成的一道省选题（菜鸡如我只会看题解qwq）还算是一道比较裸的莫队题把，比有的题目简单很多，也很好想怎么O(1)转移，比别的题就多了一个组合数计算（还有gcd？？），还没算%意义下，也是很良心了 int get(int x){ if(x<=1)return 0; retur...

2020-05-06

0 572

洛谷P1972 【[SDOI2009]HH的项链】

这道题想了很久，发题解是为了理解的更深刻一点。。。（管理放我过好嘛qwq）步入正题：这道题应该是很多做法，我选择的是离线+树状数组。首先输入数组。用fisrt数组先记录元素最开始出现的位置，对应的每一个树状数组的位置add一下（树状数组洛谷也有模板题的了解一下就ok啦）。 rep(i,...

2020-05-06

0 797

线段树模板（hdu1166）

#include <set> #include <map> #include <queue> #include <stack> #include <math.h> #include <bitset> #include <v...

2020-05-06

0 438