2020-12-06

2019 ACM-ICPC, Asia Shanghai Regional

字数统计: 2.8k字 | 阅读时长: 14分

solved	A	B	C	D	E	F	G	H	I	J	K	L	M
4 / 13	·	O	·	·	Ø	·	·	Ø	·	·	O	·	·

O：比赛时通过
Ø：赛后通过
!：比赛时尝试了未通过
·：比赛时未尝试

比赛题解

B - Prefix Code

Solved by all. 0:49(+1)

题意： 给你一堆数字，问你是否没有任何一个完整的数字是其他数字的前缀。

题解： 上来直接冲了发字典树，后来发现没有考虑类似于53 5的这种情况。于是sort了一下再进行插入操作。

AC代码

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define endl "\n"
#define _for(i, a, b) for(int i = (a); i <= (b); ++i)
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {	cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' '; err(args...);}

inline int rd () {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 7;
int ans = 0;

struct Trie{
	struct node{
		int nx[11];
		int cnt;
		void init() {
			memset(nx, -1, sizeof(nx));
			cnt = 0;
		}
	}t[maxn];
	
	int tot, root;
	int newnode() {
		++tot;
		t[tot].init();
		return tot;
	}
	void init() {
		tot = 0;
		root = newnode();
	}
	void insert(string s) {
		int len = s.size();
		int now = root;
		for (int i = 0 ; i < len; ++i) {
			int v = s[i] - '0';
			if (t[now].nx[v] == -1) t[now].nx[v] = newnode();
			now = t[now].nx[v];
			if (t[now].cnt) ans = -1;
		}
		t[now].cnt = 1;
	}
}trie;
int n, cas;
string s;
vector<string> G;
void run () {
	trie.init();
	G.clear();
	cin >> n;
	ans = 0;
	while(n--) {
		cin >> s;
		G.push_back(s);
	}
	sort(G.begin(), G.end());
	for (auto v : G) {
		trie.insert(v);
	}
	cout << "Case #" << ++cas << ": ";
//	printf("Case #%d: ", ++cas);
	if (ans == -1) cout << "No" << endl;
	else cout << "Yes" << endl;
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	int _T;
	cin >> _T;
	while (_T--) run();
    return 0;
}

E - Cave Escape【最大生成树】

solved by lllllan. (-)

题意： 在一个 $N * M$ 的图中，你需要从指定起点走到指定终点（但是到了终点仍然可以继续移动）。每当移动到一个为访问过的位置，将获得一个 $权值W = 该位置的权值V_{<X, Y>}*上一位置的权值V_{<x, y>}$ 。求最大能获得的权值和。

题解： 指定终点是可以忽略的，反正到达终点以后还能移动，最后计算的也是最多一共可以获得多少权值。转念一想指定起点也是可以忽略的，因为不要求输出路径，并且需要遍历全图，那就干脆从左上角第一个点出发遍历所有的点也是一样的。而路径的选择上便是“贪心”，从某个点出发的四条路，选择其中能获得的权值最大的边先行。然后就发现，其实就是一颗生成树了。虽然最后总的路径不一定是树，但是能够获得权值的路径一定是树。 所以就变成了一个求最大生成树的题目。

常规的最大生成树方法 由于这样的复杂度只是勉强能接受，所以在建边是千万不要重复【一模一样的代码交了五次TLE了一次，通过的运行时间为 $1638ms$ 】

AC代码

#include<bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); ++i)
inline int rd () {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 10;
int n, m, sx, sy, ex, ey;
int cnt, cas, a, b, c, p;
int v[maxn][maxn];
int s[maxn * maxn];
int x[maxn * maxn];
int dir[][2] = {{1, 0}, {0, 1}};

struct node { int x, y;};
struct edge {
    int u, v, w;
    friend bool operator<(const edge& A, const edge& B) { return A.w > B.w;}
} e[4 * maxn * maxn];
void addedge(int u, int v, int w) {cnt++, e[cnt].u = u, e[cnt].v = v, e[cnt].w = w;}
int find (int x) { return s[x] == x ? x : s[x] = find(s[x]);}

void Kruskal () {
    ll ans = 0;
    sort(e + 1, e + cnt + 1);
    _for(i, 1, n * m) s[i] = i;
    _for(i, 1, cnt) {
        int a = find(e[i].u), b = find(e[i].v);
        if (a == b) continue;
        s[b] = a;
        ans += (ll)e[i].w;
    }
    printf("Case #%d: %lld\n", ++cas, ans);
}

void run () {
	scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &ex, &ey);
	scanf("%d%d%d%d%d%d", x + 1, x + 2, &a, &b, &c, &p);
    cnt = 0;
    _for (i, 3, n * m) x[i] = (a * x[i - 1] + b * x[i - 2] + c) % p;
	_for (i, 1, n) _for (j, 1, m)  v[i][j] = x[(i - 1) * m + j];
	_for (i, 1, n) _for (j, 1, m) {
        _for (k, 0, 1) {
            int nx = i + dir[k][0];
            int ny = j + dir[k][1];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
                int u = (i - 1) * m + j;
                int to = (nx - 1) * m + ny;
                addedge(u, to, v[i][j] * v[nx][ny]);
            }
        }
    }
	Kruskal();
}

int main () {
	int _T = rd();
	while (_T--) run();
    return 0;
}

一点变形 运行时间 $666ms$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); ++i)
inline int rd () {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 10;
int n, m, sx, sy, ex, ey;
int cas, a, b, c, p;
int v[maxn][maxn];
int s[maxn * maxn];
int x[maxn * maxn];
vector<pair<int, int> > w[10010];
int find (int x) { return s[x] == x ? x : s[x] = find(s[x]);}

void run () {
	scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &ex, &ey);
	scanf("%d%d%d%d%d%d", x + 1, x + 2, &a, &b, &c, &p);
    _for(i, 1, 10000) w[i].clear();
    _for (i, 3, n * m) x[i] = (a * x[i - 1] + b * x[i - 2] + c) % p;
	_for (i, 1, n) _for (j, 1, m)  v[i][j] = x[(i - 1) * m + j];
	_for (i, 1, n) _for (j, 1, m) {
        if (!v[i][j]) continue;
        if (i < n && v[i + 1][j]) w[v[i][j] * v[i + 1][j]].push_back({(i - 1) * m + j, i * m + j});
        if (j < m && v[i][j + 1]) w[v[i][j] * v[i][j + 1]].push_back({(i - 1) * m + j, (i - 1) * m + j + 1});
    }
    ll ans = 0;
    int tot = 0;
    _for(i, 1, n * m) s[i] = i;
    for (int i = 10000; i >= 0; --i) {
        for (int j = 0; j < w[i].size(); ++j) {
            int u = find(w[i][j].first);
            int v = find(w[i][j].second);
            if (u == v) continue;
            tot++, ans += (ll)i;
            s[u] = v;
            if (tot == n * m - 1)break;
        }
        if (tot == n * m - 1)break;
    }
    printf("Case #%d: %lld\n", ++cas, ans);
}

int main () {
	int _T = rd();
	while (_T--) run();
    return 0;
}

H - Tree Partition

Solved by Sstee1XD. (-)

题意： 给你一棵树以及它的所有点权，问你把这棵树分成k份以后，最大值的最小值是多少。

题解： 想不到十分优秀的时间复杂度的算法来解决，所以我们考虑二分。二分出子树的最大值，每次贪心地去合并小的，直到合并不了了，那么剩下的子树都单独成树，最后出来再把份数+1。注意如果算出来的份数比要分的小也要记录答案，不然就过不了类似于 4 500 500 2 (2)这样子的分成三份的树的样例。

AC代码

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

#define endl "\n"
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err() { cout << endl; }
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' '; err(args...);
}
template <class T> inline void read(T &x) {
    int f = 0; x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    if (f) x = -x;
}
typedef long long ll;
const int maxn = 1e5 + 7;
const ll INF = 1e14;
int n, m, cas;
ll w[maxn], tw[maxn], tmp, ans;
vector<int>G[maxn];
void dfs(int u, int fa, ll mid) {
    priority_queue<ll, vector<ll>, greater<ll>> q;
    tw[u] = w[u];
    for (auto v : G[u]) {
        if (v == fa) continue;
        dfs(v, u, mid);
        q.push(tw[v]);
    }
    while (!q.empty()) {
        ll t = q.top();
        if (tw[u] + t > mid) break;
        q.pop();
        tw[u] += t;
    }
    tmp += q.size();
}
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        G[i].clear();
    }
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    ll l = 1, r = INF;
    for (int i =1; i <= n; ++i) cin >> w[i], l = max(l, w[i]);
    ans = l;
    ll mid;
    while (l <= r) {
        mid = l + r >> 1;
        tmp = 1;
        dfs(1, -1, mid);
        if (tmp <= m) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << "Case #" << ++cas << ": " << ans << endl;
    //printf("Case #%d: %lld\n", ++cas, ans);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    cin >> _T;
    while (_T--) solve();
}

/*
1
5 3
1 2
2 3
3 4
3 5
4 500 500 2 2
*/

K - Color Graph

solved by Sstee1XD & lllllan. 02:31(+1)

题意： 给定一个简单图，对边进行染色，要求不能出现所有边都被染色的奇环。求最多可以染多少条边。

题解： 如果不能有环，则为一棵树，可以有环但是不能有奇环，则为二分图。则将所有的点分成两个集合，不同集合之间的点的边可以进行染色。因为点最多只有16，即可暴力枚举点的情况，针对所有的情况去计算可以染色的边数，求最大值。

AC代码

#include<bits/stdc++.h>
using namespace std;
inline int rd () {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

typedef long long ll;
const int inf = 0x3f3f3f3f;
int n, m, tot, cor, cas, ans;
struct edge { int u, v;} e[130];

int solve () {
	int res = 0;
	for (int i = 0; i < m; ++i) {
		int u = e[i].u - 1;
		int v = e[i].v - 1;
		if (((cor >> u) & 1) == ((cor >> v) & 1)) continue;
		res++;
	}
	return res;
}

void run () {
	n = rd(), m = rd(); ans = 0;
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &e[i].u, &e[i].v);
	}
	tot = 1 << n;
	for (cor = 0; cor < tot; ++cor) {
		int tem = solve();
		ans = max(ans, tem);
	}
	printf("Case #%d: %d\n", ++cas, ans);
}

int main () {
	int _T = rd();
	while (_T--) run();
    return 0;
}