2002(div1+div2)
A. Distanced Coloring
你从一个神秘的来源收到了一个
消息来源告诉你用一些颜色给网格着色,要满足以下条件:
- 如果
、 是两个颜色相同的单元格,那么就是 。
您不喜欢使用过多的颜色。请找出给网格着色所需的最少颜色数。
猜的...
void solve() {
int n, m, k;cin >> n >> m >> k;
cout << min(k, n) * min(k, m) << '\n';
}
B. Removals Game
爱丽丝得到了
在每个回合中,会依次发生以下事件:
- 爱丽丝选择数组中的第一个或最后一个元素,并将其从数组中删除;
- 鲍勃选择自己数组中的第一个或最后一个元素,并将其从数组中移除。
游戏持续
如果是
若
数组或者颠倒的 数组是和 数组相等的,则 win,否则 win, 还是比较容易看出来的.
void solve() {
int n;cin >> n;
vector<int> a(n + 1), b(n + 1);
for (int i = 1;i <= n;i++)cin >> a[i];
for (int i = 1;i <= n;i++)cin >> b[i];
vector<int> c(b);
reverse(c.begin() + 1, c.end());
int ok1 = 1, ok2 = 1;
for (int i = 1;i <= n;i++) {
if (a[i] != b[i]) {
ok1 = 0;
}
if (a[i] != c[i]) {
ok2 = 0;
}
}
if (!ok1 && !ok2) {
cout << "Alice\n";
} else {
cout << "Bob\n";
}
}
C. Black Circles
二维平面上有
圆的半径以每秒
你目前在
请判断这是否可行。
只需要判断到达终点时,终点是否被圆包围即可,其实和我刚开始的结论相同。
#define int long long
void solve() {
int n;cin >> n;
vector<int> x(n), y(n);
int sx, sy, tx, ty;
for (int i = 0;i < n;i++)cin >> x[i] >> y[i];
cin >> sx >> sy >> tx >> ty;
int time = ((sx - tx) * (sx - tx) + (sy - ty) * (sy - ty));
for (int i = 0;i < n;i++) {
int dis = ((x[i] - tx) * (x[i] - tx) + (y[i] - ty) * (y[i] - ty));
if (dis <= time) {
cout << "NO\n";return;
}
}
cout << "YES\n";
}
D1/2. DFS Checker (Easy Version)
给你一棵树
您需要回答
请注意,通过查询,交换是持久的。
DFS 序:
DFS 序并不是唯一的
dfs_order = []
function dfs(v):
append v to the back of dfs_order
pick an arbitrary permutation s of children of v
for child in s:
dfs(child)
dfs(1)
Solution
这里的 DFS 序代表的是先父亲节点,然后是子节点任意选择一个
这样的 DFS 序满足其节点的子节点一定在其之后,不然就不满足要求。
check
函数是用来检测节点
即保证对于所有节点
,其子树节点下标能达到的最小值和最大值都在父节点 的子树范围内即可
void solve() {
int n, Q;cin >> n >> Q;
vector<int> fa(n + 1), p(n + 1), q(n + 1), siz(n + 1, 1);
set<int> son[n + 1];
for (int i = 2; i <= n; i++) cin >> fa[i];
for (int i = n; i >= 2; i--) siz[fa[i]] += siz[i];
for (int i = 1; i <= n; i++) {
cin >> p[i];
son[fa[p[i]]].insert(i);
q[p[i]] = i;
}
auto check = [&](int x) ->int {
if (son[x].size()) {
return q[x] < *son[x].begin() &&
*--son[x].end() + siz[p[*--son[x].end()]] <= q[x] + siz[x];
} else {
return 1;
}
};
int cnt = 0;
for (int i = 1; i <= n; i++) cnt += check(i);
while (Q--) {
int i, j;cin >> i >> j;
int x = p[i], y = p[j];
set<int> s;
s.insert(x), s.insert(y), s.insert(fa[x]), s.insert(fa[y]);
for (auto x : s) if (x) cnt -= check(x);
son[fa[x]].erase(i);
son[fa[y]].erase(j);
swap(p[i], p[j]);
swap(q[x], q[y]);
son[fa[x]].insert(j);
son[fa[y]].insert(i);
for (auto x : s) if (x) cnt += check(x);
cout << (cnt == n ? "YES" : "NO") << '\n';
}
}
E. Cosmic Rays
给定一个整数数组
将数组的强度定义为数组变空所需的秒数。
给你一个由整数组成的数组,以
对于每个
Solution
单调栈
没怎么看懂,但也不再浪费时间了...
#define int long long
void solve() {
int n;cin >> n;
vector<pair<int, int>> stk(n + 1);
int ans = 0;
for (int i = 1;i <= n;i++) {
int a, b;cin >> a >> b;
int len = 0;
while (stk.size()) {
if (stk.back().first == b) {
len += stk.back().second;
stk.pop_back();
} else {
if (a <= 0)break;
int t = min(a, stk.back().second);
a -= t;
len += t;
stk.back().second -= t;
if (stk.back().second == 0)stk.pop_back();
}
}
ans += a;len += a;
stk.push_back({b,len});
cout << ans << " \n"[i == n];
}
}