水原_

分类

ACM(13) 题解(28)

/ 注册

全部文章（共41篇）

莫比乌斯反演

前置知识积性函数若函数为正整数对任意的满足的两个数有，则称为积性函数。特别的，若对任意，则称为完全积性函数。常见积性函数莫比乌斯函数约数函数对于迪利克雷卷积的乘法单位函数（完全积性）迪利克雷卷积定义对于两个以正整数为定义域的...

2020-01-02

1 592

lca(倍增)

用记录的入序和出序，就可以判断是不是的祖先。在找的时候就可以只跳一个点。注：需先设定习题： #10131. 「一本通 4.4 例 2」暗的连锁掉附加边不会影响原图的连通性，所以分成哪两部分取决于去掉树上的哪条边。我们枚举去掉树上的哪条边，如果这条边去掉后分成...

2020-01-02

0 603

并查集-区间染色

楼下老哥的并查集操作好是巧妙，但是并没有讲具体如何用并查集来覆盖区间以至于我查了好多资料才搞明白。。。（也许是因为我⑨）所以，在此将并查集实现这题的原理讲一讲。有如下问题：长为的序列，开始均无颜色，有个操作，每次将到的数全染成色，求最终的序列。我们考虑将染色反着来，则一个数若被染色一...

2020-01-02

0 1554

P1901 发射站

看到这题我就想到了2018预赛的毒瘤双向链表。。。然而现在我还是不会。于是我用表水过了这题。对于发射站，以找它左边第一个比它大的发射站为例：我们可以通过二分来找到最大的，满足。表示区间中的最大高度。对于区间高度最小值，我们可以用线段树或者表来维护。如果用线段树，预处理是，查询是，无法满...

2020-01-02

0 559

P2723 丑数 Humble Numbers

挺好的一道题。我只想到了用的丑数依次生成丑数，用优先队列来找最小的做法。代码如下： #include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<...

2020-01-02

0 566

P4933 大师

介绍一个较为好想的做法。记为以第位为为首项，第为第二项的等差数列的个数。（）则显然有（真的显然，做多了线性动态规划的人相信都能看出），其中这样，状态，转移，总复杂度。但有，为什么能过？因为实际上,枚举的常数是，因为。然后发现大概计算次数只有, 然后又有，就可以卡过此题。 (其实和正解的...

dp

2020-01-02

0 677

P1276 校门外的树（增强版）

楼下的线段树写的都太过麻烦，这是因为楼下的线段树均为及时更新答案。但是，询问只有一次，我们不需要费力对每次询问维护答案。对于第一问，留下的树苗数等于：留下的（树与树苗）总数减去留下的（树）的总数。对于v第二问，种上又被拔掉的树苗数等于：被砍掉的（树与树苗）总数减去被砍掉的（树）的总数。那么我...

2020-01-02

0 739

P1103 书本整理

本题细节错的较多。 #include<algorithm> #include<iostream> #include<cmath> #define inf 20000000 #define rep(i,a,b) for(int i=(a);i<=(b);i++...

2020-01-02

0 491

P1053 篝火晚会

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #define rep(i,a,b) for(int i=(a);i<=(b);i++) #def...

模拟

2020-01-02

0 619

P1805 关灯

f[n] =0,n=0 else =f[n-1],s[n]=0 else =2^n-1,s[i]=0,1<=i<=n-1 else =f[k-1]+2^n-2^k,k为1到n-1中最后一个一位数 #include<iostream> #include<cstring&g...

2020-01-02

0 694