单调队列？入门题了解一下1、定义 单调队列顾名思义就是具有单调性的队列 单调性：所有元素保持同一种状态（递减 or 递增） 2、作用 可以优化dp,求最值将元素压入队列之中,同时保持队列的单调性,之后再取出队首（最优当前解） 3、使用 P2422 良好的感觉 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<bits/stdc++.h>#define gt getchar()#define int long longusing namespace std;const int maxn = 100001;int n, l, r;int v[maxn]; int sum[maxn];int q[maxn], dp[maxn];int x, head, tail, ans;int read() { char c = gt; int x = 0, f = 1; for(; !isdigit(c); c = gt) if(c == &#x ...

模板题1、作用 查找区间最值（最大值和最小值） 时间复杂度为 O（nlogn）预处理 查询只需要 O（1）的复杂度 2、原理分析 初始化就是复杂度最高的，也是较难理解的可以将 i~j 的一块区域分为左边和右边来求解 因为是求最值 不是和或差 所以是成立的如图 3、数组的定义123f[i][j] //代表从第i个数开始(包括自身)//向后延伸 2的j次方 个数的最值 所以 1f[i][0] //就是第i个数的值 4、处理 我们可以枚举j，i来求出最值 当然不要忘了赋初值循环j，i（不要越界） 123456int i, j;for(j = 1; j <= log2(n); j++) { for(i = 1; i + (1 << j) - 1 <= n; i ++) { f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); }} 5、代码12345678910111213141516171819202122232425262 ...

原题链接题意分析 根据题目可以发现，每一个为n的图腾都可以由3个n-1大小的图腾拼成 所以我们可以根据这一点进行分开计算 建议1.建议倒着处理，较为方便2.数组的初始值应为1' '//空格 防止初始值为NULL出错Code的处理1.因为图腾最小为1是所以可以进行打表处理2.根据样例可以判断出每一个图形的宽度wide是成倍增长的 所以将wide设为初始长度 wide=4 3.可以运用dep来保存第几个需要复制的图形 总共只要复制n-1次，因为第一次打表了 4.重点来了 每次复制有两个要点 将左侧复制和将右侧复制每次复制的深度为 wide/2每次复制的长(宽)度为 wide 所以可以推出公式 12mp[i+wide/2][j+wide/2]=mp[i][j]mp[i][j+wide]=mp[i][j] 空格是成2倍增加的，所以把之前的图形向右移，之后再复制 5.输出 因为一开始是倒着存储的所以输出时也应该倒着输出 wide的处理必须注意 Code12345678910111213141516171819202122232425262728 ...

1. 首先，复赛的时候注意时间复杂度和空间大小 1.看题目时必须仔细,例如数组的大小在空间允许的情况下，多开10倍 2.如果采用暴力算法，记得剪枝或者记忆化 2.关于区间dp常规模版：1234for ...//枚举区间长度 for ...//枚举左右两个端点 for ...//枚举断点，或者直接dp dp方程 推导方程的思路 1.运用数组，灵活表示当前的状态 例如P1880 [NOI1995]石子合并 设置 $f1[i][j]$ 代表第 $i\sim j$ 这个区间，石子合并的最大值 设置 $f2[i][j]$ 代表第 $i\sim j$这个区间，石子合并的最小值 通过题意得知，总价值=合成石子的数量的和 所以枚举一个中间点 $k$ (断点) $f[i][j]=\max(f[i][j],val[l][k] + val[k + 1][r] + merge(l, k, k + 1, r))$ 所以 $dp$ 是一个由小规模向大规模推导的过程 用数组或其他来描述当前的状态 3.关于记忆化关于记忆化模板 ...

Tram(电车)题目大意： 萨格勒布的电车网络由许多交叉路口和连接其中一些的铁路组成。在每个交叉路口都有一个开关，指向从交叉路口出来的一条铁轨。当有轨电车进入交叉路口时，它只能沿开关指向的方向离开。如果驾驶员想要采取其他方式，他/她必须手动更换开关。 当驾驶员从交叉路口A到交叉路口B进行驾驶时，他/她试图选择将最小化他/她必须手动更换开关的次数的路线。 编写一个程序，计算从交叉路口 $A$ 到交叉路口 $B$ 所需的最小开关变化次数。输入输入的第一行包含整数 $N$，$A$ 和 $B$，由单个空白字符分隔，$2 \le N \le 100,1 \le A，B \le N，N$ 是网络中的交叉点数，以及交叉点从 $1$ 到 $N$ 编号。 以下 $N$ 行中的每一行包含由单个空白字符分隔的整数序列。第 $i$ 行中的第一个数字 $K_i（0 \le K_i \le N-1）$表示从第i个交叉点出来的轨道数。下一个 $K_i$ 数字表示直接连接到第i个交叉点的交叉点。第i个交叉点中的交换点最初指向列出的第一个交叉点的方向。产量输出的第一行也是唯一一行应包 ...

P1463 [POI2001][HAOI2007]反素数 题解题意分析 首先这是一个数论题 $\tt Solution$ 根据数据分析得出 $2^9<\text{前十个质数的乘积}$ 由此判断出所有数中所含有的质数不会超过 $10$ 个即 $2,3,5,7,11,13,17,19,23,29,31$ 因为每个数都可以分成(质数除外)若干质数的乘积 此题中只有 $10$ 个质数 那么 约数个数的公式为 $f(n)=(a1+1)\times(a2+1)\times\dots(an+1)$ $ai$ 为 $n$ 分解出来的质数的指数从大到小排列 因为约数相同,最小的数才一定是反质数 之后通过搜索算法找到答案即可。 $Code$123456789101112131415161718192021222324252627#include <iostream>#include <cstdio>using namespace std;int f[]={0,2,3,5,7,11,13,17,19,21,23,29,31};//因为2*3* ...