devbox
算法创新者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Codeforces Round #704 (Div. 2) A-E题解

作者：算法创新者 | 2024-02-02 10:56:07

赞

踩

codeforces round #704 (div. 2)

A Three swimmers
题意 三个人每人游一个来回时间分别是a、b、c，那么在 a、b、c的倍数时间点上 三个人均会在左边的点，题目问你p时刻来 还要等多久最快遇到三个人 1e18 除法判断是否整除相减即可

#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<iostream>
#include<queue>
using namespace std;
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl
const int MAX_N = 100005;
priority_queue<pair<int,int> > q;
int ans[MAX_N],arr[MAX_N];
int num = 0;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        num = 0;
        int n;
        scanf("%d",&n);
        for(int i = 1;i<=n;++i)
        {
            scanf("%d",&arr[i]);
            q.push(make_pair(arr[i],i));
        }
        int maxx = n;
        while(!q.empty())
        {
            pair<int,int> top = q.top();
            q.pop();
            if(top.second>maxx) continue;
            int xb = top.second;
            while(xb<=maxx)
            {
                ans[++num] = arr[xb];
                xb++;
            }
            maxx = top.second-1;
        }
        for(int i = 1;i<=n;++i)
        {
            i==n?printf("%d\n",ans[i]):printf("%d ",ans[i]);
        }
    }
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

BCard Deck
按照卡牌顺序你每次选k张，然后将k张从最下面反过来放到新桌子上获得收益，收益因为是n的次方，我们发现每个卡牌是小于等于n，所以你把大的放在最下面获得收益最高，如果每个卡牌不是小于等于n 需要dp计算

#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<iostream>
#include<queue>
using namespace std;
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl
const int MAX_N = 100005;
priority_queue<pair<int,int> > q;
int ans[MAX_N],arr[MAX_N];
int num = 0;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        num = 0;
        int n;
        scanf("%d",&n);
        for(int i = 1;i<=n;++i)
        {
            scanf("%d",&arr[i]);
            q.push(make_pair(arr[i],i));
        }
        int maxx = n;
        while(!q.empty())
        {
            pair<int,int> top = q.top();
            q.pop();
            if(top.second>maxx) continue;
            int xb = top.second;
            while(xb<=maxx)
            {
                ans[++num] = arr[xb];
                xb++;
            }
            maxx = top.second-1;
        }
        for(int i = 1;i<=n;++i)
        {
            i==n?printf("%d\n",ans[i]):printf("%d ",ans[i]);
        }
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

C. Maximum width
定义完美字符串为T每个字符按顺序均属于S 两个字符间最长距离为所求值，一开始想到可能和长度有关 压位dp，但是不太好定义 于是定义出如下dp含义 dp[i][2] - dp[i][0] 代表T中第 i 个字符属于S最左能在什么位置 当然要比dp[i-1][0] 大，那么dp[i][1] 代表T中第 i 个字符属于S最右能在什么位置 当然要比 dp[i+1][1] 小 枚举点求答案

#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<iostream>
#include<queue>
using namespace std;
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl
const int MAX_N = 200005;
priority_queue<pair<int,int> > q;
long long dp[MAX_N][2];
char str[MAX_N],str_[MAX_N];
vector<int> vt[35];
int main()
{
    int n,m,ans = 0;
    scanf("%d%d",&n,&m);
    scanf("%s",str+1);
    for(int i = 1;i<=n;++i)
    {
        vt[str[i]-'a'+1].push_back(i);
    }
    scanf("%s",str_+1);
    for(int i = 1;i<=m;++i)
    {
        dp[i][0] = 0x3f3f3f3f;
        dp[i][1] = 0;
    }
    dp[0][0] = 0,dp[m+1][1] = 0x3f3f3f3f;
    for(int i = 1;i<=m;++i)
    {
        int l = 0,r = vt[str_[i]-'a'+1].size()-1;
        while(l<=r)
        {
            int mid = (l+r)/2;
            if(vt[str_[i]-'a'+1][mid] > dp[i-1][0]) r = mid - 1;
            else l = mid + 1;
        }
        dp[i][0] = vt[str_[i]-'a'+1][l];
    }
    for(int i = m;i>=1;--i)
    {
        int l = 0,r = vt[str_[i]-'a'+1].size()-1;
        while(l<=r)
        {
            int mid = (l+r)/2;
            if(vt[str_[i]-'a'+1][mid] < dp[i+1][1]) l = mid+1;
            else r = mid - 1;
        }
        dp[i][1] = vt[str_[i]-'a'+1][r];
    }
    dp[m+1][1] = 0;
    for(int i = 1;i<=m;++i)
    {
        ans = max(1ll*ans,dp[i+1][1]-dp[i][0]);
    }
    printf("%d\n",ans);
    return 0;
}



  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63

D. Genius’s Gambit
当a=0或者b=1情况比较明显
手完出了 k<=a 与 k <=b-1的情况，写了个暴力归纳k<=a+b-2的情况 a+b-2可以将 k<=a 与 k<=b-1结合起来玩

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int MAX_N = 200025;
char str[MAX_N];
int main()
{
    int a,b,k;
    scanf("%d%d%d",&a,&b,&k);
    if(a==0)
    {
        if(k==0)
        {
            printf("Yes\n");
            for(int i = 1;i<=b;++i) printf("1");printf("\n");
            for(int i = 1;i<=b;++i) printf("1");printf("\n");
        }
        else
        {
            printf("No\n");
        }
    }
    else if(b==1)
    {
        if(k==0)
        {
            printf("Yes\n");
            for(int i = 1;i<=b;++i) printf("1");for(int i = 1;i<=a;++i) printf("0");printf("\n");
            for(int i = 1;i<=b;++i) printf("1");for(int i = 1;i<=a;++i) printf("0");printf("\n");
        }
        else
        {
            printf("No\n");
        }
    }
    else
    {
        if(k<=a)
        {
            printf("Yes\n");
            for(int i = 1;i<=b-1;++i) printf("1");printf("1");for(int i = 1;i<=k;++i) printf("0");for(int i = 1;i<=a-k;++i) printf("0");printf("\n");
            for(int i = 1;i<=b-1;++i) printf("1");for(int i = 1;i<=k;++i) printf("0");printf("1");for(int i = 1;i<=a-k;++i) printf("0");printf("\n");
        }
        else if(k<=b-1)
        {
            printf("Yes\n");
            printf("1");for(int i = 1;i<=a-1;++i) printf("0");for(int i = 1;i<=k;++i) printf("1");printf("0");for(int i = k+2;i<=b;++i) printf("1");printf("\n");
            printf("1");for(int i = 1;i<=a-1;++i) printf("0");printf("0");for(int i = 1;i<=k;++i) printf("1");for(int i = k+2;i<=b;++i) printf("1");printf("\n");
        }
        else if(k<=a+b-2)
        {
            int len = 0;
            printf("Yes\n");
            for(int i = 1;i<=b;++i) printf("1");for(int i = 1;i<=a;++i) printf("0");printf("\n");
            for(int i = 1;i<=b-1;++i) str[++len] = '1';
            int xb = b;
            for(int i = 1;i<=a;++i) str[++len] = '0';
            str[++len] = '1';
            for(int i = 1;i<=k-a;++i) swap(str[xb],str[xb-1]),xb--;
            printf("%s\n",str+1);
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70

E. Almost Fault-Tolerant Database
这题给你 n ∗ m n*m n∗m 个数，问你能否找到一行 m m m 个数，使得这 m m m 个数与每一行不同的数不超过 2 2 2 个
我们先考虑答案肯定和第一行不超过两个数（如果存在） 那么我们去拿第一行假设作为答案与其余行求 m a x d i f f maxdiff maxdiff 如果 m a x d i f f maxdiff maxdiff >= 5 5 5 肯定无解，因为你只能换两个位置 5 − 2 = 3 > = 2 5-2=3 >= 2 5−2=3>=2 那么当 m a x d i f f < = 2 maxdiff <= 2 maxdiff<=2 肯定输出第一行本身 如果 m a x d i f f = 4 maxdiff = 4 maxdiff=4 则交换其中两个元素， m a x d i f f = 3 maxdiff=3 maxdiff=3 比较麻烦，先交换一个，然后看是否满足情况 如果继续 m a x d i f f = 3 maxdiff = 3 maxdiff=3 则做组合交换 3 ∗ 3 3*3 3∗3 情况，题解说 3 3 3 种情况 可能还是有不同的地方 另外代码也写的不够美观 感觉定义的太随意了 代码就越来越臃肿

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<stack>
#include<cstring>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;

#define ll long long

const int MAX_N = 250025;
vector<int> vt[MAX_N];
int ans[MAX_N],cnt[MAX_N],maxx,xb,n,m,tmp[5],tmpLen,maxx_,xb_,tmp_[5],tmpLen_,maxx__,xb__;

void findDiff()
{
    maxx = -1;
    for(int i = 1;i<=n;++i) cnt[i] = 0;
    for(int i = 1;i<=n;++i)
    {
        for(int j = 1;j<=m;++j)
        {
            if(vt[i][j]!=ans[j]) cnt[i]++;
        }
        if(cnt[i]>maxx)
        {
            maxx = cnt[i];
            xb = i;
        }
    }
}

void findDiffOne()
{
    maxx_ = -1;
    for(int i = 1;i<=n;++i) cnt[i] = 0;
    for(int i = 1;i<=n;++i)
    {
        for(int j = 1;j<=m;++j)
        {
            if(vt[i][j]!=ans[j]) cnt[i]++;
        }
        if(cnt[i]>maxx_)
        {
            maxx_ = cnt[i];
            xb_ = i;
        }
    }
}

void findDiffTwo()
{
    maxx__ = -1;
    for(int i = 1;i<=n;++i) cnt[i] = 0;
    for(int i = 1;i<=n;++i)
    {
        for(int j = 1;j<=m;++j)
        {
            if(vt[i][j]!=ans[j]) cnt[i]++;
        }
        if(cnt[i]>maxx__)
        {
            maxx__ = cnt[i];
            xb__ = i;
        }
    }
}

void GOOD()
{
    printf("Yes\n");
    for(int i = 1;i<=m;++i)
    {
        i==m?printf("%d\n",ans[i]):printf("%d ",ans[i]);
    }
}

bool gao(int x,int y,int initXb)
{
    for(int i = 1;i<=m;++i) ans[i] = vt[1][i];
    ans[tmp[x]] = vt[initXb][tmp[x]];
    ans[tmp[y]] = vt[initXb][tmp[y]];
    findDiff();
    if(maxx<=2)
    {
        return true;
    }
    return false;
}

bool gaoOne(int x)
{
    ans[tmp_[x]] = vt[xb_][tmp_[x]];
    findDiffTwo();
    if(maxx__<=2)
    {
        return true;
    }
    return false;
}

int main()
{
    int x;
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=n;++i) vt[i].push_back(-1);
    for(int i = 1;i<=n;++i)
    {
        for(int j = 1;j<=m;++j)
        {
            scanf("%d",&x);
            vt[i].push_back(x);
        }
    }
    for(int i = 1;i<=m;++i) ans[i] = vt[1][i];
    findDiff();
    if(maxx<=2)
    {
        GOOD();
    }
    else if(maxx>=5)
    {
        printf("No\n");
    }
    else if(maxx==3)
    {
        tmpLen = 0;
        for(int i = 1;i<=m;++i)
        {
            if(ans[i]!=vt[xb][i]) tmp[++tmpLen] = i;
        }
        for(int i = 1;i<=tmpLen;++i)
        {
            for(int j = 1;j<=m;++j) ans[j] = vt[1][j];
            ans[tmp[i]] = vt[xb][tmp[i]];
            findDiffOne();
            if(maxx_<=2)
            {
                GOOD();
                return 0;
            }
            if(maxx_>3)
            {
                continue;
            }
            tmpLen_ = 0;
            for(int j = 1;j<=m;++j) if(ans[j]!=vt[xb_][j]) tmp_[++tmpLen_] = j;
            for(int j = 1;j<=tmpLen_;++j)
            {
                int lastOne = ans[tmp_[j]];
                if(gaoOne(j))
                {
                    GOOD();
                    return 0;
                }
                else
                {
                    ans[tmp_[j]] = lastOne;
                }
            }
        }
        printf("No\n");

    }
    else
    {
        tmpLen = 0;
        for(int i = 1;i<=m;++i)
        {
            if(ans[i]!=vt[xb][i]) tmp[++tmpLen] = i;
        }
        int initXb = xb;
        if(gao(1,2,initXb)||gao(1,3,initXb)||gao(1,4,initXb)||gao(2,3,initXb)||gao(2,4,initXb)||gao(3,4,initXb))
        {
            GOOD();
        }
        else
        {
            printf("No\n");
        }
    }


    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/54909?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号