题面：https://codeforces.com/problemset/problem/1603/A

大致题意：给定数组$a_1,a_2,....,a_n$,每次可以消除掉$a_i$,如果满足条件：$a_i%(i+1)!=0$,每次消除后更新数组的下标，判断所给数组能否变成空数组

题解：对于给定的$a_i$，与其原始下标i，易知，$a_i$的下标经过变换后只能为1~i，若1~i的范围内存在下标，则可将数移到该位置消去。

如何保证下标范围为1~i，即前面的数均可消去，而如果前面的数出现不可消去的数，则直接输出NO，故上述条件为充分必要条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<cstdio>
#include<list>
#include<stack>
#include<deque>;
#include<unordered_set>
using namespace std;
using ll = long long;
ll T;
ll n;
ll m, k;
ll a[300005];
ll ans[300005];
const ll INF = 1e12;
int main()
{
	cin >> T;
	while (T--)
	{
		cin >> n;
		for (ll i = 1; i <= n; i++)
		{
			cin >> a[i];
		}
		bool OK = 1;
		for (ll i = 1; i <= n; i++)
		{
			bool flag = 0;
			for (ll j = i; j >= 1; j--)
			{
				if (a[i] % (j + 1) != 0)
				{
					flag = 1;
					break;
				}
			}
			if (!flag)
			{
				OK = 0;
				break;
			}
		}
		cout << (OK ? "YES\n" : "NO\n");
	}
		
	return 0;
}

题面：第k次动作可以为向前走k步或向后退1步，给定坐标x，求最少需要几步才能走到x

正解:假设走k次，若k次全向前，则走了$k*(k+1)/2$步，若k-1次向前时，当前位置在x前面，则k-1次必定到不了x，故我们找到最小的k满足$k*(k+1)/2>=x$

我们进行分类讨论，能否在第k步到达x

1.若当前位置等于x，则第k步即为最优答案

2.若当前位置大于x，我们能否通过将一定数量的前进改成后退来使当前位置等于x？将第k次向前改成向后，可以视作向后走k+1步，但修改一定数量太难考虑，故我们想进一步缩小范围，证明修改两步以上是冗余的做法，可以通过修改1步做到

证明如下：若需要后退的步数大于k，则与第k-1次前进没到达x的假设相悖;若需要后退的步数小于k，则后退2~k+1步都能通过修改一次前进得到；若需要后退的步数等于1，则修改一次无法达到效果，必须多一次后退操作

附code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<cstdio>
#include<list>
#include<stack>
#include<unordered_set>
using namespace std;
using ll = long long;
ll T;
ll n;
ll m, k;
ll a[200005];
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> T;
	while (T--)
	{
		cin >> n;
		ll tmp = 0;
		while (tmp * (tmp + 1) / 2 < n)
		{
			tmp++;
		}
		if (n + 1 == tmp * (tmp + 1) / 2)
		{
			cout << tmp + 1 << '\n';
		}
		else
		{
			cout << tmp << '\n';
		}
	}	
	return 0;
}

在本人依据网上教程创建blog的流程中，由于npm的版本、教程的年代过于久远等问题，踩了不少坑，因此写这篇blog在记录下使用hexo创建blog的基本流程与容易踩到的一些坑

预警：因为本人懒得截图，故具体操作没有附图

eg:NOIP2003-P1041

给定传染病传染树，一个周期内只能切断一条途径，求最多能减少多少病人

贪心想法：统计切掉当前途径能减少多少病例，从多到少切

但是不同的途径在不同的时间点能减少的病人也不一样，故该贪心错误

使用随机函数寻找切掉的节点，通过设置权值使程序偏向寻找可能性最大的节点（辅以最优性剪枝），重复该操作直至无点可切

多次重复上述操作取最优值，最优解大概率正确

srds，这题是错题，数据极水。。直接用dfs遍历所有情况就可以

顾名思义，便是从目标状态与起始状态两个方向进行搜索，其实就是“关于dfs剪枝优化”中提到的二分优化（个人觉得用双向广度搜索更贴切hhh），将搜索的深度/2，而搜索深度所导致的时间复杂度是指数级的，故可大大优化时间复杂度

用八数码问题举例，用bfs搜索预处理出到达各个状态的最少步数并存储起来（此处运用到hash，不再赘述），然后再从目标状态反过来进行bfs，判断当前状态是否与之前预处理出的状态一致（依然是用hash判断），若一致，则当前步数+预处理步数则为最少步数

首先，我们运用dij等算法能较易得到最短路，但如果要求s到t的第k短路呢？

明显，这里需要用到搜索，需要从小往大搜索s到t的路径

我们运用A*算法，即f(n)=g(n)+h(n),引入i节点到t的最短路径作为h(i),我们运用SPFA算法处理出h(i)，g(n)则为s到i节点的实际距离，我们在优先队列中压入s节点，依据边更新g(n)与h(n),当n=t时，h(n)=0,f(n)=g(n),我们知道f(n)最小的路径总是最先得到，故我们取第k次搜索到t的实际距离，即为答案

注意：优先队列中通过估计距离来维护

第一次求最短路要用反向边

我们也由此看出A*的优势，可以依次求出第k优解

为什么要剪枝？