当前位置：首页 > news >正文

Codeforces Round 965 (Div. 2)

news 来源：原创 2024/9/20 18:48:15

前言

有人在过七夕，我在打 cf ，还有某人独自一人在学校机房，凌晨一点骑上共享单车回宿舍欣赏沿途的秋风扫落叶。

Standings：2166

题目链接：Dashboard - Codeforces Round 965 (Div. 2) - Codeforces

A. Find K Distinct Points with Fixed Center

题意：

给一个点（x,y），要求构造 k 个点使得这 k 个点的中心是（x,y）。

思路：

分奇偶讨论，两两对应即可。

#include<cstdio>
#include<cstring>
using namespace std;int T,x,y,k;int main()
{scanf("%d",&T);while (T --){scanf("%d%d%d",&x,&y,&k);if(k & 1){printf("%d %d\n",x,y);for (int i = 1;i <= k / 2;++ i) printf("%d %d\n%d %d\n",x + i,y + i,x - i,y - i);}else{for (int i = 1;i <= k / 2;++ i) printf("%d %d\n%d %d\n",x + i,y + i,x - i,y - i);}}return 0;
}

B. Minimize Equal Sum Subarrays

题意：

给你一个 1 ~ n 的排列 p ，你需要构造出一个新的 1 ~ n 的排列 q ，使得满足条件的（i , j）对的数目最小：

$p_i+p_{i+1}+...+p_j=q_i+q_{i+1}+...+q_j$

思路：

只要使每一位的前缀和不一样即可，其实整体往右挪一位就是答案。

比赛时打得太丑，才知道 vector 的 erase 复杂度是 O（n）的，过 B 的时候就已经心态崩了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;#define N 200005int T,n,fst;
long long sum[N],a[N],b[N],pre[N],las[N],now;int main()
{scanf("%d",&T);while (T --){scanf("%d",&n),sum[0] = now = 0ll;for (int i = 1,x;i <= n;++ i)scanf("%lld",&a[i]),sum[i] = sum[i - 1] + a[i],b[i] = 0,pre[i] = i - 1,las[i] = i + 1;fst = 1;for (int i = 1;i <= n;++ i){if(i == n || (now + a[fst] != sum[i])){b[i] = a[fst];now += b[i];fst = las[a[fst]];}else{b[i] = a[las[fst]];now += b[i];las[fst] = las[las[fst]];}}for (int i = 1;i <= n;++ i) printf("%lld ",b[i]);printf("\n");}return 0;
}

C. Perform Operations to Maximize Score

题意：

给一个序列 a 和一个 01 串 b ，可以进行 k 次操作，每次操作可以让 b 中为 1 的某一位对应的 a 加上一，求 k 次操作之后以下值的最大值：

$max_{i=1}^n(a_i + median(c_i))$

其中 $c_i$ 表示序列 a 挖去 $a_i$ 之后的序列，median 表示中位数。

思路：

可以分 $b_i$ = 0 和 $b_i$ = 1 讨论。

1. $b_i$ = 1 的情况：显然让 k 次操作都加在 $a_i$ 上最优，O（n）扫一遍即可。

2. $b_i$ = 0 的情况：发现最大的那个 $a_i$ 能得到最大的贡献，于是我们只用考虑挖去最大的 $a_i$ 后的序列，让它的中位数尽可能大即可。我们可以二分中位数的值，再判断是否合法即可。

好在是压线调出来了，以致于没有掉大分。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;#define N 200005int T,n,mid,m;
long long k,ans,mx1,mx2;struct Node
{int val,b;
}a[N],c[N];long long max(long long x,long long y) { return x > y ? x : y ; }int cmp(Node x,Node y) { return x.val < y.val ; }int check(int x)
{int tmp = m - mid + 1;int fl = m;for (int i = m; i ;-- i)if(c[i].val >= x) -- tmp,fl = i - 1;else break;if(tmp <= 0) return 1;int now = k;for (int i = fl; i ;-- i){if(c[i].b) now -= x - c[i].val,-- tmp;if(now <= 0 || tmp <= 0) break;}if(now < 0) return 0;if(tmp <= 0) return 1;return 0;
}int main()
{scanf("%d",&T);while (T --){scanf("%d%lld",&n,&k),ans = a[n + 1].val = 0ll;mid = n / 2;for (int i = 1;i <= n;++ i){scanf("%lld",&a[i].val);if(a[i].val >= mx1) mx2 = mx1,mx1 = a[i].val;}for (int i = 1;i <= n;++ i) scanf("%d",&a[i].b);sort(a + 1,a + n + 1,cmp);int bz = 0;for (int i = 1;i <= n;++ i)if(a[i].b){int tp;if(i <= mid) tp = a[mid + 1].val;else tp = a[mid].val;ans = max(ans,a[i].val + k + tp);}else{bz = i;}if(bz){m = 0;for (int i = 1;i <= n;++ i)if(i != bz) c[++ m].b = a[i].b,c[m].val = a[i].val;ans = max(ans,a[bz].val + c[mid].val);int l = c[mid].val;int r = 1e9;while (l <= r){int md = (l + r) >> 1;if(check(md)) l = md + 1,ans = max(ans,a[bz].val + md);else r = md - 1;}}printf("%lld\n",ans);}return 0;
}

D. Determine Winning Islands in Race

题意：

给 n 座岛屿，第 i 座和第 i + 1 座之间有一座桥（基础桥），除此之外还有若干座桥（附加桥），所有桥都是单向的且由标号小的岛屿指向标号大的岛屿。最初，Elsie 在 1 号岛屿，Bessie 在 s 号岛屿，他们都需要前往 n 号岛屿；Bessie 只能走基础桥，而 Elsie 可以走附加桥。

由 Bessie 率先开始，每一轮这个人都可以走一条存在的桥，然后他原先所在的岛屿立刻坍塌，这意味着所有与原先岛屿相连的桥也同时坍塌；如果当前无路可走，则这个人终止在这个岛屿。

两个人都采取最优策略，对于每个 $s\in[1,n-1]$ ，判断 Bessie 能否到达 n 号岛屿。

思路：

假设有一座 u -> v 的桥，若 E 可以通过这段桥超过 B ，则必须要满足一下条件：

1. u < s

2. v - s > t （t 是 A 到达 v 所用的最快时间）

即 $s \in [u+1,v-t-1]$

用 BFS 求出 A 到每个点的最短时间，再用差分数组统计贡献即可。

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;#define N 200005int T,n,m,cnt,st[N],dis[N],vis[N],dif[N];struct Edge
{int next,to;
}ed[N << 1];queue<int> q;void add(int u,int v)
{ed[++ cnt].next = st[u];ed[cnt].to = v;st[u] = cnt;return;
}void bfs()
{while (!q.empty()) q.pop();	q.push(1),vis[1] = 1;while (!q.empty()){int x = q.front();q.pop(),vis[x] = 0;for (int i = st[x]; ~i ;i = ed[i].next){int rec = ed[i].to;if(dis[x] + 1 < dis[rec]){dis[rec] = dis[x] + 1;if(!vis[rec]) q.push(rec),vis[rec] = 1;}int l = x + 1;int r = rec - (dis[x] + 1) - 1;if(l <= r) ++ dif[l],-- dif[r + 1];}}return;
}int main()
{scanf("%d",&T);while (T --){scanf("%d%d",&n,&m),cnt = 0;for (int i = 1;i <= n;++ i) st[i] = -1,dis[i] = n + 1,vis[i] = dif[i] = 0;dis[1] = dif[0] = 0;for (int i = 1;i < n;++ i) add(i,i + 1);for (int i = 1,u,v;i <= m;++ i) scanf("%d%d",&u,&v),add(u,v);bfs();for (int i = 1;i < n;++ i) dif[i] += dif[i - 1],printf("%d",(dif[i]) ? 0 : 1);printf("\n");}return 0;
}

E1. Eliminating Balls With Merging (Easy Version)

题意：

给一行小球，每个小球上面都标有一个分值，小球可以通过向左右吃掉分值小于等于自己的球，并加上所吃小球的分值。问有多少个小球有可能成为最后剩下的那个小球。

思路：

Easy Version 我们可以利用贪心，按分值从大到小将球排序，从大球到小球进行处理。我们用单调栈记录一下每个小球左右两边第一个比它大的小球，分别记作 l 和 r 。容易发现，如果 l 或者 r 能成功留下，且当前小球可以吃掉它，那么当前小球一定可以成功留下，反之不行。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;#define N 200005int T,n,k,l[N],r[N],f[N],mx,ans;
long long a[N],pre[N];struct Node
{long long val,id;
}b[N];stack<int> q;int cmp(Node x,Node y) { return x.val > y.val ; }long long max(long long x,long long y) { return x > y ? x : y ; }int main()
{scanf("%d",&T);while (T --){scanf("%d%d",&n,&k),pre[0] = f[0] = f[n + 1] = mx = ans = 0;for (int i = 1;i <= n;++ i){scanf("%lld",&a[i]);b[i].id = i,b[i].val = a[i],f[i] = 0,mx = max(mx,a[i]),pre[i] = pre[i - 1] + a[i];}for (int i = 1;i <= n;++ i) f[i] = (a[i] == mx);sort(b + 1,b + n + 1,cmp);while (!q.empty()) q.pop();q.push(0),a[0] = 1e9 + 1ll;for (int i = 1;i <= n;++ i){while (!q.empty() && a[i] >= a[q.top()]) q.pop();l[i] = q.top();q.push(i);}while (!q.empty()) q.pop();q.push(n + 1),a[n + 1] = 1e9 + 1ll;for (int i = n; i ;-- i){while (!q.empty() && a[i] >= a[q.top()]) q.pop();r[i] = q.top();q.push(i);}for (int i = 1;i <= n;++ i){if(b[i].val == mx) continue;int now = b[i].id;long long sum = pre[r[now] - 1] - pre[l[now]];if(sum >= a[l[now]]) f[now] |= f[l[now]];if(sum >= a[r[now]]) f[now] |= f[r[now]];}for (int i = 1;i <= n;++ i) ans += f[i];printf("%d\n",ans);}return 0;
}

E2. Eliminating Balls With Merging (Hard Version)

题意：

Hard Version 唯一的区别就是给出一个 x ，对于所有 $i\in[x,n]$ ，都要统计子序列 1 ~ i 的 Easy Version 的问题。

思路：

按 Easy Version 的做法肯定会超时，我们试试 “返璞归真” ，回归最原始易得的想法。

对于某个球 i 要是想留下来，就一定要把 1 ~ i - 1 都吃掉，那么我们可以计算想要把 1 ~ i - 1 都吃掉，至少需要往右吃到的位置 minr ；再根据已经把 1 ~ i - 1 都吃掉的情况下，至多往右吃到的位置 maxr 。那么球 i 对答案的贡献区间就是 [minr , maxr] ，用差分数组标记即可。

对于求 minr 和 maxr 的过程，可以用 ST 表 + 二分做，循环判断向左最多吃到哪，和向右最优吃到哪，如果吃不动就跳出。这样是不会超时的，因为每次吃到卡住的地方都说明那个位置的分值比你目前拥有的一段区间的分值之和要大，也就是说每一次扩散都会让你手上的值至少翻倍，因此这一过程的复杂度是 log(最大分值) 的。

#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;#define N 200005int T,n,p,lg[N],dif[N];
long long a[N],pre[N],f[N][22];stack<long long> st;long long max(long long x,long long y) { return x > y ? x : y ; }void RMQ()
{for (int i = 1;i <= lg[n];++ i)for (int j = 1;j + (1 << i) - 1 <= n;++ j)f[j][i] = max(f[j][i - 1],f[j + (1 << (i - 1))][i - 1]);return;
}int getMINR(int x)
{int tl,tr;tl = tr = x;while (tl > 1){int ml = 1;int mr = tl - 1;int now = tl;long long sum = pre[tr] - pre[tl - 1];int mid,len;while (ml <= mr){mid = (ml + mr) >> 1;len = tl - mid;long long mx = max(f[mid][lg[len]],f[tl - (1 << lg[len])][lg[len]]);if(sum >= mx) now = mid,mr = mid - 1;else ml = mid + 1;}if(tl > 1 && tl == now){ml = tr + 1;mr = n;now = tr;sum = pre[tr] - pre[tl - 1];while (ml <= mr){mid = (ml + mr) >> 1;len = mid - tr;long long mx = max(f[tr + 1][lg[len]],f[mid - (1 << lg[len]) + 1][lg[len]]);if(sum >= mx && sum + pre[mid] - pre[tr] >= a[tl - 1]) now = mid,mr = mid - 1;else if (sum >= mx) now = mid,ml = mid + 1;else mr = mid - 1;}if(now == tr){tr = -1;break;}else tr = now;}else tl = now;}return tr;
}int getMAXR(int x)
{while (x < n){int ml = x + 1;int mr = n;int now = x;long long sum = pre[x];while (ml <= mr){int mid = (ml + mr) >> 1;int len = mid - x;long long mx = max(f[x + 1][lg[len]],f[mid - (1 << lg[len]) + 1][lg[len]]);if(sum >= mx) now = mid,ml = mid + 1;else mr = mid - 1;}if(now == x) break;x = now;}return x;
}int main()
{lg[1] = 0;for (int i = 2;i <= 200000;++ i) lg[i] = lg[i >> 1] + 1;scanf("%d",&T);while (T --){scanf("%d%d",&n,&p),pre[0] = 0ll,a[0] = a[n + 1] = 1e9 + 1,dif[0] = 0;for (int i = 1;i <= n;++ i)scanf("%lld",&a[i]),f[i][0] = a[i],pre[i] = pre[i - 1] + a[i],dif[i] = 0;RMQ();for (int i = 1;i <= n;++ i){int mnr = getMINR(i);if(mnr == -1) continue;int mxr = getMAXR(i);++ dif[mnr],-- dif[mxr + 1];}for (int i = 1;i <= n;++ i){dif[i] += dif[i - 1];if(i >= p) printf("%d ",dif[i]);}printf("\n");}return 0;
}