水原_

题解

ACM(13)

/ 注册

全部文章 / 题解（共28篇）

P2257 YY的GCD

P2257 YY的GCD 按照套路化到最后是：问题就在于怎么求法 : 对做唯一分解，则然后用数组记录含有的质数个数，是否为以上两种形式之一，即可递推。法 : 考虑在线性筛的时候处理。筛合数时，，若的唯一分解中每一项...

2020-01-02

0 631

P2522 [HAOI2011]Problem b

P2522 [HAOI2011]Problem b 与 P3455 类似，只不过变成了。两种方法解决：用前缀和，转化为四个。整除分块的时候分为四条轴。要注意的是其中两条轴很快会变为0，此时就不能用来更新了。否则分母会为 #include<algo...

2020-01-02

0 518

P3455 [POI2007]ZAP-Queries

P3455 [POI2007]ZAP-Queries 由莫比乌斯反演，方便计算，改变一下枚举方式，我们枚举，则可以看出莫比乌斯反演的实质：容斥原理将代入，然后用整除分块即可。 #include<algorithm> #include<iostrea...

2020-01-02

0 659

并查集-区间染色

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

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