Kyooma's Blog

2022-09-24周赛

  • ~20.03K 字

题目来自: 2019-2020 ICPC Southwestern European Regional Programming Contest (SWERC 2019-20)

B - Biodiversity

签到, 问是否存在一个出现了一半次数的字符串

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

void solve(){
	int n;
	cin >> n;
	map<string, int> mp;
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		mp[s]++;
	}
	for(auto i : mp){
		if(i.second > n - i.second){
			cout << i.first << '\n';
			return;
		}
	}
	cout << "NONE\n";
}

int main(){
	int T = 1;
	ios::sync_with_stdio(false);
	while(T--) solve();
	return 0;
}

I - Rats

签到, 抄一下柿子就行

CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

void solve(){
	int a, b, c;
	cin >> a >> b >> c;
	int ans = (a + 1) * (b + 1) / (c + 1) - 1;
	cout << ans << '\n';
}

int main(){
	int T = 1;
	ios::sync_with_stdio(false);
	while(T--) solve();
	return 0;
}

C - Ants

签到, 给一堆长度小于$100$位的数(可以有负数), 问最小的未出现的自然数是啥

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 10;

int v[N];

void solve(){
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		if(s[0] == '-' || s.size() > 7) continue;
		int res = 0;
		for(char j : s){
			res = res * 10 + j - '0';
		}
		if(res > 1e6) continue;
		v[res] = 1;
	}
	for(int i = 0; i <= N - 10; i++){
		if(!v[i]){
			cout << i << '\n';
			return;
		}
	}
}

int main(){
	int T = 1;
	ios::sync_with_stdio(false);
	while(T--) solve();
	return 0;
}

F - Icebergs

签到, 给若干个不重叠的多边形, 求总面积

SOLUTION

叉乘一下就行

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
44
45
46
47
48
49
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 10;

struct P{
	double x, y;
	double operator ^ (const P &b) const{
		return x * b.y - y * b.x;
	}
};

vector<P> p;

double getarea(){
	double sum = 0;
	int n = (int)p.size();
	for(int i = 0; i < n; i++){
		sum += (p[i] ^ p[(i + 1) % n]);
	}
	return fabs(sum) / 2;
}


void solve(){
	int n;
	scanf("%d", &n);
	double ans = 0;
	for(int i = 0, m; i < n; i++){
		scanf("%d", &m);
		p.clear();
		for(int j = 0; j < m; j++){
			int x, y;
			scanf("%d%d", &x, &y);
			p.push_back({x, y});
		}
		ans += getarea();
	}
	ll res = ans;
	printf("%lld\n", res);
}

int main(){
	int T = 1;
	while(T--) solve();
	return 0;
}

A - Environment-Friendly Travel

给出起点$s$和终点$d$, 以及最多行驶里程$B(\le 200)$, 又给出了$n(\le 1000)$个站点的图以及每条边的$CO_2$花费量(即$C_i$), 初始你在起点能开车前往任意一个点, 但是花费量是$C_0(C_0 > C_i)$. 定义$dist(a, b) = \lceil \sqrt{(x_a - x_b) ^ 2 + (y_a - y_b) ^ 2}\rceil$, $cost(a, b, i) = C_i \times dist(a, b)$, 求到达终点且满足里程小于等于$B$时最小的$cost$

SOLUTION

注意到$B$只有$200$, 可以考虑用$dis[i][j]$ 表示到达$i$点且行驶了$j$里程时的最小$cost$.

所以用最短路的方式转移即可.

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
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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e3 + 10, inf = 0x3f3f3f3f;

struct P{
	int x, y;
};

int calc(P x, P y){
	int r = (x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y);
	int s = sqrt(r);
	if(s * s != r) s++;
	return s;
}

P s, t, p[N];
int B, c[N], dist[N], co2[N], n;
vector<pii> e[N];

int dp[N][N];
int vis[N][N];
struct node{
	int id, dis;
	int cost;
	bool operator < (const node &k)const{
		return cost > k.cost; 
	}
};

void solve(){
	cin >> s.x >> s.y;
	cin >> t.x >> t.y;
	cin >> B;
	cin >> c[0];
	int T;
	cin >> T;
	for(int i = 1; i <= T; i++) cin >> c[i];
	cin >> n;
	for(int i = 0, l; i < n; i++){
		cin >> p[i].x >> p[i].y;
		cin >> l;
		for(int j = 0, to, ci; j < l; j++){
			cin >> to >> ci;
			e[i].push_back({to, ci});
			e[to].push_back({i, ci});
		}
	}
    priority_queue<node> q;
	for(int i = 0; i < n; i++){
        for(int j = 0; j <= B; j++){
            dp[i][j] = inf;
        }
        int dis = calc(p[i], s);
        if(dis > B) continue;
        dp[i][dis] = dis * c[0];
        q.push({i, dis, dp[i][dis]});
    }
    while(!q.empty()){
        auto [u, dis, cost] = q.top();
        q.pop();
        if(vis[u][dis]) continue;
        vis[u][dis] = 1;
        for(auto[v, ci] : e[u]){
            int dv = calc(p[u], p[v]), disv = dis + dv;
            if(disv > B) continue;
            int costv = cost + dv * c[ci];
            if(dp[v][disv] > costv){
                dp[v][disv] = costv;
                q.push({v, disv, costv});
            }
        }
    }
    int ans = calc(s, t) * c[0];
    if(calc(s, t) > B) ans = -1;
    for(int i = 0; i < n; i++){
        int d = calc(p[i], t);
        for(int j = 0; j <= B - d; j++){
            ans = min(dp[i][j] + d * c[0], ans);
        }
    }
    cout << ans << '\n';
}

int main(){
	int T = 1;
	ios::sync_with_stdio(false);
	while(T--) solve();
	return 0;
}

K - Birdwatching

给一张$n$点$m$边的有向图和一个点$T$, 问满足从$T’$走到$T$的所有路径中，一定包含$T’ → T$这条边的点$T’$有哪些

SOLUTION

首先$T’$必须有一条连向$T$的边, 又因为题目要求的是所有路径, 所以从$T’$出发不存在第二条到$T$点的路径

如果把原图的边全都反向, 那么如果这个点被两个与$T$直连的点到达了, 这个点就不是答案中的点, 所以可以对这张反向图进行$BFS$, 顺便标记一下即可(感觉有点瞎搞)

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10;

vector<int> e[N];
int ok[N], v[N];

void solve(){
	int n, m, t;
	cin >> n >> m >> t;
	for(int i = 0, u, v; i < m; i++){
		cin >> u >> v;
		e[v].push_back(u);
	}
	for(int i = 0; i < n; i++) ok[i] = 1, v[i] = -1;
	queue<int> q;
	q.push(t);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int i : e[u]){
			if(u == t){
				v[i] = i;
				q.push(i);
			}else if(ok[u]){
				if(v[i] == -1){
					v[i] = v[u];
					q.push(i);
				}else if(v[i] != v[u]){
					ok[i] = 0;
					q.push(i);
				}
			}else{
				if(v[i] == -1 || ok[i]){
					ok[i] = 0;
					q.push(i);
					v[i] = n;
				}
			}
		}
	}
	vector<int> ans;
	for(int i : e[t]){
		if(ok[i] && v[i] == i) ans.push_back(i);
	}
	cout << ans.size() << '\n';
	sort(ans.begin(), ans.end());
	for(int i : ans){
		cout << i << '\n';
	}
	
}

int main(){
	int T = 1;
	ios::sync_with_stdio(false);
	while(T--) solve();
	return 0;
}

G - Swapping Places

给出$S(S \le 200)$种字符串, $L(L \le 10000)$种关系, 长度$N(\le 100000)$的字符串序列, 若两种字符串存在关系且在序列中位置相邻, 那么就可以交换它们的位置, 求可以得到的字典序最小的序列.

SOLUTION

考虑两种没有关系的字符串, 它们不可能通过这种交换来做到交换它们两个的先后顺序, 也就是说, 对于两种没有关系的字符串, 它们的先后顺序是固定的.

那么, 可以对原序列中所有没有关系的字符串建一张图, 在这张图上跑出一个字典序最小的拓扑序就是答案了.

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10, M = 500 + 10;

int e[M][M];
int a[N], la[N], d[N];
vector<int> edge[N];
string id[M];

void solve(){
	int s, l, n, tot = 0;
	cin >> s >> l >> n;
	map<string, int> mp;
	for(int i = 0; i < s; i++){
		string t;
		cin >> t;
		mp[t]++;
	}
	for(auto &i : mp){
		i.second = ++tot;
		id[tot] = i.first;
	}
	for(int i = 0, u, v; i < l; i++){
		string s1, t;
		cin >> s1 >> t;
		u = mp[s1];
		v = mp[t];
		e[u][v] = e[v][u] = 1;
	}
	for(int i = 1; i <= n; i++){
		string t;
		cin >> t;
		a[i] = mp[t];
		for(int j = 1; j <= s; j++){
            if(e[a[i]][j] || !la[j]) continue;
            edge[la[j]].push_back(i);
            d[i]++;
        }
        la[a[i]] = i;
	}
    priority_queue<pii, vector<pii>, greater<pii>> q;
    for(int i = 1; i <= n; i++){
        if(!d[i]) q.push({a[i], i});
    }
    while(!q.empty()){
        int u = q.top().second;
        q.pop();
        cout << id[a[u]] << ' ';
        for(int i : edge[u]){
            d[i]--;
            if(!d[i]) q.push({a[i], i});
        }
    }
}

int main(){
	int T = 1;
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	while(T--) solve();
	return 0;
}

D - Gnalcats

有一个无限长的简单元素序列, 以及若干个操作($X$表示后续无限个元素):

  1. $C$ : 复制第一个元素 即 $a−X → a-a-X$
  2. $D$ : 删除第一个元素 即 $a−X → X$
  3. $L$ : 将第一个元素变成复合它的左元素, 若第一个不是复合元素则失败并停止后续所有操作 即 $(a, b)-X → a-X$
  4. $P$ : 将第一个元素作为左元素和第二个元素作为右元素复合为一个新元素 即 $a-b-X→(a,b)-X$
  5. $R$ : 将第一个元素变成复合它的右元素, 若第一个不是复合元素则失败并停止后续所有操作 即 $(a,b)-X→b-X$
  6. $S$ : 改变第一个元素和第二个元素的顺序 即 $a-b-X→b-a-X$
  7. $U$ : 将第一个元素变成复合它的两个元素, 若第一个不是复合元素则失败并停止后续所有操作 即 $(a,b)-X→a-b-X$

给出两个操作序列, 问这两个操作序列生成的最后的元素序列是否相同

SOLUTION

直接用一个类似栈的东西模拟操作

要注意的是, 虽然复合操作最后会连出一个二叉树, 但是最后判断两个序列相同时不能用直接递归整棵树的方式, 否则会$TLE$.

可以对复合操作进行$Hash$存储(CODE1的做法), 但是后来想了想发现可以直接用map 来存每个元素, 比一开始的做法简单了很多

CODE1
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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
const int base = 114514, mod = 1e9 + 9;

int f[N][2], tot, n = 1e4, vi[N];
string s;

int run(){
    vector<int> v, fi;
    tot = 0;
    ll res = 0;
    for(int i = 1; i <= 10000; i++){
        f[i][0] = f[i][1] = -1;
        v.push_back(++tot);
        vi[tot] = tot;
        res = (res * base % mod + vi[tot]) % mod;
        fi.push_back(res);
    }
    for(char i : s){
        if(i == 'C'){
            int p = v.back();
            res = fi.back();
            res = (res * base % mod + vi[p]) % mod;
            v.push_back(p);
            fi.push_back(res);
        }else if(i == 'D'){
            v.pop_back();
            fi.pop_back();
        }else if(i == 'P'){
            int p = v.back();
            v.pop_back();
            fi.pop_back();
            int q = v.back();
            fi.pop_back();
            v.pop_back();
            tot++;
            f[tot][0] = p;
            f[tot][1] = q;
            vi[tot] = (vi[p] * base % mod + vi[q]) % mod;
            res = fi.back();
            res = (res * base % mod + vi[tot]) % mod;
            fi.push_back(res);
            v.push_back(tot);
        }else if(i == 'L'){
            int p = v.back();
            if(p <= n){
                return -1;
            }
            v.pop_back();
            fi.pop_back();
            v.push_back(f[p][0]);
            res = fi.back();
            res = (res * base % mod + vi[f[p][0]]) % mod;
            fi.push_back(res);
        }else if(i == 'R'){
            int p = v.back();
            if(p <= n){
                return -1;
            }
            v.pop_back();
            v.push_back(f[p][1]);
            fi.pop_back();
            res = fi.back();
            res = (res * base % mod + vi[f[p][1]]) % mod;
            fi.push_back(res);
        }else if(i == 'S'){
            int p = v.back();
            v.pop_back();
            int q = v.back();
            v.pop_back();
            v.push_back(p);
            v.push_back(q);
            fi.pop_back();
            fi.pop_back();
            res = fi.back();
            res = (res * base % mod + vi[p]) % mod;
            fi.push_back(res);
            res = (res * base % mod + vi[q]) % mod;
            fi.push_back(res);
        }else{
            int p = v.back();
            if(p <= n){
                return -1;
            }
            v.pop_back();
            v.push_back(f[p][1]);
            v.push_back(f[p][0]);
            fi.pop_back();
            res = fi.back();
            res = (res * base % mod + vi[f[p][1]]) % mod;
            fi.push_back(res);
            res = (res * base % mod + vi[f[p][0]]) % mod;
            fi.push_back(res);
        }
    }
    return fi.back();
}


void solve() {
    cin >> s;
    int v1 = run();
    cin >> s;
    int v2 = run();
    if(v1 == v2) cout << "True\n";
    else cout << "False\n";
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    // cin >> T;
    while (T--) solve();
    return 0;
}
CODE2
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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10, Log = 20, inf = 0x3f3f3f3f;

map<pii, int> mp;
vector<int> v;
string s;
int n, f[N][2];
int pop(){
    int p = v.back();
    v.pop_back();
    return p;
}

void push(int x){
    v.push_back(x);
}

int merge(int x, int y){
    if(mp.count({x, y})) return mp[{x, y}];
    mp[{x, y}] = ++n;
    f[n][0] = x;
    f[n][1] = y;
    return n;
}

vector<int> run(){
    v.clear();
    for(int i = 0; i < 10000; i++){
        int p = merge(i, -1);
        v.push_back(p);
        f[p][0] = f[p][1] = -1;
    }
    for(char i : s){
        if(i == 'C'){
            int x = pop();
            push(x);
            push(x);
        }else if(i == 'D'){
            int x = pop();
        }else if(i == 'L'){
            int x = pop();
            if(f[x][0] == -1){
                return {-1};
            }
            push(f[x][0]);
        }else if(i == 'P'){
            int x = pop(), y = pop();
            push(merge(x, y));
        }else if(i == 'R'){
            int x = pop();
            if(f[x][0] == -1){
                return {-1};
            }
            push(f[x][1]);
        }else if(i == 'S'){
            int x = pop(), y = pop();
            push(x);push(y);
        }else{
            int x = pop();
            if(f[x][0] == -1){
                return {-1};
            }
            push(f[x][1]);
            push(f[x][0]);
        }
    }
    return v;
}

void solve() {
    cin >> s;
    vector<int> v1 = run();
    cin >> s;
    vector<int> v2 = run();
    if(v1 == v2) cout << "True\n";
    else cout << "False\n";
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    while (T--) solve();
    return 0;
}

H - Pseudo-Random Number Generator

题目给出了一个奇怪的序列生成器, 问这个序列的前$n(0\le n \le 2^{63}-1 )$项里有多少个偶数

$M = 2^{40}$

$S(0)=0x600DCAFE$

$S(n+1)=(S(n)+(S(n-1) >> 20) + 12345)\%M$

SOLUTION

因为有取模, 所以一定会存在环(循环节), 先跑了遍$Floyd$判环发现环的长度为$182129209$, 起点到环的距离是$350125310$, 因为时限只有$300ms$, 所以直接暴力跑肯定是不行的, 那么可以采用分块打表的方式, 在本地先暴力跑出每一块的答案, 然后就可以用$O(块长)$的复杂度算出答案了. 我这里选择的块长是$3\times 10^7$

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
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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll mod = 1099511627776;

ll calc(ll x){
    return (x + (x >> 20) + 12345) % mod;
}

void Floyd_Cycle_Detection_Algorithm(){
    ll p1 = 1611516670, p2 = 1611516670; // 起始点
    do{
        p1 = calc(p1); // 移动一次
        p2 = calc(calc(p2)); // 移动两次
    }while(p1 != p2);
    // 存在环
    ll len = 0;// 环长
    do{
        p2 = calc(p2);
        len++;
    }while(p1 != p2);
    p1 = 1611516670;// 寻找环起点
    ll c1 = 0;
    while(p1 != p2){
        p1 = calc(p1);
        p2 = calc(p2);
        c1++;
    }
    cout << p1 << ' ' << len << ' ' << c1 << '\n';
}

pll ans0[12] = {{1, 1611516670},
                {15011683, 83248007737},
                {30040232, 622741727028},
                {45056959, 35943646365},
                {60057168, 310147760736},
                {75074286, 11901289737},
                {90060817, 151258698876},
                {105080524, 1072246754882},
                {120091493, 70512631458},
                {135114812, 538598461112},
                {150119937, 29466792348},
                {165108248, 267368060404}};
pll ans_loop[7] = {{1, 516914},
                   {14984747, 72602179030},
                   {29971111, 552368730897},
                   {44967154, 30528085091},
                   {59985791, 274358548202},
                   {74980113, 9149398605},
                   {89965024, 133077482701}};


void init() {// 打表部分
//    Floyd_Cycle_Detection_Algorithm();
    // 环长182129209 起点到环350125310 516914  175147925
//    ll s = 1611516670, cnt = 0;
//    for(int i = 0; i < 350125310; i++){
//        if(~s&1) cnt++;
//        if(i % 30000000 == 0){
//            cout << cnt << ", " << s << '\n';
//        }
//        s = calc(s);
//    }
//    if(~s&1) cnt++;
//    cout << s << ' ' << cnt;
    ll s = 516914, cnt = 0;
    for(int i = 0; i < 182129209; i++){
        if(~s&1) cnt++;
        if(i % 30000000 == 0){
            cout << cnt << ", " << s << '\n';
        }
        s = calc(s);
    }
    cout << s << ' ' << cnt;
}

void solve(){
    ll n;
    cin >> n;
    if(!n){
        cout << "0\n";
        return;
    }
    n--;
    if(n < 350125310){
        ll p = n / 30000000, q = n % 30000000, ans = ans0[p].first;
        ll s = ans0[p].second;
        for(int i = 0; i < q; i++){
            s = calc(s);
            if(~s&1) ans++;
        }
        cout << ans << '\n';
        return;
    }
    n -= 350125310;
    ll ans = 175147925, loop = 91029304;;
    ans += loop * (n / 182129209);
    n %= 182129209;
    ll p = n / 30000000, q = n % 30000000;
    ans += ans_loop[p].first;
    ll s = ans_loop[p].second;
    for(int i = 0; i < q; i++){
        s = calc(s);
        if(~s&1) ans++;
    }
    cout << ans << '\n';
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    // cin >> T;
//    init();
    while (T--) solve();
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可