2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest
Contents
Contest Info
Solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
10/13 | - | - | Ø | O | O | O | O | O | O | O | O | - | O |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
A. Automatic Door
UnSolved.
题意:
思路:
B. Berland Army
UnSolved.
题意:
思路:
C. Downloading B++
UpSolved by Dup4.
题意:
要下载一个软件,默认的下载速度是
思路:
枚举一个加速包的用量,二分另一个加速包的用量。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#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 ll INF = 1e18;
ll f, T, t0, a1, t1, p1, a2, p2, t2;
inline ll ceil(ll x, ll y) {
return (x + y - 1) / y;
}
inline void chmin(ll &x, ll y) {
if (x > y)
x = y;
}
struct E {
ll a, t, p;
bool operator<(const E &other) const {
if (t != other.t)
return t < other.t;
return p < other.p;
}
} e[3];
ll calc(ll remind, ll x, E e) {
ll _remind = remind - e.a * x;
if (_remind < 0)
_remind = 0;
ll useT = e.t * (remind - _remind);
return useT + _remind * t0;
}
ll gao() {
if (t0 * f <= T)
return 0;
ll res = INF;
int n = ceil(f, e[1].a);
for (int i = 0; i <= n; ++i) {
ll now = e[1].p * i;
ll remind = f - e[1].a * i;
if (remind < 0)
remind = 0;
ll useT = e[1].t * (f - remind);
if (useT > T)
break;
ll _T = T - useT;
// dbg(i, remind, f - remind, useT, now, _T);
if (remind * e[0].t <= _T) {
chmin(res, now);
// dbg(i, remind, remind * e[0].t, now);
} else {
if (remind * e[2].t > _T)
continue;
int _n = ceil(remind, e[2].a);
int l = 0, r = _n, tar = _n;
while (r - l >= 0) {
int mid = (l + r) >> 1;
// dbg(mid, calc(remind, mid, e[2]));
if (calc(remind, mid, e[2]) <= _T) {
tar = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
// dbg(i, tar, _n);
chmin(res, now + e[2].p * tar);
}
}
if (res >= INF)
return -1;
return res;
}
int main() {
scanf("%lld%lld%lld", &f, &T, &t0);
scanf("%lld%lld%lld", &a1, &t1, &p1);
scanf("%lld%lld%lld", &a2, &t2, &p2);
e[0] = {1, t0, 0};
e[1] = {a1, t1, p1};
e[2] = {a2, t2, p2};
sort(e + 1, e + 3);
printf("%lld\n", gao());
return 0;
}
D. Packmen Strike Back
Solved By Hsueh-. 4:29(+)
题意:
一个 P
规定一个方向,一旦方向确定就不能更改,问吃到最大的 *
的最下时间。
思路:
- 当
P
的个数大于等于的时候可以吃到所有的 *
。 - 那么二分答案去 check。
表示前 个 能覆盖的最大的 。 - 对于
个 有三种转移,分别是向左,向右或者 向左 向右, 去 check。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
#define dbg(x...) \
do { \
cout << #x << " -> "; \
err(x); \
} while (0)
void err() {
cout << endl;
}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
cout << arg << ' ';
err(args...);
}
int n;
char s[N];
int a[N];
int f[N];
int P[N], tot;
bool ok(int l, int r) {
if (l > r)
return 1;
else
return a[r] - a[l - 1] == 0;
}
bool check(int x) {
memset(f, 0, sizeof f);
for (int i = 1; i <= tot; ++i) {
// left
if (ok(f[i - 1] + 1, P[i] - x - 1))
f[i] = max(f[i], P[i]);
// right
if (ok(f[i - 1] + 1, P[i] - 1))
f[i] = max(f[i], P[i] + x);
// left right
if (i >= 2 && ok(f[i - 2] + 1, P[i] - x - 1))
f[i] = max(f[i], P[i - 1] + x);
}
// dbg(f[1], f[2]);
return ok(f[tot] + 1, n);
}
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
for (int i = 1; i <= n; ++i) {
a[i] = a[i - 1] + (s[i] == '*');
}
for (int i = 1; i <= n; ++i) {
if (s[i] == 'P') {
P[++tot] = i;
}
}
if (tot == 1) {
int cnt1 = 0, cnt2 = 0, pos = P[1], l = 0, r = 0;
for (int i = pos - 1; i >= 1; --i) {
if (s[i] == '*') {
++cnt1;
l = i;
}
}
for (int i = pos + 1; i <= n; ++i) {
if (s[i] == '*') {
++cnt2;
r = i;
}
}
int res1 = 0, res2 = 0;
if (cnt1 > cnt2) {
res1 = cnt1, res2 = pos - l;
} else if (cnt2 > cnt1) {
res1 = cnt2, res2 = r - pos;
} else {
res1 = cnt1, res2 = min(pos - l, r - pos);
}
printf("%d %d\n", res1, res2);
} else {
printf("%d ", a[n]);
// check(4);
int l = 0, r = n, res = -1;
while (r - l >= 0) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid - 1;
res = mid;
} else {
l = mid + 1;
}
}
printf("%d\n", res);
}
return 0;
}
E. Field of Wonders
Solved By Hsueh-. 1:39(+)
题意:
长度为 *
的字符有几个。
思路:
模拟。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m;
string s;
string str[N];
int vis[N], cnt[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> s;
for (auto it : s) {
vis[it]++;
}
cin >> m;
for (int i = 1; i <= m; ++i) {
cin >> str[i];
}
int res = 0;
for (int i = 'a'; i <= 'z'; ++i) {
char c = i;
if (vis[i])
continue;
bool F = true;
for (int j = 1; j <= m; ++j) {
memset(cnt, 0, sizeof cnt);
bool FF = true;
for (int k = 0; k < n; ++k) {
if (s[k] == '*' && vis[str[j][k]]) {
FF = false;
break;
}
if (s[k] == '*') {
cnt[str[j][k]]++;
} else if (s[k] != str[j][k]) {
FF = false;
break;
}
}
if (FF && !cnt[c]) {
F = false;
break;
}
}
res += F;
}
cout << res << "\n";
return 0;
}
F. Lost in Transliteration
Solved By Hsueh-. 0:32(+)
题意:
u
可以变成oo
。h
可以变成kh
。- 问有几种字符串?
思路:
u
变成oo
。- 遇到
h
删去前面的k
。 - 然后去重统计个数。
Code
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
map<string, int> mp;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n;
int res = 0;
for (int i = 1; i <= n; ++i) {
cin >> s;
string t = "";
for (int j = 0, len = s.size(); j < len; ++j) {
if (s[j] == 'u')
t += "oo";
else {
if (s[j] == 'h') {
while (!t.empty() && t[t.size() - 1] == 'k') {
t.pop_back();
}
}
t += s[j];
}
}
if (!mp.count(t)) {
mp[t]++;
++res;
}
}
cout << res << "\n";
return 0;
}
G. Orientation of Edges
Solved By Hsueh-. 2:38(+)
题意:
一张混合图,有一些有向边和无向边,给定一个起点,分别给无向边定向使得 S
到达的点最多最小,独立回答最大最小值。
思路:
- 最大值,贪心的拓展到没到达的点。
- 最小值,贪心的不拓展到其他点。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
struct Edge {
int to, id, val;
Edge() {}
Edge(int to, int id, int val) : to(to), id(id), val(val) {}
};
int n, m, s, tot;
vector<vector<Edge>> G, und;
int res[N], vis[N];
void gao1() {
int cnt = 1;
memset(vis, 0, sizeof vis);
memset(res, 0, sizeof res);
queue<int> q;
q.push(s);
vis[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto it : G[u]) {
int v = it.to;
if (!vis[v]) {
++cnt;
vis[v] = true;
q.push(v);
}
}
for (auto it : und[u]) {
int v = it.to, id = it.id, val = it.val;
if (!vis[v] && !res[id]) {
res[id] = val;
++cnt;
vis[v] = true;
q.push(v);
}
}
}
printf("%d\n", cnt);
for (int i = 1; i <= tot; ++i) {
if (res[i] == 1)
putchar('+');
else
putchar('-');
}
puts("");
}
void gao2() {
int cnt = 1;
memset(vis, 0, sizeof vis);
memset(res, 0, sizeof res);
queue<int> q;
q.push(s);
vis[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto it : G[u]) {
int v = it.to;
if (!vis[v]) {
++cnt;
vis[v] = true;
q.push(v);
}
}
for (auto it : und[u]) {
int v = it.to, id = it.id, val = it.val;
if (!res[id]) {
res[id] = -val;
}
}
}
printf("%d\n", cnt);
for (int i = 1; i <= tot; ++i) {
if (res[i] == 1)
putchar('+');
else
putchar('-');
}
puts("");
}
int main() {
scanf("%d %d %d", &n, &m, &s);
G.clear();
G.resize(n + 1);
und.clear();
und.resize(n + 1);
for (int i = 1, op, u, v; i <= m; ++i) {
scanf("%d %d %d", &op, &u, &v);
if (op == 1) {
G[u].push_back(Edge(v, 1, 1));
} else {
und[u].push_back(Edge(v, ++tot, 1));
und[v].push_back(Edge(u, tot, -1));
}
}
gao1();
gao2();
return 0;
}
H. Palindromic Cu
Solved By Dup4. 2:01(+1)
题意:
给出一个字符串
思路:
- 考虑串的个数
是 的因子,然后暴力枚举。 - 如何判断是否合法?
令
- 如果
,那么输出原串。 - 否则需要满足
, 是偶数,并且 也是偶数。
Code
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int(x.size()))
#define mkp make_pair
const int N = 4e5 + 10;
int n;
char s[N];
int cnt[320];
void gao(int k) {
cout << k << "\n";
vector<string> pre(k, ""), mid(k, "");
vector<char> DB;
if ((n / k) % 2) {
vector<char> single;
for (int i = 1; i < 255; ++i) {
if (cnt[i] & 1) {
single.push_back(char(i));
--cnt[i];
}
}
for (int i = 1; i < 255; ++i) {
while (cnt[i] > 0 && SZ(single) + 2 <= k) {
cnt[i] -= 2;
single.push_back(char(i));
single.push_back(char(i));
}
}
for (int i = 0; i < k; ++i) {
mid[i] += single.back();
single.pop_back();
}
}
for (int i = 1; i < 255; ++i) {
assert(cnt[i] % 2 == 0);
while (cnt[i] >= 2) {
cnt[i] -= 2;
DB.push_back(char(i));
}
}
for (int i = 0; i < k; ++i) {
while (SZ(pre[i]) * 2 + SZ(mid[i]) + 2 <= n / k) {
pre[i] += char(DB.back());
DB.pop_back();
}
}
for (int i = 0; i < k; ++i) {
assert(SZ(pre[i]) + SZ(mid[i]) + SZ(pre[i]) == n / k);
if (SZ(pre[i]))
cout << pre[i];
if (SZ(mid[i]))
cout << mid[i];
if (SZ(pre[i])) {
reverse(pre[i].begin(), pre[i].end());
cout << pre[i];
}
cout << " \n"[i == k - 1];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
memset(cnt, 0, sizeof cnt);
cin >> n >> (s + 1);
for (int i = 1; i <= n; ++i) {
assert(int(s[i]) <= 255);
++cnt[int(s[i])];
}
int a = 0;
for (int i = 1; i < 255; ++i)
if (cnt[i] & 1)
++a;
for (int i = 1; i <= n; ++i)
if (n % i == 0) {
if (i == n) {
gao(i);
break;
}
if (a == 0 && (n / i) % 2 == 0) {
gao(i);
break;
}
if (a > 0 && i >= a && (i - a) % 2 == 0 && ((n / i) - 1) % 2 == 0) {
gao(i);
break;
}
}
return 0;
}
I. Photo Processing
Solved By Dup4 & Hsueh-. 2:28(+1)
题意:
- 给出
个物品,第 个物品的权值为 ,现在考虑将它们分组,每组物品个数不少于 个,一组物品的代价为其物品的极差,考虑如何分组使得最大极差最小。 - 输出这个最小的最大极差。
思路:
先二分
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...);
}
const int N = 3e5 + 10;
int n, K, a[N], f[N], S[N];
int ok(int x) {
// dbg(x);
memset(f, 0, sizeof f);
S[0] = 0;
int l = 1;
for (int i = 1; i <= n; ++i) {
while (a[i] - a[l] > x) ++l;
int r = i - K + 1;
// dbg(i, l, r);
if ((l <= r && (l - 1 <= 0 || S[r - 1] - S[l - 2] > 0)))
f[i] = 1;
S[i] = S[i - 1] + f[i];
}
return f[n];
}
int main() {
scanf("%d%d", &n, &K);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
sort(a + 1, a + 1 + n);
int l = 0, r = a[n] - a[1], res = r;
while (r - l >= 0) {
int mid = (l + r) >> 1;
if (ok(mid)) {
r = mid - 1;
res = mid;
} else {
l = mid + 1;
}
}
printf("%d\n", res);
return 0;
}
J. Renovation
Solved By Dup4. 4:47(+1)
题意:
有
求最多能拆几座城市。
思路:
- 使劲儿贪心。
- 一座城市如果它要被拆,那么拆的越晚,答案肯定不会更差。
- 那么预处理出每座城市最晚什么时候被拆。
- 然后将城市按
从小到大排序,一一决策,假设当前这座城市能够被拆,那么一定拆。
怎么样能被拆?
- 假设这座城市最晚被拆的时间为
,那么前 个月份还剩下的钱要大于等于 ,然后我们考虑花哪个月份的钱,肯定是小于 ,并且离 越近的那个月份,这个可以用线段树维护一下,然后暴力去扣钱,一个每个月份只会被扣光一次。 - 时间复杂度
。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pII = pair<int, int>;
#define fi first
#define se second
#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 = 1e5 + 10;
int n, m, a[N];
struct E {
int b, p, id;
bool operator<(const E& other) const {
if (p != other.p)
return p < other.p;
return b < other.b;
}
} e[N];
struct SEG {
struct node {
ll val;
int pos;
node() {
val = 0, pos = -1;
}
node operator+(const node& other) const {
node res = node();
res.val = val + other.val;
res.pos = max(pos, other.pos);
return res;
}
} t[N << 2];
void build(int id, int l, int r) {
t[id] = node();
if (l == r) {
t[id].val = a[l];
if (t[id].val == 0)
t[id].pos = -1;
else
t[id].pos = l;
// dbg(id, l, r, t[id].pos, t[id].val);
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
t[id] = t[id << 1] + t[id << 1 | 1];
}
void update(int id, int l, int r, int pos, int v) {
if (l == r) {
t[id].val += v;
if (t[id].val == 0)
t[id].pos = -1;
else
t[id].pos = l;
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];
}
ll query(int id, int l, int r, int ql, int qr) {
if (l >= ql && r <= qr)
return t[id].val;
int mid = (l + r) >> 1;
ll res = 0;
if (ql <= mid)
res += query(id << 1, l, mid, ql, qr);
if (qr > mid)
res += query(id << 1 | 1, mid + 1, r, ql, qr);
return res;
}
int queryPos(int id, int l, int r, int ql, int qr) {
if (l >= ql && r <= qr)
return t[id].pos;
int mid = (l + r) >> 1;
int pos = -1;
if (ql <= mid)
pos = max(pos, queryPos(id << 1, l, mid, ql, qr));
if (qr > mid)
pos = max(pos, queryPos(id << 1 | 1, mid + 1, r, ql, qr));
return pos;
}
} seg;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
for (int i = 1; i <= m; ++i) scanf("%d", &e[i].b);
for (int i = 1; i <= m; ++i) scanf("%d", &e[i].p);
vector<pII> vec;
for (int i = 1; i <= n; ++i) {
while (SZ(vec) && a[i] >= vec.back().fi) vec.pop_back();
vec.push_back(pII(a[i], i));
}
reverse(vec.begin(), vec.end());
for (int i = 1; i <= m; ++i) {
auto pos = lower_bound(vec.begin(), vec.end(), pII(e[i].b, -1));
if (pos == vec.end())
e[i].id = -1;
else
e[i].id = pos->se;
// dbg(i, e[i].id);
}
sort(e + 1, e + 1 + m);
int res = 0;
seg.build(1, 1, n);
for (int i = 1; i <= m; ++i)
if (e[i].id != -1) {
int id = e[i].id;
if (seg.query(1, 1, n, 1, id) >= e[i].p) {
++res;
int need = e[i].p;
while (need > 0) {
int pos = seg.queryPos(1, 1, n, 1, id);
if (a[pos] >= need) {
a[pos] -= need;
seg.update(1, 1, n, pos, -need);
need = 0;
} else {
need -= a[pos];
seg.update(1, 1, n, pos, -a[pos]);
a[pos] = 0;
}
}
}
}
printf("%d\n", res);
return 0;
}
K. Road Widening
Solved By Hsueh-. 1:05(+)
题意:
思路:
正着推一遍,倒着推一遍即可。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int n;
ll a[N], b[N], f[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld %lld", a + i, b + i);
f[i] = a[i] + b[i];
}
for (int i = 2; i <= n; ++i) {
f[i] = min(f[i - 1] + 1, f[i]);
}
for (int i = n - 1; i >= 1; --i) {
f[i] = min(f[i + 1] + 1, f[i]);
}
for (int i = 1; i <= n; ++i) {
if (f[i] < a[i]) {
puts("-1");
return 0;
}
}
ll res = 0;
for (int i = 1; i <= n; ++i) {
res += f[i] - a[i];
}
printf("%lld\n", res);
for (int i = 1; i <= n; ++i) {
printf("%lld%c", f[i], " \n"[i == n]);
}
return 0;
}
L. Berland.Taxi
UnSolved.
题意:
思路:
M. Quadcopter Competition
Solved By Dup4. 0:17(+)
题意:
在二维平面上给出一个起点和一个 flag
,然后要求从起点出发绕一圈回来,使得 flag
严格被包含于这个圈子。
思路:
分共线和不共线讨论,其实也可以归并成一条。
Code
#include <bits/stdc++.h>
using namespace std;
int x[2], y[2];
int dis(int x, int y, int x1, int y1) {
return abs(x - x1) + abs(y - y1);
}
int main() {
scanf("%d%d%d%d", x, y, x + 1, y + 1);
int Dis = dis(x[0], y[0], x[1], y[1]);
if (x[0] == x[1] || y[0] == y[1])
printf("%d\n", Dis * 2 + 6);
else
printf("%d\n", Dis * 2 + 4);
return 0;
}
Created: March 27, 2022