sdnu2020WinterContest3rd题解报告

这篇文章是关于SDNU_ACM_ICPC_2020_Winter_Contest_3rd的题解.

sdnu2020WinterContest-3 题解报告

这次的榜单和预想偏差较大

好多模拟，暴力没人做， ~~果然暴力，模拟这些体力活没人愿意干~~

由于uva的本体问题，有四道题变成了oi赛制，

A: hud-1364

tag： dfs， dp，暴力

题意：Tom 抓 Jerry, 他只大概记得他怎么走的，问你可能的出发点, 给出了地图，和走的每一步的最小步数和最大步数和方向

题解：

1
2
3

Q: 那我怎么办嘛

A: 由于数据范围很小，正向枚举每个点为起点，dfs， 或者反向dp直接搞

这题挺暴力，简单的，是根据训练计划出的中等题，~~大家弃a题不顾的行为令人心寒~~

dfs就不说了，直接搞, 判断就行

dp的时候设dp[s][i][j], s为第s步，i, j为坐标，转移方程为dp[s - 1][i][j] = dp[s][x][y]能否到达，怎么判呢，暴力啊2333，注意反向就行。这题就是告诉你们， dp，就是暴力 (误

dp :

/*************************************************************************
    > File Name: solve.cpp
    > Author: XeroxAuto
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-01-28 21:00:08
 ************************************************************************/

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<=(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define seg(t) (t).begin(), (t).end()
#define ep(x) emplace_back((x))
#define F first
#define S second

typedef pair<int, int> pa;
typedef std::string str;
typedef long long ll;
typedef __gnu_pbds::priority_queue<int> pq;

const int Ma = 110, inf = 0x3f3f3f3f;

bool dp[2][Ma][Ma];
int mz[Ma][Ma];
pa indx[Ma];
int n, m;

bool check(int r, int c) {
	return r >= 0 && r < n && c >= 0 && c < m && mz[r][c] != 1;
}

struct Step {
	int l, r;
	char ind;
};

void change(int& r, int& c, char dir) {
	r += indx[dir].F, c += indx[dir].S;
}

void print(int now) {
	rep(i, n){
		rep(j, m) if(dp[now][i][j])cerr << "1 "; else cerr << "0 ";
		cout << endl;
	}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
	indx['L'] = pa(0, 1), indx['R'] = pa(0, -1);
	indx['U'] = pa(1, 0), indx['D'] = pa(-1, 0);
	int T;
	cin >> T;
	while(T--) {
		cin >> n >> m;
		rep(i, n)rep(j, m)cin >> mz[i][j];
		int a, b; char c;
		vector<Step> v;
		while(cin >> a >> b, a + b) {
			cin >> c;
			v.ep((Step{a, b, c}));
		}
		int now = 0;
		rep(i, n) rep(j, m) if(check(i, j))dp[now][i][j] = true; else dp[now][i][j] = false;
		for(auto k = v.rbegin(); k != v.rend(); k++) {
			memset(dp[!now], 0, sizeof dp[!now]);
			rep(i, n) rep(j, m) if(dp[now][i][j]){
				int r = i, c = j, cnt = 1;
				while(cnt < k->l && check(r, c))cnt++, change(r, c, k->ind);
				if(cnt != k->l || !check(r, c)) continue;
				while(cnt <= k->r) {
					change(r, c, k->ind);
					cnt++;
					if(check(r, c))dp[!now][r][c] = true;
					else break;
				}
			}
			now = !now;
		}
		int ans = 0;
		rep(i, n) rep(j, m) if(dp[now][i][j]) ++ans;
		cout << ans << endl;
	}
    
    return 0;
}

dfs:

/*************************************************************************
    > File Name: solve.cpp
    > Author: XeroxAuto
    > Mail: lanzongwei@gmail.com
    > Created Time: 2020-01-28 21:00:08
 ************************************************************************/

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<=(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define seg(t) (t).begin(), (t).end()
#define ep(x) emplace_back((x))
#define F first
#define S second

typedef pair<int, int> pa;
typedef std::string str;
typedef long long ll;
typedef __gnu_pbds::priority_queue<int> pq;

const int Ma = 110, inf = 0x3f3f3f3f;

int mz[Ma][Ma];
int n, m;
pa indx[Ma];

bool check(int r, int c) {
	return r >= 0 && r < n && c >= 0 && c < m && mz[r][c] != 1;
}

struct Step {
	int l, r;
	char ind;
};

vector<Step> v;

void change(int& r, int& c, char dir) {
	r += indx[dir].F, c += indx[dir].S;
}

bool dfs(int r, int c, int step) {
	if(step == v.size())return true;
	int L = v[step].l, R = v[step].r; char ind = v[step].ind;
	int cnt = 1;
	while(cnt < L && check(r, c))change(r, c, ind), cnt++;
	if(cnt != L || !check(r, c))return false;
	while(cnt <= R) {
		change(r, c, ind);
		cnt++;
		if(check(r, c)){
			if(dfs(r, c, step + 1))
				return true;
		}else return false;
	}
	return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
	indx['R'] = pa(0, 1), indx['L'] = pa(0, -1);
	indx['D'] = pa(1, 0), indx['U'] = pa(-1, 0);
	int T;
	cin >> T;
	while(T--) {
		cin >> n >> m;
		rep(i, n)rep(j, m)cin >> mz[i][j];
		int a, b; char c;
		v.clear();
		while(cin >> a >> b, a + b) {
			cin >> c;
			v.ep((Step{a, b, c}));
		}
		int ans = 0;
		rep(i, n) rep(j, m) if(check(i, j) && dfs(i, j, 0)) ++ans;
		cout << ans << endl;
	}
    
    return 0;
}

B: CodeForces - 1242B

tag: 最小生成树，贪心

题意：给你一个有m条权值为1的无向边的完全图，问你得到的最小生成树的权值为多少

题解：贪心想来，肯定是能用权值为0的边我就用，权值为0用着不吃亏嘛。

那么对那m条边的端点，将他能用0边到达的点都和他缩在一块

在对缩完的点进行用1边连接，所以答案为缩完后的点数减一

1
2
3

Q: 什么是最小生成树，什么是完全图，什么是blabla

A: 对于基础遗忘的大一之流，建议找本《算法竞赛入门经典》，《挑战程序设计竞赛》，《算法竞赛进阶指南》之类的看看

或者找我深入♂交流

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
/*************************************************************************
> File Name: solve.cpp
> Author: XeroxAuto
> Mail: lanzongwei@gmail.com
> Created Time: 2020-01-30 14:56:16
************************************************************************/

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<=(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define seg(t) (t).begin(), (t).end()
#define ep(x) emplace_back(x)
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second

typedef pair<int, int> pa;
typedef std::string str;
typedef long long ll;
typedef __gnu_pbds::priority_queue<int> pq;

const int Ma = 1e5 + 100, inf = 0x3f3f3f3f;

unordered_set<int> mp[Ma];
set<int> point;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
rep(i, m) {
int u, v;
cin >> u >> v;
mp[u].emplace(v);
mp[v].emplace(u);
}
fep(i, 1, n)point.emplace(i);
function<void(int)> dfs = [&](int u) {
point.erase(u);
int now = 0;
while(!point.empty()) {
auto i = point.upper_bound(now);
if(i == point.end()) break;
now = *i;
if(!mp[u].count(now))dfs(now);
}
};

int cnt = 0;

fep(i, 1, n)if(point.count(i))
dfs(i), ++cnt;
cout << cnt - 1 << endl;

return 0;
}

C: UVA - 12879

tag：fft，生成函数

题意: 给你n个不同数字，问你能组成多少个给定数字

题解：设 \(ax^i\) a为这个数字出现了几次，i为这个数字，将数据全整理成了这样子后，让他自己乘自己

\[ \sum_{i=0}^n{a x^i} * \sum_{i=0}^n{b x^i} \]

你会发现指数相加后，如果系数不为0，就能组成，而如何处理多项式乘法呢？就是fft的事情了

1
2
3
4
5
6
7
Q: 师哥，我好喜欢fft，我想学

A: 你怎么什么都想学，是不是ntt你也想学

Q: 对呀对呀，我想学

A: 太棒了，16年国家队集训队论文，还有各种博客，论文都为你准备着呢

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
/*************************************************************************
> File Name: c.cpp
> Author: ghost_lzw
> Mail: lanzongwei@gmail.com
> Created Time: Thu 30 Jan 2020 03:30:00 PM DST
************************************************************************/

#include<bits/stdc++.h>
using namespace std;

const double PI = acos(-1.0);

const int Ma = 2e6 + 100;
bool be[Ma];
double ans[Ma];

typedef complex<double> cp;

void ReBuild(int& n){
int t = 1;
while(n * 2 >= t)
t <<= 1;
n = t;
}

cp omega(int n, int k){
return cp(cos(2.0 * PI * k / n), sin(2.0 * PI * k / n));
}

void fft(cp* X, int len, bool inv){
if(len == 1)return ;
static cp buf[Ma];
int m = len / 2;
for(int i = 0; i < m; i++){
buf[i] = X[2 * i];
buf[i + m] = X[2 * i + 1];
}
for(int i = 0; i < len; i++)
X[i] = buf[i];
fft(X, m, inv);
fft(X + m, m, inv);
for(int i = 0; i < m; i++){
cp x = omega(len, i);
if(inv) x = conj(x);
buf[i] = X[i] + x * X[i + m];
buf[i + m] = X[i] - x * X[i + m];
}
for(int i = 0; i < len; i++)
X[i] = buf[i];
}

void solve(int n, int big){
static cp X[Ma];
ReBuild(big);

for(int i = 0; i < big; i++){
if(i == 0 || be[i])X[i] = cp(1, 0);
else X[i] = cp(0, 0);
}
fft(X, big, false);
for(int i = 0; i < big; i++)
X[i] *= X[i];
fft(X, big, true);
memset(ans, 0, sizeof(ans));
for(int i = 0; i < big; i++)
ans[i] = X[i].real();
}

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
while(cin >> n){
memset(be, 0, sizeof(be));
int Max = 0;
for(int t, i = 0; i < n; i++)
cin >> t, be[t] = true, Max = max(Max, t);
solve(n, Max);
int m;
cin >> m;
int cnt = 0;
while(m--){
int t;
cin >> t;
if(ans[t] > 0.5)cnt++;
}
cout << cnt << '\n';
}

return 0;
}

D: UVA - 806

tag: 模拟，暴力

题意：让在四分树和矩阵表达之间转换

题解：按题意模拟即可，注意输出数字时每十二个一行，和全为1时的处理

1
2
3
Q: 我不会大模拟怎么办

A: 多写，多练，提高码力和注意力 (扔给队友

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
/*************************************************************************
> File Name: d.cpp
> Author: ghost_lzw
> Mail: lanzongwei@gmail.com
> Created Time: Thu 30 Jan 2020 03:32:19 PM DST
************************************************************************/

#include <bits/stdc++.h>
using namespace std;

const int Ma = 72;
int Pic[Ma][Ma];
vector<int>ans;

int Pow(int n){
if(n == -1)return 0;
int sum = 1;
while(n)sum *= 5, n--;
return sum;
}

int J(int a){
return a > 0 ? 1 : 0;
}

int build(int len, int xp, int yp, int indx, int bit, int pre){
int pp = pre + indx * Pow(bit);
//cout << len << ' ' << xp << ' ' << yp << ' ' << pp << ' ' << Pic[xp][yp] << endl;
if(len == 1)return bit == -1 ? Pic[yp][xp] : Pic[yp][xp] * pp;
int p1 = build(len / 2, xp, yp, 1, bit + 1, pp);
int p2 = build(len / 2, xp + len / 2, yp, 2, bit + 1, pp);
int p3 = build(len / 2, xp, yp + len / 2, 3, bit + 1, pp);
int p4 = build(len / 2, xp + len / 2, yp + len / 2, 4, bit + 1, pp);
int ju = J(p1) + J(p2) + J(p3) + J(p4);
//cout << "son " << p1 << ' ' << p2 << ' ' << p3 << ' ' << p4 << endl;
if(ju == 4){
return bit == -1 ? 1 : pp;
}else {
if(J(p1))ans.emplace_back(p1);
if(J(p2))ans.emplace_back(p2);
if(J(p3))ans.emplace_back(p3);
if(J(p4))ans.emplace_back(p4);
return 0;
}
}

void solvePic(int n){
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
scanf("%1d", &Pic[i][j]);
/* for(int i = 0; i < n; i++, cout << '\n')
for(int j = 0; j < n; j++)
cout << Pic[i][j];*/
if(build(n, 0, 0, 0, -1, 0))ans.emplace_back(0);
sort(ans.begin(), ans.end());
int cnt = 0;
for(auto i = ans.begin(); i != ans.end(); i++){
if(cnt)cout << ' ';
cout << *i;
if(cnt == 11)cnt = 0, cout << '\n';
else cnt++;
}
if(cnt && ans.size() > 0)cout << '\n';
cout << "Total number of black nodes = " << ans.size() << '\n';
}

void Full(int t, int n){
int bit = 0;
int len = n, xp = 0, yp = 0;
for(;;){
int pos = t % 5;
if(pos == 0){
for(int i = 0; i < len; i++)
for(int j = 0; j < len; j++)
Pic[yp + i][xp + j] = 1;
break;
}
else if(pos == 2)xp += len / 2;
else if(pos == 3)yp += len / 2;
else if(pos == 4)xp += len / 2, yp += len / 2;
t /= 5;
len /= 2;
}
}

void solveNum(int n){
memset(Pic, 0, sizeof(Pic));
int t;
while(cin >> t && ~t)
Full(t, n);
for(int i = 0; i < n; i++, cout << '\n')
for(int j = 0; j < n; j++)
cout << (Pic[i][j] ? '*' : '.');
}

int main(){
int n, k = 0;
bool im = false;
while(cin >> n && n){
if(im)cout << '\n';
else im = true;
cout << "Image " << ++k << '\n';
ans.clear();
if(n > 0)solvePic(n);
else solveNum(-n);
}

return 0;
}

E: CodeForces - 489C

tag: 构造贪心

题意：让你给出m位，每位数字和为s所能组成的最大值和最小值

题解：可以直接贪，首先考虑-1 -1 的情况，只有s大于了9 * m，或者s等于0，但m却不等于0的情况，最小肯定最大位至少放一，然后从后往前贪，尽量放满后面，最大从前往后贪，尽量放满前面

可以每位每位构造，也可以直接构造，最小就在最高位为一的情况上加，最小就在m+1位为1的情况向下减,

1
2
3
Q: what are you talking about?

A: talk is cheap, show me the code.

1
2
3
m, s = map(int, input().split())
if s > 9 * m or (s == 0 and m != 1) : print(-1, -1)
else : print(int(10 ** (m - 1) + ((s - 1) % 9 + 1) * 10 ** ((s - 1) // 9) - 1), int(10 ** m - int((10 - (s % 9)) * 10 ** (m - s // 9 - 1))))

F: POJ - 1364

tag: 差分约束系统

题意：给你m个约束条件，问你是否合情合理
题解：是否记起了1st的l题？各位补过题的有福了，这又是一道差分约束系统，太棒了，~~大家都会做了~~
根据题意建图，跑bellman-Ford判负环即可

1
2
3
Q: 我不会差分约束系统怎么办

A: 这问题你在1st就该问自己了

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
/*************************************************************************
> File Name: solve.cpp
> Author: XeroxAuto
> Mail: lanzongwei@gmail.com
> Created Time: 2020-01-29 13:08:56
************************************************************************/

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<=(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define seg(t) (t).begin(), (t).end()
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define ep(x) emplace_back(x)

typedef pair<int, int> pa;
typedef long long ll;

const int Ma = 200, inf = 0x3f3f3f3f;

struct Node {
int v, nex, w;
}node[Ma * 10];

int head[Ma], tot;

void init() {
memset(head, -1, sizeof head);
tot = 0;
}

void add(int u, int v, int w) {
node[tot].v = v, node[tot].w = w;
node[tot].nex = head[u], head[u] = tot++;
}

int n, m;

bool spfa(int s) {
int dis[Ma]; bool vis[Ma];
memset(dis, inf, sizeof dis), memset(vis, 0, sizeof vis);
queue<int> q;
q.push(s);
q.push(0);
dis[s] = 0;
while(!q.empty()) {
int t = q.front(); q.pop();
int cnt = q.front(); q.pop();
if(cnt > n)return false;
vis[t] = false;
qxx(i, t) {
const Node& g = node[i];
if(dis[g.v] > dis[t] + g.w) {
dis[g.v] = dis[t] + g.w;
if(!vis[g.v])q.push(g.v), q.push(cnt + 1), vis[g.v] = true;
}
}
}
return true;
}

int main() {
while(scanf("%d%d", &n, &m) == 2) {
init();
rep(i, m) {
int u, v, w; char com[5];
scanf("%d %d %s %d", &u, &v, com, &w);
v += u;
if(com[0] == 'g')add(v, u - 1, -w - 1);
else add(u - 1, v, w - 1);
add(n + 1, v, 0), add(n + 1, u - 1, 0);
}
if(spfa(n + 1))puts("lamentable kingdom");
else puts("successful conspiracy");
}

return 0;
}

G: CodeForces - 787D

tag: 最短路线段树

题意：给你三种单向边

点到点 u -> v

点到区间 v -> [l, r]

区间到点 [l, r] -> v

让你找从s点到其他所有点的最短路

题解：建立两颗线段树，连边的时候就从第一棵线段树连到第二棵线段树，第一颗线段树向上走无花费，第二棵向下走无花费，第二棵再将叶子节点连向第一颗的叶子节点

如此建图，建完后在这张图上跑最短路即可

1
2
3
Q: 我不会...

A: 闭嘴，最短路你会，线段树你也会 (dog head

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
/*************************************************************************
> File Name: solve.cpp
> Author: XeroxAuto
> Mail: lanzongwei@gmail.com
> Created Time: 2020-01-29 15:42:06
************************************************************************/

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fep(i,b,e) for(int i=(b);i<=(e);++i)
#define rep(i,x) for(int i=0;i<(x);++i)
#define seg(t) (t).begin(), (t).end()
#define ep(x) emplace_back(x)
#define qxx(i,x) for(int i = head[x]; ~i; i = node[i].nex)
#define F first
#define S second

typedef pair<int, int> pa;
typedef std::string str;
typedef long long ll;
typedef __gnu_pbds::priority_queue<int> pq;

const int Ma = 1e6 + 100;
const ll inf = 0x3f3f3f3f3f3f3f3f;

inline int id(int l, int r) {
return (l + r) | (l != r);
}

struct Node {
int v, w, nex;
}node[Ma * 10];

int head[Ma * 4], tot;

void init() {
memset(head, -1, sizeof head);
tot = 0;
}

void add(int u, int v, int w) {
node[tot].v = v, node[tot].w = w;
node[tot].nex = head[u], head[u] = tot++;
}

int n;

#define o id(l, r)
#define lc id(l, mid)
#define rc id(mid + 1, r)

void build(int l, int r) {
if(l == r) return;
int mid = (l + r) >> 1;
build(l, mid), build(mid + 1, r);
if(l > n)add(o, lc, 0), add(o, rc, 0);
else add(lc, o, 0), add(rc, o, 0);
}

void connect(int l, int r, int L, int R, int v, int w) {
if(l > R || r < L) return ;
if(L <= l && r <= R) {
if(l > n)add(id(v, v), o, w);
else add(o, id(v, v), w);
return ;
}
int mid = (l + r) >> 1;
connect(l, mid, L, R, v, w), connect(mid + 1, r, L, R, v, w);
}

ll dis[Ma * 4];
bool vis[Ma * 4];

void spfa(int s) {
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
queue<int> q;
q.emplace(s);
while(!q.empty()) {
int u = q.front(); q.pop(); vis[u] = false;
qxx(i, u) {
const auto& t = node[i];
if(dis[t.v] > dis[u] + t.w) {
dis[t.v] = dis[u] + t.w;
if(!vis[t.v]) {
q.emplace(t.v);
vis[t.v] = true;
}
}
}
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
init();
int q, s;
cin >> n >> q >> s;
build(1, n); build(n + 1, 2 * n);
fep(i, 1, n) add(id(i + n, i + n), id(i, i), 0);
rep(i, q) {
int t, v, l, r, w;
cin >> t;
if(t == 1) {
cin >> v >> l >> w;
add(id(v, v), id(l + n, l + n), w);
}else {
cin >> v >> l >> r >> w;
if(t == 2)connect(n + 1, 2 * n, l + n, r + n, v, w);
else connect(1, n, l, r, v + n, w);
}
}
spfa(id(s, s));
fep(i, 1, n) {
ll now = dis[id(i, i)];
if(now == inf) now = -1;
cout << now;
if(i != n)cout << ' ';
else cout << endl;
}

return 0;
}

H: UVA - 12118

tag: 欧拉路贪心

题意：在权值为t的完全图上，让你一定要走e条边，问你最少花费

题解：对这e条边，如果其中几条在一个联通块内，那么最优策略就是只走这些边一次

也就是一条欧拉路，对于不是欧拉路的情况，我们通过加边来使他变成欧拉道路即可，每加一条边能消去两个奇数点

对于两个联通块之间，我们通过一条边来连接

所以，花费为 e + 为达成欧拉路加的边 + 连接联通块的边的数量乘 t

1
2
3
Q: 欧拉路是啥？

A: 每条边恰好走一次的路，他有许多美妙的性质值得你摸♂索

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
/*************************************************************************
> File Name: h.cpp
> Author: ghost_lzw
> Mail: lanzongwei@gmail.com
> Created Time: Thu 30 Jan 2020 03:39:06 PM DST
************************************************************************/

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pa;
#define F first
#define S second

const int Ma = 1e3 + 100;
std::vector<int> g[Ma];
bool vis[Ma];

void dfs(int d, int& n){
vis[d] = true;
n += (g[d].size() & 1);
for(const auto& i : g[d]) if(!vis[i])
dfs(i, n);
}

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, e, t, k = 0;
while(cin >> n >> e >> t && n){
for(int i = 0; i < n; i++)
g[i].clear(), vis[i] = false;
cout << "Case " << ++k << ": ";
for(int u, v, i = 0; i < e; i++){
cin >> u >> v;
u--, v--;
g[u].emplace_back(v), g[v].emplace_back(u);
}
int ans = 0, cnt = 0;
for(int i = 0; i < n; i++) if(!vis[i] && !g[i].empty()){
int num = 0;
dfs(i, num);
if(num > 2)ans += (num - 2) / 2;
cnt++;
}
cout << (ans + max(cnt - 1, 0) + e) * t << '\n';
}

return 0;
}

I: CodeForces - 479C

tag: 贪心

题意：给你n场考试，每场你可在ai或bi中选一天考，其中ai > bi, 问你如何打破a的递增且考完考试的天数最小

题解：按a递增排序后，能在第b天考就在第b天考

1
2
3
Q: 我能早点考试吗？

A: tql，我，，先去复习会，

1
2
3
4
ans = 0
for a, b in sorted(list(map(int, input().split())) for _ in range(int(input()))) :
ans = a if ans > b else b
print(ans)

J: UVA - 10410

tag: dfs 模拟

题意：给你一颗树的bfs序和dfs序，保证为字典序最小，让你重建这棵树

题解：以dfs序为主递归遍历重建，用dfs序来检测两节点是否在同一层

1
2
3
Q: 师哥师哥，我会dfs和模拟但我不会这个

A: 你真的会dfs和模拟吗

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
/*************************************************************************
> File Name: j.cpp
> Author: ghost_lzw
> Mail: lanzongwei@gmail.com
> Created Time: Thu 30 Jan 2020 03:48:41 PM DST
************************************************************************/

#include <bits/stdc++.h>
using namespace std;

const int Ma = 1e3 + 100;
int dfs[Ma];
int wb[Ma];
list<int>ans[Ma];

void init(int n){
for(int i = 0; i <= n; i++)
ans[i].clear();
}

int gao(int le, int ri){
int root = dfs[le], last = le + 1, val = dfs[last];
for(++le; le < ri; le++){
if(val < dfs[le] && wb[val] + 1 == wb[dfs[le]])
val = dfs[le],
ans[root].emplace_back(gao(last, le)),
last = le;
}
if(last < ri)ans[root].emplace_back(gao(last, ri));
return root;
}

/*6
1 2 3 4 5 6
1 2 4 5 3 6*/

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
while(cin >> n){
init(n);
for(int b, i = 0; i < n; i++)
cin >> b, wb[b] = i;
for(int i = 0; i < n; i++)
cin >> dfs[i];
gao(0, n);
for(int i = 1; i <= n; i++){
cout << i << ':';
for(const auto& j : ans[i])
cout << ' ' << j;
cout << '\n';
}
}

return 0;
}

K: HYSBZ - 1036

tag: 树链剖分线段树

题意：中文题面，就是带修改地问你树上两点之间的最大值和两点之间的和

题解：树剖经典题。

我们用重链剖分整棵树后，用线段树log(n)维护树上信息

并利用树剖在链上进行跳转查询

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
171
172
173
174
175
176
177
178
/*************************************************************************
> File Name: k.cpp
> Author: ghost_lzw
> Mail: lanzongwei@gmail.com
> Created Time: Thu 30 Jan 2020 03:51:27 PM DST
************************************************************************/

#include <bits/stdc++.h>
using namespace std;

const int Ma = 3e4 + 100;
int V[Ma * 2], W[Ma], nex[Ma * 2];
int head[Ma], cnt;
int top[Ma], dfn[Ma], rnk[Ma], all;
int fa[Ma], deep[Ma], siz[Ma], son[Ma];

const int inf = 0x3f3f3f3f;

struct SegTree{
int sum[Ma * 4], Max[Ma * 4];
void build(int o, int l, int r){
if(l == r){
sum[o] = Max[o] = W[rnk[l]];
return ;
}
int mid = (l + r) >> 1;
build(o << 1, l, mid);
build(o << 1 | 1, mid + 1, r);
sum[o] = sum[o << 1] + sum[o << 1 | 1];
Max[o] = max(Max[o << 1], Max[o << 1 | 1]);
}
int qmax(int o, int l, int r, int L, int R){
if(l > R || r < L)return -inf;
if(l >= L && r <= R)return Max[o];
int mid = (l + r) >> 1;
return max(qmax(o << 1, l, mid, L, R), qmax(o << 1 | 1, mid + 1, r, L, R));
}
int qsum(int o, int l, int r, int L, int R){
if(l > R || r < L)return 0;
if(l >= L && r <= R)return sum[o];
int mid = (l + r) >> 1;
return qsum(o << 1, l, mid, L, R) + qsum(o << 1 | 1, mid + 1, r, L, R);
}
void update(int o, int l, int r, int pos, int val){
if(l == r){
sum[o] = Max[o] = W[rnk[l]] = val;
return ;
}
int mid = (l + r) >> 1;
if(pos <= mid)
update(o << 1, l, mid, pos, val);
else update(o << 1 | 1, mid + 1, r, pos, val);
sum[o] = sum[o << 1] + sum[o << 1 | 1];
Max[o] = max(Max[o << 1], Max[o << 1 | 1]);
}
}st;

void add(int u, int v){
V[cnt] = v;
nex[cnt] = head[u];
head[u] = cnt++;
}

void dfs1(int now){
son[now] = -1;
siz[now] = 1;
for(int i = head[now]; ~i; i = nex[i]){
int v = V[i];
if(!deep[v]){
deep[v] = deep[now] + 1;
fa[v] = now;
dfs1(v);
siz[now] += siz[v];
if(!~son[now] || siz[son[now]] < siz[v])
son[now] = v;
}
}
}

void dfs2(int now, int tp){
top[now] = tp;
dfn[now] = all;
rnk[all++] = now;
if(!~son[now])return ;
dfs2(son[now], tp);
for(int i = head[now]; ~i; i = nex[i]){
int v = V[i];
if(v != son[now] && v != fa[now])
dfs2(v, v);
}
}

void init(int n){
cnt = 0;
for(int i = 0; i <= n; i++)
head[i] = -1;
}

void build(int n){
deep[1] = 1;
fa[1] = 1;
dfs1(1);
all = 1;
dfs2(1, 1);
st.build(1, 1, n);
}

void update(int pos, int val, int n){
st.update(1, 1, n, dfn[pos], val);
}

int querryMax(int u, int v, int n){
int ans = -inf;
while(top[u] != top[v]){
if(deep[top[u]] >= deep[top[v]]){
ans = max(ans, st.qmax(1, 1, n, dfn[top[u]], dfn[u]));
u = fa[top[u]];
}else {
ans = max(ans, st.qmax(1, 1, n, dfn[top[v]], dfn[v]));
v = fa[top[v]];
}
}
if(u != v){
int *bg = (dfn[u] >= dfn[v] ? &u : &v), *sm = (dfn[u] >= dfn[v] ? &v : &u);
ans = max(ans, st.qmax(1, 1, n, dfn[*sm], dfn[*bg]));
}else ans = max(ans, W[u]);
return ans;
}

int querrySum(int u, int v, int n){
int ans = 0;
while(top[u] != top[v]){
if(deep[top[u]] >= deep[top[v]]){
ans += st.qsum(1, 1, n, dfn[top[u]], dfn[u]);
u = fa[top[u]];
}else {
ans += st.qsum(1, 1, n, dfn[top[v]], dfn[v]);
v = fa[top[v]];
}
}
if(u != v){
int *bg = (dfn[u] >= dfn[v] ? &u : &v), *sm = (dfn[u] >= dfn[v] ? &v : &u);
ans += st.qsum(1, 1, n, dfn[*sm], dfn[*bg]);
}else ans += W[u];
return ans;
}

int main(){
int n;
scanf("%d", &n);
init(n);
for(int a, b, i = 0; i < n - 1; i++){
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
for(int i = 1; i <= n; i++)
scanf("%d", W + i);
build(n);
int q;
scanf("%d", &q);
while(q--){
char com[10];
int u, v;
scanf("%s%d%d", com, &u, &v);
if(com[0] == 'C'){
update(u, v, n);
}else {
if(com[1] == 'M'){
printf("%d\n", querryMax(u, v, n));
}else if(com[1] == 'S'){
printf("%d\n", querrySum(u, v, n));
}else assert(false);
}
}

return 0;
}

L: HYSBZ - 1935

tag: 离线 cdp

题意：中文题面给你树的坐标，和m个二维询问

题解：可以加一维时间，转换为三维偏序问题, 询问离线下来，cdq分治第二维，树状数组维护第三维，稍微注意下cdp细节处理

也可以离线下来，离散下，容斥乱搞

这儿是cdq分治做的，另一种可询@The_Flash

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
/*************************************************************************
> File Name: l.cpp
> Author: ghost_lzw
> Mail: lanzongwei@gmail.com
> Created Time: Thu 30 Jan 2020 03:52:53 PM DST
************************************************************************/

#include<bits/stdc++.h>
using namespace std;

struct InputOutputStream {
enum { SIZE = 1000001 };
char ibuf[SIZE], *s, *t, obuf[SIZE], *oh;
bool eof;

InputOutputStream() : s(), t(), oh(obuf), eof(false) {}
~InputOutputStream() { fwrite(obuf, 1, oh - obuf, stdout); }

inline char read() {
if (s == t) t = (s = ibuf) + fread(ibuf, 1, SIZE, stdin);
return s == t ? -1 : *s++;
}

template <typename T>
inline InputOutputStream &operator>>(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) {eof = true; return *this;}
iosig |= c == '-';
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
if (iosig) x = -x;
return *this;
}

inline void print(char c) {
if (oh == obuf + SIZE) {
fwrite(obuf, 1, SIZE, stdout);
oh = obuf;
}
*oh++ = c;
}

template <typename T>
inline void print(T x) {
static int buf[23], cnt;
if (x != 0) {
if (x < 0) print('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
} else print('0');
}

template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}
} io;

const int Ma = 5e5 + 100;

struct Node{
int type, x, y;
int aim;
int* ans;
Node(int _t = 0, int _x = 0, int _y = 0, int _a = 0, int* _an = NULL) :
type(_t), x(_x), y(_y), aim(_a), ans(_an) {}
}node[Ma * 5];

int ans[Ma];
Node temp[Ma * 5];

namespace Tree{
const int Max = 100005;
int ssum[Max];
int lowbit(int x){return -x & x;}
void add(int pos, int val){
++pos;
while(pos < Max){
ssum[pos] += val;
pos += lowbit(pos);
}
}
void init(){
memset(ssum, 0, sizeof(ssum));
}
int sum(int pos){
++pos;
int Sum = 0;
while(pos){
Sum += ssum[pos];
pos -= lowbit(pos);
}
return Sum;
}
}

void cdq(int L, int R){
if(R - L <= 1)return ;
int mid = (L + R) >> 1;
cdq(L, mid), cdq(mid, R);
int l = L, r = mid, cnt = 0;
list<int>clean;
while(l < mid && r < R){
if(node[l].x <= node[r].x){
temp[cnt] = node[l++];
if(!temp[cnt].type)Tree::add(temp[cnt].y, 1), clean.push_back(cnt);
}else {
temp[cnt] = node[r++];
if(temp[cnt].type)*temp[cnt].ans += temp[cnt].aim * Tree::sum(temp[cnt].y);
}
cnt++;
}
while(l < mid)temp[cnt++] = node[l++];
while(r < R){
temp[cnt] = node[r++];
if(temp[cnt].type)*temp[cnt].ans += temp[cnt].aim * Tree::sum(temp[cnt].y);
cnt++;
}
list<int>::iterator it = clean.begin();
for(; it != clean.end(); it++)
Tree::add(temp[*it].y, -1);
for(int i = 0; i < cnt; i++)
node[L + i] = temp[i];
}

int main(){
int n, m;
io >> n >> m;
Tree::init();
for(int i = 0; i < n; i++)
node[i].type = 0, io >> node[i].x >> node[i].y;
int cnt = n;
for(int x, y, tx, ty, i = 0; i < m; i++){
ans[i] = 0;
io >> x >> y >> tx >> ty;
node[cnt++] = Node(1, x - 1, y - 1, 1, &ans[i]);
node[cnt++] = Node(1, tx, y - 1, -1, &ans[i]);
node[cnt++] = Node(1, x - 1, ty, -1, &ans[i]);
node[cnt++] = Node(1, tx, ty, 1, &ans[i]);
}
cdq(0, cnt);
for(int i = 0; i < m; i++)
io << ans[i] << '\n';

return 0;
}

M: CodeForces - 50A

tag: 思维水题

题意：让你用1 * 2的砖去铺n * m的地板

题解: n * m只要有两个格子有空闲就能塞下一个1 * 2，所以直接输出n * m / 2即可

1
2
n, m = map(int, input().split())
print(n * m // 2)

各位，补题，做自己不会的题，才能有效提升自身能力，慎记，慎记

有不明了之处，欢迎来讨论

Prev Home Next

sdnu2020WinterContest3rd题解报告

A: hud-1364

dp :

dfs:

B: CodeForces - 1242B

C: UVA - 12879

D: UVA - 806

E: CodeForces - 489C

F: POJ - 1364

G: CodeForces - 787D

H: UVA - 12118

I: CodeForces - 479C

J: UVA - 10410

K: HYSBZ - 1036

L: HYSBZ - 1935

M: CodeForces - 50A

Comments