Atcoder ABC 398

思路：

坐标动，人和原点不动

记录偏移量

dx

和

dy

。此时原点即为

（0 - dx, 0 - dy）

,人的坐标为

(r - dx, c - dy)

。

可用

map

或

set

记录是否存在。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n, r, c;
string s;
int main(){
	cin >> n >> r >> c >> s;
	int dx = 0, dy = 0; // 偏移 
	set< pair<int, int> >st;
	st.insert({0, 0});
	for(int i = 0; i < n; i++){
		if(s[i] == 'N') dx--;
		else if(s[i] == 'S') dx++;
		else if(s[i] == 'W') dy--;
		else dy++;
		if(!st.count({-dx, -dy})) st.insert({-dx, -dy});
		if(st.count({r - dx, c - dy})) cout << 1;
		else cout << 0;
	}
	return 0;
}

E - Tree Game

一道交互图

floyd

算法计算一下所有点之间距离；

如果任意两点的距离为奇数, 那么这两点之间就是偶数环.

记录偶数环的数量，如果奇数个，我方先手，否则对方先手。

输出一个消灭一个，直到输入

-1 \ -1

结束程序

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int d[N][N];
void floyd(){
	for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <=n; j++){
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}
int main(){
	memset(d, 0x3f, sizeof d);
	cin >> n;
	for(int i = 1; i <= n; i++) d[i][i] = 0;
	for(int i = 1; i < n; i++){
		int u,v;
		cin >> u >> v;
		d[u][v] = d[v][u] = 1;
	}
	floyd();
	set<pair<int, int>> ans;
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			if(d[i][j] > 1 && d[i][j] % 2) // 偶数环 
				ans.insert({i, j});
		}
	}
	if(ans.size() % 2){ // 则 "我”先手 
		cout << "First" << endl;
		auto x = *ans.begin();
		cout << x.first << ' ' << x.second << endl;
		ans.erase(ans.begin());
	}
	else cout << "Second" << endl;
	int x, y;
	while(1){
		cin >> x >> y;
		if(x == -1 && y == -1) break;
		if(x > y) swap(x, y);
		ans.erase({x, y}); // 存在则删除， 不存在则没有删除操作 
		auto x = *ans.begin();
		cout << x.first << ' ' << x.second << endl;
		ans.erase(ans.begin());
	}
	return 0;
}

F - ABCBA

给你一个字符串s，需要输出一个最短的回文串，要求回文串以s为前缀.

若将s翻转后得到字符串t，将t接在s的后面，显然就是一个回文。

比如说ABC

\rightarrow

ABCCBA，这是最短的以s为前缀的字符串。

但是形如ABCCC,翻转后拼接为ABCCCCCCBA,显然不是最短的，最短的为ABCCCBA,可以得出，需要求出最长的后缀回文。

寻找最长的后缀回文，可以用kmp，字符串哈希，马拉车等算法。

CPP

#include<bits/stdc++.h>
using namespace std;
const int B = 13;
const int mod = 1e9 + 7;
string s, r;
int ans, n;
long long h, t, p = 1;
int main(){
	cin >> s;
	r = s;
	reverse(r.begin(), r.end());
	n = r.size();
	for(int i = 0; i < n; i++){
		h = h + (r[i] - 'A' + 1) * p; h %= mod;
		t = t * B + (r[i] - 'A' + 1); t %= mod;
		p *= B; p %= mod;
		if(h == t) ans = i + 1;
	}
	cout << s;
	for(int i = ans; i < n; i++) cout << r[i];
	return 0;
}

文章操作

相关推荐

评论

Atcoder ABC 398