Codeforces Round 975 (Div. 2) A~F 题解（Div.1 A~D)
也是补完整场了。
A. Max Plus Size
枚举最大值的位置，使长度最长，更新答案。
B. All Pairs Segments
每个线段内部的点的答案都是一样的，在处理一下线段两边边界的点。被包含次数就是左边 \(\times\) 右边。
用 \(map\) 记录答案即可。
const int N = 2e5+5;
int n,q;
int a[N];
map<ll,ll> mp;
void solve()
{
mp.clear();
cin >> n >> q;
rep(i,1,n) a[i] = rd();
rep(i,1,n)
{
mp[(i-1)*(n-i+1) + (n-i)]++;
}
rep(i,1,n-1)
{
mp[i*(n-i)] += (a[i+1] - a[i]-1);
}
while (q--)
{
ll k = rd();
printf("%lld ",mp[k]);
}
puts("");
}
signed main()
{
int t;cin >> t;
while(t--)
{
solve();
}
return 0;
}
C. Cards Partition
简明题意：你有 \(a_i\) 个数字 \(i\)，可至多新增 \(k\) 个数字，然后把这些数字分成 \(m\) 组，每组所含数字数量相同且数字互不相同，问每组所含数字数量最大值。
观察 \(1\)：\(m \ge max \ a_i\)
观察 \(2\)：当确定 \(m \ge max \ a_i\) 时，且新增个数没有限制时，可以保证构造出一组合法的分组。
构造方法：从 \(a_i\) 大到小，依次填数，填一个就换下一个组，没有下一个就到第一个。因为 \(m \ge max \ a_i\) ，因此这样并不会出现重复。
于是有做法：
枚举每组的大小 \(size\)，算出组数至少为：\(\large max(max\ a_i,\left \lceil \frac{\sum a_i}{size} \right \rceil )\)
在每组大小确定的情况下，此时的组数是最小的可以保证合法的组数，而我们只需要判断 \(m * size - \sum a_i \le k\) 即可。
const int N = 2e5+5;
int n,k,a[N];
int sum;
int mx;
bool check(int x)
{
int chang =(sum+x-1)/x;
chang = max(chang,mx);
return (chang * x - sum) <= k;
}
void solve()
{
cin >> n >> k;
sum = 0,mx = 0;
rep(i,1,n) a[i] = rd(),sum += a[i],mx = max(mx,a[i]);
int ans = 0;
for (int i = 1;i <= n;i++) if (check(i)) ans = i;
printf("%lld\n",ans);
}
signed main()
{
int t;cin >> t;
while(t--)
{
solve();
}
return 0;
}
D. Speedbreaker
感觉是最不太会的一道。
赛时一顿瞎做过了。
一排有 \(n\) 个城市，从左到右编号为 $1, 2, \dots, n $。
- 在时间 \(1\) 时，你正好征服了一座城市，称为起始城市。
- 在时间 \(2, 3, \ldots, n\) 时，你可以选择一个与迄今为止征服的城市相邻的城市并征服它。
如果在每个 \(i\) 中，你在不晚于 \(a_i\) 的时间征服了城市 \(i\) ，那么你就赢了。获胜策略可能存在，也可能不存在，这也取决于起始城市。有多少个起始城市可以让你获胜？
首先有一个贪心策略：每次前往没有访问过的 \(a_i\) 最小的城市。
猜测起始城市是一段区间，发现最小 \(a_i\) 的城市作为起点是最优的，于是在其左右两边二分寻找区间。
但赛时不太会证明答案是一段区间。
根据官方题解，这段区间要么不存在，要么是 \([i-a_i+1,i+a_i-1]\) 的交集。
所以碰巧就做出来了 qwq。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define PII pair<int,int>
#define rep(k,a,b) for (int k = a;k <= b;k++)
#define adde(a,b) v[a].push_back(b)
#define rd read
int read()
{
int f=1,k=0;char c = getchar();
while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();
return k*f;
}
const int N = 2e5+5;
int n,a[N];
int pre[N],suf[N];
bool pd(int st) //贪心策略
{
if (st == 0) return 0;
int l = st,r = st;
int cur = 1;
while (l > 1 || r < n)
{
if (a[pre[l-1]] < a[suf[r+1]])
{
for (int i = l-1;i >= pre[l-1];i--)
{
cur++;
if (a[i] < cur) return 0;
}
l = pre[l-1];
}
else
{
for (int i = r+1;i <= suf[r+1];i++)
{
cur++;
if(a[i] < cur) return 0;
}
r = suf[r+1];
}
}
return 1;
}
void solve()
{
cin >> n;
a[0] = a[n+1] = INF;
int mink = -1;
rep(i,1,n)
{
a[i] = rd();
if (mink == -1 || a[mink] > a[i]) mink = i;
}
rep(i,0,n+2) pre[i] = suf[i] = 0;
// memset(pre,INF,sizeof pre);
// memset(suf,INF,sizeof suf);
rep(i,1,n)
{
pre[i] = pre[i-1];
if ( pre[i-1] == 0 || a[i] < a[pre[i-1]]) pre[i] = i;
}
for (int i = n;i >= 1;i--)
{
suf[i] = suf[i+1];
if (suf[i+1] == 0 || a[i] < a[suf[i+1]] ) suf[i] = i;
}
if (!pd(mink)) puts("0");
else
{
int ans = 0;
int l = 0,r = mink;
while (l < r)
{
int mid = l + r >> 1;
if (pd(mid)) r = mid;
else l = mid + 1;
}
ans += mink-l;
l = mink,r = n;
while (l < r)
{
int mid = l + r+1 >> 1;
if (pd(mid)) l = mid;
else r = mid-1;
}
ans += l-mink;
ans++;
cout << ans << endl;
}
}
int main()
{
int t;cin >> t;
while(t--)
{
solve();
}
return 0;
}
E. Tree Pruning
先开的这道再开的 \(E\)。
比 \(C,D\) 简单。
题意：一次操作是每次删除一个叶子，问最少进行多少次操作使得所有叶子与根距离相同。
这题很一眼啊，题中的距离其实就是深度，枚举深度，统计一下删除了多少点就做完了。
const int N = 5e5+5;
vector<int> v[N];
int mxp[N],cntp[N];
int dep[N];
bool leaf[N];
int mxdep[N];
int maxn;
void dfs(int x,int fa)
{
dep[x] = dep[fa] + 1;
maxn = max(maxn,dep[x]);
mxdep[x] = dep[x];
for (auto y : v[x])
{
if (y==fa) continue;
dfs(y,x);
mxdep[x] = max(mxdep[x],mxdep[y]);
}
cntp[dep[x]]++;
mxp[mxdep[x]]++;
}
void solve()
{
int n = rd();
rep(i,1,n) v[i].clear(),mxdep[i] = mxp[i] = cntp[i] = dep[i] = maxn = 0;
rep(i,1,n-1)
{
int x = rd(),y = rd();
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
int cur = 0;
int ans = 0;
for (int i = 1;i <= maxn;i++)
{
cur += cntp[i];
ans = max(ans,cur);
cur -= mxp[i];
}
printf("%d\n",n-ans);
}
int main()
{
int t;cin >> t;
while(t--)
{
solve();
}
return 0;
}
F. Max Plus Min Plus Size
感觉是一道想法很奇妙的题目。
题意：给定 \(a_i\)，选出 \(a_i\) 的子序列 \(b\)，要求其中元素不能相邻，问 \(max \{ \max \ b_i + \min \ b_i + len(b)\}\)
观察 \(1\) ：\(b\) 中必包含 \(max \ a_i\)。
若不包含，可以删除最大值旁边两个数，并将最大值加入，不会使得答案变小。
那我们就可以从大到小枚举最小值，每次将这个值加入，我们会发现此时形成了若干联通块。
而对于每个联通块内部最多可以选 $\left \lceil \frac{size}{2} \right \rceil $ 个。
此时我们还需要保证最大值被选中，于是对于每个联通块维护奇数位是否有最大值，偶数位是否有最大值等。
判断是否可以在子序列长度最长的情况下选中最大值。
若每个联通块都不能做到，那么总答案减 \(1\)。
维护联通块用并查集即可。
这里还有一个小细节，就是需不需要判断最小值有没有选到呢？答案是不需要。因为没有选到最小值的情况已经在上一轮考虑过了，
在当前这轮考虑不优。
const int N = 2e5+5;
int n,a[N];
vector<int> nums;
map<int,vector<int> > pos;
int f[N];
int siz[N];
bool gmax[N][2];
int mxcnt;
int maxn;
int sum;
void init()
{
sum = 0,maxn = 0,mxcnt = 0;
for (int i = 0;i <= n+5;i++) siz[i] = f[i] = gmax[i][0] = gmax[i][1] = 0;
pos.clear(),nums.clear();
}
int find(int x)
{
if (x!=f[x]) f[x] = find(f[x]);
return f[x];
}
int getn(int x)
{
return (siz[x]&1)?gmax[x][1]:(gmax[x][0]|gmax[x][1]);
}
void merge(int x,int y)
{
int fx = find(x),fy = find(y);
sum -= (siz[fx]+1)/2 + (siz[fy]+1)/2;
f[fx] = fy;
int tmp = getn(fx) + getn(fy);
if (siz[fy]&1) gmax[fy][0] |= gmax[fx][1],gmax[fy][1] |= gmax[fx][0];
else gmax[fy][0] |= gmax[fx][0],gmax[fy][1] |= gmax[fx][1];
siz[fy] += siz[fx];
int now = getn(fy);
mxcnt -= (tmp-now);
sum += (siz[fy]+1)/2;
}
void solve()
{
cin >> n;
init();
rep(i,1,n)
{
a[i] = rd();
nums.push_back(a[i]);
pos[a[i]].push_back(i);
maxn = max(maxn,a[i]);
}
sort(nums.begin(),nums.end(),greater<int>());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
int ans = 0;
for (auto num : nums)
{
for (auto x : pos[num])
{
f[x] = x;
siz[x] = 1,sum++;
if (a[x] == maxn) gmax[x][1] = 1,mxcnt++;
if (f[x-1] != 0)
merge(x-1,x);
if (f[x+1] != 0)
merge(x,x+1);
}
ans = max(ans,num + maxn + sum - (mxcnt==0));
}
cout << ans << endl;
}
int main()
{
int t;t = rd();
while(t--)
{
solve();
}
return 0;
}