J-Number Game
签到题。
给你四个数 $A, B, C,x$,可以进行以下任意一种操作任意次,问能不能把 $C$ 变成 $x$。
- 把 $B$ 变成 $A-B$
- 把 $C$ 变成 $B-C$
容易发现任意一个操作执行 $2$ 次之后 $B,C$ 其中一个会变回初始的数。手写几个找规律会发现 $x = k\times (A - 2B) + C$ or $x = k\times (A-2B)+B-C$。
改写一下就是 $x-c = 0 \mod{(A-2B)}$ 和 $x-B+C = 0\mod{(A-2B)}$
特判一下 $A-2B=0$。
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int a, b, c, x;
cin >> a >> b >> c >> x;
bool ok = false;
if (2 * b == a) {
ok |= (x - c == 0) || (x - b + c == 0);
} else {
ok |= (x - c) % (a - 2 * b) == 0;
ok |= (x - b + c) % (a - 2 * b) == 0;
}
cout << (ok ? "Yes" : "No") << '\n';
}
return 0;
}
M-Z-Game on grid
两个人在 $n\times m$ 的网格上轮流移动一个棋子。棋子初始位为 $(1, 1)$,每次只能向某一维的正方向移动一格。网格上有一些特殊点,移到标 A
的点先手胜,移到标 B
的点先手败,没有移到特殊点且不能再移动棋子则为平局。问先手是否有必胜、必平局、必败的策略。
考虑 $dp$,$dp(i, j):= 用三位二进制数表示走到(i,j)的情况(001表示先手胜,010表示平局,100表示后手胜)$
将所有 A
初始化成 $1$,B
初始化成 $4$,转移时只用考虑右边和下边有没有先手胜的策略,分类讨论。
- 轮到先手走棋,且右边和下边某一处有
A
,先手胜 $dp(i, j) = dp(i + 1, j) \or dp(i, j + 1)$ - 轮到后手走棋,且右边和下面两个都是
A
,先手胜 $dp(i, j) = dp(i + 1, j) \and dp(i, j + 1)$ - 其他情况同理。
最后判断 $dp(1, 1)$ 每一位是否可行。
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "/Users/aaron/Documents/template/debug.hpp"
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n, m;
cin >> n >> m;
vector<string> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int win = 1, draw = 2, lose = 4;
vector dp(n, vector<int>(m, 0));
auto get = [&](int i, int j) {
if (a[i][j] == 'A') return win;
else if (a[i][j] == '.') return draw;
else return lose;
};
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
if (i == n - 1 && j == m - 1) {
dp[i][j] = get(i, j);
continue;
}
if (a[i][j] != '.') {
dp[i][j] = get(i, j);
} else if (i == n - 1) {
dp[i][j] = dp[i][j + 1];
} else if (j == m - 1) {
dp[i][j] = dp[i + 1][j];
} else {
if ((i + j) & 1) {
dp[i][j] = dp[i][j + 1] & dp[i + 1][j];
} else {
dp[i][j] = dp[i][j + 1] | dp[i + 1][j];
}
}
}
}
for (int i = 0; i < 3; i++) {
cout << ((dp[0][0] >> i & 1) ? "yes" : "no") << " \n"[i == 2];
}
}
return 0;
}
B-Eezie and Pie
给定一棵树,根为 $1$,每个节点可以为它的 $0\sim d[i]$ 级祖先贡献 $1$ 的价值。求最终每个点的价值。
这题的所有树上路径都是从根节点到某个节点的,不需要考虑两个节点之间的路径,所以这不是树上差分模板题吗??
只要考虑怎么往上找第 $d[i]$ 级祖先就可以了,维护 dfs 栈就可以得到。这题允许 log,所以用树上倍增或者树剖什么的都行。
然后树上差分把点权 $+1$ 即可。
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "/Users/aaron/Documents/template/debug.hpp"
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<vector<int>> adj(n + 1);
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> d(n + 1);
for (int i = 1; i <= n; i++) {
cin >> d[i];
}
vector<int> f(n + 1);
vector<int> st(1, 0);
function<void(int, int)> dfs = [&](int u, int pr) {
st.push_back(u);
f[u]++;
int k = st.size() - 1 - min(d[u] + 1, (int)st.size() - 1);
f[st[k]]--;
for (int v : adj[u]) {
if (v == pr) {
continue;
}
dfs(v, u);
}
st.pop_back();
};
dfs(1, -1);
dfs = [&](int u, int pr) {
for (int v : adj[u]) {
if (v == pr) {
continue;
}
dfs(v, u);
f[u] += f[v];
}
};
dfs(1, -1);
for (int i = 1; i <= n; i++) {
cout << f[i] << " \n"[i == n];
}
return 0;
}
G-Icon Design
画画,n = 5 直接手玩