- 博客(118)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 读入挂模板 常用
inline int read(){ char ch = getchar(); int x = 0, f = 1; while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();} while('0' <= ch && ch <= '9') {x = x * 1...
2019-04-07 13:19:59
144
原创 排序算法 （c/c++)
冒泡排序（Bubble Sort）步骤1: 比较相邻的元素。如果第一个比第二个大，就交换它们两个； 步骤2: 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； 步骤3: 针对所有的元素重复以上的步骤，除了最后一个； 步骤4: 重复步骤1~3，直到排序完成。void work(){ int n=10; int a[15]={2...
2020-08-17 14:31:11
177
原创 mysql基础语句整理
创建数据库： create databse xxx 删除数据库： drop database xxx 查看数据库： show databases进入使用xxx库： use xxx 查看数据库表： show tables 删除表： drop table xxx查看具体表结构： desc xxx创建表： create table `表名`( 'Field' ty...
2020-04-07 22:04:56
151
原创 二叉树根据前序和中序确定后续 中序后续确定前序
前序和中序确定后序a// 前序b// 中序void getpost(int root,int start,int end){ if(start>end) return ; int i=start; while(i<end&&b[i]!=a[root]) i++; getpost(root+1,start,i-1); ...
2019-11-06 14:46:40
900
原创 Tempter of the Bone hdu 1010 (奇偶剪枝）
Problem DescriptionThe doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He re...
2019-10-28 21:05:25
103
原创 poj3641 快速幂+米勒罗宾
DescriptionFermat's theorem states that for any prime numberpand for any integera> 1,ap=a(modp). That is, if we raiseato thepthpower and divide byp, the remainder isa. Some (but no...
2019-10-24 11:05:15
144
原创 整除分块
对于求解以上公式时不难发现n/i等于k时 n往往是连续一段段的那么就可以计算这个长度直接乘使得复杂度由O(n)降到了O(sqrt(n))ans=0;for(int l,r;i<=n;l=r+1){ r=n/(n/l); ans+=(r-l+1)*(n/l);}...
2019-09-27 20:21:50
118
原创 Space Ant 极角排序
题意：给定n个点，任意两点不在一个x轴和y轴上，输出一条能经过最多点的路线，就下面这图，每次只能左转，实际就是外面一圈包进去，选择一个最外侧点，对剩下点做极角排序，一个个点选下去。能保证每个点都经过。#include<stdio.h>#include<iostream>#include<math.h>#include<...
2019-09-25 21:00:20
158
原创 hdu5667 Sequence (矩阵快速幂+费马小定理）
SequenceSample Input15 3 3 3 233Sample Output190题解：根据递推式可以发现，答案是以a为底数的一个值，所以对指数部分做快速幂得到k，最后答案就是qpow（a,k)%mod根据递推式易得构造矩阵 fn c 1 b fn-1fn-1 = 1 0 0 * fn-2 1 0 0 1 ...
2019-09-10 19:26:18
127
原创 矩阵快速幂板子
ll a0,a1,p,q,k; struct matrix{ ll a[2][2]; matrix() { memset(a,0,sizeof a); }};matrix operator *(const matrix &x,const matrix &y)//矩阵相乘函数 { matrix res; ...
2019-09-09 21:11:45
95
原创 BM求线性递推 快速推线性数列第n项
BM模板（杜教版）：#include<bits/stdc++.h>#include <unordered_map>using namespace std;typedef long long ll;typedef vector<long long> VL;const ll mod = 998244353;ll powmod(ll a, ll b)...
2019-09-09 13:19:07
178
原创 最长公共子序列&&最长公共子串 模板 LCS
最长公共子序列int lcs(char a[],char b[]) { int i , j , k , w , ans , l , r , mid ; for( i = 0 ; i < 26 ; i++) location[i].clear() ; for( i = strlen(b)-1 ; i >= 0 ; i--) location[b[i]...
2019-08-30 15:26:00
206
原创 Dijkstra模板 最短路最小花费
struct dij{ int n; const int inf = 0x3f3f3f3f; int maps[maxn][maxn]; int d[maxn], v[maxn]; int Dijkstra(int s, int t) { memset(d, inf, sizeof d); memset(v, 0,...
2019-08-30 15:09:58
134
原创 主席树板子（静态，区间第k大，小）
#include<bits/stdc++.h>using namespace std;const int N = 1e5 + 5;int n, m, x, y, k;class zhuxishu{private: int a[N], cnt, root[N]; vector<int>v; struct node { ...
2019-08-27 16:16:42
126
原创 Miller_rabin板子 快速判断是否素数
板子，除了这个算法不保证一定正确，效率很高，错误率很低可以忽略不记如果用这个板子出现了wa而不是tle的时候，可以适当增加_time的次数const int _time=5;ll multi(ll a, ll b, ll mod) { ll ret = 0; while(b) { if(b & 1) ret = ret + a; ...
2019-08-22 15:03:58
144
原创 HDU 6659 Acesrc and Good Numbers
Problem DescriptionAcesrc is a famous mathematician at Nanjing University second to none. Playing with interesting numbers is his favorite. Today, he finds a manuscript when cleaning his room, which...
2019-08-14 17:02:09
198
原创 拓展欧几里得算法
求下列方程的一组解：ax + by = gcd(a, b)当gcd(a, b) = 1，即a, b互质的时候，这个方程的解实际上就对应了a关于模b的逆元。给出伪代码Input: a, bOutput: a solution to ax + by = gcd(a, b)1: function extended gcd(a,b)2: if b = 0 then3: retur...
2019-08-13 10:51:45
264
原创 c++ distance unique
函数distance()用来处理两个迭代器之间的距离Dist distance(pos1,pos2);传回来的是两个迭代器之间的距离两个迭代器必须指向同个容器对于random access迭代器，此函数仅仅只是传回pos2-pos1，复杂度为常数级别；对于其他迭代器类型，distance()会不断递增pos1，直到抵达pos2为止，然后传回递增次数，也就是说其他类型的迭代器，d...
2019-08-06 11:32:59
512
原创 快速幂之欧拉降幂
求a^b(mod p)的值 ，当b很大很大很大很大很大的时候，可以使用欧拉降幂欧拉定理：若n，a为正整数，且n，a互质，则：拓展：那么根据欧拉定理，可以求得φ(n)的值：ll euler_phi(ll n){ ll k = (ll)sqrt(n + 0.5); ll ans = n; for(int i = 2; i <= k; i++) ...
2019-08-02 20:34:11
340
原创 十进制快速幂 模板
ll pow ( ll a, ll b, ll n ) { while(n) { if(n&1) b=b*a; a=a*a; n>>=1; } return b;}ll tenpow(){ int len=s.size()-1; ll res=a,base=1; ...
2019-08-02 14:17:09
156
原创 牛客多校 generator 1
题意：求fn的第1e10e6项，用广义欧拉降幂了半天都wa，后来才知道时十进制快速幂，nnd第一次知道这玩意构造矩阵：|a,b||1,0|然后跑一下十进制快速幂就好了#include<bits/stdc++.h>using namespace std;typedef long long ll;#define mp make_pairty...
2019-08-02 13:21:09
160
原创 HDU6050 Funny Function 矩阵快速幂
Funny FunctionTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1693Accepted Submission(s): 859Problem DescriptionFunctionFx,ysatisfie...
2019-08-02 10:07:57
95
原创 ZOJ Summer 2018 1020
#include <deque>There is a deque of sizenand you want to use it now, but unfortunately it's not empty yet. So, before using it, you're forced to do this boring work: clear it.Each ti...
2019-08-02 10:07:33
131
原创 ST和RMQ 区间最值
ST（Sparse Table）和 RMQ（Range Minimum/Maximum Query）对于长度为n的数列A，回答若干次询问RMQ(i,j)，返回数列A中下标在区间[i,j]中的最小/大值。一般我们用ST算法解决这样的问题。ST（Sparse Table）算法可以在O(nlogn)时间内进行预处理，然后在O(1)时间内回答每个查询。板子：void st(int n){...
2019-07-31 10:38:46
90
原创 杭电多校 Fansblog
FansblogTime Limit: 2000/2000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 3170Accepted Submission(s): 671Problem DescriptionFarmer John keeps a websi...
2019-07-30 09:57:39
149
原创 C - Emergency Evacuation
题目链接：GYM108082题意：一群人从位置上通过逃生通道离开，通道不能并行，只能单人有序通行，求全部人出去的最小时间题解：每个人的路线都是固定的，那么只要前方有空位就走，没空位就等着，然后我们考虑一下每个人的路线，如果这两个人在没有阻挡的情况下，到达终点的时间是是一样的话，那么必定会在某一点相遇，此时就需要有一个人要等一个时刻，如果有第三个人的话，这第三个就要等两个时刻，那么我...
2019-07-29 11:04:22
263
原创 线段树 | 单点，区间更新（set,add) | 区间最大值，最小值，区间和
#include <bits/stdc++.h>using namespace std;typedef long long LL;const LL Inf=1LL<<62;const int maxn=1e5+5;int T,n,m;struct segement_tree{ struct node { int l,r; ...
2019-07-19 21:01:25
129
原创 zoj Heltion and Triangle
对边排个序，由小到大开始三个三个遍历，求到面积最大的一个#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=1e5+5;ll s[maxn];int n,m;int main(){ ios::sync_with_stdio(false);cin....
2019-07-15 14:42:18
165
原创 zoj Sky_miner and Odious Number
1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59, 61, 62, 64, 67, 69, 70, 73, 74, 76, 79, 81, 82, 84, 87, 88, 91, 93, 94, 97, 98, 1...
2019-07-11 14:30:12
107
原创 Wheat
#include<bits/stdc++.h>using namespace std;#define Inc(i,L,r) for(register int i=(L);i<=(r);++i)#define Red(i,r,L) for(register int i=(r);i>=(L);--i)const int N = 1e4+10,Maxsiz ...
2019-07-10 21:42:30
129
原创 Miner's Necklace
#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn=1e6+5;int n,m;int s[maxn],t[maxn];int vis[maxn],next[maxn];int fs[max...
2019-07-10 20:43:15
105
原创 ZOJ Summer 2018 #include <list>
For a sequenceX.Xn+1= (a*Xn+c) %p. Now givena,c,X0,n,p, you need to calculateXn.InputThe first line contains an integerT, indicating that there areTtest cases (T<= 20);Fo...
2019-07-08 19:06:19
109
原创 斐波那契第n项，快速幂，玄学算法
斐波那契快速幂下面的神仙代码的构造矩阵是| 1 0 || 0 1 |留着用来当模板。#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<ll,ll> pll;const int mod=1e9+7; pll operator *(const...
2019-07-08 11:20:40
239
原创 Saber
Saber is a Class in the Holy Grail War. This Class is regarded as one of the most powerful Class.Saber is a tree-lover. She loves all kinds of trees. One day, she suddenly comes up with a curious ...
2019-07-06 13:05:34
401
原创 阿力的第三场难题
A:算贪心两个数组排个序瞎搞搞就行了#include <bits/stdc++.h>using namespace std;const int maxn=0x3f3f3f3f;int n, a[50005], b[50005], ans = maxn, maxn, cmp;int main() { cin >> n; for (int i ...
2019-06-21 23:00:17
137
原创 点分治
#include<bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3f int n,m,len=0,Size;struct node{int x,y,z,next;};node e[20010];int first[10010];int root,ms,size[10010],mson[10010],sum[...
2019-06-21 15:30:17
78
原创 FWT 快速沃尔什变换
void fwt(ll *a, int op){ for (int cnt_pre = 1, cnt_cur = 2; cnt_pre < tot; cnt_pre <<= 1, cnt_cur <<= 1) for (int i = 0; i < tot; i += cnt_cur) fo...
2019-06-21 15:29:59
150
原创 阿力的第二场难题
A:本意是当签到题，但是可能低估了这题的难度在线标记处理二分查找#include <bits/stdc++.h>using namespace std;const int maxn = 1000005;int n, w[maxn];bool vis[maxn];set<int> a;set<int>::iterator it;inli...
2019-06-20 22:50:58
157
原创 HDU - 5909 Tree Cutting FWT+树形dp（点分治不会）
Byteasar has a treeTTwithnnvertices conveniently labeled with1,2,...,n1,2,...,n. Each vertex of the tree has an integer valuevivi.The value of a non-empty treeTTis equal tov1⊕v2⊕...⊕vnv1⊕v2...
2019-06-04 17:01:00
133
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人