感觉下次打 ARC-- 可能可以上大分 qwq
AT_arc215_a
我说这题其实是 club。
先把所有的操作机会交替放在路径两端（第一次放在间隔比较长的那一边），然后考虑把所有操作一次次放到相邻两个间隔最长的僵尸中间，这样做，原本最后一次操作的贡献会减去，但是会使后面左右交替移动一次的时间增加，并且还有额外的初始贡献。每次这样调整一次，直到贡献为负停止。实现有点麻烦。
//to kill a living book
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+7;
int n,k,l,a[N];
void solve(){cin>>n>>k>>l;priority_queue<int> pq;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1);for(int i=1;i<n;i++) pq.push(a[i+1]-a[i]);int ans=0;ans+=max(l-a[n],a[1]);ans+=(k-1)*(l-(a[n]-a[1]));bool ok=true;int lst=k-1,dis=l-(a[n]-a[1]),ini=max(l-a[n],a[1]);for(int i=1;i<k;i++){if(!pq.size()) break;if(!lst) break;int x=pq.top(); pq.pop();int con=-dis+(--lst)*x+(x/2)+x/2;if(con<=0){ok=false;break;}ans+=con,dis+=x,ini+=x/2;}if(ok){if((!lst)&&pq.size()){int x=pq.top();int con=-ini+(x/2);if(con>0) ans+=con;} }cout<<ans<<"\n";
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t; cin>>t;while(t--) solve();return 0;
}
AT_arc215_b
没啥好说的，就是让你扣一半下来，能连尽量连就好了，容易证明隔板不可能超过 \(n\) 个。看代码就行了。
//to kill a living book
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+7;
int n,a[N<<1];
void solve(){cin>>n;for(int i=1;i<=(n<<1);i++) cin>>a[i];set<int> s[2];vector<int> ans;int sta=1;for(int i=1;i<=(n<<1);i++){if(!s[sta].count(a[i])) s[sta].insert(a[i]);else ans.push_back(i-1),s[sta=1-sta].insert(a[i]);}cout<<ans.size()<<"\n";for(int x:ans) cout<<x<<" ";cout<<"\n";
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t; cin>>t;while(t--) solve();return 0;
}
AT_arc215_c
感觉不好想，没 D 好做。
首先转化条件，对于每一个人来说，这个条件不好转化，直接把所有人揉在一起考虑条件。
满足题意的人的集合的 \(x\)，\(y\)，\(x\) 的最小值必须要大于不在集合里面的 \(x\)，\(y\)，\(z\) 的最大值，这样集合外面的人不可能活下来。但是此时我们不能保证集合里面的元素都能活下来，所以再加一个满足以上条件的最小非空集的限制就行了。如何找？直接先固定一维，按 \(x\) 倒序排序，然后检查所有前缀即可。代码太简单不放了。
AT_arc215_d
直接转化值域为 \([0,M]\) 这个条件不是很方便，还是考虑原始的 \(A\) 序列吧。那 \(A\) 序列如何满足 \(S\) 递增呢？\(A_i+A{i+1} \le A_{i+1}+A_{i+1}\)，所以 \(A_i \le A_{i+2}\)。这启发我们把 \(A\) 按数位奇偶拆成两个递增序列进行组合。但是一个 \(S\) 可能对应多种组合。对于一个组合，我们不停地把奇数位的数全部减一，偶数位全部加一。直到不能再减（奇数位第一个等于 \(0\) 或者偶数位最后一个等于 \(M\)）。所以我们只需要找到以下条件的 \(A\) 集合的大小就行了：要么奇数位第一个等于 \(0\)，要么偶数位最后一个等于 \(M\)。如果不满足这个条件，就一定可以通过以上操作变成这种状态，那么对于满足条件的，还原成 \(S\) 一定互不相同。所以只计算满足条件的就行。直接用最简单的容斥原理就行了，代码太简单不放了。
AT_arc215_e
没看。
AT_arc215_f
听同学说是点分治+DP，没看。