首页 / 更多教程 / Codeforces Round #715 (Div. 2)

Codeforces Round #715 (Div. 2)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Codeforces Round #715 (Div. 2)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4623字，纯文字阅读大概需要7分钟。

内容图文

Codeforces Round #715 (Div. 2)

C. The Sports Festival DP

题目大意：

给你一个序列 \(s\) ，你可以重新排列这个序列，成为一个新序列 \(a\) 。设 \(d_i=max(a_1,..,a_i)-min(a_1,...,a_i)\) ，求最小的 \(d_1+d_2+...+d_n\)

题解：

倒过来想，就是对于一个已经排好的序列，每次选择删掉最大值还是最小值，因为删掉中间的值是不会有影响的。

定义 \(dp[i][j]\) 表示从 \(i\) 到 \(j\) 的最小的值。

然后转移每次只能从 \(dp[i+1][j]\) 转移过来，或者从 \(dp[i][j-1]\) 转移过来。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10;
typedef long long ll;
ll dp[maxn][maxn],a[maxn];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==1) dp[j][j] = 0;
            else dp[j][i+j-1] = min(dp[j+1][i+j-1],dp[j][i+j-2]) + a[i+j-1]-a[j];
        }
    }
    printf("%lld\n",dp[1][n]);
}

D Binary Literature 思维

题目大意：

给你三个长度为 \(2n\) 的 \(01\) 串，让你构造一个长度为 \(3n\) 的 \(01\) 串，并且这个 \(01\) 必须包含这三个 \(01\) 串中至少 2 个作为它的子序列。看样例理解。

题解：

因为长度都为 \(2n\) 的 \(01\) 串，所以要么 \(0\) 的数量大于等于 \(1\) 的数量，要么 \(1\) 的数量大于 \(0\) 的数量，三个串分成两类，所以至少存在两个串属于同一类。

假设：\(A\) 串和 \(B\) 串都是 \(0\) 的数量大于等于 \(1\) 的数量，那么显而易见就是：

  • \(B\) 开头的 1 全部放入答案，然后找到第一个是 0 的位置存下来
  • 接下来就把 \(A\) 顺序放入答案，如果第 \(i\) 个位置是 0，那么同时 \(B\) 也可以往后移动一格
  • 如果 \(B\) 往后移动到的这个位置是 \(1\) ，那么把 \(B\) 的这一段连续的 1 全部放入答案。
  • 重复2 3 操作
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int s[3][maxn],ans[maxn],n,num[3];
/*
011001
111010

100110
000101
 */
void solve(int x,int y,int f) {
    int now = 0, pos = 1;
    while (pos <= 2 * n && s[y][pos] == 1) ans[++now] = 1, pos++;
    for (int j = 1; j <= 2 * n; j++) {
        ans[++now] = s[x][j];
        if (s[x][j] == 0) {
            if (pos <= 2 * n) pos++;
            while (s[y][pos] == 1 && pos <= 2 * n) ans[++now] = 1, pos++;
        }
    }
    while (now <= 3 * n) ans[++now] = 0;
    if (f) {
        for (int i = 1; i <= 3 * n; i++) ans[i] ^= 1;
    }
}
bool check(int x,int y){
    if(num[x]>=n&&num[y]>=n) {
        for(int i=1;i<=2*n;i++){
            s[x][i] ^=1;
            s[y][i] ^=1;
        }
        if(num[x]<num[y]) swap(x,y);
        solve(x,y,1);
        return true;
    }
    else if(num[x]<=n&&num[y]<=n){
        if(num[x]>num[y]) swap(x,y);
        solve(x,y,0);
        return true;
    }
    return false;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<=2;i++){
            num[i] = 0;
            for(int j=1;j<=2*n;j++){
                scanf("%1d",&s[i][j]);
                num[i] += s[i][j];
            }
        }
        bool flag = true;
        for(int i=0;i<=2&&flag;i++){
            for(int j=i+1;j<=2&&flag;j++){
                if(check(i,j)) {
                    flag = false;
                }
            }
        }
        for(int i=1;i<=3*n;i++) printf("%d",ans[i]);
        printf("\n");
    }
}

E Almost Sorted 思维

题目大意：

给你一个排列，定义一个近乎顺序的序列， \(a_{i+1}\geq a_i-1\) 。求这个排列的第 \(k\) 大的近乎顺序排列。

题解：

这个题目其实不是很难，首先你要写一下这个排列，观察这个排列的性质：

以 \(n = 6\) 为例：

1) 1 2 3 4 5 6
2) 1 2 3 4 6 5
3) 1 2 3 5 4 6
4) 1 2 3 6 5 4
5) 1 2 4 3 5 6
6) 1 2 4 3 6 5
7) 1 2 5 4 3 6
8) 1 2 6 5 4 3
9) 1 3 2 4 5 6
10)1 3 2 4 5 6
11)1 3 2 5 4 6
12)1 3 2 6 5 4
13)1 4 3 2 5 6
14)1 4 3 2 6 5
15)1 5 4 3 2 6
16)1 6 5 4 3 2
...
  • 观察这个序列，容易发现：第一个是1 的有 16个，在第一个是1 的情况下第二个是2的有8个，依此类推，容易发现：如果 \(k<=16\) ，那么 \(ans[1] = 1\) ，\(k<=8\) ，那么 \(ans[2]=2\)
  • 对上面的式子总结，可以发现，\(k<2^{n - i - 1}\) ，\(ans[i] = i\)
  • 继续观察，如果 \(n = 6,k = 6\) ，那么：\(ans[1] = 1,ans[2] = 2\) ，然后不确定 \(ans[3]\) ，枚举这个位置是多少，如果是 4 ，那么3 一定紧接着4，但是5 和 6 是没有约束的，所以此时的种类就是 \(2^{n - 4 - 1}\) ，如果之前的一个基数 \(res\)（此时也就是当 \(ans[3] = 3\) ，\(res = 4\)）是小于 k，并且 \(res + 2^{n- 4 - 1}\leq k\) ，那么说明 \(ans[3] = 4,ans[4] = 3\) ，然后再去判断 \(ans[5],ans[6]\)

差不多就是上述的思路，写起来注意一下细节即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
int ans[maxn];
ll f[110];

int main() {
    f[0] = 1;
    for (int i = 1; i <= 61; i++) f[i] = f[i - 1] * 2;
    int T;
    scanf("%d",&T);
    while(T--){
        ll n, k;
        scanf("%lld%lld", &n, &k);
        int pos = -1;
        for (int i = 1; i < n; i++) {
            if (n - i - 1 >= 61) continue;
            if (f[n - i - 1] < k) {
                pos = i;
                break;
            }
        }
        if(n - 1<=60 && f[n-1]<k) {
            printf("-1\n");
            continue;
        }
        if (pos == -1) {
            for (int i = 1; i <= n; i++) ans[i] = i;
        } else {
            ll res = 0;
            for (int i = 1; i < pos; i++) ans[i] = i;
            while (pos <= n) {
                for (int i = pos; i <= n; i++) {
                    ll tmp = 1;
                    if (n - i - 1 >= 0) tmp = f[n - i - 1];
                    if (res < k && res + tmp >= k) {
                        int x = pos;
                        for (int j = i; j >= x; j--) ans[pos++] = j;
                        break;
                    } else res += tmp;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            printf("%d",ans[i]);
            if(i==n) printf("\n");
            else printf(" ");
        }
    }
}

内容总结

以上是互联网集市为您收集整理的Codeforces Round #715 (Div. 2)全部内容，希望文章能够帮你解决Codeforces Round #715 (Div. 2)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1005176.html

来源：【匿名】