Codeforces Round 1046
2A
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
void solve() {
int a, b, c, d; cin >> a >> b >> c >> d; c -= a, d -= b;
if ((a + 1) * 2 < b || (b + 1) * 2 < a || (c + 1) * 2 < d || (d + 1) * 2 < c) puts("NO");
else puts("YES");
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T; cin >> T;
while (T --) solve();
return 0;
}
2B
对于每个 \(s_i = 1\) 的位置依次填 \(1 \sim n\)，不合法当且仅当一个长度为 \(k\) 的区间全是 \(s_i = 1\)。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 200010;
int p[N];
void solve() {
int n, k; cin >> n >> k;
string s; cin >> s;
for (int i = 1; i <= n; i ++) p[i] = 0;
for (int i = 0; i < s.size(); i ++) {
int j = i + 1; if (s[i] != '1') continue;
while (j < s.size() && s[j] == '1') j ++;
if (j - i >= k) return puts("NO"), void();
i = j;
}
int cnt = 0;
for (int i = 0; i < n; i ++)
if (s[i] == '1') p[i + 1] = ++ cnt;
for (int i = 1; i <= n; i ++)
if (!p[i]) p[i] = ++ cnt;
puts("YES");
for (int i = 1; i <= n; i ++) printf("%d ", p[i]);
puts("");
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T; cin >> T;
while (T --) solve();
return 0;
}
1A
显然要 DP，设 \(f_i\) 为 \(1 \sim i\) 的答案。
转移分为选 \(i\) 和不选 \(i\) 两种，比较简单。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 200010;
int n, a[N], f[N];
vector<int> cnt[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++) f[i] = 0, cnt[i].clear();
for (int i = 1; i <= n; i ++) {
cnt[a[i]].push_back(i);
if (cnt[a[i]].size() >= a[i]) {
int l = cnt[a[i]].size();
f[i] = max(f[i], f[cnt[a[i]][l - a[i]] - 1] + a[i]);
}
f[i] = max(f[i], f[i - 1]);
}
printf("%d\n", f[n]);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T; cin >> T;
while (T --) solve();
return 0;
}
1B
注意到当我们走到很远的角落时会对固定点产生贡献。
于是先每次跳 \(K\) 走到右上角，在跳到左上角，这样就能得到初始点 \((x, y)\) 的两个方程得到答案。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 200010, K = 1e9;
int n;
struct Point {
int x, y;
} p[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> p[i].x >> p[i].y;
sort(p + 1, p + 1 + n, [&](Point a, Point b) {
return a.x + a.y < b.x + b.y;
});
int ans, ans2, ans3;
cout << "? U " << K << endl;
cin >> ans;
cout << "? U " << K << endl;
cin >> ans;
cout << "? R " << K << endl;
cin >> ans;
cout << "? R " << K << endl;
cin >> ans2;
cout << "? L " << K << endl;
cin >> ans;
cout << "? L " << K << endl;
cin >> ans;
cout << "? L " << K << endl;
cin >> ans;
cout << "? L " << K << endl;
cin >> ans3;
int q1 = ans2 - 4 * K + (p[n].x + p[n].y);
sort(p + 1, p + 1 + n, [&](Point a, Point b) {
return a.x - a.y < b.x - b.y;
});
int q2 = ans3 - 4 * K - (p[1].x - p[1].y);
int x = (q1 - q2) / 2, y = (q1 + q2) / 2;
cout << "! " << x << ' ' << y << endl;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
int T; cin >> T;
while (T --) solve();
return 0;
}
1C
开始神秘起来了。但还是比较简单。
直接计数非常困难，考虑找一些性质。
注意到对于一个环，如果环上有超过一种颜色那一定无解，否则分为环长为奇和偶两种情况。
环长为偶时，任意分割环都会得到两个长度奇偶性相同的链，于是环上的数字只要全部相同即可。若环上全是 \(-1\)，贡献为 \(V\)，否则贡献为 \(1\)。
环长为奇时，要求环上的数字全为 \(0\)，于是当环上的颜色不为 \(0\) 时无解，否则贡献 \(1\)。
然后考虑将整个图划分成一些点双，每个点双内部通过二分图找奇环，如果存在奇环则一圈至少得都是 \(0\)，导致偶环上也只能都是 \(0\)。
二分图染色跑一下即可。
多测一定要正确清空。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 400010, Mod = 998244353;
int n, m, V, a[N];
int dfn[N], low[N], vis[N], bridge[N], b[N], timestamp;
int col[N];
vector<PII> G[N];
vector<int> bcc[N];
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ timestamp;
for (auto [v, id]: G[u]) {
if (!dfn[v]) {
tarjan(v, id);
if (dfn[u] < low[v]) bridge[id] = 1;
low[u] = min(low[u], low[v]);
} else if (id != fa) low[u] = min(low[u], dfn[v]);
}
}
void dfs(int u, int bccid) {
bcc[bccid].push_back(u); vis[u] = 1, b[u] = bccid;
for (auto [v, id] : G[u]) {
if (bridge[id] || vis[v]) continue;
dfs(v, bccid);
}
}
bool dfs2(int u, int c) {
col[u] = c;
for (auto [v, id] : G[u]) {
if (b[v] != b[u]) continue;
if (!col[v]) {
if (!dfs2(v, 3 - c)) return false;
}
else if (col[v] == c) return false;
}
return true;
}
void solve() {
cin >> n >> m >> V; V %= Mod;
for (int i = 1; i <= n; i ++) G[i].clear(), bcc[i].clear();
for (int i = 1; i <= n; i ++) dfn[i] = low[i] = vis[i] = b[i] = col[i] = 0;
for (int i = 1; i <= m; i ++) bridge[i] = 0;
timestamp = 0;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= m; i ++) {
int a, b; cin >> a >> b;
G[a].push_back({b, i}); G[b].push_back({a, i});
}
tarjan(1, 0);
int cnt = 0;
for (int i = 1; i <= n; i ++)
if (!vis[i]) dfs(i, ++ cnt);
int ans = 1;
for (int i = 1; i <= cnt; i ++) {
int c = -1;
for (auto u : bcc[i]) if (a[u] != -1) {
if (c == -1) c = a[u];
else if (c != a[u]) { ans = 0; break; }
}
if (!ans) break;
bool f = dfs2(bcc[i][0], 1);
if (f) ans = 1ll * ans * (c == -1 ? V : 1) % Mod;
else if (c > 0) ans = 0;
if (!ans) break;
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T; cin >> T;
while (T --) solve();
return 0;
}
1D1
还蛮简单的。
首先肯定要用依次全 \(1\) 得到 \(W \in [L, R]\)，然后考虑构造 \(L, 1, L, 2, ..., L, R - L\)，由于 \(L > R - L\)，所以正确性可以保证。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
void solve() {
cout << "? " << 100000 << ' ';
for (int i = 1; i <= 100000; i ++) cout << 1 << ' ';
cout << endl;
int ans; cin >> ans;
if (ans == 1) return cout << "! 100000" << endl, void();
int L = (100000 + ans - 1) / ans, R = (100000 + ans - 2) / (ans - 1) - 1;
if (L == R) return cout << "! " << L << endl, void();
cout << "? " << (R - L) * 2 << ' ';
for (int i = 1; i <= R - L; i ++) cout << L << ' ' << i << ' ';
cout << endl;
cin >> ans;
cout << "! " << R - (ans - R + L) << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T; cin >> T;
while (T --) solve();
return 0;
}
1D2
在 D1 的基础上优化操作长度。显然我们不能直接问 \(1\) 了，考虑问 \(N\) 个 \(B\)。
如果问出来 \(W \in [1, B - 1]\) 就再问 \(B^2\) 个 \(1\)。容易发现对于每个不同的 \(W\) 都给出了不同的答案。
否则我们照样得到了一个区间 \([L, R]\)，推一下式子，令前面得到的答案为 \(r = \lceil \frac{N}{\lfloor \frac{W}{B} \rfloor} \rceil\)。
先令 \(k = \lfloor \frac{W}{B} \rfloor\)，则 \(r - 1 < \frac{N}{k} \leq r\)，从而 \(\lceil \frac{N}{r} \rceil \leq k \leq \lceil \frac{N - 1}{r - 1} \rceil\)。
然后又有 \(Bk \leq W \leq B(k + 1) - 1\)，最后就是 \(W \in [B(\lceil \frac{N}{r} \rceil), B(\lceil \frac{N - 1}{r - 1} + 1\rceil) - 1]\)，即 \(W \in [B(\lfloor \frac{N - 1}{r} \rfloor + 1), B(\lfloor \frac{N - 1}{r - 1} \rfloor + 1) - 1]\)。
然后比较魔怔地调参数，根据官解，应该选择 \(N = 11343, B = 116\)。
浙公网安备 33010602011771号