2018 ACM-ICPC, Syrian Collegiate Programming Contest
Contents
Contest Info
Solved | A | B | C | D | E | F | G | H | I | J | K | L |
---|---|---|---|---|---|---|---|---|---|---|---|---|
10/12 | O | O | O | O | - | O | O | O | O | O | O | - |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
A. Hello SCPC 2018!
Solved By Hsueh-. 0:04(+)
题意:
- 判断十二个数字是否满足;
- 前4个递增
- 后面8个严格大于前4个
思路:
模拟。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main() {
freopen("hello.in", "r", stdin);
int T;
scanf("%d", &T);
while (T--) {
for (int i = 0; i < 12; ++i) {
scanf("%d", a + i);
}
sort(a + 4, a + 12);
bool F = true;
for (int i = 1; i < 12; ++i) {
if (a[i] < a[i - 1]) {
F = false;
break;
}
}
puts(F ? "yes" : "no");
}
return 0;
}
B. Binary Hamming
Solved By Dup4. 0:10(+)
题意:
- 给出两个
01
串,可以打乱字母排列顺序,使得两个01
串的汉明码距离最大。
思路:
尽可能贪心放 01
使得同一位不同即可。
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("hamming.in", "r", stdin);
int _T;
cin >> _T;
string s, t;
while (_T--) {
int n;
cin >> n;
cin >> s >> t;
int a[2] = {0, 0}, b[2] = {0, 0};
for (auto &c : s) ++a[c - '0'];
for (auto &c : t) ++b[c - '0'];
cout << min(a[0], b[1]) + min(a[1], b[0]) << "\n";
}
return 0;
}
C. Portals
Solved By Dup4. 1:00(+)
题意: 有一个 .
表示空地,#
表示障碍物,o
表示传送门(即含有 o
的格子都可以互相到达), s
表示起点,e
表示终点。 现在可以将 #
边成 .
,问最少的次数使得 s
不能到达 e
。
思路:
- 需要最多的次数是
,并且可以发现肯定是将离 s
或者e
最近的.
更改掉,分类讨论一下然后判连通即可。
Code
#include <bits/stdc++.h>
using namespace std;
#define dbg(x...) \
do { \
cout << "\033[32;1m" << #x << " -> "; \
err(x); \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
cout << arg << ' ';
err(args...);
}
#define SZ(x) (int(x.size()))
const int N = 2e5 + 10;
int n, st, ed;
char s[N];
struct UFS {
int fa[N], rk[N];
void init(int n) {
memset(fa, 0, sizeof(fa[0]) * (n + 5));
memset(rk, 0, sizeof(rk[0]) * (n + 5));
}
int find(int x) {
return fa[x] == 0 ? x : fa[x] = find(fa[x]);
}
bool merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
if (rk[fx] > rk[fy])
swap(fx, fy);
fa[fx] = fy;
if (rk[fx] == rk[fy])
++rk[fy];
return true;
}
return false;
}
bool same(int x, int y) {
return find(x) == find(y);
}
} ufs;
bool ok() {
ufs.init(n);
vector<int> vec;
for (int i = 1; i <= n; ++i) {
if (s[i] == 'o')
vec.push_back(i);
}
for (int i = 2; i <= n; ++i)
if (s[i] == '.' || s[i] == 'o' || s[i] == 's' || s[i] == 'e') {
if (s[i - 1] == '.' || s[i - 1] == 'o' || s[i - 1] == 's' || s[i - 1] == 'e')
ufs.merge(i - 1, i);
}
for (int i = 1; i < SZ(vec); ++i) ufs.merge(vec[i - 1], vec[i]);
return !ufs.same(st, ed);
}
int gao1(int st) {
for (int i = st - 1; i >= 1; --i) {
if (s[i] == '.') {
s[i] = '#';
if (ok())
return 1;
s[i] = '.';
break;
}
}
for (int i = st + 1; i <= n; ++i) {
if (s[i] == '.') {
s[i] = '#';
if (ok())
return 1;
s[i] = '.';
break;
}
}
return 0;
}
int gao2(int st) {
int i, j;
for (i = st - 1; i >= 1; --i) {
if (s[i] == '.') {
break;
}
}
for (j = st + 1; j <= n; ++j) {
if (s[j] == '.') {
break;
}
}
// dbg(st, i, j);
if (i >= 1 && j <= n) {
s[i] = '#';
s[j] = '#';
if (ok())
return 1;
s[i] = '.';
s[j] = '.';
}
return 0;
}
int gao() {
if (ok())
return 0;
if (gao1(st))
return 1;
if (gao1(ed))
return 1;
if (gao2(st))
return 2;
if (gao2(ed))
return 2;
return -1;
}
int main() {
freopen("portals.in", "r", stdin);
int _T;
cin >> _T;
while (_T--) {
scanf("%d%s", &n, s + 1);
for (int i = 1; i <= n; ++i) {
if (s[i] == 's')
st = i;
else if (s[i] == 'e')
ed = i;
}
printf("%d\n", gao());
}
return 0;
}
D. Carnival Slots
Solved By Heush-. 1:44(+)
题意:
- 一张
的的图,你可以任意修改 \
,/
使得每列掉下来的权值数量和最大。
思路: - 记忆化搜索。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e2 + 10;
int n, m;
char G[N][N];
int f[N][N], num[N], val[N];
int gao(int x, int y) {
if (x == n + 1) {
return val[y];
}
if (f[x][y] != -1)
return f[x][y];
int& res = f[x][y];
res = gao(x + 1, y);
if (G[x][y] != '.' && y - 1 >= 1)
res = max(res, gao(x + 1, y - 1));
if (G[x][y] != '.' && y + 1 <= m)
res = max(res, gao(x + 1, y + 1));
return res;
}
int main() {
freopen("balls.in", "r", stdin);
int _T;
scanf("%d", &_T);
while (_T--) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
f[i][j] = -1;
}
}
for (int i = 1; i <= m; ++i) {
scanf("%d", num + i);
}
for (int i = 1; i <= n; ++i) {
scanf("%s", G[i] + 1);
}
for (int i = 1; i <= m; ++i) {
scanf("%d", val + i);
}
ll res = 0;
for (int i = 1; i <= m; ++i) {
res += 1ll * gao(1, i) * num[i];
}
printf("%lld\n", res);
}
return 0;
}
E. 2Nodes
UnSolved.
题意:
- 有一棵树,每个点有颜色(白、红、蓝),每秒钟,对于每个白色节点,如果它相邻的节点中存在非白色的,那么就将当前节点染色成那个节点的颜色,如果有多个,那么选取标号最小的那个点的颜色作为当前点的染色。
- 现在最多能将
个点变成白色,问如何变使得最终红色点最多?
思路:
F. Pretests
Solved By Dup4. 2:45(+2)
题意:
- 对于一个题目,有
组数据,有 份待评测的程序,每份程序如果挂在了第 个点,那么它需要的测试时间为 ,如果通过所有数据,那么测试的时间为 ,现在给出每份程序对于每个点的通过情况,可以重新安排测试点的顺序,使得总的测试时间最小。 输出字典序最小的方案。
思路:
表示前 个测试点的集合为 ,需要的最少测试时间,然后枚举一个 进行转移, 要包含在 中。 - 然后发现额外的贡献是测试程序的通过测试点的集合是
的超集,然后这部分贡献可以用高维前缀和预处理。 - 总时间复杂度
,对于字典序,直接记录一个 string
即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10, INF = 0x3f3f3f3f;
int t, n, cnt[N], f[N];
char s[110];
vector<int> g[N];
inline void chmin(int &x, int y) {
if (x > y)
x = y;
}
int main() {
freopen("tests.in", "r", stdin);
int _T;
scanf("%d", &_T);
while (_T--) {
scanf("%d%d", &t, &n);
for (int i = 0; i < (1 << t); ++i) cnt[i] = 0, f[i] = INF, g[i].clear();
f[0] = 0;
int more = 0;
for (int i = 1; i <= n; ++i) {
scanf("%s", s);
int res = 0;
for (int j = 0; j < t; ++j) {
if (s[j] == '1') {
res |= 1 << j;
}
}
if (res == (1 << t) - 1)
more += t - 1;
else
++cnt[res];
}
for (int j = 0; j < t; ++j) {
for (int i = 0; i < 1 << t; ++i) {
if (!(i >> j & 1))
cnt[i] += cnt[i ^ (1 << j)];
}
}
for (int i = 1; i < 1 << t; ++i) {
for (int j = 0; j < t; ++j) {
if ((i >> j) & 1) {
int nx = i ^ (1 << j);
g[nx].push_back(j);
if (f[nx] < f[i] || (f[nx] == f[i] && g[nx] < g[i])) {
f[i] = f[nx];
g[i] = g[nx];
}
g[nx].pop_back();
}
}
f[i] += cnt[i];
}
printf("%d\n", f[(1 << t) - 1] + n + more);
for (int i = 0; i < t; ++i) printf("%d%c", g[(1 << t) - 1][i] + 1, " \n"[i == t - 1]);
}
return 0;
}
G. Is Topo Logical?
Solved By Dup4. 3:22(+1)
题意:
- 给出一个
和两个入度数组 ,要求构造一个 个点的有向图,满足刚开始时第 个点的入度为 ,跑完拓扑排序后第 个点的度数为 。
思路:
- 基于
数组中是否为 将点分成两部分,为 的那部分组成一条链,不为 的那部分组成一个环。 - 然后根据入度连边即可,根据
讨论一下入度的来源。
Code
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int(x.size()))
#define dbg(x...) \
do { \
cout << "\033[32;1m" << #x << " -> "; \
err(x); \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
cout << arg << ' ';
err(args...);
}
const int N = 2e5 + 10;
int n, a[N], b[N], need[N];
vector<vector<int>> G;
bool gao() {
G.clear();
G.resize(n + 1);
vector<int> A, B;
for (int i = 1; i <= n; ++i) {
need[i] = a[i] - b[i];
if (!b[i])
A.push_back(i);
else
B.push_back(i);
}
if (SZ(B) == 1)
return 0;
for (int i = 0; i < SZ(B); ++i) {
if (!i)
G[B.back()].push_back(B[i]);
else
G[B[i - 1]].push_back(B[i]);
--b[B[i]];
}
for (int i = 0; i < SZ(B); ++i) {
for (int j = 0; b[B[i]] && j < SZ(B); ++j)
if (i != j) {
if (i == 0 && j == SZ(B) - 1)
continue;
if (i != 0 && j == i - 1)
continue;
--b[B[i]];
G[B[j]].push_back(B[i]);
}
if (b[B[i]])
return 0;
for (int j = 0; need[B[i]] && j < SZ(A); ++j) {
--need[B[i]];
G[A[j]].push_back(B[i]);
}
if (need[B[i]])
return 0;
}
sort(A.begin(), A.end(), [&](int x, int y) {
return a[x] < a[y];
});
for (int i = 0; i < SZ(A); ++i) {
if (a[A[i]] > i)
return 0;
for (int j = 0; a[A[i]] && j < i; ++j) {
--a[A[i]];
G[A[j]].push_back(A[i]);
}
}
int sze = 0;
for (int i = 1; i <= n; ++i) sze += SZ(G[i]);
printf("%d\n", sze);
for (int i = 1; i <= n; ++i) {
for (auto& it : G[i]) {
printf("%d %d\n", i, it);
}
}
return 1;
}
int main() {
freopen("topo.in", "r", stdin);
int _T;
scanf("%d", &_T);
while (_T--) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
for (int i = 1; i <= n; ++i) scanf("%d", b + i);
if (!gao())
printf("-1\n");
}
return 0;
}
H. Bugged System
Solved By Hsueh-. 1:29(+4)
题意:
- 一个地铁站,有
个站,但是存在一个 bug,如果一个人从 站进站 站出来则不用钱,人们可以交换地铁卡。 - 问
个人分别从 进站, 出站,是否存在一个方案使得大家不花钱。 - 如果存在则输出最小行动距离和。
思路:
- 很显然如果存在则是一个环,那么每个站的进站数量等于出站数量,距离就是每个人的行动距离
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e6 + 10;
int n, m;
ll a[N];
int vis[N];
int main() {
freopen("bugged.in", "r", stdin);
int _T;
scanf("%d", &_T);
while (_T--) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
vis[i] = 0;
}
for (int i = 1; i <= n; ++i) {
scanf("%lld", a + i);
}
ll res = 0;
for (int i = 1, s, d; i <= m; ++i) {
scanf("%d %d", &s, &d);
vis[s]++;
vis[d]--;
res += abs(a[s] - a[d]);
}
for (int i = 1; i <= n; ++i) {
if (vis[i]) {
res = -1;
break;
}
}
printf("%lld\n", res);
}
return 0;
}
I. Rise of the Robots
Solved By Hsueh-. 2:34(+3)
题意:
- 一个半径为
的图,一个半径为 机器人,经过 次操作,每次操作都从 到 ,问是否存在一个起点,使得机器人没有出整个圆。
思路:
- 猜测可以求出一个圆表示机器人的路径,那么求一个最小覆盖圆即可。
Code
#include <bits/stdc++.h>
using namespace std;
using db = double;
const int N = 1e5 + 10;
const db eps = 1e-10;
mt19937 rnd(time(0));
int sgn(db x) {
if (fabs(x) < eps)
return 0;
return x > 0 ? 1 : -1;
}
struct Point {
db x, y;
Point(db x = 0, db y = 0) : x(x), y(y) {}
Point operator+(const Point& b) const {
return Point(x + b.x, y + b.y);
}
Point operator-(const Point& b) const {
return Point(x - b.x, y - b.y);
}
Point operator*(const db& b) const {
return Point(x * b, y * b);
}
Point operator/(const db& b) const {
return Point(x / b, y / b);
}
db operator^(const Point& b) const {
return x * b.y - y * b.x;
}
db operator*(const Point& b) const {
return x * b.x + y * b.y;
}
db len() {
return hypot(x, y);
}
db len2() {
return x * x + y * y;
}
db dis(Point b) {
return hypot(x - b.x, y - b.y);
}
Point rotright() {
return Point(y, -x);
}
} p[N];
struct Circle {
Point p;
db r;
Circle() {}
Circle(Point p, db r) : p(p), r(r) {}
Circle(db x, db y, db r) : p(Point(x, y)), r(r) {}
Circle(Point a, Point b, Point c, int opt = 0) {
if (opt == 0) {
Point p0 = (a + b) / 2;
Point v0 = (b - a).rotright();
Point p1 = (a + c) / 2;
Point v1 = (c - a).rotright();
db t = ((p1 - p0) ^ v1) / (v0 ^ v1);
p = p0 + v0 * t;
r = p.dis(a);
}
}
};
int n, R, r;
Point solve() {
shuffle(p + 1, p + 1 + n, rnd);
Circle cir(0, 0, 0);
for (int i = 1; i <= n; ++i) {
if (sgn((cir.p - p[i]).len2() - cir.r) > 0) {
cir.p = p[i];
cir.r = 0;
for (int j = 1; j < i; ++j) {
if (sgn((cir.p - p[j]).len2() - cir.r) > 0) {
cir.p = (p[i] + p[j]) / 2;
cir.r = (p[j] - cir.p).len2();
for (int k = 1; k < j; ++k) {
if (sgn((cir.p - p[k]).len2() - cir.r) > 0) {
cir = Circle(p[i], p[j], p[k]);
cir.r = (p[k] - cir.p).len2();
}
}
}
}
}
}
cir.p.x *= -1;
cir.p.y *= -1;
if (sgn(cir.p.x) == 0)
cir.p.x = 0;
if (sgn(cir.p.y) == 0)
cir.p.y = 0;
return cir.p;
}
int main() {
freopen("robots.in", "r", stdin);
int _T;
scanf("%d", &_T);
while (_T--) {
scanf("%d %d %d", &n, &R, &r);
db x = 0, y = 0;
for (int i = 1, dx, dy; i <= n; ++i) {
scanf("%d %d", &dx, &dy);
x += dx, y += dy;
p[i] = Point(x, y);
}
++n;
p[n] = Point(0, 0);
Point res = solve();
printf("%.9f %.9f\n", res.x, res.y);
}
return 0;
}
J. Clarifications
Solved By Dup4 & Hsueh-. 4:19(+)
题意:
- 在一场时长为
的比赛中,有 个问题,有 个种类的问题,有两个回答的人 A
和B
,A
能在任何时刻回答任何问题,B
只能回答在这之前A
回答过的问题中相同种类的问题。 - 每个问题有两个参数
,分别表示询问的时刻和种类。现在问基于上述限制条件,回答完所有问题最少需要多少时间。
思路:
- 考虑已经被
A
回答过的种类是没有区别的,并且优先级最低。 - 然后考虑还没有回答过的,但是已经在队列中了,我们根据他们在队列中出现的次数进行优先级排序,对于
A
来说,每次取优先级最高的出来回答掉,然后释放出一些问题,可以让B
也一起帮忙回答。 - 但是如果有两个问题的出现次数相同,我们可以将下一秒会出现的问题也纳入考量之中。
- 维护优先级的操作可以用线段树维护。
Code
#include <bits/stdc++.h>
using namespace std;
using pII = pair<int, int>;
#define dbg(x...) \
do { \
cout << "\033[32;1m" << #x << " -> "; \
err(x); \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
const int N = 1e5 + 10, INF = 1e9;
int n, m, K, sta[N];
struct SEG {
struct node {
int val, pos;
node(int val = 0, int pos = 0) : val(val), pos(pos) {}
node operator+(const node &other) const {
node res = node();
if (val > other.val) {
res = (*this);
} else {
res = other;
}
return res;
}
} t[N << 2];
void build(int id, int l, int r) {
t[id] = node();
if (l == r) {
t[id].pos = l;
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
}
void update(int id, int l, int r, int pos, int v) {
// dbg(id, l, r, pos, v);
if (l == r) {
t[id].val += v;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
update(id << 1, l, mid, pos, v);
else
update(id << 1 | 1, mid + 1, r, pos, v);
t[id] = t[id << 1] + t[id << 1 | 1];
}
} seg;
int main() {
freopen("clar.in", "r", stdin);
int _T;
scanf("%d", &_T);
while (_T--) {
scanf("%d%d%d", &m, &n, &K);
vector<vector<int>> vec(m + 5);
for (int i = 1, t, p; i <= n; ++i) {
scanf("%d%d", &t, &p);
vec[t].push_back(p);
}
// 0 没出现过 1 在seg中 2 被回答过一次
for (int i = 1; i <= K; ++i) sta[i] = 0;
seg.build(1, 1, K);
int cnt = 0;
int t = 1;
int remind = n;
while (remind) {
if (t <= m)
for (auto &it : vec[t]) {
if (sta[it] == 0) {
++sta[it];
seg.update(1, 1, K, it, 1);
} else if (sta[it] == 1) {
seg.update(1, 1, K, it, 1);
} else if (sta[it] == 2) {
++cnt;
}
}
if (t + 1 <= m)
for (auto &it : vec[t + 1]) {
if (sta[it] == 1) {
seg.update(1, 1, K, it, 1);
}
}
if (cnt)
--cnt, --remind;
int val = seg.t[1].val, pos = seg.t[1].pos;
if (sta[pos] != 1)
pos = 0;
if (pos) {
cnt += val - 1;
sta[pos] = 2;
--remind;
seg.update(1, 1, K, pos, -INF);
} else if (cnt) {
--cnt;
--remind;
}
if (t + 1 <= m)
for (auto &it : vec[t + 1]) {
if (it == pos) {
--cnt;
} else if (sta[it] == 1) {
seg.update(1, 1, K, it, -1);
}
}
++t;
}
printf("%d\n", t - 1);
}
return 0;
}
K. Tourists' Tour
Solved By Dup4 & Hsueh-. 1:11(+1)
题意:
- 有
座山峰,每座山峰的高度为 ,对于第 座山峰,如果它左边有比他高的山峰,那么它会找一座离它最近的并且比它高的然后在这之间建立一座桥(即连一条边)。 - 对于右边亦是如此,现在要对这些边进行染色,使得任意两条相邻的边不同色,注意边是无向边。
思路:
强制让高的山峰连向低的山峰,变成 DAG,然后暴力染色即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int a[N];
vector<vector<int> > G;
int col[N], in[N], vis[N][6];
int gao() {
int rt = 0;
for (int i = 1; i <= n; ++i) {
if (in[i] == 0) {
rt = i;
break;
}
}
int Max = 0;
queue<int> q;
q.push(rt);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 1; i <= 5; ++i) {
if (vis[u][i])
continue;
col[u] = i;
Max = max(Max, i);
for (auto v : G[u]) {
vis[v][i] = 1;
in[v]--;
if (in[v] == 0) {
q.push(v);
}
}
break;
}
}
return Max;
}
int main() {
freopen("tour.in", "r", stdin);
int _T;
scanf("%d", &_T);
while (_T--) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
col[i] = 0;
in[i] = 0;
for (int j = 0; j < 6; ++j) {
vis[i][j] = 0;
}
}
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
G.clear();
G.resize(n + 1);
stack<int> stk;
for (int i = 1; i <= n; ++i) {
while (!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
if (!stk.empty()) {
int u = stk.top();
int v = i;
G[u].push_back(v);
in[v]++;
}
stk.push(i);
}
while (!stk.empty()) stk.pop();
for (int i = n; i >= 1; --i) {
while (!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
if (!stk.empty()) {
int u = stk.top();
int v = i;
G[u].push_back(v);
in[v]++;
}
stk.push(i);
}
int Max = gao();
printf("%d\n", Max);
for (int i = 1; i <= n; ++i) {
printf("%d%c", col[i], " \n"[i == n]);
}
}
return 0;
}
L. Sad Meals
UnSolved.
题意:
- 有一个厨师做菜,假设他在第
天之前已经会了 道菜了。 - 那么他在第
可能学新菜,即 。 - 也可能顺着前一天的顺序做菜,即
。 - 如果前一天做完了已经学会的菜,那么就重新开始轮回,即做第一道菜
。 - 现在给出
数组,但是挖空了一些位置,要求补充上这些位置,使得满足上述限制条件。
思路:
Last update: March 27, 2022
Created: March 27, 2022
Created: March 27, 2022