250813 模拟赛
给定一个长度为 \(n\)（\(n\) 是奇数）的序列，你可以进行 \(\frac{n-1}2\) 次操作，将序列删为只剩一个数。每次操作你选择序列中一个数字（不能是开头结尾），然后将它相邻两个数字删掉。一个数字被删掉后，两侧的数字变为相邻。操作的价值定义为你选择的数字大小。问操作价值最小值的最大值。
\(n\le 2\times 10^6,\ 1\le a_i\le 10^9\)
考虑二分答案，问题转化为：序列上一些数字被标记为 \(1\)，你只能对标记为 \(1\) 的位置进行操作，问能否将所有 \(0\) 都删去。
不断操作序列中心的位置是平凡的，先特判掉。我们考虑经典思路：一次操作最优删掉两个 \(0\)，而一次操作不可能同时删去同一个连续段内的两个 \(0\)，因此操作总次数不小于最长 \(0\) 连续段，因此 \(0\) 连续段的长度不能超过最多操作次数 \(\frac{n-3}2\)（\(1\) 的数量大于一个，将连续段删空之后至少还要再删一次，所以要减一）。
尝试构造并证明上面的条件是充要的。假设最后一次操作的数字在初始时位于下标 \(x\)，不妨设 \(x\) 在序列左半段。如果我们能删去 \([x+1,n]\) 中的 \(n-2x-1\) 个数字，那么然后我们只需要一直操作 \(x\) 即可。假设我们在右边区间内一直操作一个下标 \(y\)，那么 \(y\) 需要满足 \(y\ge x+\frac{n-2x+1}2\) 且 \(y\le n-\frac{n-2x-1}2\)。其中第一个条件等价于 \(y\) 要在序列的右半区间内，第二个条件等价于 \(y\) 和 \(x\) 之间的间隔不超过 \(\frac{n-3}{2}\)。两个条件等价于序列中点所在的连续段长度不超过 \(\frac{n-3}{2}\)。
最长连续段是容易 \(O(n)\) 求出的。时间复杂度 \(O(n\log V)\)。
代码
| #include<iostream>
using namespace std;
const int N = 2e6 + 10;
int T, n;
int a[N];
bool check(int mid) {
int pre = 0;
for(int i = 1; i <= n + 1; i++) {
if(a[i] < mid) continue;
if(i - pre - 1 > (n - 3) / 2) return false;
pre = i;
}
return true;
}
int main() {
freopen("largenumber.in", "r", stdin);
freopen("largenumber.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while(T--) {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
a[n + 1] = 1e9 + 20;
int l = 1, r = 1e9 + 10;
while(l < r) {
int mid = (l + r + 1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
l = max(l, a[(n + 1) / 2]);
cout << l << '\n';
}
return 0;
}
|
T2
状压板子，没动脑子写了个 \(32\times nm\) 的做法，据说可以 \(4\times nm\)。
给定一个简单无向图和其上的一个节点 \(t\)，请你判定它是否存在一个子图（原图点集和边集各选出一个子集，边集必须是导出子图边集的子集）满足：
- 与 \(t\) 相连的边都在该子图内；
- 该图存在一条欧拉路径满足 \(t\) 是起点（终点）；
\(n,m\le 10^6\)
先把原图上和 \(t\) 不在同一连通块的节点删掉。分讨 \(t\) 度数的奇偶性。若 \(deg[t]\) 是偶数，等价于需要把 \(t\) 的邻居两两匹配，满足匹配双方存在一条简单路径（不能经过 \(t\)），并且路径之间没有公共边。
发现如果 \(t\) 的一个儿子连通块中包含奇数个 \(t\) 的邻居，那么无解。剩下的构造部分其实很容易，考虑每个儿子连通块的一棵生成树，然后任意匹配连通块内 \(t\) 的邻居，将匹配双方路径上的边全都 flip 即可。
若 \(deg[t]\) 是奇数，任意选择一个包含奇数邻居的连通块，然后再任选其中的一个邻居作为起点，删掉它，就和偶数的情况一样了。
代码
| #include<iostream>
using namespace std;
const int N = 1e6 + 10;
struct Edge {
int v, next;
} pool[2 * N];
int ne, head[N];
void addEdge(int u, int v) {
pool[++ne] = {v, head[u]};
head[u] = ne;
}
int T;
int n, m, s, t;
int tag[N], cnt;
int d[N], vis[N];
int ans[N], top;
bool flag;
namespace G2 {
Edge pool[2 * N];
int ne, head[N];
void addEdge(int u, int v) {
pool[++ne] = {v, head[u]};
head[u] = ne;
}
void clear() {
for(int i = 0; i <= n; i++) head[i] = 0;
ne = 1;
}
}
void clear() {
for(int i = 0; i <= n + 5; i++) head[i] = tag[i] = d[i] = vis[i] = 0;
ne = cnt = 0;
flag = true;
G2::clear();
}
int dfs1(int u) {
vis[u] = 1;
int res = tag[u];
for(int e = head[u]; e; e = pool[e].next) {
int v = pool[e].v;
if(vis[v] || v == t) continue;
res += dfs1(v);
}
return res;
}
void dfs2(int u, int fa) {
vis[u] = 1;
for(int e = head[u]; e; e = pool[e].next) {
int v = pool[e].v;
if(vis[v] || v == t) continue;
dfs2(v, u);
d[u] ^= d[v];
}
if(d[u]) {
if(!fa) flag = false;
else G2::addEdge(u, fa), G2::addEdge(fa, u);
}
}
void dfs3(int u) {
for(int e = G2::head[u]; e; e = G2::pool[e].next) {
int v = G2::pool[e].v;
if(!v) continue;
G2::pool[e].v = 0;
G2::pool[e ^ 1].v = 0;
dfs3(v);
}
ans[++top] = u;
}
int main() {
freopen("walk.in", "r", stdin);
freopen("walk.out", "w", stdout);
cin >> T;
while(T--) {
cin >> n >> m >> t;
s = t;
clear();
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
addEdge(u, v);
addEdge(v, u);
}
for(int e = head[t]; e; e = pool[e].next) {
int v = pool[e].v;
G2::addEdge(t, v);
G2::addEdge(v, t);
tag[v] = d[v] = 1;
++cnt;
}
if(cnt & 1) {
for(int e = head[t]; e; e = pool[e].next) {
int v = pool[e].v;
if(vis[v]) continue;
if(dfs1(v) & 1) { s = v; break; }
}
d[s] = 0;
}
for(int i = 0; i <= n + 5; i++) vis[i] = 0;
for(int e = head[t]; e && flag; e = pool[e].next) {
int v = pool[e].v;
if(!vis[v]) dfs2(v, 0);
}
if(!flag) { cout << -1 << '\n'; continue; }
top = 0;
dfs3(s);
cout << top << ' ';
for(int i = top; i >= 1; i--) cout << ans[i] << ' ';
cout << '\n';
}
return 0;
}
|
T4
整体二分 / 树套树板子。multiset 的 erase 又忘了套 find，挂成 85 分。