2025年5月2日CF补题
Codeforces Round 1022 (Div. 2) 补题
此次排名情况：
- 共8k+，排名3037，做出ABC三题。
- Rating+35，当前为
1361。 - 比赛链接
A. Permutation Warm-Up
题意：给定一个数字 \(n\) ，求 \(1\sim n\) 的所有排列与 \(1 \sim n\) 差值的和的不同数量。
赛时我通过部分样例总结规律，得出会 \(1,1,2,2,3,3,...\) 的差值往下增加。
于是先预处理，然后输出。
vector<int> vt(510);
void init(){
vt[0]=0;
vt[1]=1;
for(int i=2,j=1;i<=500;i++){
vt[i]=vt[i-1]+j;
if(i%2) j++;
}
}
void solve(){
cin>>n;
cout<<vt[n]<<"\n";
}
部分大佬题解：
对于一个 \(p_i=i\) 的排列，我们可以通过不断交换两个位置的数把它变成任意排列。
发现每次交换两个数增加的值是偶数，那么最后和的值只会是偶数。
然后猜测所有偶数都可以拿到。那么求出最大的值看有多少偶数。
最大的值为最后一个排列的差，即 \(n,n-1,....,1\) 与 \(1,2,...,n\) 的差。
void solve() {
int n;cin >> n;
int ans = 0;
for (int i = 1; i <= n; ++ i) {
ans += abs(i - (n - i + 1));
}
cout << ans / 2 + 1 << "\n";
}
还有一种写法没看懂：
void solve(){
int n;cin >> n;
int res = 0;
for (int i = 1; i < n; i++)
res += min(i, n - i);
cout << res + 1 << '\n';
}
B. SUMdamental Decomposition
题意：构造一个长度为 \(n\) 的正整数数组，数组元素全部异或结果为 \(x\) ，求这个数组的和最小是多少。
两个数异或为 \(0\) 不会对结果造成任何影响，当都取 \(1\) 时结果最小。
我们可以看 \(x\) 有多少个 \(1\)，如果 \(n\) 大于这个数，就需要将多余的变成 \(0\)。小于或等于的直接就是 \(x\) 。可以采用新学的 bitset 来判断有多少个 \(1\) 。
一直错test2的测试点，特判 \(m=0\) 和 \(m=1\) 过了。
void solve(){
cin>>n>>m;
if(n==1&&m==0){
cout<<"-1\n";
return;
}
if(n==2&&m==1){
cout<<"5\n";
return ;
}
if(m==0){
if(n%2==0) cout<<n<<"\n";
else cout<<5+n-2<<"\n";
return ;
}
if(m==1){
if(n%2==1) cout<<n<<"\n";
else cout<<5+n-2<<"\n";
return ;
}
bitset<33> b(m);
int z=b.count();
ll sum=0;
if(n>=z){
if((n-z)%2==1){
if(m%2==1){
sum=m+n-z+1;
}
else sum=m+n-z+1;
}
else sum=m+n-z;
}else{
sum=m;
}
cout<<sum<<"\n";
}
部分大佬题解：
不需要 bitset ，直接使用内置函数 __builtin_popcount(x) 返回 \(1\) 的个数。
for(int t = rd();t--;){
int n = rd(),x = rd(),v = __builtin_popcount(x);
if(n <= v)printf("%d\n",x);
else if((n-v)%2==0)printf("%d\n",x+n-v);
else if(x > 1)printf("%d\n",x+n-v+1);
else if(x == 1)printf("%d\n",n+3);
else printf("%d\n",n>1?n+3:-1);
}
C. Neo’s Escape
题意：给定一个数组 \(a\) ，需要按大小顺序遍历所有元素，可以新建一个克隆人在一个元素前面，也可以让现有的克隆人左右移动，但是移动到某个元素，若该元素为遍历则直接遍历。最小新建克隆人数量是多少？
不要被题目带偏，说是要按大小顺序遍历所有元素，并且克隆人可以左右移动。
本质上这题目就是在统计数组 \(a\) 的峰的数量。
int n;cin >> n;
vector<int> a(n);
for (int i=0;i<n;i++) cin >> a[i];
ll ans=1;
bool d=0;
for(int i=1;i<n;i++){
if(d==0&&a[i-1]>a[i]) d=1;
else if(d==1&&a[i-1]<a[i]){
ans++;
d=0;
}
}
cout<<ans<<"\n";
D. Needle in a Numstack
题意：交互题。给定 \(n\) 和 \(k\) ，有两个数组 \(A\) 和 \(B\) ，有几个条件
- 两个数组长度之和是 \(n\)。
- 两个数组的长度都至少为 \(k\)。
- 数组中只包含从 \(1 \sim k\) 的数字。
- 从 \(A\) 中任意取出 \(k\) 个连续元素，每个元素都是不同的，B也同样。
现在将 \(C\) 数组等于数组 \(A\) 加上数组 \(B\)，即 \(C=A_1,...,A_x,B_1,...,B_y\)。
你可以提出问题询问 \(C\) 数组中第 \(i\) 个元素的值，请你找出数组 \(A\) 和数组 \(B\) 的长度，或者无法唯一确定长度。
CF大佬代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int T,n,k,a[N],b[N];
vector<int> p;
void solve(){
if(n==2*k){
cout<<'!'<<' '<<k<<' '<<k<<"\n";
return;
}
if(p.empty()){
cout<<'!'<<' '<<-1<<"\n";
return;
}
int l=0,r=p.size()-1,res;
cout<<'?'<<' '<<p[0]<<"\n";
cin>>res;
if(res==b[p[0]]){
if(p[0]==k+1) cout<<'!'<<' '<<k<<' '<<n-k<<"\n";
else cout<<'!'<<' '<<-1<<"\n";
return;
}
while(l<r){
int mid=l+r+1>>1;
cout<<'?'<<' '<<p[mid]<<"\n";
cin>>res;
if(res==a[p[mid]]) l=mid;
else r=mid-1;
}
if(r==p.size()-1){
if(p[r]==n-k) cout<<'!'<<' '<<n-k<<' '<<k<<"\n";
else cout<<'!'<<' '<<-1<<"\n";
return;
}
if(p[r]+1==p[r+1]) cout<<'!'<<' '<<p[r]<<' '<<n-p[r]<<"\n";
else cout<<'!'<<' '<<-1<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>T;
while(T--){
cin>>n>>k;
for(int i=1;i<=k;++i) cout<<'?'<<' '<<i<<"\n",cin>>a[i];
for(int i=n-k+1;i<=n;++i) cout<<'?'<<' '<<i<<"\n",cin>>b[i];
for(int i=k+1;i<=n;++i) a[i]=a[i-k];
for(int i=n-k;i;--i) b[i]=b[i+k];
p.clear(),p.shrink_to_fit();
for(int i=k+1;i<=n-k;++i) if(a[i]!=b[i]) p.emplace_back(i);
solve();
}
return 0;
}
知乎大佬题解：
特别注意前后的长度都要大于等于 \(k\)。
询问前 \(k\) 个和后 \(k\) 个，观察循环节是否相同。
不相同，直接二分找到什么时候不相同的一段
然后直接暴力询问 \(k+1\) 长度，判断中间是否有一段即在 \(A\) ，也在 \(B\).
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve(){
int n, k;
cin >> n >> k;
auto query = [&](int x) -> int {
cout << "? " << x <<"\n";
int res;
cin >> res;
return res;
};
vector<int> pre(k), sf(k);
for (int i = 1; i <= k; i++)
pre[i % k] = query(i);
for (int i = n - k + 1; i <= n; i++)
sf[i % k] = query(i);
if (pre == sf) {
if (n == 2 * k) {
cout << "! " << k << " " << k << "\n";
} else {
cout << "! -1" << "\n";
}
return;
}
int id = -1;
for (int i = 0; i < k; i++)
if (pre[i] != sf[i])
id = i;
if (id == 0) id = k;
int c = n / k + ((n % k) >= id ? 1 : 0);
int l = 1, r = c;
while (l < r) {
int mid = l + r >> 1;
if (query((mid - 1) * k + id) == pre[id % k]) {
l = mid + 1;
} else {
r = mid;
}
}
int lena = 0, lenb = n;
for (int i = (l - 2) * k + id; i <= (l - 1) * k + id; i++) {
int res = query(i);
if (res == pre[i % k] && res != sf[i % k]) {
lena = i;
} else if (res != pre[i % k] && res == sf[i % k]) {
lenb = min(lenb, i);
}
}
lena = max(lena, k);
lenb = min(lenb, n - k + 1);
if (lena == lenb - 1)
cout << "! " << lena << " " << n - lena << "\n";
else
cout << "! -1" << "\n";
}
int main(){
std::ios::sync_with_stdio(0);
int t = 1;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
E. Spruce Dispute
题意：有一棵有 \(n\) 个顶点的树，其中的 \(n-1\) 个顶点上挂着饰品，有 \(\frac{n-1}{2}\) 种不同的颜色，每种颜色恰好有两个饰品。
移走树的哪一条边，重新排列饰品，使相同颜色的饰品之间路径长度最大呢？
移走一条边：选择一对相邻顶点 \(a\) 和 \(b( a<b )\)，然后从装饰树中移除顶点 \(b\) 并将 \(b\) 的所有相邻顶点( \(a\) 除外)直接连接到 \(a\) 。
知乎大佬题解：
首先观察到，所有的边都被最大的路径数经过时最优。
所有我们希望找到一个根，每棵子树的的大小都小于等于 \(n/2\)，一定能找到。
然后所有点的贡献都是到他的路径长度加上点子树大小。我们发现这个点一定是叶子节点。
对于把节点分成两部分，且编号相同的不在同一个子树中，使用DFS序。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve(){
int n;cin >> n;
vector<vector<int>> adj(n + 1);
for (int i = 1; i < n; i++) {
int u, v;cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> sz(n + 1, 1), dep(n + 1), p(n + 1), in(n + 1), ord(n + 1);
int cur = 0;
auto dfs = [&](auto self, int u, int fa) -> void {
sz[u] = 1;
p[u] = fa;
in[u] = ++cur;
ord[in[u]] = u;
for (auto v : adj[u]) {
if (v == fa) {
continue;
}
dep[v] = dep[u] + 1;
self(self, v, u);
sz[u] += sz[v];
}
};
dfs(dfs, 1, 0);
auto find = [&](auto self, int u) -> int {
for (auto v : adj[u]) {
if (v == p[u] || 2 * sz[v] <= n) {
continue;
}
return self(self, v);
}
return u;
};
int rt = find(find, 1);
p[rt] =dep[rt] =cur = 0;
dfs(dfs, rt, 0);
int x = -1;
for (int i = 1; i <= n; i++) {
if (i != rt && adj[i].size() == 1 && (x == -1 || dep[x] > dep[i])) {
x = i;
}
}
cout << x << " " << p[x] << "\n";
if (x < p[x]) x = p[x];
vector<int> ans(n + 1);
ord.erase(ord.begin() + in[x]);
for (int i = 1; i <= n / 2; i++) {
ans[ord[i]] = ans[ord[i + n / 2]] = i;
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << " \n"[i == n];
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
int t = 1;cin >> t;
while (t--) {
solve();
}
return 0;
}
F. Fallen Towers
题意：有一个长度为 \(n\) 的 \(a\) 数组。有一种操作是使 \(a_i=0\)，\(a_i\) 后面的元素都 \(+1\)，如果\(a_i\)本来就等于0，就不会都 \(+1\)。
现在按照任意顺序对所有的元素进行操作，即每个 \(a_i\) 都会操作一次。
最终得到的 \(a\) 数组必须是不递减的。求最终得到的 \(a\) 数组中不存在的最小非负整数。
CF大佬代码：
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N=5e5+10;
int n;
i64 a[N],b[N],c[N],d[N];
bool check(int x){
for(int j=n;j>=1;j--){
c[j]=x-1-(n-j);
c[j]=max(0ll,c[j]);
}
for(int i=1;i<=n;i++) b[i]=a[i];
for(int j=1;j<=n;j++) d[j]=0;
for(int i=1;i<=n;i++){
d[i]+=d[i-1];
if(d[i]<c[i]) return 0;
if(i==n) return 1;
i64 val=d[i]-c[i]+b[i];
if(val==0) continue;
i64 l=i+1;
i64 r=min((i64)n,i+val);
d[l]+=1;
d[r+1]-=1;
}
return 1;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++) b[i]=0;
for(int i=1;i<=n;i++) cin>>a[i];
a[n]=0;
int l=1,r=n+1;
while(l<r){
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<r<<"\n";
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;cin>>t;
while(t--) solve();
return 0;
}
