- 博客(72)
- 收藏
- 关注
RSS订阅
原创 素数专题
1.埃氏筛法for(int i=2;i<=n;i++) { if(fl[i]==0) prime[++tot]=i; for(int j=1;j<=tot&&i*prime[j];j++) { fl[i*prime[j]]=1; if(i%prime[j]==0) break; } ...
2019-04-02 15:40:43
217
原创 洛谷 P1330 封锁阳光大学【图论】
题目描述 https://www.luogu.org/problem/P1330染色问题#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N=2e4+4,M=2e5+5;int h[N],to[M],next[M],tot;void a...
2019-10-06 17:28:00
119
原创 洛谷 P1133 教主的花园【dp】
题目描述 https://www.luogu.org/problem/P1133首尾相连 需要特殊判断dp[i][j[k]表示第i个树选第j种（0，1，2）左右比它高低（1，0）的最大价值#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int ...
2019-10-06 17:26:15
158
原创 洛谷 P2939 [USACO09FEB]改造路Revamping Trails【分层图】
题目描述 https://www.luogu.org/problem/P2939#include<iostream>#include<cstring>#include<cstdio>#include<queue>using namespace std;priority_queue< pair<int,int> > ...
2019-10-06 17:22:43
114
原创 洛谷 P4568 [JLOI2011]飞行路线【分层图】
题目描述 https://www.luogu.org/problem/P4568#include<iostream>#include<cstring>#include<cstdio>#include<queue>using namespace std;priority_queue< pair<int,int> > ...
2019-10-06 17:21:46
118
原创 洛谷 P4822 [BJWC2012]冻结【分层图】
题目描述 https://www.luogu.org/problem/P4822分层图的模板题#include<iostream>#include<cstring>#include<cstdio>#include<queue>using namespace std;priority_queue< pair<int,int&g...
2019-10-06 17:20:46
132
原创 洛谷 P1323 删数问题
题目描述 https://www.luogu.org/problem/P1323把一个大问题分成两个小问题来解决。#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;priority_queue<int,vect...
2019-10-06 17:19:22
247
原创 洛谷P1059 明明的随机数
题目描述 https://www.luogu.org/problemnew/show/P1059标记 排序#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n,cnt,nm[105];bool fl...
2019-04-30 17:18:04
160
原创 洛谷P1068 分数线划定【排序】
题目描述 https://www.luogu.org/problemnew/show/P1068跟分数线相同分的人都能录取#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;struct node{ int...
2019-04-30 17:15:54
377
原创 洛谷P1781 宇宙总统
题目描述 https://www.luogu.org/problemnew/show/P1781逐一比较字符串#include<iostream>#include<cstdio>#include<cstring>using namespace std;string a,b="";int n,p;int main() { scanf("%...
2019-04-30 16:47:36
184
原创 洛谷P1583 魔法照片【排序】
题目描述 https://www.luogu.org/problemnew/show/P1583#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;struct node{ int w,nm;}a[2000...
2019-04-30 16:37:41
197
原创 洛谷P1051 谁拿了最多奖学金【排序】
题目描述 https://www.luogu.org/problemnew/show/P1051先把每个人的分数算出，再按多因素排序#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;struct node{...
2019-04-30 16:35:53
143
原创 洛谷P1093 奖学金【排序】
题目描述 https://www.luogu.org/problemnew/show/P1093多个因素排序#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;struct node{ int sc,ch,...
2019-04-30 16:34:07
333
原创 洛谷P1309 瑞士轮【排序】
题目描述 https://www.luogu.org/problemnew/show/P1309简单的sort会超时，需要两个数组分别记录获胜者和失败者，这样分数依然单调，最后再合在一起。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using ...
2019-04-30 16:32:18
151
原创 数论培训day 3下午【组合数】
组合数问题加法原理乘法原理Question 1Question 2Question 3组合排列Question 4Question 5Question 6Question 7Question 8Question 9Question 10Question 11组合数极其相关性质证明经典题若不加上不穿过y=x...
2019-04-07 07:56:20
172
原创 数论培训day 3上午【数论】
数论函数的卷积公式题目：知道从1到n的f[] g[] 值，求1到n的 (f*g)[]做法：枚举因数i j 假设i<j h[i+j]+=f[i]*g[j]+f[j]*g[i]代码实现 LL f[N], g[N], h[N]; void calc(int n) { for (int i = 1; i * i <= n; i++) { h[i * i] +=...
2019-04-06 19:15:00
160
原创 数论培训day 2下午【数论】
逆元欧拉定理的证明线性求逆元解决这样只要前面求出(p mod i)的逆元就能求出i的逆元练习解决前面的算法在这道题面前一点用不管，只能用暴力，但是可以用BSGS算法优化暴力代码实现int size;bool erfen(int x){ int l=0,r=size; while (l+1!=r) { int m=(l+r)>>1; if ...
2019-04-05 20:15:14
180
原创 数论培训day 2上午【数论】
数论的性质ℤ整数 ∃存在 |整除质数整数分解定理证明N=p*(N/p) 若N不满足条件 则N/p也不满足条件 就不满足N是最小的这个的证明过程用到了而这个的证明用到了整数分解定理 所以也就是说我们用了整数分解定理证明了整数分解定理，所以这个证明方法是不对的。正确的后面再说素数的判定Miller-rabin素性测试性质:s.t. 使得证明做法 选k个...
2019-04-05 18:42:27
173
原创 大佬的头文件
不废话 看代码#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>//头文件using namespace std;typedef long long ll...
2019-04-04 11:10:03
138
原创 数论培训day1 上午【数论基础】
一、高精度1.加法2.减法注意 最后要用while而不是if3.乘法4.除法（高精除以单精）优化 压位二、模意义下的运算1、满足乘法、加法、减法，满足交换律，结合律2、快速幂if(b==1) return a;基本思想实现费马小定理组合数应用实现最大公约数最小公倍数 a*b/gcd(a,b)代码写法 防爆质数判别1.sqrt判别...
2019-04-04 10:27:27
147
原创 洛谷P1367 蚂蚁
题目描述 https://www.luogu.org/problemnew/show/P1367看似模拟，却不是模拟。两个蚂蚁相碰，实际上就是互换名字的蚂蚁互相穿过去，而且相对位置没有变化，比如 2与3相碰（2在前），碰完后，2还在3前面。、所以只要序号的位置就行了，第一次排序后，记录第i个点以前的位置，因为相对位置不会改变，所以就需要记录一次就行了。#include<iostrea...
2019-04-02 11:26:23
463
原创 洛谷P1582 倒水
题目描述 https://www.luogu.org/problemnew/show/P1582这道题经历了 70 80 90 100的坎坷路程易得2的次方个瓶子可以倒在一起，所以只需要每一次找出n中最大的2的次方的数，将n减去这个数，k–,直到k=1然后找出比k大的最小2的次方数，用这个数减去k就是答案。然而我只得了70分，后来我想是不是2的31次方是不是不能用int,果然改了long ...
2019-04-02 09:28:48
194
原创 洛谷P4942 小凯的数字
题目描述 https://www.luogu.org/problemnew/show/P4942题目要求从l到r组成的数取模9后的数，其实就是从l到r每次数字模9的和，证明例如 2345%9=(2000%9+300%9+40%9+5%9)%9而2000%9=(21000)%9=2%91000%9=2%9任何整十模9都等于1知道这个规律以后，却发现枚举一遍会超时，所以可以用等差数列求和公...
2019-04-02 08:57:30
215
原创 洛谷P1162 填涂颜色【搜索】
题目描述 https://www.luogu.org/problemnew/show/P1162搜索搜索搜索。。。。#include<iostream>#include<cstring>#include<cstdio>using namespace std;const int N=35;int a[N][N],b[N][N],n;int dx[4...
2019-04-01 16:39:10
235
原创 洛谷P2735 电网 Electric Fences
题目描述 https://www.luogu.org/problemnew/show/P2735先不管p，先处理(n,m)、(n,0)和坐标原点构成的直角三角形中的合理点数，然后再判断n和p的大小关系，在算有一个直角三角形中合理点数，用相似三角形拉解。#include<iostream>#include<cstdio>#include<cstring>...
2019-04-01 16:29:46
124
原创 洛谷P1827 美国血统 American Heritage
题目描述 https://www.luogu.org/problemnew/show/P1827前序遍历本区间第一个就是该子树的根然后就在中序遍历此区间中找到该节点，节点左边就是左子树，右边就是右子树，然后递归根据后序遍历性质，输出答案按照以下次序：找到节点后：1.递归左子树2.递归右子树3.输出该节点即为本树的后序遍历。#include<iostream>#inc...
2019-04-01 10:14:19
280
原创 洛谷P2723 丑数 Humble Numbers
题目描述 https://www.luogu.org/problemnew/show/P2723为了找第i个丑数，那么一定要比第i-1个丑数大，而且是最小的那一个，可以发现比i-1大的丑数一定是比i-1小的丑数乘某个质数得到的，鉴于质数的数量很少，而丑数的数量很大，我们枚举质数，然后枚举丑数，直到大于第i-1个丑数，记录一下，找到所有的符合条件的丑数以后，找出最小值（也可以在寻找的途中更新最小值...
2019-04-01 09:01:46
188
原创 LOJ#10211. Sumdiv【乘法逆元】
题目描述 https://loj.ac/problem/10211约数和公式：对于已经分解的整数A=(p1k1)*(p2k2)*(p3k3)*…*(pnkn)有A的所有因子之和为分两种情况讨论，p1是9901的倍数，p1不是9901的倍数。#include<iostream>#include<cstdio>#include<cstring>#in...
2019-03-31 16:33:23
108
原创 洛谷P1516 青蛙的约会【扩欧】
题目描述 https://www.luogu.org/problemnew/show/P1516根据题目写出方程，判断无解的条件，再求出最小的正整数解。#include<iostream>#include<cstring>#include<cstdio>using namespace std;typedef long long ll;ll x,y,...
2019-03-31 16:20:59
172
原创 洛谷P1495 曹冲养猪【中国剩余定理】
题目描述 https://www.luogu.org/problemnew/show/P1495中国剩余定理的模板题，用到了扩展欧几里得算法，到最后ans可能是负值，需要加模取模。#include<iostream>#include<cstdio>#include<cstring>using namespace std;typedef long lo...
2019-03-31 16:17:40
353
原创 LOJ#10220. Fibonacci 第 n 项【矩阵乘法】
题目描述 https://loj.ac/problem/10220求斐波那契数列的第n项，由于数很大，直接递推会超时超空间，这就需要用到矩阵乘法，由于数很大，要开long long，乘的时候也注意数据大小。#include<iostream>#include<cstdio>#include<cstring>using namespace std;ty...
2019-03-31 11:20:00
216
原创 洛谷P1546 最短网络 Agri-Net【最小生成树】
题目描述 https://www.luogu.org/problemnew/show/P1546最小生成树的模板题，题目中说的一行接一行读入对本题没有半毛钱影响。。。#include<iostream>#include<cstdio>#include<cstring>using namespace std;int n,a[105][105],d[10...
2019-03-28 21:03:41
111
原创 洛谷P1529 回家 Bessie Come Home【最短路径】
题目描述 https://www.luogu.org/problemnew/show/P1529把字母转换成数字后，求离Z点最近的奶牛，近似模板题。#include<iostream>#include<cstdio>#include<cstring>using namespace std;int mp[60][60],p; int main() ...
2019-03-28 21:00:57
170
原创 洛谷P2722 总分 Score Inflation【完全背包】
题目描述 https://www.luogu.org/problemnew/show/P2722完全背包的模板题。。。。#include<iostream>#include<cstring>#include<cstdio>using namespace std;const int N=1e4+5;int n,m,f[N],c[N],t[N];in...
2019-03-28 20:59:02
157
原创 洛谷P1518 两只塔姆沃斯牛 The Tamworth Two【模拟】
题目描述 https://www.luogu.org/problemnew/show/P1518模拟模拟模拟 变量名像注意不能打错，只有遇到障碍或是边界才能转方向，也只能顺时针转#include<iostream>#include<cstdio>#include<cstring>using namespace std;bool fl;int a[1...
2019-03-28 19:43:28
250
原创 洛谷P1522 牛的旅行 Cow Tours【最短路径】
题目描述 https://www.luogu.org/problemnew/show/P1522要求找到连接两个牧场以后距离的最大值，首先要计算出每个点的最大距离（能到达它的点到它的最远距离），然后枚举不连通的两个点，计算出这两个点的最远距离之和以及它们之间的距离和，注意算出的最小值要与没联通之前的两点之间最大距离相比，输出最小值。注意：要初始化两点之间的距离，本身的距离为0.#includ...
2019-03-28 19:37:50
245
原创 洛谷P1211 [USACO1.3]牛式 Prime Cryptarithm
题目描述 https://www.luogu.org/problemnew/show/P1211暴力 数组范围开大点#include<iostream>#include<cstdio>#include<cstring>using namespace std;int n,ca,cb,c[10],a[10005],b[1005],ans;bool fl...
2019-03-24 16:41:38
253
原创 洛谷P1215 [USACO1.4]母亲的牛奶 Mother's Milk
题目描述 https://www.luogu.org/problemnew/show/P1215方法很多，主要是找全。搜素，哪个有牛奶就倒哪个，注意重复，最后排序输出。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace...
2019-03-24 16:05:18
190
原创 洛谷P1218 [USACO1.5]特殊的质数肋骨 Superprime Rib
题目描述 https://www.luogu.org/problemnew/show/P1218我以为这个题也可以用埃氏筛法来做，但位数太大，boom，空间爆了。其实就直接搜就行了，由题意能知道，这些数是不含有偶数的，第一位也一定是质数，这样能提高效率。#include<iostream>#include<cstring>#include<cstdio>...
2019-03-24 16:02:05
210
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人