Kyooma's Blog

2022上海省赛

  • ~13.27K 字

题目来自: 2022 Shanghai Collegiate Programming Contest

A - Another A+B Problem

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
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>

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

vector<int> a, res, b;
vector<string> ans;
int ban[10], cnt[10];

void dfs(int u){
	if(u == 6){
		int ok = 1;
		vector<int> c(10);
		for(int i = 0; i < 6; i++){
			if(b[i] == 1) continue;
			c[res[i]]++;
			if(res[i] == a[i]) ok = 0;
		}
		for(int i = 0; i < 10; i++){
			if(ban[i] && cnt[i] != c[i]) ok = 0;
			if(!ban[i] && c[i] < cnt[i]) ok = 0;
		}
		int d1 = res[0] * 10 + res[1];
		int d2 = res[2] * 10 + res[3];
		int d3 = res[4] * 10 + res[5];
		if(d1 + d2 != d3) ok = 0;
		if(ok){
			string r;
			for(int i : res){
				r += char('0' + i);
				if(r.size() == 2) r += "+";
				if(r.size() == 5) r += "=";
			}
			ans.push_back(r);
		}
		return;
	}
	if(b[u] == 1){
		res.push_back(a[u]);
		dfs(u + 1);
		res.pop_back();
		return;
	}
	for(int i = 0; i <= 9; i++){
		res.push_back(i);
		dfs(u + 1);
		res.pop_back();
	}
}

void solve(){
	string e, s;
	cin >> e >> s;
	for(int i = 0, x; i < e.size(); i++){
		if(e[i] >= '0' && e[i] <= '9'){
			a.push_back(e[i] - '0');
			if(s[i] == 'B') x = 0;
			else if(s[i] == 'G') x = 1;
			else x = 2;
			b.push_back(x);
			if(!x) ban[e[i] - '0'] = 1;
			if(x == 2) cnt[e[i] - '0']++;
		}
	}
	dfs(0);
	cout << ans.size() << '\n';
	for(string r : ans) cout << r << '\n';
}

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

B - Bracket Query

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
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
#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;

struct DSU{
    int fa[N], val[N];// val 表示i到i所在连通块的根节点的势能, 根节点势能为0
    void init(int n){
        for(int i=1;i<=n;i++) fa[i] = i, val[i] = 0;
    }
    int find(int x){
        if(x == fa[x]) return x;
        int fx = find(fa[x]);
        val[x] += val[fa[x]];
        fa[x] = fx;
        return fx;
    }
};

struct Edge{
    int v, w;
};

vector<Edge> e[N];
int dist[N];

bool Bellman_Ford(int n) {
    dist[n] = dist[0] = 0;
    dist[1] = 1;
    for (int i = 0; i < n; i++) {
        bool jud = false;
        for (int u = 0; u <= n; u++){
            for(auto [v, w] : e[u]){
                if(dist[v] > dist[u] + w){
                    dist[v] = dist[u] + w;
                    jud = true;
                }
            }
        }
        if (!jud) break;
    }
    for (int u = 0; u <= n; u++){
            for(auto [v, w] : e[u]){
                if(dist[v] > dist[u] + w){
                    return false;
                }
            }
        }
    return true;
}

void solve() {
    int n, q;
    cin >> n >> q;
    DSU dsu{};
    for(int i = 0; i <= n; i++){
        dist[i] = inf;
    }
    dsu.init(n);
    for(int i = 0, u, v, w; i < q; i++){
        cin >> u >> v >> w;
        u--;
        if(((v - u) ^ abs(w)) & 1){
            cout << "?\n";
            return;
        }
        int fu = dsu.find(u), fv = dsu.find(v);
        if(fu != fv){
            dsu.val[fv] = dsu.val[u] - w - dsu.val[v];
            dsu.fa[fv] = fu;
            e[u].push_back({v, w});
            e[v].push_back({u, -w});
            // v - u = w
            // v - u <= w  ->  v <= u + w
            // v - u >= w  ->  u <= v - w
        }else if(dsu.val[u] - dsu.val[v] != w) {
            cout << "?\n";
            return;
        }
    }
    for(int i = 1; i <= n; i++){
        e[i - 1].push_back({i, 1});
        e[i].push_back({i - 1, 1});
    }
    bool ok = Bellman_Ford(n);
    if(dist[n] || dist[0] || dist[1] != 1) ok = false;
    for(int i = 1; i <= n; i++){
        if(dist[i] < 0) ok = false;
    }
    if(!ok){
        cout << "?\n";
        return;
    }
    // for(int i = 0; i <= n; i++) cout << dist[i] << ' ';cout << '\n';
    cout << "! ";
    for(int i = 1; i <= n; i++){
        int p = dist[i] - dist[i - 1];
        if(p == 1) cout << "(";
        else cout << ")";
    }
}

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

J - Just Some Bad Memory

SOLUTION

tarjan 分类讨论，判断是否为仙人掌树。

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
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;
typedef long long ll;
const int N = 1e5 + 10;

/*
n小于4 -> -1
只需要建5条边 -> 5 - min(m, 2)
对于一个连通块:
判断仙人掌 -> 否 -> 必有偶环 -> 01染色 -> 否 -> 有奇环 -> 0
         |                         |
         |                         -> 是 -> 无奇环 -> 1
         -> 是 -> 判断仙人掌的环 -> 有奇有偶 -> 0
                              |
                              -> 全奇 -> 有大于3的环 -> 1
                              |      |
                              |      -> 只有长3的环 -> 判断该环有无额外连着的环外的点 -> 有 -> 1
                              |                                                |
                              |                                                -> 无 -> 2
                              -> 无环 -> 个数大于3 -> 2
                              |
                              -> 全偶 -> 1

对于多个连通块:
若别的连通块有奇环 -> 当前有偶环 -> 0
                |
                -> 当前有长为4的链 -> 1
反之同理
 */

vector<int> e[N];
int dfn[N], dep[N], fa[N], low[N], tot;
int du[N], is_cactus = true, odd = -1, even = -1, ok;
int vis[N], ao = -1, ae = -1;
vector<int> cc;

void DP(int rt, int v){
    int num = dep[v] - dep[rt] + 1;
    if(num & 1){
        odd = max(odd, num);
    }else{
        even = max(even, num);
    }
    for(int i = v; i != rt; i = fa[i]){
        du[i]++;
        if(du[i] > 1){
            is_cactus = false;
            return;
        }
    }
}

void tarjan(int x){
    dfn[x] = low[x] = ++tot;
    cc.push_back(x);
    for(int v : e[x]){
        if(v == fa[x]) continue;
        if(!dfn[v]){
            fa[v] = x;
            dep[v] = dep[x] + 1;
            tarjan(v);
            low[x] = min(low[x], low[v]);
        }else{
            low[x] = min(low[x], dfn[v]);
        }
    }
    if(!is_cactus) return;
    for(int v : e[x]){
        if(fa[v] != x && dfn[x] < dfn[v]) DP(x, v);
    }
}

void dfs(int u, int f){
    if(!ok) return;
    if(vis[u]){
        if(vis[u] != f) ok = 0;
        return;
    }
    vis[u] = f;
    for(int i : e[u]){
        dfs(i, f ^ 1);
    }
}

int dp[N];

void dfs1(int u, int f){
    dp[u] = dp[f] + 1;
    for(int i : e[u]){
        if(i == f) continue;
        dfs1(i, u);
    }
}

void solve(){
    int n, m;
    cin >> n >> m;
    if(n < 4){
        cout << "-1\n";
        return;
    }
    for(int i = 0, u, v; i < m; i++){
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int ans = 5 - min(m, 2);
    for(int i = 1; i <= n; i++){
        if(!dfn[i]){
            tot = 0;
            odd = even = -1;
            is_cactus = true;
            tarjan(i);
            ao = max(ao, odd);
            ae = max(ae, even);
        }
    }
    if(ao != -1 && ae != -1) ans = min(ans, 0);
    for(int i = 1; i <= n; i++) dfn[i] = low[i] = du[i] = fa[i] = 0;
    for(int i = 1; i <= n; i++){
        if(!dfn[i]){
            tot = 0;
            odd = even = -1;
            is_cactus = true;
            cc.clear();
            tarjan(i);
            if(is_cactus){
                if(odd != -1 && even != -1) ans = min(ans, 0);
                else if(even != -1) ans = min(ans, 1);
                else if(odd != -1){
                    if(odd > 3 || tot > 3){
                        ans = min(ans, 1);
                    }else{
                        ans = min(ans, 2);
                    }
                }else if(tot > 3){ // 是一棵树
                    ans = min(ans, 2);
                    if(ao != -1){
                        dfs1(i, 0);
                        int root = i;
                        for(int j : cc){
                            if(dp[j] > dp[root]) root = j;
                        }
                        dfs1(root, 0);
                        for(int j : cc){
                            if(dp[j] > 3){
                                ans = min(ans, 1);
                                break;
                            }
                        }
                    }
                }
            }else{
                ok = 1;
                dfs(i, 2);
                if(ok) ans = min(ans, 1);
                else ans = min(ans, 0);
            }
            if(ae != -1 && tot >= 3) ans = min(ans, 1);
        }
    }
    cout << ans << '\n';
}

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

L - Last Warning of the Competition Finance Officer

SOLUTION

注意到不同长度只有$\sqrt{n}$种，直接暴力哈希，建图之后dp即可。

当然用ac自动机的话复杂度会更加优秀。

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

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

const int N=2e5+10, p = 998244353;
const pii base = {131, 251}, mod = {1e9 + 7, 1e9 + 9};

pll pw[N];
pll operator*(const pll &p1, const pll &p2){
	return {p1.first * p2.first % mod.first, p1.second * p2.second % mod.second};
}

pll operator+(const pll &p1, const pll &p2){
	return {(p1.first + p2.first) % mod.first, (p1.second + p2.second) % mod.second};
}

pll operator-(const pll &p1, const pll &p2){
	return {(p1.first - p2.first + mod.first) % mod.first, (p1.second - p2.second + mod.second) % mod.second};
}

struct Hash{
	vector<pll> f;
	int n{};
	void init(int ss[], int _n){
		n = _n;
		f.resize(n + 1, {0, 0});
		for(int i = 1; i <= n; i++){
			ll ch = ss[i];
			f[i] = f[i - 1] * base + pll{ch, ch};
		}
	}
	
	pll ask(int l, int r){
		return f[r] - f[l - 1] * pw[r - l + 1];
	}
};

int a[N], dp[N];
map<pll, int> mp;

struct Edge{
	int v, w;
};

vector<Edge> e[N];

void solve(){
	string s;
	int n, len;
	cin >> s >> n;
	len = s.size();
	for(int i = 1; i <= s.size(); i++){
		a[i] = s[i - 1] - 'a' + 1;
	}
	Hash h{};
	h.init(a, s.size());
	set<int> st;
	for(int i = 0, x; i < n; i++){
		string t;
		cin >> t >> x;
		pll res = {0, 0};
		for(char j : t){
			res = res * base + pll{j - 'a' + 1, j - 'a' + 1};
		}
		mp[res] = x;
		st.insert(t.size());
	}
	for(int m : st){
		for(int i = 1; i <= len - m + 1; i++){
			pll res = h.ask(i, i + m - 1);
			if(mp.count(res)){
				e[i + m - 1].push_back({i, mp[res]});
			}
		}
	}
	dp[0] = 1;
	for(int i = 1; i <= len; i++){
		dp[i] = dp[i - 1];
		for(Edge j : e[i]){
			int v = j.v, w = j.w;
			dp[i] += 1ll * dp[v - 1] * w % p;
			if(dp[i] >= p) dp[i] -= p;
		}
		cout << dp[i] << ' ';
	}
}

int main(){
	int T = 1;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	pw[0] = {1, 1};
	for(int i = 1; i <= N - 1; i++) pw[i] = pw[i - 1] * base;
//	cin>>T;
	
	while(T--) solve();
	return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可