把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF 1547E Air Conditioner
题目大意：长度为N（2e5）的房间，有k个空调（<=N），每个有一定的位置pi和温度bi，房间里的每个格子的温度为min(bi+|pi-x|)，求每个格子最后的温度。

解：

每个空调可以看做一个二维坐标系上会往斜向上两个方向放出射线的点，由于射线的角度是一样的，实际上在一个点上只存在两个方向的射线，左斜向下和右斜向下，而且这两种中每种中只有最下面的那一条有效，那么这时我们不要把两条线综合来看，而是各自只看一个方向，这样问题就很轻易地变成了一个dp问题：因为右斜向下的线在点X上，只有空调位于X左边的时候才有效，在X之后每过一个单位距离就降低一个单位距离，相当于dp1[i]=min(dp1[i-1]+1,ac[i])（因为空调一定是从这一格开始生效），对dp2进行同样的处理，然后答案就是min(dp1[i],dp2[i])了。
这题的关键在于把原本二维上的几何分割成了两个线性的问题的比较，如果没有做过很容易看成几何问题然后做不出来呢。

代码

代码
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <queue>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 300005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(int i=0;i<n;i++)a[i]=m;
#define endl '\n'
#define pi 3.141592657
using namespace std;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll cpow(ll x, ll n) {
	ll ans = 1;
	while (n > 0) {
		if (n & 1) ans = (ans * x) % mdl;
		x = (x * x) % mdl;
		n >>= 1;
	}
	return ans;
}
/*

---------------------------------------------------------------------

*/

ll tpa[maxn];
ll dpL[maxn], dpR[maxn];
ll it[maxn], tp[maxn];
int main() {
	cfast;
	int t = 1;
	cin >> t;
	while (t--) {
		int m = 0;
		int n, k;
		cin >> n >> k;
		inc(i, 1, n + 1) {
			dpL[i] = 1e15;
			dpR[i] = 1e15;
			tpa[i] = 1e15;
		}
		dpL[0] = 1e15;
		dpR[n + 1] = 1e15;
		inc(i, 0, k) {
			cin >> it[i];
		}
		inc(i, 0, k) {
			cin >> tp[i];
			tpa[it[i]] = tp[i];
		}
		inc(i, 1, n + 1) {
			dpL[i] = min(dpL[i - 1] + 1, tpa[i]);
		}
		for (int i = n; i >= 1; i--) {
			dpR[i] = min(dpR[i + 1] + 1, tpa[i]);
		}
		inc(i, 1, n + 1) {
			cout << min(dpL[i], dpR[i]) << " ";
		}cout << endl;
	}
}
/*
2022.5.16 18：41

*/