C20193620-CSDN博客

原创 ARC067F Yakiniku Restaurants 决策单调性分治优化

题目链接题意一条街上有N家烧烤店，从西到东编号为1至N，第i家和i+1家之间的距离是A[i]。Joisino有M张餐票，编号从1到M。每家烧烤店都提供M种烧烤套餐，用不同编号的餐票可以换取不同种类的套餐。在烧烤店i，用编号为j的餐票可以买到美味值为B[i][j]的套餐。每张餐票只能使用一次，但是在每个店可以使用任意数量的餐票。Joisino希望通过从她选择的一家店开始，然后反复前往另...

2019-12-13 20:53:00 296

原创【模板】Tarjan（边双）

模板题#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<stack>using namespace std;struct mzls{ int to,nt;}a[200005];int n,m,ncnt,cnt;...

2019-10-24 21:04:19 207

原创【模板】树链剖分

模板题#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define lch i<<1#define rch i<<1|1#define N 30005struct mzls{ int to,nt;}a[N*2];s...

2019-10-03 11:43:50 208

原创【模板】树上莫队

模板题#include<bits/stdc++.h>using namespace std;#define N 100005vector<int>g[N];int st[N],nd[N],a[N];int pos[N],dfn[N],cnt,sum[N];int fa[N][20],dep[N],ans[N],n,m,an;bool f[N];stru...

2019-10-03 11:39:12 227

原创【模板】带修莫队

模板题#include<bits/stdc++.h>using namespace std;int n,a[300005],pos[300005],m,sum[1000005],ans[2000005],t1,t2,a2[2000005][2],la[2000005],a3[1000005];struct mzls{ int l,r,id,mo; bool opera...

2019-10-03 11:09:35 184

原创【模板】莫队

模板题#include<bits/stdc++.h>using namespace std;int n,a[300005],pos[300005],m,sum[1000005];long long ans[2000005],x;struct mzls{ int l,r,id; bool operator<(const mzls &x)const {...

2019-10-03 11:05:53 165

原创【模板】线性基

模板题#include<bits/stdc++.h>using namespace std;typedef long long LL;int n,cnt;LL a[100005],d[65],d1[65],s;inline void insert(LL x){ LL x1=x; for(int i=63;i>=0;i--) if(x1&(1ll&...

2019-10-03 10:53:53 147

原创【模板】Dancing-Link X

模板题#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;#define N 1005#define INF 0x3f3f3f3fint n,m;int row[N*N],s1[N];int L[N*N],...

2019-10-03 10:51:16 197

原创【模板】BSGS

模板题#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>using namespace std;typedef long long LL;#define hmod 1389001LL A,B,mod;inline LL Pow(LL a,LL b...

2019-10-03 10:48:02 165

原创【模板】Miller-Rabin素性测试与Pollard-Rho因数分解

#include<cstdio>#include<algorithm>using namespace std;typedef long long LL;const int prim[]={2,3,5,7,11,13,17,19,23,29};inline LL Add(LL a,LL b,LL mod){ LL ret=0; while(b) { i...

2019-09-17 22:07:42 220

原创【模板】树上启发式合并

模板题#include<bits/stdc++.h>using namespace std;#define N 100005int n,a[N],ans[N],son[N],siz[N];vector<int>g[N];int f[N],sum,m;inline void dfs1(int x,int fa){ siz[x]=1; int ml=0,...

2019-08-04 11:11:49 348

Day 0其实本来是准备了十天的假期，接着吴老师就给我们推荐了这个“完全自愿”的外培。。。31号全员机场集合。刚到的时候下着小雨，穿过云层后看到了蓝天（可能无法想象我们后来是多么渴望阳光）。下飞机又是两个小时的车程，到了就开始布置寝室。对于这个学校的第一影响，就是很大，然后餐饮和住宿条件都有点像BZ；中山市主要因为台风（韦帕）的影响天天下雨，而且都是在CQ没听说过的的特大暴雨（新闻是这样描述的...

2019-08-01 21:48:32 176

原创【模板】最短路Dijkstra

模板题#include<bits/stdc++.h>using namespace std;#define N 200005struct mzls{ int nt,w,to;}a[N];struct node{ int x1,dis; node(){} node(int x,int y) { x1=x,dis=y; }};bool operato...

2019-07-19 08:57:36 141

原创【模板】扩展中国剩余定理

模板题推荐博客#include<cstdio>#include<algorithm>using namespace std;typedef long long LL;#define N 1005inline LL exgcd(LL a,LL b,LL &x,LL &y){ LL d=a; if(b>0) { d=exgc...

2019-03-18 13:36:02 217

原创【模板】后缀数组

模板#include<bits/stdc++.h>#define N 1000005using namespace std;int t1[N],t2[N],sa[N],h[N],rk[N],c[N],a[N],g[36][N],lg[N];inline void SA(int n,int m){ //DA->SA int *x=t1,*y=t2,p=0,...

2019-02-20 22:38:45 193

原创【模板】网络流Dicnic

模板题#include<cstdio>#include<algorithm>#include<cstring>#include<queue>using namespace std;#define N 1000005typedef long long LL;#define INF 1000000000000000000lls...

2019-01-29 14:39:48 360

原创【模板】AC自动机

模板题 #include<cstdio>#include<cstring>#include<queue>#include<algorithm>using namespace std;struct mzls{ int next[26],fail,count; void init() { memset(next,-1,si...

2019-01-29 14:36:18 210

原创【模板】Splay

模板题 #include<cstdio>#include<algorithm>using namespace std;#define N 100000#define INF 2000000005struct mzls{ mzls *ch[2]; mzls *fa; int key; int siz;}t[N+5];mzls *root,*N...

2019-01-29 14:34:16 207

原创【CF】Codeforces Round #531 (Div. 3) 题解

比赛经历第一次Div.3，难度不大，B题真的神，看了30分钟题懵一脸，1个小时两道题很绝望。结果后面加起来30分钟左右做完了，呵呵（B题还是FST，敢情我半个比赛都在研究英语阅读题还错了）。1102A-Integer Sequence Dividing材料阅读题。简单找下规律，n%4==3||n%4==0输出0，其他输出1就行了。1102B-Array K-Coloring...

2019-01-10 23:39:34 361

原创【模板】欧拉回路

题目注意欧拉回路和欧拉路径的区别#include<bits/stdc++.h>using namespace std;int T,n,m,aa;bool f1[200005],vis[200005],f2[200005];int a1[200005][2],c[200005],id[200005],ans[200005],s,t,d,t2;inline int ab...

2018-11-28 13:45:06 357

原创【模板】Tarjan（割点&割边）

题目#include<cstdio>#include<algorithm>#include<cstring>#include<vector>using namespace std;struct mzls{ int to,nt;}a[200005];int n,m,ncnt,cnt;int low[20005],dfn[200...

2018-11-28 13:20:50 359

原创【模板】Manacher算法

模板题推荐博客#include<iostream>#include<string>using namespace std;int p[30000005];inline int M(string s) { string s1="$#"; for(int i=0;i<s.size();i++) { s1+=s[...

2018-11-26 23:19:56 61

原创【模板】声明

本版块主要为博主个人所用，仅供参考

2018-11-26 23:19:48 444

原创 NOIP2018游记

什么都不说，先来张图Day -n第一次停课复习，半期也算是放弃了，大概两个星期，每天还要从本部回来自习。Day 0下午走的时候，陪着高二的学长把机房收拾了，机房很空，也不知道他们还有几个能回来。到了巴蜀试机，惊奇的发现我们学校竟然派了十几个初二的来参赛（还有一个初一），学校像是把我们年级抛弃了一样，除了我们四个跟着高二过来，其他的都没有试机。晚上回去的时候，二十分钟...

2018-11-19 13:52:24 435

原创【NOIP2018】旅行

题目链接做这题一定要看数据范围，从数据范围中可以得到，这个图要么是一棵树，要么是一棵基环树（树上多一条边）对于一棵树，每一步贪心取最小节点就行了。对于一棵基环树，你只需要枚举多的那条边删去按正常的树做。注意删去这条边后剩下的图应该联通，意思就是不能删去割边，所以先把割边找出来然后枚举每条非割边，然后就做完了。#include<cstdio>#include<a...

2018-11-18 11:00:26 771

原创【NOIP2018】货币系统

题目链接考试的时候理解错了题目，以为交易中是可以找零的，第一组样例也说得通（19=10*4-3*7）。后来发现如果这样的话第二组样例就错了（13=11+19-17），我才看到了题目中的t[i]是非负整数。于是转换题意，问你一个序列中最多有多少个数能被其他数表示（只能相加，每个数个数无限）。显然最小的数无法被表示，于是把数列排序后从最小的数开始做完全背包，每加入一个数就判断一...

2018-11-18 10:45:39 1319

原创【NOIP2018】铺设道路

题目链接水题不详写从头到尾扫一遍，如果后一个比前一个大就把差值加入答案。#include<cstdio>#include<algorithm>#include<cstring>#include<queue>using namespace std;int n,a[100005],ml;long long ans;int ma...

2018-11-18 10:28:49 1235

原创 C++程序细节优化总结

一、时间复杂度常数优化（一）输入、输出优化cin加速：关闭标准输入流的同步 ios::sync_with_stdio(false); 解除cin与cout的绑定 cin.tie(0); 利用getchar()&putchar()手写输入输出函数：读入优化 inline int read(){ int x=0,f=1;char c...

2018-10-30 17:14:25 1179

原创【NOIP2018模拟】电压机制

【问题描述】科学家在“无限神机”（Infinity Machine）找到一个奇怪的机制，这个机制有N 个元件，有M条电线连接这些元件，所有元件都是连通的。两个元件之间可能有多条电线连接。科学家对这些元件可以任意地设置为“高电压”和“低电压”两种模式，如果一条电线的一端为高电压，另一端为低电压，这条电线就会产生电流。为了安全的研究“无限神机”，科学家需要找到一条电线，将它的两端设为相同 ...

2018-10-20 16:32:25 414

原创 2018"ACM暑期多校联合训练"参（bao）赛（zha）记

（这毁了我一个暑假的东西）时间2018-7-23至2018-8-22，一星期2场，共10场，每场5个小时。题目链接（楼教主："是男人就过八（116）题"）评分规则单场得分 = 本队本次解题数 / 本次比赛前200名队伍全部解题数 *（500-队伍排名）* 日期系数（30+x）每次比赛只有前200名或者和第200名同样题数才有积分,否则0分取全部10场比赛中成绩最好的8场...

2018-08-23 12:33:35 655

原创树链剖分基础

基本定义把一棵树分成很多条链，然后利用数据结构（线段树、树状数组等）来维护这些链。作用树链剖分用于树路径信息维护。剖分方式随便剖分随机剖分轻重链剖分（本文）轻重链剖分的基本概念重结点：子树结点数目最多的结点；轻节点：父亲节点中除了重结点以外的结点；重边：父亲结点和重结点连成的边；轻边：父亲节点和轻节点连成的边；重链：由多条...

2018-08-05 10:35:34 280

原创 CDQ分治基础

引入偏序问题：这种类型的题目通常会告诉我们n个数组，其中每个元素有不同属性，询问通常是回答有多少元素A满足元素B的属性条件。如一个元素有三种属性：a,b,c，对于元素B，求满足条件的元素A（A.a<B.a,A.b>B.b,A.c<B.c）的个数，这就是一道典型的三维偏序问题。而解决偏序问题通常有以下方法：排序，数据结构(树状数组，线段树，平衡树)，cdq分治。在...

2018-08-03 10:22:00 322

转载 POJ题目分类

OJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)初期:一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. ...

2018-04-06 16:16:32 199

原创并查集基础

并查集的原理、实现与应用什么是并查集如果给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。什么是等价类在并查集中，同一个集合中的元素直接或者间接地有联系，我们就把这些元素称为属于同一个等价类。等价类具有三个基本性质：（用Ｘ~Ｙ表Ｘ与Ｙ等价）自反性：如Ｘ~Ｘ则Ｘ~Ｘ； ...

2018-02-12 10:18:15 366

原创二分图基础--匈牙利算法

二分图的概念 二分图又称作二部图，是图论中的一种特殊模型。 设G=(V, E)是一个无向图。如果顶点集V可分割为两个互不相交的子集X和Y，并且图中每条边连接的两个顶点一个在X中，另一个在Y中，则称图G为二分图二分图的性质 定理：当且仅当无向图G的每一个环(即回路、圈，英文为circle)的结数均是偶数时， G才是一个二分图。如果无环，相当于每个环的结点数为0，故也视为二分图二分图的判定...

2018-02-11 10:27:06 318

原创 DP——快速求和

快速求和版本一：题目描述给定一个数字字符串，用最少次数的加法让字符串等于一个给定的目标数字。每次加法就是在字符串的某个位置插入一个加号。在需要的所有加号都插入后，就象做普通加法那样来求值。例如，考虑字符串”12”，做0次加法，我们得到数字12。如果插入1个加号，我们得到3。因此，这个例子中，最少用1次加法就得到数字3。再举一例，考虑字符串”303”和目标数字6，最佳方法不是”3+0+

2017-12-12 18:05:19 672

原创 [NOIP2017普及组]跳房子

注：思想学习了wzy的博客，自己也有感受。题目描述跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。跳房子的游戏规则如下：在地面上确定一个起点，然后在起点右侧画n 个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定：玩

2017-11-24 14:05:19 831 1

原创 NOIP2017——总结

NOIP2017 一、score成绩（具体内容点开看）水题一道，废话不多二、librarian图书管理员（具体内容点开看）这个题我还是说一下，虽然我最后是AC了，但我们学校的同学还是提到了前导零的问题。举个例子：有一本书：23 有个人需要：023 显然这本书是不行的，但我们大多数人的算法都可以查找到。虽然测试数据中没有考虑前导零，但我认为我们还是可以严...

2017-11-21 14:09:41 301

原创 [NOIP2017普及组]图书管理员

题目描述图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个正整数。每位借书的读者手中有一个需求码，这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。小 D 刚刚当上图书馆的管理员，她知道图书馆里所有书的图书编码，她请你帮她写一个程序，对于每一位读者，求出他所需要的书中图书编码最小的那本书，如果没有他

2017-11-21 13:32:27 2809 1

原创 [NOIP2017普及组]成绩

找信心的题走个形式直接上代码#include#include#include#include#includeusing namespace std;int a,b,c;int main(){ //freopen("score.in","r",stdin); //freopen("score.out","w",stdout); scanf("%d%d%d",&a,&

2017-11-21 13:26:48 1256

空空如也

空空如也