ARC126 A-D
A.
题意
(N_2)个2，(N_3)个3，(N_4)个4，可以拼凑出多少个10
分析
枚举可以发现，凑出10的方案只有以下:
显然，对于这些方案，贪心方法一定是一直用某种方案直到不能用了，因此只需要枚举这些方案的顺序对答案取max即可
代码
int main(){
int T = rd();
while(T--){
ll N1 = rd();
ll N2 = rd();
ll N3 = rd();
vector<int> op(5);
for(int i = 0;i < 5;i++)
op[i] = i;
ll res = -1;
do{
ll n2 = N1;
ll n4 = N3;
ll n3 = N2;
ll mx;
ll ans = 0;
for(int i = 0;i < 5;i++){
if(!op[i]) {
mx = n2 / 5;
n2 -= mx * 5;
ans += mx;
}
else if(op[i] == 1){
mx = min(n2 / 2,n3 / 2);
n2 -= mx * 2;
n3 -= mx * 2;
ans += mx;
}
else if(op[i] == 2){
mx = min(n2 / 3,n4);
n2 -= mx * 3;
n4 -= mx;
ans += mx;
}
else if(op[i] == 3){
mx = min(n2,n4 / 2);
n2 -= mx;
n4 -= mx * 2;
ans += mx;
}
else {
mx = min(n3 / 2,n4);
n3 -= mx * 2;
n4 -= mx;
ans += mx;
}
}
res = max(res,ans);
}while(next_permutation(op.begin(),op.end()));
printf("%lld
",res);
}
}
B.
题意
给出(2N)个点，分别是((1-N,0),(1-N,1))
给出(M)条边，第(i)条连接((a_i,0))和((b_i,1))
在(M)条中选出最大的个数，使得边在平面上不相交(也不能有相同endpoint)
分析
固定一维，显然这个时候就是要求另一维的最长上升子序列，(否则一定有交)，如果这一维不存在(a_i = a_j)的话显然就直接可以做了，但是题目只确保不重边
这个时候只需规定(a_i = a_j)时，若(b_i > b_j)，(i)排在(j)的前面即可，这样就避免了求(LIS)时同时选到同一个点，且对其他点无影响
剩下只要求(O(nlogn))的(LIS)即可
代码
inline bool cmp(pair<int,int> a,pair<int,int> b){
if(a.fi == b.fi) return a.se > b.se;
return a.fi < b.fi;
}
int main(){
int n = rd();
int m = rd();
vector<pair<int,int>> v(m);
for(int i = 0;i < m;i++)
v[i].fi = rd(),v[i].se = rd();
sort(v.begin(),v.end(),cmp);
VI tmp;
for(int i = 0;i < m;i++){
if(tmp.empty() || tmp.back() < v[i].se) tmp.push_back(v[i].se);
else *lower_bound(tmp.begin(),tmp.end(),v[i].se) = v[i].se;
}
cout << (int)tmp.size();
}
C.
题意
给定数组(A),可以进行至多(k)次操作，每次操作选择(A)中某个数+1，找出操作后最大的(gcd)
分析
求最大的(gcd)，可以等价为求最大的某个数(x)，使得(x|a_i,forall i in [1,n])
当(k)非常大时，我们肯定希望每个数的大小都相同，如果最后的答案要大于(a_i)，只需把所有数加到答案
如果最后答案等于已经存在(a_i)，我们发现可以较快的计算出所需的操作次数
考虑答案为(x)，(a_i)变为的最小操作次数即找到某个(k)，使得((k -1)x leq a_i leq k x),次数(kx - a_i)
答案即(sum (kx - a_i) = sum cnt - sum a_i) ，(sum cnt)可以用一个前缀桶存储出现次数来维护，枚举(x)和枚举(k)，复杂度显然就是调和级数
代码
int main(){
int n = rd();
ll k = rd();
VI v(n + 1);
ll tot = 0;
for(int i = 1;i <= n;i++)
v[i] = rd(),tot += v[i];
ll mx = *max_element(v.begin() + 1,v.end());
if(k >= mx * n - tot) {
printf("%lld
",(k + tot) / n);
return 0;
}
VI cnt(2 * mx + 1);
for(int i = 1;i <= n;i++)
cnt[v[i]]++;
for(int i = 1;i <= mx * 2;i++)
cnt[i] = cnt[i] + cnt[i - 1];
for(int x = mx;x >= 1;x--){
ll cost = 0;
for(int l = 1;l <= mx;l += x){
cost += (cnt[l + x - 1] - cnt[l - 1]) * (l + x - 1);
}
cost -= tot;
if(cost <= k) {
printf("%d
",x);
return 0;
}
}
}
D.
题意
给定(N)个值域([1,k])的数，每次可以交换距离为(1)的数，求最小的次数使得存在子区间([1，2，...k-1,k])
分析
看数据范围容易想到是状压DP,(dp[i][S])表示前(i)个数，已经凑出状态(S)的最小交换次数
显然答案由两部分组成：逆序对个数和组成答案的数到最终区间的位置
考虑转移：加入一个数时，从前向后加入某个数时，显然要加上比它大的个数(逆序对)。考虑位置，每次要到某个区间，要么已经存在的数要整体移动一个位置，要么还没加入的数要整体移动一个位置，对两者取min
代码
int main(){
int n = rd();
int k = rd();
VI dp(1 << k,1e9);
dp[0] = 0;
for(int i = 0;i < n;i++){
int a = rd();
a--;
for(int j = (1 << k ) - 1;j >= 0;j--){
if(dp[j] != 1e9) {
if(!((j >> a) & 1))
dp[j | 1 << a] = min(dp[j | 1 << a],dp[j] + __builtin_popcount(j & ~((1 << a) - 1)));
dp[j] += min(__builtin_popcount(j),__builtin_popcount(j ^ (1 << k) - 1));
}
}
}
printf("%lld",dp[(1 << k) - 1]);
}