ABC320

发布时间 2023-09-16 23:52:38作者: V_Melville

T1:Leyland Number

模拟

代码实现
a, b = map(int, input().split())
print(a**b+b**a)

T2:Longest Palindrome

模拟

代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

bool isPalindrome(string s) {
    string t = s;
    reverse(t.begin(), t.end());
    return s == t;
}

int main() {
    string s;
    cin >> s;
    int n = s.size();
    
    int ans = 0;
    rep(r, n)rep(l, r+1) {
        string ns = s.substr(l, r-l+1);
        if (isPalindrome(ns)) ans = max(ans, r-l+1);
    }
    
    cout << ans << '\n';
	
	return 0;
}

T3:Slot Strategy 2 (Easy)

暴搜这 \(3\) 个转盘停止旋转的时间

代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
	int m;
	cin >> m;
	
	vector<string> s(3);
	rep(i, 3) cin >> s[i];
	
	const int INF = 1001001001;
	int ans = INF;
	rep(t0, 300)rep(t1, 300)rep(t2, 300) {
	    if (t0 == t1) continue;
	    if (t0 == t2) continue;
	    if (t1 == t2) continue;
	    if (s[0][t0%m] != s[1][t1%m]) continue;
	    if (s[0][t0%m] != s[2][t2%m]) continue;
	    ans = min(ans, max({t0, t1, t2}));
	}
	
	if (ans == INF) ans = -1;
	cout << ans << '\n';
	
	return 0;
}

或者暴搜这 \(3\) 个转盘停止旋转的顺序以及以哪个数停止

代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
	int m;
	cin >> m;
	
	vector<string> s(3);
	rep(i, 3) cin >> s[i];
	
	const int INF = 1001001001;
	int ans = INF;
	vector<int> p = {0, 1, 2};
	rep(d, 10) {
	    char c = '0'+d;
    	do {
    	    int t = -1;
    	    rep(i, 3) {
    	        t++;
    	        while (t < 300 and s[p[i]][t%m] != c) t++;
    	    }
    	    if (t < 300) ans = min(ans, t);
    	} while (next_permutation(p.begin(), p.end()));
	}
	
	if (ans == INF) ans = -1;
	cout << ans << '\n';
	
	return 0;
}

T4:Relative Position

显然我们只需得知点 \(1\) 所在的连通分量中的点的位置
注意原图可能有环,所以不能跑拓扑排序
这里我们可以用 \(\operatorname{dfs}\)\(\operatorname{bfs}\) 解决
注意需要存无向边,因为从点 \(1\) 出发不一定能走到属于同一个连通分量中的某个点

代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

struct Edge {
    int to, x, y;
    Edge(int to=-1, int x=0, int y=0): to(to), x(x), y(y) {} 
};

int main() {
	int n, m;
	cin >> n >> m;
	
	vector<vector<Edge>> g(n);
	rep(i, m) {
	    int a, b, x, y;
	    cin >> a >> b >> x >> y;
	    --a; --b;
	    g[a].emplace_back(b, x, y);
	    g[b].emplace_back(a, -x, -y);
	}
	
	const ll INF = 1e18;
	vector<ll> x(n, INF), y(n, INF);
	x[0] = y[0] = 0;
	queue<int> q;
	q.push(0);
	while (q.size()) {
	    int v = q.front(); q.pop();
	    for (auto [u, dx, dy] : g[v]) {
	        if (x[u] != INF) continue;
	        x[u] = x[v]+dx;
	        y[u] = y[v]+dy;
	        q.push(u);
	    }
	}
	
	rep(i, n) {
	    if (x[i] == INF) puts("undecidable");
	    else cout << x[i] << ' ' << y[i] << '\n';
	}
	
	return 0;
}