比赛题目训练系列07 (2019 China Collegiate Programming Contest Qinhuangdao Onsite)
A. Angle Beats
- 给定一个点，问有多少条点对，可以与这个点构成一个直角三角形。
- 思路很简单，就是非常卡时间。我们分为 A i A_i Ai 是否作为直角边分类讨论。把所有的边存在哈希表中，然后查找。
- 省时间策略:
- 不用map，用unordered_map
- unordered_map里面不要存pair，更不要存三元组，存一维的元素，省空间省时间。具体hash的办法很简单，就是 x * hash_num + y 即可。
- 把线段方向保存为向量(dx, dy)，而不是保存倾斜角，防止浮点数误差。dx, dy 都除以最大公约数，用这种方式把它们都标准化。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
using namespace std;
#define x first
#define y second
typedef long long ll;
const int maxn = 2010;
const ll hash_num = 3e9 + 9;
typedef pair<int, int> P;
ll Hash(const P& p) {
return hash_num * (ll)p.x + (ll)p.y;
}
P ps[maxn], qs[maxn];
unordered_map<ll, int> tmap;
int ans[maxn];
inline int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
inline void normalize(P& p) {
int dx = p.x, dy = p.y;
int d = gcd(abs(dx), abs(dy));
dy /= d, dx /= d;
p.x = dx, p.y = dy;
}
int main() {
int N, Q;
scanf("%d%d", &N, &Q);
for (int i = 1; i <= N; i++) {
scanf("%d%d", &ps[i].x, &ps[i].y);
}
for (int i = 1; i <= Q; i++) {
scanf("%d%d", &qs[i].x, &qs[i].y);
}
for (int i = 1; i <= Q; i++) {
tmap.clear();
for (int j = 1; j <= N; j++) {
P p(qs[i].x - ps[j].x, qs[i].y - ps[j].y);
normalize(p);
tmap[Hash(p)]++;
}
for (int j = 1; j <= N; j++) {
P p(qs[i].x - ps[j].x, qs[i].y - ps[j].y);
normalize(p);
//两个方向都要加上去
ans[i] += tmap[Hash(P(-p.y, p.x))];
ans[i] += tmap[Hash(P(p.y, -p.x))];
}
ans[i] /= 2;
}
for (int i = 1; i <= N; i++) {
tmap.clear();
for (int j = 1; j <= N; j++) {
if (i != j) {
P p = { ps[i].x - ps[j].x, ps[i].y - ps[j].y };
normalize(p);
tmap[Hash(p)]++;
}
}
for (int j = 1; j <= Q; j++) {
P p = { ps[i].x - qs[j].x, ps[i].y - qs[j].y };
normalize(p);
ans[j] += tmap[Hash(P(-p.y, p.x))];
ans[j] += tmap[Hash(P(p.y, -p.x))];
}
}
for (int i = 1; i <= Q; i++) {
printf("%d\n", ans[i]);
}
return 0;
}
B. The Tree of Haruhi Suzumiya
- 太难，挖坑
C. Sakurada Reset
D. Decimal
- 找找规律会发现，把n质因数分解后，只要分解的结果，含有除2或5以外其他质因数，那么就是无限小数。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
while (n % 2 == 0) n /= 2;
while (n % 5 == 0) n /= 5;
if (n == 1) printf("No\n");
else printf("Yes\n");
}
return 0;
}
E. Escape
- 最大流。。。
F. Forest Program
- 图论，6月份把这个题补掉。
G. Game on Chessboard
- 插头dp，挖坑
H. Houraisan Kaguya
I. Invoker
- dp问题，感觉应该归为一个状态机的问题。 d p [ i ] [ j ] dp[i][j] dp[i][j] = m i n ( d p [ i ] [ j ] , d p [ i − 1 ] [ k ] + d i s t ( k → j ) min(dp[i][j],dp[i-1][k]+dist(k \rightarrow j) min(dp[i][j],dp[i−1][k]+dist(k→j)。搜索从 i - 1 到 i 状态，从6种字母到另外 6 种字母，的最小值。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
using namespace std;
char words[10][6][4] = {
{"QQQ","QQQ","QQQ","QQQ","QQQ","QQQ"},
{"QQW","QWQ","WQQ","WQQ","WQQ","WQQ"},
{"QQE","QEQ","EQQ","EQQ","EQQ","EQQ"},
{"WWW","WWW","WWW","WWW","WWW","WWW"},
{"QWW","WQW","WWQ","WWQ","WWQ","WWQ"},
{"WWE","WEW","EWW","EWW","EWW","EWW"},
{"EEE","EEE","EEE","EEE","EEE","EEE"},
{"QEE","EQE","EEQ","EEQ","EEQ","EEQ"},
{"WEE","EWE","EEW","EEW","EEW","EEW"},
{"QWE","QEW","EQW","EWQ","WEQ","WQE"},
};
const int maxn = 100010;
char str[maxn], p[maxn];
int f[maxn][6];
unordered_map<char, int> um;
int dist(int a, int b, int x, int y) {
//计算从 words[a][b] 到 words[x][y] 需要在末尾添加几个字母，即用几次技能。
if (words[a][b][0] == words[x][y][0] && words[a][b][1] == words[x][y][1] && words[a][b][2] == words[x][y][2]) {
return 0;
}
if (words[a][b][1] == words[x][y][0] && words[a][b][2] == words[x][y][1]) {
return 1;
}
if (words[a][b][2] == words[x][y][0]) {
return 2;
}
return 3;
}
int main() {
um['X'] = 0; um['V'] = 1; um['G'] = 2;
um['C'] = 3; um['X'] = 4; um['Z'] = 5;
um['T'] = 6; um['F'] = 7; um['D'] = 8; um['B'] = 9;
scanf("%s", str);
//前后两个字母相同只需要按R，把这些东西先挑出来。
int sz = 0, res1 = strlen(str);
p[sz++] = um[str[0]];
for (int i = 1; str[i]; i++) {
if (str[i] != str[i - 1]) p[sz++] = um[str[i]];
}
//for (int i = 0; i < sz; i++) {
// printf("* %d\n", p[i]);
//}
//printf("%d\n", res1);
memset(f, 0x3f, sizeof f);
for (int j = 0; j < 6; j++) f[0][j] = 3;
for (int i = 1; i < sz; i++) {
for (int j = 0; j < 6; j++) {
for (int k = 0; k < 6; k++) {
f[i][j] = min(f[i][j], f[i - 1][k] + dist(p[i - 1], k, p[i], j));
}
//printf("### %d %d %d\n", i, j, f[i][j]);
}
}
int res2 = 1e9;
for (int j = 0; j < 6; j++) {
res2 = min(res2, f[sz - 1][j]);
}
printf("%d\n", res1 + res2);
return 0;
}
J. MUV LUV EXTRA
- 字符串，KMP + 最小循环节。我们发现一个规律（假设ne数组和模式串下标均从1开始）：最小循环节（题目中的 l）= i - ne[i]. （其实告诉这个规律后，发现道理也挺显然的）
- i 从 1 到 N 一直更新答案就可以了
ans = max(ans, a * i - b * (i - ne[i]))
完整代码：
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 10000010;
int ne[maxn], N;
char str[maxn], p[maxn];
typedef long long ll;
ll a, b;
int main() {
scanf("%lld%lld%s", &a, &b, str);
for (int i = 0; str[i]; i++) {
if (str[i] == '.') {
strcpy(p + 1, str + i + 1);
break;
}
}
N = strlen(p + 1);
reverse(p + 1, p + N + 1);
//计算 ne 数组
for (int i = 2, j = 0; i <= N; i++) {
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j++;
ne[i] = j;
}
//printf("### %s\n", p + 1);
//for (int i = 1; i <= N; i++) printf("*** %d %d\n", i, ne[i]);
ll ans = -1e9;
for (int i = 1; i <= N; i++) {
ll p = i, l = i - ne[i];
ans = max(ans, a * p - b * l);
}
printf("%lld\n", ans);
return 0;
}
K. MUV LUV UNLIMITED
- 题意：两人轮流在树上删除至少一个叶子。最后删掉根节点的人获胜，问是先手必胜还是后手必胜。
- 公平组合游戏的某个状态，要么为必胜态，要么为必败态。
- 若只有一条链，链长为偶数则先手必胜。
- 若不止一条链，这么考虑吧：
- 第一种情况：所有叶子节点的父亲的出度都等于 1。求出每个叶子节点的链长（即到达第一个出度不为 1 的祖先需要经过多少条边）。如果所有链长均为偶数则先手必败，否则先手必胜。其中必胜的策略为将所有链长为奇数的叶子删去使得他们链长变为偶数。而偶数的话一定是必败的：先手取若干叶节点之后，某些链长变成奇数。那么，后手就可以让这些链长重新变成偶数。那么先手在删除的时候，会出现除了最长链之外其余链至多有一个节点的情况（最长链也可能只有一个结点）。那么，后手可以删掉出最长链以外的所有结点，并且让仅剩最长链的长度为奇数。这样子就变成了一条链的状态。
- 第二种情况：存在叶节点的父亲的出度大于等于2。那么，假设所有叶子结点构成的集合为 S，那么，先手可以删掉一个叶节点（并且其父结点出度大于等于2）加上一些其他结点。那么会出现两种情况，要么直接拿走一些结点成为第一种情况中的必败态，
要么走到其他的必败态（越分析越复杂）。
别人谜之题解
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1000010, maxm = maxn * 2;
int h[maxn], e[maxm], ne[maxm], idx, Fa[maxn];
int dout[maxn];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int N, M;
int dfs(int u, int fa)
{
bool is_leave = true;
for(int i = h[u]; i != -1; i = ne[i]){
int v = e[i];
if(v == fa) continue;
is_leave = false;
if(dfs(v, u)) return 1;
}
if(is_leave){
int father = u;
int cnt = 0;
while(father != 1){
cnt++;
father = Fa[father];
if(dout[father] > 1){
return (cnt & 1);
}
}
if(father == 1) return !(cnt & 1);
}
return 0;
}
int main()
{
int T;
scanf("%d", &T);
while(T--){
scanf("%d", &N);
fill(h, h + N + 1, -1);
idx = 0;
fill(dout, dout + N + 1, 0);
for(int i = 2; i <= N; i++){
int p;
scanf("%d", &p);
Fa[i] = p;
dout[p]++;
add(i, p), add(p, i);
}
Fa[1] = -1;
if(dfs(1, -1)) printf("Takeru\n");
else printf("Meiya\n");
}
return 0;
}