使得字符串的字典序最小,  倍增一般是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<=R)L=mid+1,R=mid-1。都如此打就可以了。

1006 神奇的国家

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

T2

 图片 4

 

倍增

  倍增一般是RMQ问题以及树上公共祖先问题。公共祖先就是个板子,打的很内行了,如若考到了,也是从未有过问题的。

1008 越狱

容斥(减法计数原理?)+多个飞跃幂(那么不难的题还可以上省选?)。

 T3

 

 图片 5

把种种元素-1,那么就足以去掉k的限定

高精

  高精度在联赛中也有出现,拔取结构体的重载运算符的写法。要越发注意前导0的意况,越发是减法。除法的话,一位一位的除就足以了。还有不要随便就觉着问题是高精度,要致密分析,例如有三回NOIP就有不是用高精不过很想高精的解方程的题材。

1009 GT考试

经典KMP递推。

T4

图片 6

 

 

模拟

  模拟题往往题面会很难懂,越发是要细致,比如NOIP2016的玩意儿谜题就是仿照,还有NOIP2006的学业调度方案。不言而喻细心就可以了。

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),
这么些不算一句话。

二分图染色、二分图匹配

  二分图的算法最好的实在匈牙利算法了。匈牙利算法每便去摸索一个轮班路,然后更新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;七个点时期的完全的段直接询问,五个点所属的段,暴力一个一个询问。注意,大多数的分块任务线段树都可以做到,要优先利用线段树,当区间没有可并性或者不佳查询时才考虑分块。例题:【HNOI2010】弹飞绵羊。

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 修车

透过把每个技能工拆成倒数第四个,倒数首个…倒数第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裸题=_=)。

1922 大陆争霸

最短路,反正机器人有卓殊个,把Dijkstra改一改就能过。

1923 外星千足虫

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

2002 弹飞绵羊

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句了吧→_→

相关文章