A. Access Denied
先问若干次,问出长度,然后再一位一位的问即可。
#include <bits/stdc++.h>
using namespace std;
int input() {
string s;
getline(cin, s);
if (s == "ACCESS GRANTED")
exit(0);
int t = 0;
for (auto i: s) {
if (i >= '0' and i <= '9')
t = t * 10 + i - '0';
}
return t;
}
int32_t main() {
int len = -1;
for (int i = 1, t; len == -1 and i <= 20; i++) {
cout << string(i, '0') << endl << flush;
t = input();
if (t != 5) len = i;
}
vector<char> ans(len), ch;
for (char i = '0'; i <= '9'; i++) ch.push_back(i);
for (auto i = 'a'; i <= 'z'; i++) ch.push_back(i);
for (auto i = 'A'; i <= 'Z'; i++) ch.push_back(i);
for (int i = 0, t; i < len; i++) {
for (auto c: ch) {
for (int j = 0; j < i; j++)
cout << ans[j];
for (int j = i; j < len; j++)
cout << c;
cout << endl << flush;
t = input();
if (t == 5 + (i + 1) * 9) continue;
ans[i] = c;
break;
}
}
for( auto i : ans )
cout << i;
cout << endl << flush;
return 0;
}
D. Dyson Circle
首先按照题目的要求,我们可以把戴森环的凹陷部分展开,这样的戴森环就变成了一个矩形。那么对于矩形,我们让边全部在对角线方向最优,所以就要找到主副对角线的边界。如果某对角线方向长度只有 1 的话不符合题目的要求,因为题目要求内点的连通是有边相邻。
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, a = INT_MIN, b = INT_MIN, c = INT_MAX, d = INT_MAX;
cin >> n;
if (n == 1) cout << "4\n", exit(0);
for (int x, y; n; n--) {
cin >> x >> y;
a = max(a, x + y);
b = max(b, x - y);
c = min(c, x + y);
d = min(d, x - y);
}
cout << 4 + a + b - c - d + (a == c) + (b == d) << "\n";
return 0;
}
G. Glossary Arrangement
#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, w;
cin >> n >> w;
vector<string> s(n);
for (auto &i: s) cin >> i;
vector<int> f(n + 1);
auto dp = [n, w, s, &f](int h) {
f.assign(n + 1, w + 1);
f[0] = -1;
for (int i = 0, mx; i < n; i++) {
mx = 0;
for (int j = i; j < n and j < i + h; j++) {
mx = max(mx, int(s[j].size()));
f[j + 1] = min(f[j + 1], f[i] + mx + 1);
}
}
return f[n];
};
int l = 1, r = n, h = -1;
for (int mid; l <= r;) {
mid = (l + r) / 2;
if (dp(mid) <= w) h = mid, r = mid - 1;
else l = mid + 1;
}
cout << h << " ";
vi v;
dp(h);
for (int i = n, j, mx; i;) {
j = i, mx = 0;
do {
j--;
mx = max(mx, int(s[j].size()));
} while (f[i] != f[j] + mx + 1);
v.push_back(mx), i = j;
}
reverse(v.begin(), v.end());
cout << v.size() << "\n";
for (auto i: v) cout << i << " ";
cout << "\n";
vector<string> res(h);
for (int i = 0, k = 0; i < v.size(); i++) {
for (int j = 0; j < h; j++) {
if (i) res[j] += " ";
string t;
if (k < n and s[k].size() <= v[i]) t = s[k++];
t.resize(v[i], ' ');
res[j] += t;
}
}
for (auto i: res)
cout << i << "\n";
return 0;
}
H. Heating Up
初始的辣度满足单调性,因此我们可以用二分答案。
有了初始辣度后,要考虑的就是如何把所有的披萨吃完,首先破环成链,然后从头开始枚举,如果可以吃就直接吃,否则就把这片披萨放进栈里,并且还原耐辣值。同时每次耐辣值上升后,都重新判断一下栈顶的披萨是否可以被吃下。
#include <bits/stdc++.h>
using namespace std;
#define int __int128
using ll = long long;
using pii = pair<int, int>;
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
constexpr int inf = 1e15;
int32_t main() {
int n = read();
vector<int> a(n + n + 1);
for (int i = 1; i <= n; i++)
a[i + n] = a[i] = read();
n = n * 2;
auto check = [a, n](int x) -> bool {
int tot = x;
stack<pii> stk;
for (int i = 1; i <= n; i++) {
if (a[i] <= tot) {
tot += a[i];
while (!stk.empty() and stk.top().first <= tot) {
tot += stk.top().second;
stk.pop();
}
} else {
stk.emplace(a[i], tot - x + a[i]);
tot = x;
}
}
return stk.empty();
};
int l = 0, r = inf, res = -1;
for (int mid; l <= r;) {
mid = (l + r) / 2;
if (check(mid)) res = mid, r = mid - 1;
else l = mid + 1;
}
cout << (ll) res << "\n";
return 0;
}
J. Jet Set
维度是没有用的。
如果在单次飞行中跨过的180 度,则一定是可行的。
否则,根据题目的要求,飞行过程中经过的经度实际上是确定的。我们只要标记即可。
最后判断有无没有被标记的点的即可。
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
int n;
cin >> n;
vector<int> a(n + 2), v(720);
for (int i = 1, x; i <= n; i++) {
cin >> x >> a[i];
a[i] = (a[i] + 180) * 2;
}
a[n+1] = a[1];
for (int i = 2, x, y; i <= n+1; i++) {
x = a[i - 1], y = a[i];
if (x > y) swap(x, y);
if (y - x == 360) cout << "yes\n", exit(0);
if (y - x < 360) {
for (int j = x; j <= y; j++) v[j] = 1;
} else {
for (int j = 0; j <= x; j++) v[j] = 1;
for (int j = y; j < 720; j++) v[j] = 1;
}
}
for( int i = 0 ; i < 720 ; i ++ )
if( v[i] == 0 ) cout << "no " << fixed << setprecision(1) << (0.5*i) - 180.0 << "\n", exit(0);
cout << "yes\n";
return 0;
}
K. Knitpicking
我们先尽可能的按照无法配对的情况去选择,最后在任意选一个即可配对,除非已经把所有的袜子全部选完。
如果袜子是任意的,则只有当无左无右的情况下,才能选择一个。否则要选择左右的较大值。
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const int N = 110;
void solve() {
int n;
cin >> n;
map<string, array<int, 3> > mp;
int z = 0;
for (int i = 0; i < n; ++i) {
string a, b;
int x;
cin >> a >> b >> x;
if (b == "left") {
mp[a][0] += x;
} else if (b == "right") {
mp[a][1] += x;
} else {
mp[a][2] += x;
}
}
int res = 0, mark = 0;
for (auto X: mp) {
string a = X.first;
z += mp[a][0] + mp[a][1] + mp[a][2];
if (mp[a][0] == 0 && mp[a][1] == 0 && mp[a][2] > 0) res += 1;
else res += max(mp[a][0], mp[a][1]);
}
if (res != z) {
cout << res + 1 << '\n';
} else cout << "impossible\n";
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1;
while (_--) {
solve();
}
return 0;
}
- 2021 Northwestern Programming European Regional2021 northwestern programming european 2019 northwestern programming european programming acm-icpc american regional programming shenyang regional contest programming regional contest 2023 programming hangzhou regional contest regional contest macau 2021 programming regional yinchuan contest programming regional contest aefhkl programming stormwind shenyang regional