浙江龙网

  1. 首页 > 生活百科 > >

XXI Open Cup, Grand Prix of Belarus 2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest 题解( 二 )

生活百科

I. Binary Supersonic Utahraptors题意：略

Solution答案恒定不变，签到题
Codeint n,m,k;void solve() {int cnt_y=0,cnt_r=0;cin>>n>>m>>k;for(int i=1,x;i<=n;++i){cin>>x;cnt_y+=(x==0);}for(int i=1,x;i<=m;++i){cin>>x;cnt_r+=(x>0);}cout<
J. Burnished Security Updates题意：略
Solution考虑二分图染色（签到题）
Codeconst int maxn = 3e5 + 100, mod = 1e9 + 7;int n, m, cnt, sz, col[maxn], ok = 1;vector e[maxn];void dfs(int u, int fa, int co) {col[u] = co;if (co == 1) cnt++;sz++;for (int v: e[u]) {if (v == fa) continue;if (col[v] == col[u]) {ok = 0;return;}if (!col[v]) dfs(v, u, -co);}}int main() {cin >> n >> m;for (int i = 1; i <= m; i++) {int u, v;cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}int ans = 0;for (int i = 1; i <= n; i++) {if (!col[i]) {cnt = sz = 0;dfs(i, 0, 1);if (!ok) {cout << -1;return 0;}ans += min(sz - cnt, cnt);}}cout << ans;}
M. Brilliant Sequence of Umbrellas【XXI Open Cup, Grand Prix of Belarus 2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest题解】构造一个长度至少为 $\left \lceil \frac{2}{3}\sqrt{n}\right \rceil $ 的递增数组 ， 使得两两做 $gcd$ 也是递增的 。
Solution由于 $gcd$ 的数组也是递增的，那么要让数组尽可能的长，就要让 $gcd$ 增长的尽可能慢 。
通过打表前面几个数
\[1 \ 2 \ 6 \ 15 \ 35 \ 56 \ 72 \ 99 \\gcd数组:2 \ 3 \ 5 \ 7 \ 8 \ 9 \ 11\]可以发现 \(gcd\) 数组要添加的数，应当是与最后一个和倒数第二个都互质的数，然后原数组就是 \(gcd\) 数组相乘回去
Codetypedef long long ll;const int mod = 998244353;const int N = 1e5 + 10;vector a{1, 2, 6}, g{1, 2, 3};void solve() {ll n;cin >> n;ll k = ceil(2 * sqrt(n) * 1.0 / 3);int cnt = 0;for (int i = 0; i < a.size(); ++i) {if (a[i] <= n) cnt++;if (cnt >= k) break;}if (cnt >= k) {cout << k << '\n';for (int i = 0; i < k; ++i) {cout << a[i] << " \n"[i == k - 1];}} else {cout << "-1\n";}}int main() {ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int t = 1;for (int i = 4; i <= 1e6; ++i) {if (__gcd(g.back(), i) == 1 $&&$ __gcd(g[g.size() - 2], i) == 1) {if (g.back() * i <= 1e12) a.push_back(g.back() * i), g.push_back(i);else break;}}while (t--) {solve();}return 0;}
N. Best Solution Unknown$n$个数，总共进行$n-1$次操作 。每次操作选两个相邻的数 ， 删去较小值 ， 若两数相等，则任意删除其一，留下的数增大$1$ 。问最后有可能剩下的数有哪些，按升序输出下标 。每次随机取比赛，求会有哪些人可能赢
Solution队友：线段树+分治因为本题中删除一个数后会改变相邻关系，所以某一段区间的最大值可以把该区间剩余的数删完的 。那么把当前区间的最大值挑出来加入答案后，会分成左右两个小区间，其各自的区间最大值也是有可能留到最后的，因此可以用分治加线段树维护区间最值来做这题 。
\([1，2，5，3，2]\)，对于这组数来说，最终留下的数一定是5，因为在取出最大值5后，分成了 \([1, 2]\)和$ [3,2]$ 两个区间 ， 但是我们发现两个区间的最大值2和3只能成长到3和4，也就是\([3，5，4]\)，所以无法留到最后 。从这里我们可以发现，对于每个分出来的区间，都会有一个区间下限，如果该区间的最大值在成长之后达不到这个下限 ， 那么这个区间就是无法产生“胜者”的 。
接下来考虑如何获得每个区间的下限 。我们用三元组\({L, R, V}\)来表示\([L, R]\)这段区间的下限值为\(V\)，假设该区间最大值的下标为\(M\)，那对于左区间的下限\(V_1\)来说 ， 不仅要“打败"\(a_M\), 还要在删完右区间后达到\(V\), 只有这样才能继续往大的区间吃 。即\(V_1 = Max(a_M,V+M-R-1)\) 。
Codeint n, a[maxn], maxx[maxn * 4];vector ans;void build(int id, int l, int r) {if (l == r) {maxx[id] = l;} else {build(ls, l, mid);build(rs, mid + 1, r);if (a[maxx[ls]] > a[maxx[rs]])maxx[id] = maxx[ls];elsemaxx[id] = maxx[rs];}}int query(int id, int l, int r, int ql, int qr) {if (ql <= l && qr >= r) return maxx[id];if (qr <= mid)return query(ls, l, mid, ql, qr);else if (ql > mid)return query(rs, mid + 1, r, ql, qr);else {int res1 = query(ls, l, mid, ql, mid);int res2 = query(rs, mid + 1, r, mid + 1, qr);if(a[res1] > a[res2]) return res1;else return res2;}}void solve(int l, int r, int maxx) {int pos = query(1, 1, n, l, r);if(a[pos] + r - l < maxx) return;ans.push_back(pos);if(l <= pos - 1) solve(l, pos - 1, max(a[pos], maxx + pos - 1 - r));if(pos + 1 <= r) solve(pos + 1, r, max(a[pos], maxx + l - pos - 1));}int main() {ios;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];build(1, 1, n);solve(1, n, 0);cout << ans.size() << endl;sort(ans.begin(), ans.end());for (int i : ans) cout << i << " ";}

推荐阅读


上一篇：Div. 2 Codeforces Round #823 A-D

下一篇：工作7年收集到的git命令