A. United We Stand
题意：给出一个长为\(n\)的数组\(a\)，将其中的元素分别放到空数组\(b\)和\(c\)中，使得\(c\)中的任意一个元素都不是\(b\)中任意一个元素的因数，并且两个数组都不是空数组
Solution
把\(a\)中最小的数放到\(b\)，其它的都放到\(c\)，一定可以保证要求成立
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a + 1, a + 1 + n);
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] == a[1])
b[++cnt1] = a[i];
else
c[++cnt2] = a[i];
}
if (cnt2 == 0)
{
cout << "-1\n";
return;
}
cout << cnt1 << " " << cnt2 << "\n";
for (int i = 1; i <= cnt1; i++)
cout << b[i] << " \n"[i == cnt1];
for (int i = 1; i <= cnt2; i++)
cout << c[i] << " \n"[i == cnt2];
}
B. Olya and Game with Arrays
题意：有\(n\)个数组arr，每个数组内的数字个数大于等于2，现在最多可以把每个数组中的一个数字移到其它数组里，问\(\sum_{i=1}^n\min arr_i\)最大是多少
Solution
其实是看第二大的数，比较一下把最小的数放到哪比较合适即可
void solve()
{
int n;
cin >> n;
int minn = 1e18;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
for (int j = 1; j <= a[i]; j++)
{
cin >> b[j];
}
sort(b + 1, b + 1 + a[i]);
c[i] = b[2];
d[i] = b[1];
minn = min(minn, d[i]);
}
int res = 0;
for (int i = 1; i <= n; i++)
{
res += c[i];
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
ans = max(ans, res - c[i] + minn);
}
cout << ans << "\n";
}
C. Another Permutation Problem
题意：给出\(n\)，构造一个排列\(a\)，使得\(\sum_{i=1}^ni\times a[i]-\max i\times a[i]\)最大
Solution
通过打表可以发现，它最大的时候会是一个\(1,2,...,x,n,n-1,...,x+1\)的排列，而这个结果是类似一个抛物线变化，所以我们只需三分找到最大值即可
int getx(int x)
{
for(int i=1;i<=x;i++)
{
a[i]=i;
}
int now=n;
for(int i=x+1;i<=n;i++)
{
a[i]=now;
now--;
}
int sum = 0;
int maxx = 0;
for (int i = 1; i <= n; i++)
{
sum += i * a[i];
maxx = max(maxx, i * a[i]);
}
return sum-maxx;
}
void solve()
{
cin >> n;
int ans = 0;
int l=0,r=n-1;
//int lans,rans;
while(l+1<r)
{
int mid1=(l+r)>>1;
int mid2=(mid1+r)>>1;
if(getx(mid1)>getx(mid2))r=mid2;
else l=mid1;
}
//cout<<l<<"\n";
cout<<getx(l)<<"\n";
}
D. Andrey and Escape from Capygrad
题意：给出几个区间\([l_i,r_i]\)和包含在里面的\([a_i,b_i]\)，如果当前在区间\([l_i,r_i]\)内，则可以传送至\([a_i,b_i]\)的任意一点，现在有\(q\)次询问，每次询问从一个点出发，最大能到达的点是多少。
Solution
先思考这样一个问题，对于一个区间，如果当前所在位置是在\([b_i,r_i]\)内，那它其实没有必要传送，此时已经是最大的了
所以我们可以把连续的\([l_i,b_i]\)合并成一个长区间，最后二分找到询问点所在或者是最近的区间即可
void solve()
{
vector<pii>v;
int n;cin>>n;
for(int i=1;i<=n;i++)
{
int l,r,a,b;cin>>l>>r>>a>>b;
v.push_back({l,b});
}
sort(v.begin(),v.end());
int lastl=-1,lastb=-1;
vector<pii>e;
for(int i=0;i<=v.size();i++)
{
if(lastl==-1)
{
lastl=v[i].first,lastb=v[i].second;
}else if(i!=v.size())
{
if(lastb>=v[i].first)
{
lastb=max(lastb,v[i].second);
}else
{
e.push_back({lastl,lastb});
lastl=v[i].first,lastb=v[i].second;
}
}else
{
e.push_back({lastl,lastb});
}
}
int q;cin>>q;
while(q--)
{
int x;cin>>x;
int l=0,r=e.size()-1;
while(l<r)
{
int mid=(l+r)>>1;
if(e[mid].first>x)
{
r=mid;
}else l=mid+1;
}
if(l==0&&e[l].first>x)
{
cout<<x<<" ";
}else if(l>0&&e[l].first>x)
{
l--;
cout<<max(x,e[l].second)<<" ";
}else if(e[l].first<=x)
{
cout<<max(x,e[l].second)<<" ";
}
}
cout<<"\n";
}
E. Maximum Monogonosity
题意：给出两个长为\(n\)的数组\(a,b\)和一个数\(k\)
定义区间\([l,r]\)贡献是 \(|b_l−a_r|+|a_l−b_r|\)
求长度之和为k的不相交的区间集合，使得贡献和最大。
Solution
给出的\(n\)和\(k\)比较小，可以考虑\(dp\)
定义\(dp[i][j]\)为前\(i\)个数中，已经取了长度和为\(j\)的区间的贡献最大值
那么就有\(dp[i][j]=max(dp[i][j],dp[i-k][j-k]+|b_i−a_{i-k+1}|+|a_{i-k+1}−b_i|)\)
但是这样算的复杂度太大了，达到了\(O(nk^2)\)
我们发现 \(|b_l−a_r|+|a_l−b_r|\)，其实就是\(max(b_l−a_r+a_l−b_r,a_r-b_l+a_l−b_r,b_l−a_r+b_r-a_l,a_r-b_l+b_r-a_l)\)
放到这里来，我们发现对于\(dp[i][j]\)，可以通过维护四个数组，即上述的\(max\)中的四个，即可转移过来
int dp[3005][3005];
int a1[3005]; //-b-a+dp
int a2[3005]; // b-a+dp
int a3[3005]; // a-b+dp
int a4[3005]; // a+b+dp
int a[3005], b[3005];
void solve()
{
int n, k;
cin >> n >> k;
for (int i = 0; i <= n; i++)
{
a1[i] = a2[i] = a3[i] = a4[i] = -1e18;
for (int j = 0; j <= k; j++)
{
dp[i][j] = 0;
}
}
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= min(i, k); j++)
{
a1[i - j] = max(a1[i - j], -a[i] - b[i] + dp[i - 1][j - 1]);
a2[i - j] = max(a2[i - j], -a[i] + b[i] + dp[i - 1][j - 1]);
a3[i - j] = max(a3[i - j], a[i] - b[i] + dp[i - 1][j - 1]);
a4[i - j] = max(a4[i - j], a[i] + b[i] + dp[i - 1][j - 1]);
dp[i][j] = dp[i - 1][j];
dp[i][j] = max(dp[i][j], a[i] + b[i] + a1[i - j]);
dp[i][j] = max(dp[i][j], -a[i] + b[i] + a2[i - j]);
dp[i][j] = max(dp[i][j], a[i] - b[i] + a3[i - j]);
dp[i][j] = max(dp[i][j], -a[i] - b[i] + a4[i - j]);
}
}
// cout << dp[1][1] << "\n";
cout << dp[n][k] << "\n";
}