- 博客(99)
- 收藏
- 关注
RSS订阅原创 数论常见公式（不间断更新）
迪利克雷卷积ϵ=μ∗1⇔ϵ(n)=∑d∣nμ(d)(1)\epsilon=\mu*1\Leftrightarrow \epsilon(n)=\sum_{d|n}\mu(d) \tag{1}ϵ=μ∗1⇔ϵ(n)=d∣n∑μ(d)(1)d=1∗1⇔d(n)=∑d∣n1(2)d=1*1\Leftrightarrow d(n)=\sum_{d|n}1 \tag{2}d=1∗1⇔d(n)=d∣n∑1...
2020-04-04 11:09:32
398
原创 容斥原理
容斥原理今天学习了容斥原理上述为容斥原理的公式，推导建议百度。我们发现，当我们要求一个集合的并集的时候，可以很好的利用容斥原理来求解。那么我们可以得到一些很好的性质。注意到偶数个集合的交集前为加号，而奇数个集合交集前面为减号。项的个数为2^k，原理为n个集合的排列组合那么我们可以解决如下问题HDU-4135 : https://vjudge.net/problem/HDU-4...
2020-04-04 10:55:53
237
原创 ACM多项式算法入门
在摸索了很久很久，还是没找到多项式的正确入门方式，所以尝试着自己写一下多项式乘法对于多项式A(x),B(x)A(x),B(x)A(x),B(x) A(x)=anxn+an−1xn−1+an−2xn−2+an−3xn−3+...+a1x+a0A(x)=a_nx^n + a_{n-1}x ^ {n-1} + a_{n-2}x ^ {n-2} + a_{n-3}x ^ {n-3} + ... + ...
2020-03-30 20:44:06
753
原创 F - Red-White Fence
选出一个山峰一样的数列，问总长度是多少，我们发现，周长的总长只取决于最长的那一块木板和选取的模板个数，总周长就是(L+M)∗2( L + M ) * 2(L+M)∗2其次，我们考虑给木板按长度分类第一类是对应长度只有一块的，那么这个木板可以放在左边，也可以放在边，对应的次数就是ai=C(sa,i)∗2ia_i = C(sa,i) * 2^iai=C(sa,i)∗2i第二类就是对应长度有两块...
2020-03-12 20:42:07
121
原创 Educational Codeforces Round 83 (Rated for Div. 2)
A - Two Regular Polygons问是否可以在一个正多边形内部内接一个正多边形，可以内接，分配给内部的多边形的每一条边的角度一样，对应的外部多边形的边数一样#include <bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigned long long ULL;int Gcd...
2020-03-10 14:47:07
241
原创 矩阵树定理
今天学习了矩阵树定理，就是求解无向图最小生成树个数的一个东西首先需要构造无向图的基尔霍夫矩阵，我们记为矩阵K。矩阵K满足，K=D−AK = D - AK=D−A其中D是这个无向图的度数矩阵，在对角线上值是每个点的度数，其他位置的值都是0，A是这个无向图的出入度矩阵，第 iii 行 jjj 列元素表示点 iii 到点 jjj 之间的边数这个矩阵KKK，随意选择下标相同的一行一列挖去，那么剩...
2020-03-09 15:32:10
449
原创 FFT处理字符串匹配问题
现在我们拥有一个文本串B一个模式串A，询问A在B中出现的次数很显然这是一个KMP的裸题，但是现在不考虑使用KMP，使用FFT来找A在B中出现的次数首先定义函数P(x)=∑i=0m−1(A(i)−B(x−m+i+1))P(x)=\sum_{i=0}^{m-1}(A(i)-B(x-m+i+1))P(x)=i=0∑m−1(A(i)−B(x−m+i+1))这个函数代表，字符串A在B中匹配以x为最...
2020-02-28 22:18:41
1166
原创 Java核心思想读书笔记---数据域的修饰符
类中数据域的四种访问类型public 全访问类型，在类内部，子类当中，同一个包但是不同的类中，不同的包的类中都可以访问 protect 局部访问， 在类内部，子类当中可以访问 private 类内部访问，在类的内部访问，其他位置均不可访问private修饰符的注意事项private不能用于修饰可修改的数据，例如某个带有set修改器的类import java.util.Date;...
2020-02-27 11:41:24
251
原创 Java核心思想读书笔记---日期GregorianCalendar类
1、学习了 GregorianCalendar 类解决日期问题，Date类暂时不推荐使用注意事项Calendar类是一个静态类，用于方便通过get访问GregorianCalendar类中的时间 Calendar类当中，Month是从0开始的，也就是1月份是0，12月份是11 Calendar类当中，DAY_OF_WEEK 注意，1是星期天认为是一个星期的开始，2是星期一，以此类推测...
2020-02-27 11:40:49
290
原创 Codeforces Round #597 (Div. 2)
洛谷博客传送门A - Good ol’ Numbers Coloring猜了个 GCD=1GCD=1GCD=1 过了#include <bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigned long long ULL;int Gcd(int a,int b){if (b == 0) ...
2019-11-02 10:57:30
187
原创 Codeforces Round #589 (Div. 2)
A:#include <bits/stdc++.h>using namespace std;int cnt[20];int main(){ int l,r; scanf("%d%d",&l,&r); for(int i=l; i<=r; i++){ memset(cnt,0,sizeof(cnt)); ...
2019-09-30 09:42:47
128
原创 2019 CCPC 秦皇岛
A：#include <bits/stdc++.h>using namespace std;const int N = 2e3 + 10;struct node{ long long x,y; node(long long x=0,long long y=0){ this->x = x; this->y = y;...
2019-09-29 16:59:21
269
原创 Educational Codeforces Round 73 (Rated for Div. 2)
A:#include <bits/stdc++.h>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/hash_policy.hpp>using namespace std;using namespace __gnu_pbds;typedef long long LL;typed...
2019-09-29 00:25:26
133
原创 Codeforces Round #588 (Div. 2)
A#include <bits/stdc++.h>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/hash_policy.hpp>using namespace std;using namespace __gnu_pbds;typedef long long LL;typede...
2019-09-29 00:23:16
147
原创 hdu 6010
#include <bits/stdc++.h>using namespace std;typedef long long LL;typedef unsigned long long ULL;LL Gcd(LL a, LL b){if (b == 0) return a; return Gcd(b , a%b);}LL Lcm(LL a, LL b){ return a/G...
2019-09-28 23:14:59
149
原创 hdu 6000
#pragma GCC optimize(2)#include <bits/stdc++.h>using namespace std;typedef long long LL;inline int read(){ int f = 1, x = 0;char ch = getchar(); while (ch > '9' || ch < '0'){i...
2019-09-28 23:13:33
102
原创 hdu 5999
#include <bits/stdc++.h>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/hash_policy.hpp>using namespace std;using namespace __gnu_pbds;typedef long long LL;typedef u...
2019-09-28 23:12:42
130
原创 HDU 6006
/* hdu 6006 solve: dp */#include <bits/stdc++.h>using namespace std;vector<int> v[20],p[20],leg[20];int cnt[200];int dp[20][(1 << 10)];int main(){ int T,kase = 1;...
2019-09-28 23:07:22
154
原创 [kuangbin带你飞] 专题四 最短路练习 练习
1、Til the Cows Come Home裸的最短路，wa一路发现自己T，N读入反了，据说还有重边，不过是邻接矩阵需要考虑的问题，前向星和邻接表可以忽略。#include <iostream>#include <algorithm>#include <cstdio>#include <queue>#include <c...
2019-04-23 21:46:25
222
原创 kuangbin专题一 简单搜索
写在前面： 最近还是想着找专题提升一下自己，尝试来写kuangbin专题，每天更新一点，希望可以更完1、棋盘问题 用 ban ，visr，visl三个数组记录那些位置可以被访问，然后dfs搜索即可 #include <iostream>#include <cstdio>#include <cstring>...
2019-04-22 21:39:03
377
原创 Codeforces Round #553 (Div. 2) E - Number of Components
要求这个所有的和，感觉不是很好想首先这个图，是一条长链。对于联通的 i 和 i+1 两个点，考虑他们对答案的贡献，如果他们不联通，那么对答案的贡献就是1对于 l <= ai <= r 同时使得 ai+1 > r || ai+1 < l 里所有的 l 和 r，对答案的贡献都是1反之对于l <= ai+1 <= r 且 ai 不在范围内，所有...
2019-04-20 22:45:21
215
原创 Codeforces Round #552 (Div. 3) G. Minimum Possible LCM
求数组中，lcm最小的一对数的下标可以考虑使用筛法，因为 LCM = a*b / GCD(a,b) 所以，对于任意的一对数来说，如果他们的gcd一样，那么这两个数越小越好。所以枚举i = gcd，找到最小的两个数gcd(a,b) = i, 求出他们的lcm，然后记录最小值即可。这里被坑了半天的原因竟然是自己写的lcm。c++17有一个库函数lcm，没有调用自己写的参数是longlong...
2019-04-20 22:36:02
123
原创 洛谷P1005 矩阵取数游戏
区间dp，转移方程为 dp[i][j] = max(dp[i-1][j]+a[k][i-1]*fac[m-j+i-1],dp[i][j]); dp[i][j] = max(dp[i][j+1]+a[k][j+1]*fac[m-j+i-1],dp[i][j]);dp[i][j] 代表区[ i , j] 的最大值，每一个状态 dp[i][j] 只能从 dp[i-1][j] 和 dp[i]...
2019-03-13 20:36:46
262
原创 Educational Codeforces Round 61 (Rated for Div. 2) 题解
A: Regular Bracket Sequence 判断括号是否匹配，只需要注意到 “（）”这样的括号数量无所谓，每一个“（（” 一定需要一个 “））” 来和它配对，每一个“）（”，只要有一对 “（（” 和 “））” 就可以有任意多个 因为可以做成 “（（” “）（””））“这样的形式。那么几个判断即可代码如下：#include <bits/stdc++.h&...
2019-03-08 11:54:52
177
原创 P2341 [HAOI2006]受欢迎的牛
如果一个牛，是明星牛，因为喜欢的关系是可以传递的，因此他喜欢的牛也都是明星牛。反之，以为这只明星牛被所有牛喜欢，那么他喜欢的牛也一定喜欢他，两只牛也一定是相互喜欢的，继续传递下去，下一只牛喜欢的也一定是明星牛，他们之间一定相互喜欢，因此，所有明星牛一定构成一个强连通分量。 并且，这个强连通分量一定有一个性质，这个强连通分量出度为0，即不存在一个点有一条指向强连通分量外一个点...
2019-03-05 09:33:33
175
原创 P2023 [AHOI2009]维护序列
线段树同时维护加法乘法的模版题详情见传送门https://blog.csdn.net/CCCCTong/article/details/88122065
2019-03-04 16:30:37
187
原创 P3373 【模板】线段树 2
线段树同时实现区间加法和乘法，因为加法乘法都涉及到了动态修改，因此我们需要两个lazy标记，我们记为add，mul，但是在pushdown的时候就会出现一个问题，乘法对之前做过的加法标记是有影响的，如果先下推加法标记，那么就忽略乘法对结果的影响，导致错误的答案 当我们需要将标记下推的时候，正确的操作应该是将当前区间的add也乘上mul，下推保证结果正确，而在添加mul标记的时候之...
2019-03-04 16:21:31
283
原创 P1198 [JSOI2008]最大数
简单的线段树模拟，首先统计最终有多少数，建好线段树之后，相当于做修改查询操作，注意到查询操作查询的区间为(len - L + 1, len) len 为当前数列的长度代码如下：#include <bits/stdc++.h>using namespace std;typedef long long LL;const int maxn = 1e6 + 10;str...
2019-03-03 15:30:19
127
原创 P5238 整数校验器 (3月份洛谷月赛2019)
比较简单的题，把x按字符串读入，先检查是否合法，如果是一个合法的数，我们再去看是否在范围内，l，r都用字符串读入，然后手写一个字符串比较函数，然后比较是否在范围内就行了，别写出bug就行。代码如下：#include <bits/stdc++.h>using namespace std;int cmp(string a,string b){ if...
2019-03-03 10:15:55
228
原创 P5239 回忆京都（3月洛谷月赛）
对任意给定的n和m，求 首先我们需要组合数表，可以使用递推公式将所求的组合数放在一个矩阵里面，i 行 j 列表示 C（i，j）代码如下：void solve(){ C[1][0] = C...
2019-03-03 10:06:47
271
转载 P1972 [SDOI2009]HH的项链
研究别人思路做出来的，本篇博客已注明转载树状数组/线段树均可过首先算出所有的数第一次出现的位置，维护一个tree数组，将这些位置修改为1 计算一个nex数组，表示当前下标的数，下一次出现的位置 离线求解，将所有询问区间按左端点排序 用一个指针 l 指向左端点之前的位置，对左端点之前的每一个位置的数，都修改他的nex值为1 由于左端点升序排列，因此当前的 l 由上一次的 l 递增而...
2019-03-03 09:53:59
137
原创 P2055 [ZJOI2009]假期的宿舍
首先先理清楚一下这题的关系，每一个人要么是学校里的学生，要么不是。而是学校里学生，要么回家了，要么没回家。那么可以提供床位的，就是学校的在校学生，而需要床位的，就是不是这个学校的学生的人，和在学校没回家的在校学生。一个人占一张床，而在校学生自己可以睡自己的床，因此我们把所有的人分成两部分，需要床的和提供床的，在校学生不回家的两边都有（建一条自己到自己的边），根据认识关系建边，因此我们得到了二分图，...
2019-02-28 22:56:10
160
1
原创 P1726 上白泽慧音
这是一个求强连通分量的模版题一般的我们都选取Tarjan算法，常数较小，写起来比较方便我们用三个数组，low[maxn],vis[maxn],dfn[maxn]其中dfn表示当前的节点被搜到的时间戳，vis表示当前这个被搜过的节点在不在栈的里面，low数组最难理解，因为tarjan基于dfs实现，dfs搜索过程构成了一颗搜索树，那么low[i] 的值代表，当前节点 i 通过一条非树边，可以走...
2019-02-28 22:43:28
267
原创 P1993 小K的农场
差分约束的模版题，建图我们选择 a b c 代表 v(b) - v(a) &lt;= -c 建图，然后注意到在区间 [ i , i + 1] 里面，有 v(i + 1) - v(i) &lt;= 1且 v(i) - v(i + 1) &lt;= 0，这样建图，可以保证整张图的联通性，然后spfa跑图上最短路（有负权边），如果存在负环，则方程无解，否则若存在最短路，则必定有解代码如下:#i...
2019-02-28 21:07:58
164
原创 P1525 关押罪犯
并查集，自己的思路和食物链这题非常的像，把在并查集中和父亲关系为 1 记为和父亲节点在同一个集合里面，0记为不在同一个集合里面，类似的可以推出一个节点和爷爷节点的关系为value[now] = (value[father[now]] + value[now]) % 2;对边排序，从大的边开始，尽量边链接的两个点不在一个集合里面，如果在，判断关系是不是 1 ，如果是就和 ans 变量取max，最...
2019-02-17 15:27:07
159
原创 洛 谷 P1119 灾后重建
询问x到y的距离，首先想到Flody方法，但是题目中，给定了最短路上，不能有城镇建好的时间超过 ti 的，因此，如果对每一次询问都跑一边Floyd，那么肯定会超时。因此我们需要更好的思路，Floyd的是基于动态规划实现的最短路算法，转移方程为dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);表示i点到j点的路径，可以用i到k，k到j点路径来松弛...
2018-12-04 22:38:29
159
转载 洛谷 P1330 封锁阳光大学
传送门：https://www.luogu.org/problemnew/show/P1330 很神奇的做法，之前没有仔细思考，贪心+优先队列去找尽可能连接多条边的点，但其实是有问题的，这样贪心的结果很可能是没有解的，而选取其他的没那么多条边的点去操作，反而是可能有解的，所以贪心不可取。 看了大佬们的思路才理解到这个题可以这样设计（思路借鉴的，已注明转载），这...
2018-10-08 21:09:02
187
原创 洛谷 P2661 信息传递
传送门：https://www.luogu.org/problemnew/show/P2661 这个是一个图的遍历问题，主要是2和7个点被卡了 类似于tarjan，我们在dfs的时候遍历到那个节点，用一个时间戳记录那个节点被搜索到的顺序，因为每次搜索一定会存在环，那么搜索到时间戳已经被记录的节点的时候，时间戳的差+1就是我们这个环的大小。 ...
2018-10-08 19:16:39
198
原创 Codeforces Round #514 (Div. 2), problem: (C) Sequence Transformation
传送门：http://codeforces.com/contest/1059/problem/C这个c题还挺有意思的，一开始实在是看不懂题，后来理解了，要字典序（误）最大，就必须越快增加整个数列的gcd越好。注意到这个数列是有序而且从1到n，那么先假设n比较大，这个时候gcd是1，我们要删掉最少的数让gcd改变，最少删掉多少呢？n范围内，是2这个数的倍数的数的个数，永远比是其他数的倍数...
2018-10-06 13:53:08
177
原创 Codeforces Round #514 (Div. 2), problem: (B) Forgery
真心觉得昨晚写这个的时候就是个傻子，硬写最后还fst19了。昨晚想到的方法对于每一个#，如果这个是一个符合条件的图，那么这个#就一定会包含在一个3X3的环内，那么这个#就有8种可能的位置，挨个去搜看有没有一个可能的位置就好。还是挺难写的这样。刚刚又想了下，每一个环，都一定会有一个中心，那么我们枚举每一个点，检测它是不是这样一个环的中心，如果是，那么久将它周围的这个环上的点都标记，那么最后扫...
2018-10-06 13:36:29
150
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人