Codeforces Round 892 (Div. 2)
文章目录
A United We Stand
给定长度为
nn
n
的数组
a
，可以将
a
中元素添加到空数组
b
或
c
中，满足两个数组均非空，且
c
中的元素不是
b
中元素的约数。若不能满足输出
-1
。
c
中的元素不是
b
中元素的约数，即
b
i
%
c
j
≠
0
b_i \;\% \;c_j \neq 0
b
i
%
c
j
=
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
成本为
Σi
=
1
n
p
i
⋅
i
−
m
a
x
j
=
1
n
p
j
⋅
j
\Sigma_{i=1}^np_i \cdot i-max_{j=1}^np_j\cdot j
Σ
i
=
1
n
p
i
⋅
i
−
ma
x
j
=
1
n
p
j
⋅
j
，找出长度
nn
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
]
[l,r]
[
l
,
r
]
上，那么便可以传送到线段
[a
,
b
]
[a,b]
[
a
,
b
]
上，
l≤
a
≤
b
≤
r
l\leq a\leq b\leq r
l
≤
a
≤
b
≤
r
。有若干条线段，给定起始位置问最院能传送到哪里
假如当前位置位于
(
b
,
r
]
(b,r]
(
b
,
r
]
就没有必要再传送了，所以有效传送区间为
[
l
,
b
]
[l,b]
[
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
∣
|b_l-a_r|+|b_r-a_l|
∣
b
l
−
a
r
∣
+
∣
b
r
−
a
l
∣
，求出总长度等于
kk
k
且不相交的线段的最大成本总和
显然这是一个DP。参考洛谷题解：
CF1859E Maximum Monogonosity – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
由于
∣
a
−
b
∣
=
m
a
x
(
a
−
b
,
b
−
a
)
|a-b|=max(a-b,b-a)
∣
a
−
b
∣
=
ma
x
(
a
−
b
,
b
−
a
)
，那么
∣
b
l
−
a
r
∣
+
∣
b
r
−
a
l
∣
=
m
a
x
(
b
l
−
a
r
,
a
r
−
b
l
)
+
m
a
x
(
b
r
−
a
l
,
a
l
−
b
r
)
|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)
∣
b
l
−
a
r
∣
+
∣
b
r
−
a
l
∣
=
ma
x
(
b
l
−
a
r
,
a
r
−
b
l
)
+
ma
x
(
b
r
−
a
l
,
a
l
−
b
r
)
，会出现四种组合方式。
令
dp[i][j]
表示前
i
个单位中选择长度为
j
的线段的最大价值。若第
i
个单位不选，那么由
d
p
[
i
−
1
]
[
j
]
dp[i-1][j]
d
p
[
i
−
1
]
[
j
]
转移过来。如果选择第
i
个单位，那么再考虑线段的长度，假设线段的长度为
k
，那么由
dp[i-k][j-k]+cost(i-k+1,i)
，并从
0~j
枚举k即可。因此
O
(
n
k
2
)
O(nk^2)
O
(
n
k
2
)
的转移方程为
d
p
i
,
j
=
m
a
x
(
d
p
i
−
1
,
j
,
m
a
x
k
=
1
j
(
d
p
i
−
k
,
j
−
k
+
∣
a
i
−
b
i
−
k
+
1
∣
+
∣
b
i
−
a
i
−
k
+
1
∣
)
)
dp_{i,j}=max(dp_{i-1,j},max_{k=1}^{j}(dp_{i-k,j-k}+|a_i-b_{i-k+1}|+|b_i-a_{i-k+1}|))
d
p
i
,
j
=
ma
x
(
d
p
i
−
1
,
j
,
ma
x
k
=
1
j
(
d
p
i
−
k
,
j
−
k
+
∣
a
i
−
b
i
−
k
+
1
∣
+
∣
b
i
−
a
i
−
k
+
1
∣
))
代入绝对值不等式，可以化简为
m
a
x
k
=
1
j
d
p
i
−
k
,
j
−
k
+
a
i
−
b
i
−
k
+
1
+
b
i
−
a
i
−
k
+
1
m
a
x
k
=
1
j
d
p
i
−
k
,
j
−
k
+
a
i
−
b
i
−
k
+
1
+
a
i
−
k
+
1
−
b
i
m
a
x
k
=
1
j
d
p
i
−
k
,
j
−
k
+
b
i
−
k
+
1
−
a
i
+
b
i
−
a
i
−
k
+
1
m
a
x
k
=
1
j
d
p
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-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 \\
ma
x
k
=
1
j
d
p
i
−
k
,
j
−
k
+
a
i
−
b
i
−
k
+
1
+
b
i
−
a
i
−
k
+
1
ma
x
k
=
1
j
d
p
i
−
k
,
j
−
k
+
a
i
−
b
i
−
k
+
1
+
a
i
−
k
+
1
−
b
i
ma
x
k
=
1
j
d
p
i
−
k
,
j
−
k
+
b
i
−
k
+
1
−
a
i
+
b
i
−
a
i
−
k
+
1
ma
x
k
=
1
j
d
p
i
−
k
,
j
−
k
+
b
i
−
k
+
1
−
a
i
+
a
i
−
k
+
1
−
b
i
即
(
m
a
x
k
=
1
j
d
p
i
−
k
,
j
−
k
−
a
i
−
k
+
1
−
b
i
−
k
+
1
)
+
a
i
+
b
i
(
m
a
x
k
=
1
j
d
p
i
−
k
,
j
−
k
+
a
i
−
k
+
1
−
b
i
−
k
+
1
)
+
a
i
−
b
i
(
m
a
x
k
=
1
j
d
p
i
−
k
,
j
−
k
−
a
i
−
k
+
1
+
b
i
−
k
+
1
)
−
a
i
+
b
i
(
m
a
x
k
=
1
j
d
p
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 \\ (max_{k=1}^{j}dp_{i-k,j-k}+a_{i-k+1}+b_{i-k+1}) -a_i-b_i \\
(
ma
x
k
=
1
j
d
p
i
−
k
,
j
−
k
−
a
i
−
k
+
1
−
b
i
−
k
+
1
)
+
a
i
+
b
i
(
ma
x
k
=
1
j
d
p
i
−
k
,
j
−
k
+
a
i
−
k
+
1
−
b
i
−
k
+
1
)
+
a
i
−
b
i
(
ma
x
k
=
1
j
d
p
i
−
k
,
j
−
k
−
a
i
−
k
+
1
+
b
i
−
k
+
1
)
−
a
i
+
b
i
(
ma
x
k
=
1
j
d
p
i
−
k
,
j
−
k
+
a
i
−
k
+
1
+
b
i
−
k
+
1
)
−
a
i
−
b
i
定义
f[x][4]
为当前转移到的位置满足
i
−
j
=
x
i-j=x
i
−
j
=
x
时，上面四种情况的最大值分别是多少。复杂度为
O
(
n
k
)
O(nk)
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';
}