2026/8/26 考试总结

hjm0703 Lv2

题目概述

省流:

首先 T1 写起来思虑还是非常明显的,我用了一种更加暴力的做法,就是去除每一个点之后再 DP 一次。最后坠机的 分,原因是我对于 存在一个特判,而他依赖于 DFS 所存贮的左右儿子。而我计算每一个位置的时候还再次 DFS 了一次,导致有极小概率会破坏掉 son 的存储。

然后 T2 第一眼就直接断定容斥加上大粪讨。 然后我一算基础容斥的时间复杂度, 这不坠机,然后就去打部分分了。然后后来为了打最后一个部分分,这里可以发现上面的时间复杂度感觉绰绰有余。然后就被容斥肘击了。目前感觉考场上写容斥都没有写出来过。但是实际上这道题更加优秀的做法是轮廓线 DP。 他不需要考虑各种 conner case。 赛后 30 分钟就写完了。实际上最开始看到那个数据范围,也大概想过,但是问题是他一共就放三个 L 再图上,这不是明显的大粪套吗。结果 是帮助轮廓线证明时间复杂度的。关键是谁能想到 NOIP 模拟赛靠轮廓线啊。

T3, T4 爽爽吃部分分,然后可以注意到 T4 如果加一个 ios 可以多得 15 分。

考场概述

T1 再 写完了,然后不想写对拍,因为暴力感觉比正解还麻烦。

然后 T2 最开始尝试容斥之后发现过于复杂,果断放弃。后来当作部分分打也写不出来了。实际上最大的问题是对于轮廓线的理解过于狭隘了。必经前面都是需要吧所有格子占满的。这里就放 个那么有规则的 L 型,感觉的不太像。你问我为什么不写容斥,这不是吃屎吗?

T3 T4 看上去部分分就很多,计划骗 分,最后得到 。

代码留存

T1
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int long long

template<class T> inline void ckmin(T& x, T y) { if(x > y) x = y; }
template<class T> inline void ckmax(T& x, T y) { if(x < y) x = y; }
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
static constexpr int N = 55;
int n, k;
string s;
int rt, du[N];
vector<int> v[N];

int son[N][2];
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/

ll dp[N][N][3], siz[N];
ll cp[4][N][3];
void solve(int x, int fa, int ignore) {
int l = -1, r = -1;
siz[x] = 1;
for(int y : v[x]) if(y != fa) {
if(y == ignore) continue;
solve(y, x, ignore);
siz[x] += siz[y];
if(l == -1) l = y;
else if(r == -1) r = y;
else cerr << "[ERROR]";
}

son[x][0] = l, son[x][1] = r;

memset(dp[x], 0, sizeof dp[x]);
if(l != -1 && r != -1) {
if(s[x] == 'Y') {
for(int i=0; i<=siz[l]; i++) {
for(int j=0; j<=siz[r]; j++) {
dp[x][i + j][0] += (dp[l][i][0] + dp[l][i][1]) * (dp[r][j][0] + dp[r][j][1]);
dp[x][i + j + 1][1] += (dp[l][i][0] + dp[l][i][1] + dp[l][i][2]) * (dp[r][j][0] + dp[r][j][1] + dp[r][j][2]);
}
}
} else {
for(int i=0; i<=siz[l]; i++) {
for(int j=0; j<=siz[r]; j++) {
dp[x][i + j][0] += (dp[l][i][0] + dp[l][i][1]) * (dp[r][j][0] + dp[r][j][1]);
dp[x][i + j + 1][1] += (dp[l][i][0] + dp[l][i][1] + dp[l][i][2]) * (dp[r][j][0] + dp[r][j][1] + dp[r][j][2]) - (dp[l][i][0] + dp[l][i][2]) * (dp[r][j][0] + dp[r][j][2]);
dp[x][i + j + 1][2] += (dp[l][i][0] + dp[l][i][2]) * (dp[r][j][0] + dp[r][j][2]);
}
}
}
} else if(l != -1) {
if(s[x] == 'Y') {
for(int i=0; i<=siz[l]; i++) {
dp[x][i][0] += dp[l][i][0] + dp[l][i][1];
dp[x][i + 1][1] += dp[l][i][0] + dp[l][i][1] + dp[l][i][2];
}
} else {
for(int i=0; i<=siz[l]; i++) {
dp[x][i][0] += dp[l][i][0] + dp[l][i][1];
dp[x][i + 1][1] += dp[l][i][1];
dp[x][i + 1][2] += dp[l][i][0] + dp[l][i][2];
}
}
} else { // 叶子节点
if(s[x] == 'Y') {
dp[x][0][0] = 1;
dp[x][1][1] = 1;
} else {
dp[x][0][0] = 1;
dp[x][1][2] = 1;
}
}

// cerr << x << '\n';
// for(int i=0; i<=siz[x]; i++) cerr << dp[x][i][0] << ' ' << dp[x][i][1] << ' ' << dp[x][i][2] << '\n';
// cerr << '\n';
}

/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
signed main() {
#ifdef LOCAL
freopen("samples/input6.txt", "r", stdin);
// freopen("samples/team6.in", "r", stdin);
freopen("samples/output.txt", "w", stdout);
#endif

freopen("team.in", "r", stdin);
freopen("team.out", "w", stdout);

cin >> n >> k >> s;
s = '#' + s;
for(int i=1; i<n; i++) {
int x, y; cin >> x >> y;
x++, y++;
v[x].push_back(y);
v[y].push_back(x);
du[x]++, du[y]++;
}

for(int i=1; i<=n; i++) if(du[i] <= 2) { rt = i; break; }

// cerr << rt << '\n';

solve(rt, 0, 0);

int sum = dp[rt][k][0] + dp[rt][k][1];

// cerr << sum << '\n';

for(int i=1; i<=n; i++) {
if(sum == 0) {
printf("%.15Lf ", 0.0l);
continue;
}

int cnt = 0, tot = 0;
if(i == rt) {
cnt = (son[i][0] != -1) + (son[i][1] != -1);
tot = 0;
if(son[i][0] != -1) {
tot++, solve(son[i][0], i, i);
memcpy(cp[tot], dp[son[i][0]], sizeof cp[tot]);
}
if(son[i][1] != -1) {
tot++, solve(son[i][1], i, i);
memcpy(cp[tot], dp[son[i][1]], sizeof cp[tot]);
}
} else {
cnt = (son[i][0] != -1) + (son[i][1] != -1) + 1;
tot = 0;
if(son[i][0] != -1) {
tot++, solve(son[i][0], i, i);
memcpy(cp[tot], dp[son[i][0]], sizeof cp[tot]);
}
if(son[i][1] != -1) {
tot++, solve(son[i][1], i, i);
memcpy(cp[tot], dp[son[i][1]], sizeof cp[tot]);
}
{
tot++, solve(rt, 0, i);
memcpy(cp[tot], dp[rt], sizeof cp[tot]);
}
}

if(cnt == 1) {
// cerr << "Case 1\n";
long double ans = 1.0l * (sum - cp[1][k][0] - cp[1][k][1]) / sum;
printf("%.15Lf ", ans);
} else if(cnt == 2) {
// cerr << "Case 2\n";
int sum2 = 0;
for(int i=0; i<=k; i++) sum2 += (cp[1][i][0] + cp[1][i][1]) * (cp[2][k-i][0] + cp[2][k-i][1]);
long double ans = 1.0l * (sum - sum2) / sum;
printf("%.15Lf ", ans);
} else {
// cerr << "Case 3\n";
int sum2 = 0;
for(int i=0; i<=k; i++) for(int j=0; i+j<=k; j++) {
int t = k - i - j;
sum2 += (cp[1][i][0] + cp[1][i][1]) * (cp[2][j][0] + cp[2][j][1]) * (cp[3][t][0] + cp[3][t][1]);
}
long double ans = 1.0l * (sum - sum2) / sum;
printf("%.15Lf ", ans);
}
}
return 0;
}

T2
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int long long

template<class T> inline void ckmin(T& x, T y) { if(x > y) x = y; }
template<class T> inline void ckmax(T& x, T y) { if(x < y) x = y; }
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
static constexpr int N = 35;
int n, m;
char c[N][N], d[N][N];
int upper[N][N], righ[N][N];

int top;
vector<pair<int, int>> a[N];
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/

bool vis[N][N];
bool check(
int x1, int y1, int x2, int y2, int x3, int y3,
int u1, int r1, int u2, int r2, int u3, int r3
) {
bool flag = true;
for(int i=0; i<=u1; i++) vis[x1-i][y1] = true;
for(int i=1; i<=r1; i++) vis[x1][y1+i] = true;

for(int i=0; i<=u2; i++) {
if(vis[x2-i][y2]) flag = false;
vis[x2-i][y2] = true;
}

for(int i=1; i<=r2; i++) {
if(vis[x2][y2+i]) flag = false;
vis[x2][y2+i] = true;
}

for(int i=0; i<=u3; i++) {
if(vis[x3-i][y3]) flag = false;
vis[x3-i][y3] = true;
}

for(int i=1; i<=r3; i++) {
if(vis[x3][y3+i]) flag = false;
vis[x3][y3+i] = true;
}

for(int i=0; i<=u1; i++) vis[x1-i][y1] = false;
for(int i=1; i<=r1; i++) vis[x1][y1+i] = false;
for(int i=0; i<=u2; i++) vis[x2-i][y2] = false;
for(int i=1; i<=r2; i++) vis[x2][y2+i] = false;
for(int i=0; i<=u3; i++) vis[x3-i][y3] = false;
for(int i=1; i<=r3; i++) vis[x3][y3+i] = false;

return flag;
}

bool check2(
int x1, int y1, int x2, int y2,
int u1, int r1, int u2, int r2
) {
bool flag = true;
for(int i=0; i<=u1; i++) vis[x1-i][y1] = true;
for(int i=1; i<=r1; i++) vis[x1][y1+i] = true;

for(int i=0; i<=u2; i++) {
if(vis[x2-i][y2]) flag = false;
vis[x2-i][y2] = true;
}

for(int i=1; i<=r2; i++) {
if(vis[x2][y2+i]) flag = false;
vis[x2][y2+i] = true;
}

for(int i=0; i<=u1; i++) vis[x1-i][y1] = false;
for(int i=1; i<=r1; i++) vis[x1][y1+i] = false;
for(int i=0; i<=u2; i++) vis[x2-i][y2] = false;
for(int i=1; i<=r2; i++) vis[x2][y2+i] = false;

return flag;
}

/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
signed main() {
#ifdef LOCAL
freopen("samples/input9.txt", "r", stdin);
// freopen("samples/problem.in", "r", stdin);
freopen("samples/output.txt", "w", stdout);
#endif

freopen("logo.in", "r", stdin);
freopen("logo.out", "w", stdout);

cin >> n >> m;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin >> c[i][j];
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) {
while(c[i - upper[i][j] - 1][j] == '.') upper[i][j]++;
while(c[i][j + righ[i][j] + 1] == '.') righ[i][j]++;
}

if(m == 2) {
int ans = 0;
for(int i=1; i<=n; i++) {
if(c[i][1] != '.' && c[i][2] != '.') continue;
for(int j=i+2; j<=n; j++) {
if(c[j][1] != '.' && c[j][2] != '.') continue;
for(int k=j+2; k<=n; k++) {
if(c[k][1] != '.' && c[k][2] != '.') continue;
int u1 = 0, u2 = 0, u3 = 0;
while(i + u1 + 1 < j && c[i + u1 + 1][2] == '.') u1++;
while(j + u2 + 1 < k && c[j + u2 + 1][2] == '.') u2++;
while(k + u3 + 1 <= n && c[k + u3 + 1][2] == '.') u3++;
ans += u1 * u2 * u3;
}
}
}
cout << ans << '\n';
return 0;
}

int ans = 0;
for(int x1=1; x1<=n; x1++) for(int y1=1; y1<=m; y1++) {
if(c[x1][y1] == '#') continue;
for(int x2=1; x2<=n; x2++) for(int y2=1; y2<=m; y2++) {
if(c[x2][y2] == '#') continue;
if(x1 == x2 && y1 == y2) continue;
for(int x3=1; x3<=n; x3++) for(int y3=1; y3<=m; y3++) {
if(c[x3][y3] == '#') continue;
if(x1 == x3 && y1 == y3) continue;
if(x2 == x3 && y2 == y3) continue;

for(int u1=1; u1<=upper[x1][y1]; u1++) for(int r1=1; r1<=righ[x1][y1]; r1++) {
for(int u2=1; u2<=upper[x2][y2]; u2++) for(int r2=1; r2<=righ[x2][y2]; r2++) {
if(!check2(x1, y1, x2, y2, u1, r1, u2, r2)) {
break;
}
for(int u3=1; u3<=upper[x3][y3]; u3++) for(int r3=1; r3<=righ[x3][y3]; r3++) {
if(check(x1, y1, x2, y2, x3, y3, u1, r1, u2, r2, u3, r3)) {
ans++;
// fprintf(stderr, "%d %d %d %d %d %d %d %d %d %d %d %d\n", x1, y1, x2, y2, x3, y3, u1, r1, u2, r2, u3, r3);
} else break;
}
}
}
}
}
}
cout << ans / 6 << '\n';

cerr << clock() / CLOCKS_PER_SEC << '\n';
return 0;
}

T3
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int long long

template<class T> inline void ckmin(T& x, T y) { if(x > y) x = y; }
template<class T> inline void ckmax(T& x, T y) { if(x < y) x = y; }
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
static constexpr int N = 50;
int d, n, m, k;
__int128 kk;
string seed;
int mul[N];
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/

int sum, cnt[N];
bool check(const string& s) {
int r = s.size() - 1;
for(int i=1; i+n-1<=r; i++) {
sum = 0; memset(cnt, 0, sizeof cnt);
for(int j=i; j<=i+n-1; j++) {
if(!cnt[s[j] - 'a']) sum++;
cnt[s[j] - 'a']++;
}
if(sum > d) return false;
}
return true;
}

vector<string> v;
void dfs(int x, string s) {
if(x == m + 1) {
if((s >= seed) && check(s)) {
v.push_back(s);
}
return ;
}

for(char i='a'; i<='z'; i++) {
s.push_back(i);
dfs(x + 1, s);
s.pop_back();
}
}

/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
signed main() {
#ifdef LOCAL
freopen("samples/input4.txt", "r", stdin);
// freopen("samples/problem.in", "r", stdin);
freopen("samples/output.txt", "w", stdout);
#endif

freopen("homogeneous.in", "r", stdin);
freopen("homogeneous.out", "w", stdout);

cin >> d >> n >> seed >> k;
m = seed.size(), seed = '#' + seed, k++;

if(m <= 4) {
dfs(1, "#");
if((int) v.size() >= k) cout << v[k-1].substr(1) << '\n';
} else if(d == n) {
kk = k;

mul[0] = 1;
for(int i=1; i<=m; i++) {
mul[i] = mul[i-1] * 26;
if(mul[i] > 2000000000000000005) mul[i] = 2000000000000000005;
}
for(int i=1; i<=m; i++) if(mul[m-i] != 2000000000000000005) kk += mul[m-i] * (seed[i] - 'a'), seed[i] = 'a';

// cerr << (ll) kk << '\n';

string ans;
for(int i=1; i<=m; i++) {
int d = 0;
// cerr << mul[m - i] << ' ' << ans << '\n';
while(kk > mul[m-i] && mul[m - i] != 2000000000000000005) d++, kk -= mul[m-i];
if(seed[i] + d > 'z') return 0;
ans.push_back(seed[i] + d);
}

cout << ans << '\n';
} else if(k == 1) {
string ans = "#";
for(int i=1; i<=m; i++) ans.push_back('z');
for(int i=1; i<=m; i++) {
bool flag = false;
for(int j=seed[i]; j<='z'; j++) {
ans[i-1] = j;
if(check(ans)) {
flag = true;
break;
}
}
if(!flag) return 0;
}
cout << ans.substr(1) << '\n';
}

cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
return 0;
}

T4
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

template<class T> inline void ckmin(T& x, T y) { if(x > y) x = y; }
template<class T> inline void ckmax(T& x, T y) { if(x < y) x = y; }
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
static constexpr int N = 1e6 + 5;
int n, m, k;

struct Node {
int x, y, z;
} a[N];

struct Edge {
int x, y, l;
} b[N];

pair<int, int> que[N];

int end_time[N], ans[N];

double dis(Node a, Node b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
double dz = a.z - b.z;
return sqrt(dx * dx + dy * dy + dz * dz);
}

vector<pair<int, int>> v[N];
vector<int> g[N];
/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/

struct DSU {
int fa[N];

void build(int n) {
for(int i=1; i<=n; i++) fa[i] = i;
}

int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
x = find(x), y = find(y);
if(x == y) return ;
fa[x] = y;
}
} dtr;

void solve() {
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i].x >> a[i].y;
for(int i=1; i<=n; i++) v[i].clear();
cin >> m;
memset(end_time, -1, sizeof end_time);
for(int i=1; i<=m; i++) {
int x, y, l; cin >> x >> y >> l;
v[x].emplace_back(y, i);
v[y].emplace_back(x, i);
b[i] = Edge{x, y, l};
if(dis(a[x], a[y]) > l) end_time[i] = 0;
}

cin >> k;
for(int i=1; i<=k; i++) {
g[i].clear();
int x, h; cin >> x >> h;
a[x].z += h;
for(auto to : v[x]) {
int y = to.first, w = b[to.second].l;
if(end_time[to.second] == -1) {
if(w < dis(a[x], a[y]))
end_time[to.second] = i;
}
}
}

// for(int i=1; i<=m; i++) cerr << end_time[i] << " \n"[i == m];

for(int i=1; i<=m; i++) if(end_time[i] > 0) g[end_time[i]].push_back(i);

int q; cin >> q;
for(int i=1; i<=q; i++) cin >> que[i].first >> que[i].second;

set<int> qu;
for(int i=1; i<=q; i++) qu.insert(i);

dtr.build(n);
for(int i=1; i<=m; i++) if(end_time[i] == -1) dtr.merge(b[i].x, b[i].y);
for(int i=k; i>=1; i--) {
vector<int> del;
for(int j : qu) if(ans[j] == 0) {
if(dtr.find(que[j].first) == dtr.find(que[j].second)) {
ans[j] = i;
del.push_back(j);
}
}
for(int x : del) qu.erase(x);
for(int x : g[i]) dtr.merge(b[x].x, b[x].y);
}

for(int i=1; i<=q; i++) {
if(ans[i] == k) cout << -1 << '\n';
else cout << ans[i] + 1 << '\n';
}
}

/*~~~~~~~~~~~~~~~~~~~~ Boundary Line ~~~~~~~~~~~~~~~~~~~~*/
signed main() {
#ifdef LOCAL
freopen("samples/input.txt", "r", stdin);
// freopen("samples/drone1.in", "r", stdin);
freopen("samples/output.txt", "w", stdout);
#endif

freopen("drone.in", "r", stdin);
freopen("drone.out", "w", stdout);

int T; cin >> T;
while(T --> 0) solve();
return 0;
}

  • 标题: 2026/8/26 考试总结
  • 作者: hjm0703
  • 创建于 : 2026-08-26 07:24:25
  • 更新于 : 2026-08-26 08:31:05
  • 链接: https://hjm-blog.de5.net/2026/08/25/2026/8/26 考试总结/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
2026/8/26 考试总结