Codeforces Round 892 (Div. 2)
目录A United We Stand
给定长度为\(n\)的数组
a，可以将a中元素添加到空数组b或c中，满足两个数组均非空，且c中的元素不是b中元素的约数。若不能满足输出-1。
c中的元素不是b中元素的约数，即\(b_i \;\% \;c_j \neq 0\)。
可以将a中元素从大到小排序，将所有最大的元素放进c中，其余元素放入b中即满足要求。若b为空，则输出-1。
const int N = 110;
int n, a[N];
void solve()
{
vector<int> b, c;
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i];
sort(a, a + n, [&](int a, int b){return a > b;}); // 从大到小排序
for(int i = 0; i < n; i ++)
{
if(a[i] == a[0]) c.push_back(a[i]); // 将所有最大值放入C数组
else b.push_back(a[i]);
}
if(b.empty())
{
cout << "-1\n";
return ;
}
cout << b.size() << " " << c.size() << endl;
for(auto p : b) cout << p << " ";
cout << endl;
for(auto p : c) cout << p << " ";
cout << endl;
}
B Olya and Game with Arrays
有
n个数组，最多可以将一个整数从一个数组移动到另一个数组。整数只能从一个数组中移动一次，但整数可以多次添加到一个数组中。对于每个数组找到其中的最小值，然后将这些值相加，求结果的最大值。
要使得最小值尽量大，可以移动每个数组的最小值，那么每个数组对答案的贡献就变成了次小值。将所有最小值插入次小值最小的数组内，可以最小化影响。
取出每个数组的最小值和次小值，将次小值的最小值与最小值的最小值取较小值，加上其余所有的次小值。
void solve()
{
vector<int> minn, lst;
int n;
cin >> n;
for(int i = 0; i < n; i ++)
{
int len;
cin >> len;
vector<int> a(len);
for(int i = 0; i < len; i ++) cin >> a[i];
sort(a.begin(), a.end());
minn.push_back(a[0]);
if(len >= 2) lst.push_back(a[1]);
}
sort(minn.begin(), minn.end());
sort(lst.begin(), lst.end());
lst[0] = min(lst[0], minn[0]);
ll ans = 0;
for(auto p : lst) ans += p;
cout << ans << endl;
}
C Another Permutation Problem
成本为\(\Sigma_{i=1}^np_i \cdot i-max_{j=1}^np_j\cdot j\)，找出长度\(n\)的所有排列中的最大成本。
先打表找个规律
void solve(int len)
{
vector<int> a(len), b;
int ans = 0;
for(int i = 1; i <= len; i ++) a[i - 1] = i;
do{
int res = 0, tmp = 0;
for(int i = 0; i < len; i ++) res += a[i] * (i + 1), tmp = max(tmp, a[i] * (i + 1));
res -= tmp;
if(res > ans) ans = max(ans, res), b = a;
}while(next_permutation(a.begin(), a.end()));
cout << ans << endl;
for(auto p : b) cout << p << " ";
cout << endl;
}
| n | ans | permutation |
|---|---|---|
| 2 | 2 | 2 1 |
| 3 | 7 | 1 3 2 |
| 4 | 17 | 1 2 4 3 |
| 5 | 35 | 1 2 5 4 3 |
| 6 | 62 | 1 2 3 6 5 4 |
| 7 | 100 | 1 2 3 4 7 6 5 |
| 8 | 152 | 1 2 3 4 8 7 6 5 |
| 9 | 219 | 1 2 3 4 5 9 8 7 6 |
| 10 | 303 | 1 2 3 4 5 6 10 9 8 7 |
通过打表可以发现，后面一部分数翻转时答案最大，排列长度最大为250，可以枚举要翻转的数量
void solve()
{
ll ans = 0;
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i ++) a[i] = i + 1;
for(int len = 1; len <= n; len ++) // 枚举要翻转的长度
{
ll res = 0, tmp = 0;
for(int i = 0; i < n - len; i ++) // 正序部分
res += a[i] * (i + 1), tmp = max(tmp, a[i] * (i + 1) * 1ll); // *1ll转换为ll类型
for(int i = n - len, j = n; i < n; i ++, j --) // 逆序部分
res += a[i] * j, tmp = max(tmp, a[i] * j * 1ll);
res -= tmp;
ans = max(ans, res);
}
cout << ans << endl;
}
D Andrey and Escape from Capygrad
当处于线段\([l,r]\)上，那么便可以传送到线段\([a,b]\)上，\(l\leq a\leq b\leq r\)。有若干条线段，给定起始位置问最院能传送到哪里
假如当前位置位于\((b,r]\)就没有必要再传送了，所以有效传送区间为\([l,b]\)。
处理出所有的传送区间，进行区间合并，那么在所有的独立区间内都可以任意传送。
二分查找起始位置位于哪个区间左端点的右边，假如起始点在传送区间内就传送到区间的右端点，否则无法传送。
typedef long long ll;
typedef pair<int, int> PII;
vector<PII> vt;
void merge(vector<PII> &segs) // 区间合并
{
sort(segs.begin(), segs.end());
vector<PII> res;
int st = -2e9, ed = -2e9;
for(auto seg : segs)
{
if(ed < seg.first)
{
if(st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
}
if(st != -2e9) res.push_back({st, ed});
segs = res;
}
bool check(int p, int x)
{
if(x >= vt[p].first) return true;
return false;
}
int bsearch(int x) // 二分查找位于哪个区间左端点的右边
{
int l = 0, r = vt.size() - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid, x)) l = mid;
else r = mid - 1;
}
return l;
}
void solve()
{
vt.clear();
int n, l, r, a, b, q, x;
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> l >> r >> a >> b;
vt.push_back({l, b});
}
merge(vt);
cin >> q;
while(q --)
{
cin >> x;
int p = bsearch(x);
if(x >= vt[p].first && x <= vt[p].second) x = vt[p].second; // 若处于传送区间内则传送
cout << x << " ";
}
cout << endl;
}
E Maximum Monogonosity
线段的成本定义为\(|b_l-a_r|+|b_r-a_l|\)，求出总长度等于\(k\)且不相交的线段的最大成本总和
显然这是一个DP。参考洛谷题解：CF1859E Maximum Monogonosity - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
由于\(|a-b|=max(a-b,b-a)\)，那么\(|b_l-a_r|+|b_r-a_l|=max(b_l-a_r, a_r-b_l)+max(b_r-a_l,a_l-b_r)\)，会出现四种组合方式。
令dp[i][j]表示前i个单位中选择长度为j的线段的最大价值。若第i个单位不选，那么由\(dp[i-1][j]\)转移过来。如果选择第i个单位，那么再考虑线段的长度，假设线段的长度为k，那么由dp[i-k][j-k]+cost(i-k+1,i)，并从0~j枚举k即可。因此\(O(nk^2)\)的转移方程为
代入绝对值不等式，可以化简为
\[max_{k=1}^{j}dp_{i-k,j-k}+a_i-b_{i-k+1}+b_i-a_{i-k+1} \\ max_{k=1}^{j}dp_{i-k,j-k}+a_i-b_{i-k+1}+a_{i-k+1}-b_i \\ max_{k=1}^{j}dp_{i-k,j-k}+b_{i-k+1}-a_i+b_i-a_{i-k+1} \\ max_{k=1}^{j}dp_{i-k,j-k}+b_{i-k+1}-a_i+a_{i-k+1}-b_i \\ \]即
\[(max_{k=1}^{j}dp_{i-k,j-k}-a_{i-k+1}-b_{i-k+1}) +a_i+b_i \\ (max_{k=1}^{j}dp_{i-k,j-k}+a_{i-k+1}-b_{i-k+1}) +a_i-b_i \\ (max_{k=1}^{j}dp_{i-k,j-k}-a_{i-k+1}+b_{i-k+1}) -a_i+b_i \\ (max_{k=1}^{j}dp_{i-k,j-k}+a_{i-k+1}+b_{i-k+1}) -a_i-b_i \\ \]定义f[x][4]为当前转移到的位置满足\(i-j=x\)时，上面四种情况的最大值分别是多少。复杂度为\(O(nk)\)。
懵懵懂懂看懂了，等我再学一段时间动态规划再来补这个坑。
int n, k;
vector<ll> a(N), b(N);
ll dp[N][N], f[N][4];
void solve()
{
memset(f, 0x80, sizeof f); // 这里不是很懂为什么是0x80
cin >> n >> k;
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 <= k && j <= i; j ++)
{
dp[i][j] = dp[i - 1][j];
f[i - j][0] = max(f[i - j][0], dp[i - 1][j - 1] + a[i] + b[i]);
f[i - j][1] = max(f[i - j][1], dp[i - 1][j - 1] + a[i] - b[i]);
f[i - j][2] = max(f[i - j][2], dp[i - 1][j - 1] - a[i] + b[i]);
f[i - j][3] = max(f[i - j][3], dp[i - 1][j - 1] - a[i] - b[i]);
dp[i][j] = max(dp[i][j], f[i - j][0] - a[i] - b[i]);
dp[i][j] = max(dp[i][j], f[i - j][1] + a[i] - b[i]);
dp[i][j] = max(dp[i][j], f[i - j][2] - a[i] + b[i]);
dp[i][j] = max(dp[i][j], f[i - j][3] + a[i] + b[i]);
}
}
cout << dp[n][k] << '\n';
}