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;
}

通过打表可以发现，后面一部分数翻转时答案最大，排列长度最大为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)\)的转移方程为

代入绝对值不等式，可以化简为

即

定义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';
}

本栏目推荐文章
• NSSCTF Round#16 Basic WriteUp
• Hey left 1 Codeforces Round 918 (Div. 4)
• vue3 获取循环的div的总宽度
• CodeForces 1312G Autocompletion
• Educational Codeforces Round 152 (Rated for Div. 2)
• codeforces 918 div4
• div滚动加载数据
• CF Beta Round 93-D.Fibonacci Sums-齐肯多夫分解、DP
• CodeForces 1329D Dreamoon Likes Strings
• CodeForces 1237H Balanced Reversals

Codeforces Round 892 Divcodeforces round 892 div codeforces round div2 892 codeforces round 892 a-e codeforces round 911 div codeforces round 864 div codeforces round 887 div codeforces round 863 div codeforces round 913 div codeforces round 915 div codeforces round 912 div