把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。
题目大意：
CF1611E2 Escape The Maze(harder version)
题目大意，给一个树（大小规模为1e5），你从1开始，想要逃到别的子节点，树上有k个朋友（位置给出），你和朋友同时开始移动，只要被朋友抓到你就寄了。现在朋友想要省点体力所以他们想用最小的人数抓到你，让你求出最小需要几个人，如果所有人都上还抓不到那你就赢了，输出-1。
解：
很容易想到，当一个朋友在你来一棵子树之前就站在这棵子树的根上，那么这个子树就不需要其他人了，而达成这个目标的条件是朋友到这个根的距离小于等于“1”到这个根的距离，于是我进行两次dfs，第一次找每棵子树是否存在一个这样的朋友能直接站在子树的根上，如果能，我打个标记，这棵子树我只需要一个人就够了。之后我进行第二次dfs，这一次的dfs就是直接返回需要的人数了，凡是打过标记的我直接返回1，否则往下继续搜索，碰到打标记的还是返回1，否则搜到路上第一个有朋友的点，如果说搜到了叶子节点还没有找到朋友，那么我就可以从这条路成功逃脱。
由于最优性的缘故还是把它归类在树形dp里了，实际上应该只能算是记忆化搜索吧。
有一说一，做这题的时候满脑子都是“想和露娜做朋友吗？”……
1900分对于树形DP还是过于早了呀。什么树分治，我不知道，没听说过，这是数据结构选手应该做的吧。
代码
代码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
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 998244353
#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);
using namespace std;
ll dp[505][505];
int C[505][505];
ll cp[505][505];
void initC(const int& n) {
for (int i = 0; i <= n; ++i) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mdl;
}
}
ll cpow(ll x, ll n) {
int tmp = n;
if (cp[x][n]!=0)return cp[x][n];
ll ans = 1;
if (n == 0)ans = 1;
else if (n % 2 == 1) {
ans = x * cpow(x, n - 1) % mdl;
}
else {
ll a = cpow(x, n / 2);
ans = a * a % mdl;
}
cp[x][tmp] = ans;
return ans;
}
int main()
{
cfast;
initC(501);
int n, x;
cin >> n >> x;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i-1; j++) {
ll multi = (cpow(j,i) - cpow(j-1,i));
while(multi < 0)multi += mdl;
dp[i][j] = C[n][i] * multi%mdl;
}
}
ll ans = 0;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= x; j++) {
for (int k = i; j + k - 1 <= x&&k<=n; k++) {
dp[k][j + k - 1] += dp[i][j] * cpow(k-1,k-i)%mdl * C[n - i][k-i]%mdl;
dp[k][j + k - 1] = dp[k][j + k - 1] % mdl;
}
}
}
for (int i = 1; i <= x; i++) {
ans += dp[n][i];
ans = ans % mdl;
}
cout << ans << endl;
}
|
Copyright Notice: 此文章版权归EmiteInna所有，多看看吧。
