倍增一般是RMQ难点以及树上公共祖先难题,使得字符串的字典序最小

数据结构

并查集:捆绑五个点的音信,推断是非

倍增:LCA,

 

开采众四个人都在搞这一个。。。自个儿也想来尝试(Solved刚到70就搞这一个靠不可信啊喂)。会更新的。嗯。

字符串

hash,模拟,

小小的表示法

给定叁个环状字符串,切开,使得字符串的字典序最小

NOIP2017赛前小结

1000-1029

图和树

割点,割边,强联通分量

点双联通分量 (把割点去掉便是)

边双联通分量

 

 

前言

  从新学期的第二周开头就是停课集中练习了,那也是一段很有意义的时光。集训时期,外地点的力量都赢得了晋级,代码技艺,应试能力,知识水平等等。NOIP2017即现在临,集中磨练也要拿出本人的成果来。为了对学过的学识,也让投机的学识进一步有系统,做一次“NOIP2017赛后小结”。

  Fighting!

1000 A+B problem

(这几个还亟需一句话吗?).

数学

O(n)筛法

欧拉函数

相当的慢幂,矩阵急迅幂

费马小定理,乘法逆元—>快捷幂

可能率与希望(离散,三番五次)

 

检验政策、方法、心态

  1. 联赛采纳Ubuntu,配置能够打好F9编写翻译以及括号补全就能够。
  2. 联赛的题面往往非常短,而且数据范围整整一版,先把3题都看贰回,看懂要干什么,数据范围能够先不去研讨。每日的率先题不要想复杂了,多多读三遍标题,然后一气浑成打完,能够再看看特殊的数码,同理可得要保管切掉,而且永不太急,45分钟只好都以足以的。然后用力去写前边两道题。第二题与第三题,部分分都不是很难想,在想到办法之后,要想想难轻便达成,细节尚未想驾驭从前不要打。然后无法卡在一道题上面了,第三题也必需留出时间,至少1h10min。最棒选用先打好暴力保底,那样本领不用缅想的企图难点。
  3. 侦察时要潜心关注,不要想一些难以置信的事物。不要因为难而令人挂念,尽力去从多角度思虑(举个例子能还是不能够打表、是或不是定论题、贪心可行呢、随机之后再贪心?、、、、、、)。
  4. 要是在想题时径直不通,能够出来洗脸等等的,让思绪越发明朗。

1001 狼抓兔子

平面图最小割转化为最短路。

动态规划

状压DP

间隔DP,先枚举长度,再枚举端点

树形DP(DP套DP)

DAG上的DP(依据拓扑序进行调换)

背包DP

前缀和优化(一维,二维)

单调栈,单调队列

线段树,堆

斜率优化

 

算法总括

1002 轮状病毒

矩阵树定理加三个手推的递推式就行了(注:在原行列式上递推有一点点麻烦,能够先递施行列式的一片段)。

搜索

 

基本功算法

1003 物流运输

枚举区间floyd求最短路,然后\(O(n^2)\)dp。。。

技巧

  • 对拍
  • 数量分治namespace

图片 1

 

 

专心:空间是加上的!!

 

  • 注意第二题 ,尽量快做
  • 贪心
  • 调查单调性
  • 拿暴力做优化
  • 非同一般数据是大数额的突破口

 

 

贪心

  贪心一般都以不会写的时候才选取的,考裸贪心的一般不太可能。大大多利欲熏心是用来协理DP分,比如一般对于区间的标题都以右端点排序之类的。

1004 Cards

直接上Burnside定理。

部分难题

分治

1005 明明的抑郁

无根树prufer连串+一点数学推理。

T1

图片 2

容斥原理

第一放伍分组,

cnt这几个会集的二进制里面有微微个1

图片 3

 

二分

  二分要静心边界的意况,本身行使的习于旧贯是闭区间即while(L<=PRADO)L=mid+1,揽胜极光=mid-1。都如此打就足以了。

1006 美妙的国家

弦图的染色数=最大团,按完美消除类别倒序染色。

T2

 图片 4

 

倍增

  倍增一般是RMQ问题以及树上公共祖先难点。公共祖先正是个板子,打地铁很熟谙了,如果考到了,也是不曾难题的。

1008 越狱

容斥(减法计数原理?)+四个高速幂(那么粗略的题还是能上省选?)。

 T3

 

 图片 5

把各类成分-1,那么就能够去掉k的限制

高精

  高精度在联赛后也可能有出现,选用结构体的重载运算符的写法。要极度注意前导0的意况,非常是减法。除法的话,一个人壹位的除即可了。还只怕有不要随意就觉着难题是高精度,要致密剖判,举个例子有三次NOIP就有不是用高精不过很想高精的解方程的难题。

1009 GT考试

经典KMP递推。

T4

图片 6

 

 

模拟

  模拟题往往题面会很难懂,特别是要致密,举个例子NOIP二〇一六的玩意儿谜题正是仿照,还应该有NOIP二零零七的学业调解方案。由此可知留心就足以了。

1010 玩具装箱

据称标算是干燥队列,但鉴于决策单调递增,然后搞二个枚举就能够过(数据太水,此做法只要有那多少个1就会卡)。

T5

图片 7

 

 

 

 图片 8

 枚举长富环,扣除答案

 

 图片 9

 

图论

1011 遥远的行星

接纳基值误差美妙将分母统一然后计算(话说那不符合物理原理吧喂)。

最短路(dijkstra、spfa、floyd)

  那三种最短路的宗旨算法不相上下。对于Floyd,适用于须求自由两点之间的最短路的意况,往往是用来支持图上DP的调换。Dijkstra则是安然无事的最短路算法,若是开掘标题会卡SPFA,就动用Dij,何况Dij可以求解次短路,使用优先队列优化,每回要弹掉队列中势必使用过的点。SPFA能够说不止是最短路,它的牵挂能够用到无数地方:“更新过就再立异任何的,不然就不立异”。

  别的,次短路主题素材也足以利用Dijkstra来求解,每一回先更新最短路,再立异次短路就可以。

1012 最大数

干燥队列+二分查找。

差分约束

  差分约束系统运用了很美妙的最短路思想。dis[u]+(u,v)>=dis[v],如若这一条边是v的最短路上的边那么纵然也就是不然就是抢先。那样就能够连一条边了。差分约束的卓越题举个例子poj-3169-layout。图中留存负环,就无解,不然的话,当到终点的相距为开端值INF,也正是不或者创新到终端,正是1~N得以极度大。图中的最短路对应着1~N的最大距离。

  借使难题反过来,供给1~N的最短距离的话,那么就是最长路了,在最长路中,dis[u]+(u,v)<=dis[v],所以加边自然也要扭转。

1013 球形空间发生器

列方程组,高斯消元。

最小生成树(kruskal、prim)

  kruskal是最常用的最小生成树的算法,然后仿佛SPFA同样,一时候出题人会去卡kruskal,所以prim也是必需调整的。prim的想想和Dijkstra同样,都是先找一个脚下具有未参预生成树的点中中远距离整个生成树距离最短的点到场生成树,然后更新与那三个点持续的全数一点的最短距离就能够。

  kruskal经典的施用是一道“Save your cats”。要想到是最小生成树依旧有思量难度的。prim算法举例Star Way To Heaven,这几个就丰裕利用了prim的喜眉笑眼来解题的。

1015 星球战役

倒着处理,并查集。

并查集

  并查集有这三个小手艺。首先就是路径压缩,能够大大晋级并查集的平安。然后写过一题名为:“好像正是并查集”。此题须要把原先在三个并查集内的三个成分移动到另二个并查集,那就不能够只变动fa[]了,不然整颗子树就全数移过去了。大家得以忽略被活动的点,然后新建贰个点代替需求活动的点,移动过去就可以。并查集还应该有带权并查集,最常见的权正是一体并查集的成分的个数恐怕到更节点的路线长度之类的,也会有难的诸如在“BZOJ4025二分图”中,维护的就是奇环照旧偶环,那一个也是倒霉维护的,何况不能够路线压缩。题中所说的加边恐怕四个端点已经是三个并查集内的,所以将要更新权值。

1021 循环的债务

运用总和不改变的习性和各样币种唯有6种处境来都行的削减回想化寻觅(或dp)枚举量。

拓扑排序、dfs 序

  那五个是二个东西,dfs序能够有限协理二个点,与她的子树,在体系中是一段连接的间隔,那样我们就能够动用数据结构举办优化了。

1022 小John的游戏

SJ定理(http://www.cnblogs.com/y-clever/p/6667592.html),
这些不算一句话。

二分图染色、二分图相配

  二分图的算法最棒的其实匈牙利(Magyarország)算法了。匈牙利(Magyarország)算法每一回去寻找叁个轮番路,然后更新con数组。用来求解二分图的最大相配。二分图的最大匹配等于二分图的最小点覆盖。最小路线覆盖=最大独立集=点数-最小点覆盖。

 1 bool dfs( int now )
 2 {
 3    vis[ now ]=1;
 4    for( int i=head[now];i;i=Next[i] )
 5       {
 6          int son=to[ i ];
 7          if( son==now )continue;
 8          if( !vis[ son ] )
 9             {
10                vis[ son ]=1;
11                if( con[ son ]<0 || dfs( con[ son ] ) )
12                   {
13                      con[ now ]=son;
14                      con[ son ]=now;
15                      return 1;
16                   }
17             }
18       }
19    return 0;
20 }

1024 破壳日欢快

暴搜(加回想化之后能够在bzoj上跑0ms)。。。

tarjan 找 scc、桥、割点、缩点

  Tarjan找这么些东西,概况上都是平等的,只是在有的小地点上区别样。五个数组dfn[],low[]。八个是访谈的dfs序,还应该有三个是通过返祖边能达到的一丝一毫dfn的点。

割点:low[v]>=dfn[u]则u是割点。

割边:low[v]>dfn[u]则(u,v)是割边。

Scc:在for(int i=head[u];i;i=Next[i])之后,如果dfn[u]==low[u]则发现了强联通分量了,把栈内成分抽出直到u结束。缩点就一向记下team[]即可。

无向图的边-双联通分量:无向图的边双的求法和强连通分量的好像,只是注意else if(dfn[v]<dfn[u] && fa!=v)中需要fa!=v。

提交无向图的点-双联通分量的求法(利用栈来求,割点属于每三个不休的点-双,所以它的team未有意义。):

 1 void Tarjan(int u,int fa)
 2 {
 3    dfn[u]=low[u]=++DFN;
 4    int child=0;
 5    for(int i=head[u];i;i=Next[i])
 6       {
 7          int v=to[i];
 8          if(!dfn[v])
 9             {
10                sta[++top]=i;//切记切记!!!要放在两个if里面,不能放在外面,否则反向的同一条边会被加2次!!!
11                child++;
12                Tarjan(v,u);
13                low[u]=min(low[u],low[v]);
14                if(low[v]>=dfn[u])
15                   {
16                      is[u]=1; cnt++; bcc[cnt].clear();
17                      int now;
18                      while(1)
19                         {
20                            now=sta[top--];
21                            if(team[from[now]] != cnt) team[from[now]]=cnt , bcc[cnt].push_back(from[now]);
22                            if(team[to[now]] != cnt) team[to[now]]=cnt , bcc[cnt].push_back(to[now]);
23                            if(from[now]==u && to[now]==v)break;
24                         }
25                   }
26             }
27          else if(dfn[v]<dfn[u] && fa!=v)
28             {
29                sta[++top]=i;
30                low[u]=min(low[u],dfn[v]);
31             }
32       }
33    if(fa==0)
34       {
35          if(child>1)is[u]=1;
36          else is[u]=0;
37       }
38 }

1025 游戏

数学推理+轻巧的分组单肩包。

树的直径、树的关键性

  树的直径正是树上的最长链。任性采用二个点,算出dis,然后找到dis最大的那么些点(它自然是最长链的一个端点),再算一次dis。就能够规定树的直径了。

  树的直径可以延长二个DAG的最长路。因为是有向图,所以从入度为0的点出发才大概是最长路。每趟从队列中抽出贰个点,–rudu[],在rudu==0时更新最长路。

  树的主旨:树的中央也叫树的质心。找到一个点,其有着的子树中最大的子树节点数最少,那么那么些点正是那棵树的器重,删去重心后,生成的多棵树尽也许平衡。与点分治相关。

1026 windy数

粗略的数位dp。

树链剖分

  树链剖分可以用来求解要修改的树上的关于链(路线)的询问难题。比方两点之间的门径上的最大边权。

  定义一批数组:fa[],sz[],top[],w[],dep[],son[].代表阿爸节点,子树大小,当前链(剖过的)的最上部节点,在线段树中对应的地点,深度,重外甥。Dep[root]=1.

  首先dfs二次求出fa[],sz[],dep[],son[].然后第二便dfs,先把重链上的全数一点遍历完,w对应线段树中一段连接的间距,然后把轻外甥的top设为外孙子本人,再把轻链加入进去。

  然后update,将兼具的边权之类的调换成线段树中去,因为映射到线段树中的是点,所以只要要求边,即将把边下放到点。接着就是修改和查询了。不在同一条重链上,就跳深度较深的,在同等条链上的时候就径直询问就能够。

1028 麻将

枚举听牌,再枚举对子,最终顺着扫贰回,顺子和刻子优先选前者。

数论

1030-1299

gcd、lcm

1 int gcd(int a,int b)
2 {
3   if(a%b==0)return b;
4   return gcd(b,a%b);
5 }

Lcm普通的正是lcm(a,b,c)=lcm(lcm(a,b),c)。Lcm(a,b)=a×b/gcd(a,b)。

1030 文本生成器

1009题的抓牢版,dp放到了AC自动机上。

埃氏筛法

线性筛质数与欧拉函数φ()。

 1 void getPrime()
 2 {
 3    is[1]=1;
 4    for(int i=2;i<=n;i++)
 5       {
 6          if(!is[i])
 7             {
 8                Q[++top]=i;
 9                Phi[i]=i-1;
10             }
11          for( int j=1 ; j<=top ; j++)
12             {
13                if( i * Q[j] > MAXN ) break ;
14                is[i * Q [j] ] = 1;
15                if( i%Q[j] == 0 )
16                   {
17                      Phi[ i*Q[j] ] = Phi[i] * Q[j];
18                      break;
19                   }
20                else
21                   Phi[ i*Q[j] ] = Phi[i] * ( Q[j] - 1 );
22             }
23       }
24 }

1031 字符加密

后缀数组裸题,只要把原串复制一份接在前面就好了。

Exgcd、求解同余方程、逆元

求解形如ax+by=gcd(a,b)的方程的一组成法解。最终将x变成正数一定要先取个模!不然T飞!

 1 int x,y;
 2 int ex_gcd(int a,int b)
 3 {
 4   if(b==0)
 5     {
 6       x=1,y=0;
 7       return a;
 8     }
 9   int ans=ex_gcd(b,a%b);
10   int t=x;
11   x=y;
12   y = t - a / b * y ;
13   return ans;
14 }

1037 生日集会

dp裸题,按男孩女孩数和有着后缀中男女孩数量的差的最大非常的小值dp。

组合数

 图片 10

1038 瞭望塔

能够窥见塔顶一定在每相邻三个终端的直线上方,所以求贰回半平面交,枚举全体已知点和享有半平面交顶点的横坐标就能够。

矩阵

矩阵连忙幂优化递推。

 图片 11

1041 圆上的整点

使用平方差公式和gcd降低枚举量。

数据结构

1042 硬币购物

dp预管理+容斥原理。

队列(单调队列)、栈(单调栈)

单调栈:是历次投入二个成分就与栈顶成分绝比较,如若栈顶成分不优,那么就弹掉栈顶。分明,单调栈是足以二分弹栈的。比方贰回考试的“lost my music”正是二分弹栈。

干燥队列:首要利用于滑动窗口难点,能够用来求解限制长度的最大子段和。更加多用来优化DP难题。注意单调队列与单调栈之内部存款和储蓄器储的一再是下标。还也可以有贰人单调队列。

单调栈:

while(st[ top ]<=a[i])top--;st[++top]=i;

干燥队列:

1 while(Q[head]<=a[i] && head>=tail)head--;
2 Q[++head]=i;
3 while(i-Q[tail]>limit)tail++;

1045 糖果传递

中位数(作者会告诉你那是蓝书例题3吧?)。

  堆能够动用系统的早期队列来贯彻,也很方便。可是不时堆要求统一,那么就要手写可并堆了也正是左偏树。对于系统堆的入眼运算符要特别注意不要打反了,即使能够超越小于都试一试就足以了。假诺是单个成分,直接加负数进去,出来再改为正数就可以。假如是结构体,bool operator <(const ed a){const };记住打好五个const,bool再次回到真,代表把小于号右边的要素丢到背后去,因为系统为大根堆而作者辈是要小跟堆,那么便是v>a.v,就把大的丢到背后去了。

左偏树的一部分操作:

除去堆顶成分:merge(ls[root],rs[root]);

参与一个因素:merge(root,now);

 1 int merge(int x,int y)
 2 {
 3     if( ! x )return y;
 4     if( ! y )return x;
 5     if( key[ x ] > key[ y ] )swap( x , y );
 6     rs[ x ] = merge( rs[ x ] , y );
 7     if( dis[ rs[ x ] ] >= dis[ ls[ x ] ] )swap( ls[ x ] , rs[ x ] );
 8     dis[ x ] = dis[ rs[ x ] ]+1;
 9     return x;
10 }

 

1047 理想的星型

开b个干燥队列维护各列在现阶段上下界的最大(最小)值,再开二个单调队列扫描叁回就可以。

线段树、树状数组

设若难点不是卡常,线段树是个科学的采取,终究打得极其的相当熟谙了。要静心打线段树从前特别注意是不是有距离的可和并性。

树状数组:加入:for(int i=v;i<=n;i+=(i*-i))c[i]++; 查询:for(int i=v;i>=0;i-=(i&-i))res+=c[i]。非常注意树状数组是从1始发,倘使输入有0,往往要++。

线段树:注意空间要够,注意Updata就足以了。还或然有正是动态开节点的线条树,只要访问的相当少,值域能够开到不小。对于lazy的操作也是要留意的,下放置后要清空。区间取模只要记下max就可以。

1048 分割矩阵

武力dp,因为标准差\(\sigma=\sqrt{\frac{1}{n}\sum_i x_i^2 –
\bar{x}^2}\),dp最小平方差。

字典树

  Tri树。重要用来字符串的询问与合营,也得以用来对与亦或的01串的贪婪。Tri树每三个点都要有那些幼子,然后消息是动态开的,要留意查询单词的时候,是急需收尾标志的,所以插入的时候要在最终打好得了标志。

  用于字符串相称半数以上就是AC自动机,这里不再赘言。

1057 棋盘制作

优化DP(据悉叫做扫描法)。

分块

  复杂度O(n√n)。把区间分成√n段,belong[i]=i/cnt+1;多少个点之间的完好的段直接询问,七个点所属的段,暴力一个二个询问。注意,半数以上的分块职责线段树都能够完结,要先行利用线段树,当区间未有可并性或许不佳查询时才思虑分块。例题:【HNOI2008】弹飞岩羊。

1059 矩阵游戏

因为同行同列的关联始终不改变,只供给找寻n个点不一致行列,也即二分图完美包容(行列为点,黑格子为边)。

动态规划

Dp总的来讲照旧要设好状态,思索改变的时候要周详。然后最棒写对拍程序,幸免出错。要疏散自身的企图,想想是或不是原先做过类似的难点。

1061 志愿者征集

经过类似线性规划的主见将问题转化为互联网流。

背包 DP

01背包:for(int i=1;i<=n;i++) for(int j=C;j>=w[i];j–) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);  当双肩包强制须求装满的时候:for(int i=1;i<=C;i++)dp[i]=-INF; 开端化为-INF,第二次只好从0转移,那样就都以满的了。

一心信封包:正是把枚举j反过来就能够了。

多种信封包:多一维枚举选取多少个。

1070 修车

经过把各种技艺工拆成倒数第二个,尾数第1个…倒数第n个,然后就足以二分图最大相配了。

树形 DP

树形DP一般都要选用到子树。例题:UVA-10859 Placing Lampposts。

1078 斜堆

找规律(提醒:斜堆的左右外孙子节点数之差的绝对值大约不改变)。。。

LCS、LIS、LCIS

最长公共子连串、最长上涨子系列、最长公共回涨子种类。那四个卓越的标题。

最长公共子连串:设dp[i][j]意味着系列a到i,系列b到j的长度,当a[i]==b[j]就能够转移dp[i][j]=dp[i-1][j-1]+1。否则dp[i][j] = max( dp[i-1][j] , dp[i][j-1] )。

最长上涨子种类:设dp[i]代表长度为i的子类别的末尾值,鲜明末尾值越小越好,每一遍二分找一个创新就可以,复杂度O(nlogn)。

最长公共上涨子类别:综合二者,一样设dp[i][j]意味着种类a到i,连串b到j的长度,只是转移更换一点就能够。For(j)的时候,每一遍从dp[i][1~j-1]中找二个b[j]小于a[i]的最大值,当a[i]==b[j]时转移即可,若不想等,直接从dp[i-1][j]转移。

1088 扫雷

那题放到广泛组也是送分题啊。。。

搜索

  搜索半数以上是用来打暴力对拍用的,可是一旦要考寻找的话,往往对代码工夫是三个挑衅,比方玛雅游戏,假使不注意,大概调节和测量试验就能够耗费时间非常多。简单的讲,寻觅要加剪枝,况且只倘使纯搜索题一定要想好细节再去打代码。

1089 严格n元树

怀想深不超越d的树数为\(f_d=f_{d-1}^n+1\),答案即为\(f_d-f_{d-1}\),python裸题。

STL

Pair<int,int>能够无需重载运算符。

Map<#,#>多少个辉映。

Queue<#>

1090 字符串折叠

\(O(n^2)\)dp。

注意事项

  1. 在互联网流中因为对应的两条边亦或1就能够得到,所以num从-1始发,head要伊始化为-1.
  2. 分块的数组的下标从零开始。
  3. 小心乘法不要爆int。
  4. 取模要注意是或不是会并发负数!加模加回来!

1192 王禅老祖的钱包

\(\lfloor log_2(m)
\rfloor+1\),即m的二进制位数(不是\(1,2,4,…\)!!!!!是\(\lceil \frac{m}2 \rceil, \lceil \frac{m}4
\rceil,…\))。

1228 E&D

观看及注明能够\(SG(i, j) =
log_2\,lowbit[(i-1) | (j-1)]\)。

1800 – 3999

1875 HH去散步

矩阵快捷幂。要以边建矩阵。

1876 SuperGCD

高精GCD。各样优化(python裸题=_=)。

1921 大陆争当霸主

最短路,反正机器人有无限个,把Dijkstra改一改就能够过。

一九二二 外星千足虫

异或方程组,bitset+高斯消元。

二〇〇四 弹飞岩羊

LCT入门题。

2427 软件设置

树形单肩包,以至没有要求优化(好像也不太能优化)。

3944 Sum

“裸”杜教筛(http://www.cnblogs.com/y-clever/p/6514901.html),
那几个不算一句话。

4500 – 4799

4513 储能表

四维(有三个维度是0/1)数位DP。

4514 数字配对

由质因数指数之和的奇偶性可窥见它是二分图(但前后相继中央直属机关接二染色就行),然后最小费用大肆流(开支为正就结束)。

4516 生成魔咒

后缀自动机裸题。每一种字符的进献是(增加后)len[last] –
len[pre[last]]。

4517 排列计数

错排数×组合数。

4518 征途

DP,斜率优化(\(\sigma^2 = \bar{x^2} –
\bar{x}^2\),方差转化为平方和)。

4600 硬币游戏

能够开掘硬币独立且翻法相当的少,暴力算SG函数就行了。

4784 仙人掌

先tarjan决断是否神灵掌并把环上的边去掉,然后有\(ans = \prod_{x \in V}
H_{deg_x+1}\),其中\(H_0=H_1=1,
H_n = (n-1)H_{n-2} +
H_{n-1}\)为n个点两两配成对(能够有不配成对的)方案数,可以暴力算;注意:那题tarjan要改成迭代,不然会爆栈,况且初始化不要memset(提醒:vis不要只存0/1)。//那都3句了吧→_→

相关文章