当前位置:   article > 正文

Codeforces Round #698 (Div. 2) A~F

codeforces round #698

A. Nezzar and Colorful Balls

题目传送门:

A. Nezzar and Colorful Balls

思路:

水题,找到最多有多少个数是相同的即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
int a[105];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int res=1;
        int num=1;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
            if(a[i]!=a[i-1]) num=1;
            else
            {
                num++;
                res=max(res,num);
            }
        }
        printf("%d\n",res);
    }
    //system("pause");
    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

B. Nezzar and Lucky Number

题目传送门:

B. Nezzar and Lucky Number

题目大意:

给你一个数字d。如果一个整数中的某一位是d则这个整数是幸运数字,给你一个整数,问这个数是否能由若干个幸运数字相加而成。

思路:

1.当 x >= d * 10 直接输出YES , 比如当d=7时, 70~76都为幸运数字,而的大于76的数都可以由其中的一个数+7的倍数组成。
2.当 x<d*10 时直接打表判断即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int f[10][15];
int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=9;i++)
        for(int j=0;j<=10;j++)
            f[i][j]=-1;
    for(int i=1;i<=9;i++)
        for(int j=1;j<=10;j++)
            if(f[i][i*j%10]==-1) f[i][i*j%10]=i*j;
    while(t--)
    {
        int q,d;
        scanf("%d%d",&q,&d);
        for(int i=1;i<=q;i++)
        {
            int x;
            scanf("%d",&x);
            if(x>=d*10) printf("YES\n");
            else
            {
                if(f[d][x%10]!=-1&&x>=f[d][x%10])
                    printf("YES\n");
                else printf("NO\n");
            }
        }
    }
    //system("pause");
    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

C. Nezzar and Symmetric Array

题目传送门:

C. Nezzar and Symmetric Array

思路:

1.由于a数组中正负两个数成对出现,所以d数组中每个数也得出现两次
2.我们假设原来的正数由a1、a2、a3、a4组成且递增,则这几个数的di为:

  • d1=a2-a1+a3-a1+a4-a1+a1+a1+a1+a2+a1+a3+a1+a4=2×a1+2×a2+2×a3+2×a4

  • d2=a2-a1+a3-a2+a4-a2+a1+a2+a2+a2+a2+a3+a2+a4=4×a2+2×a3+2×a4

  • d3=a3-a1+a3-a2+a4-a3+a1+a3+a2+a3+a3+a3+a3+a4=6×a3+2×a4

  • d4=a4-a1+a4-a2+a4-a3+a1+a4+a2+a4+a3+a4+a4+a4=8×a4
    这规律应该就很明显了吧,判断一下整除和正负关系即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
LL d[N],a[N],ans[N];
map<LL,int>mp;//记录每个数字出现的次数
int tot=0;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        mp.clear();
        int flag=0;
        tot=0;
        for(int i=1;i<=2*n;i++)
        {
            scanf("%lld",&d[i]);
            if(!mp[d[i]]) a[++tot]=d[i];
            mp[d[i]]++;
            if(mp[d[i]]>2) flag=1;
        }
        if(flag==1)
        {
            printf("NO\n");
            continue;
        } 
        sort(a+1,a+1+tot);
        for(int i=1;i<=tot;i++)
        {
            if(mp[a[i]]==1)
            {
                flag=1;
                break;
            }
        }
        if(flag==1)
        {
            printf("NO\n");
            continue;
        }
        LL sum=0;
        for(int i=tot;i>=1;i--)
        {
            LL k=2*i;
            a[i]=a[i]-2*sum;
            if(a[i]%k||a[i]<=0)
            {
                flag=1;
                break;
            }
            ans[i]=a[i]/k;
            sum=sum+ans[i];
        }
        if(flag==0) printf("YES\n");
        else printf("NO\n");
    }
    //system("pause");
    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

D. Nezzar and Board

题目传送门:

D. Nezzar and Board

题目大意:

给你n个n个不同的整数,你可以选2个数x,y(可以相同),进行2*x-y的操作,并将操作后的数加入其中。问经过一系列的操作,能不能得到整数m。

思路:

如果把这个操作看成 x + ( x - y ),那么就可以把整个过程看做是任取一个元素x,并加上两个数的差。我们又可以注意到像a3-a1这样的差可以由 ( a3 - a2 ) + ( a2 - a1 ) 来构成。及任意两项的差都可以转化为相邻两项的差得到。其实我们可以固定x为a1。那么式子就可以转化为 :

a1+k1(a2-a1)+k2(a3-a2)+k3(a4-a3)……kn(an-an-1)=m

k1(a2-a1)+k2(a3-a2)+k3(a4-a3)……kn(an-an-1)=m-a1

看着这个式子是不是很像裴蜀定理。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
LL a[N];
LL gcd(LL x,LL y)
{
    if(x%y==0) return y;
    return gcd(y,x%y);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        LL n,k;
        scanf("%lld%lld",&n,&k);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        LL g=abs(a[2]-a[1]);
        for(int i=3;i<=n;i++)
            g=gcd(g,abs(a[i]-a[i-1]));
        if((k-a[1])%g!=0) printf("NO\n");
        else printf("YES\n");
    }
    //system("pause");
    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

E. Nezzar and Binary String

题目传送门:

Nezzar and Binary String

题目大意:

给你一个长度为n的二进制字符串s,有q个询问,每次询问区间[l,r]。每次操作分为两个部分:
1.询问区间[l,r]中是否同时含有1和0,如果同时含有,则立即停止
2.如果区间中全部都为1种元素,那么你可以修改其中严格少于区间长度的一半的元素。
问经过q次操作之后是否能从字符串s到字符串f。

思路:

正着想比较难想,于是我们反着来。
那么也就是先进行修改。将查询区间都修改为1种元素。最后再和目标序列比较。那么怎么进行修改呢,就是把数量少的元素向数量多的元素进行修改,这样才能满足修改数量的限制。当区间长度为偶数,且0和1的数量相等时,这时无法修改,直接退出并输出NO

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],b[N],l[N],r[N];
struct node
{
    int l,r;
    int num0,num1;
    int lazy;
}tr[N*4];
void pushup(int k)
{
    tr[k].num0=tr[k<<1].num0+tr[k<<1|1].num0;
    tr[k].num1=tr[k<<1].num1+tr[k<<1|1].num1;
}
void pushdown(int k)
{
    if(tr[k].lazy)
    {
        int x=0,y=0;
        if(tr[k].num0) x=1;
        if(tr[k].num1) y=1;
        tr[k<<1].num0=x*(tr[k<<1].r-tr[k<<1].l+1);
        tr[k<<1].num1=y*(tr[k<<1].r-tr[k<<1].l+1);
        tr[k<<1|1].num0=x*(tr[k<<1|1].r-tr[k<<1|1].l+1);
        tr[k<<1|1].num1=y*(tr[k<<1|1].r-tr[k<<1|1].l+1);
        tr[k<<1].lazy=tr[k<<1|1].lazy=1;
        tr[k].lazy=0;
    }
}
void build(int k,int l,int r)
{
    tr[k].l=l,tr[k].r=r;
    tr[k].lazy=0;
    if(l==r)
    {
        if(b[l]==0)
        {
            tr[k].num0=1;
            tr[k].num1=0;
        }
        else
        {
            tr[k].num1=1;
            tr[k].num0=0;
        }
        return ;
    }
    int mid=(l+r)/2;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    pushup(k);
}
int query(int k,int l,int r)   //返回的是0的数量
{
    if(tr[k].l>=l&&tr[k].r<=r)
        return tr[k].num0;
    pushdown(k);
    int mid=(tr[k].l+tr[k].r)/2;
    int res=0;
    if(l<=mid) res=query(k<<1,l,r);
    if(r>=mid+1) res+=query(k<<1|1,l,r);
    return res;
}
void modify(int k,int l,int r,int x)
{
    if(tr[k].l>=l&tr[k].r<=r)
    {
        if(x==0)
        {
            tr[k].num1=0;
            tr[k].num0=tr[k].r-tr[k].l+1;
        }
        else
        {
            tr[k].num0=0;
            tr[k].num1=tr[k].r-tr[k].l+1;
        }
        tr[k].lazy=1;
        return ;
    }
    pushdown(k);
    int mid=(tr[k].r+tr[k].l)/2;
    if(l<=mid) modify(k<<1,l,r,x);
    if(r>=mid+1) modify(k<<1|1,l,r,x);
    pushup(k);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,q;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++)
            scanf("%1d",&a[i]);
        for(int i=1;i<=n;i++)
            scanf("%1d",&b[i]);
        for(int i=1;i<=q;i++)
            scanf("%d%d",&l[i],&r[i]);
        build(1,1,n);
        int flag=0;
        for(int i=q;i>=1;i--)
        {
            int k=query(1,l[i],r[i]);
            int len=r[i]-l[i]+1;
            if(len%2==0&&k==len/2)
            {
                flag=1;
                break;
            }
            else
            {
                if(k>len-k)//0的数量比较多
                    modify(1,l[i],r[i],0);
                else modify(1,l[i],r[i],1);//1的数量比较多
            }
        }
        if(flag==1)
        {
            printf("NO\n");
            continue;
        } 
        for(int i=1;i<=n;i++)
        {
            if(a[i]==0&&!query(1,i,i))
            {
                flag=1;
                break;
            }
            if(a[i]==1&&query(1,i,i))
            {
                flag=1;
                break;
            }
        }
        if(flag==1) printf("NO\n");
        else printf("YES\n");
    }
    //system("pause");
    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

F. Nezzar and Nice Beatmap

借鉴了某大佬博客

在这里插入图片描述

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>pii;
const int N=5005;
pii a[N];
LL dist(const pii &a,const pii &b)
{
    LL dx=a.first-b.first;
    LL dy=a.second-b.second;
    return dx*dx+dy*dy;
}
bool st[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].first,&a[i].second);
    st[1]=1;
    printf("1 ");
    int ans=1;
    for(int i=2;i<=n;i++)
    {
        LL maxn=-1e18;
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(st[j]) continue; //已经用过了
            LL d=dist(a[ans],a[j]);
            if(d>maxn)
            {
                maxn=d;
                t=j;
            }
        }
        if(t==-1) break;
        st[t]=1;
        ans=t;
        printf("%d ",t);
    }
    //system("pause");
    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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/75404
推荐阅读
相关标签
  

闽ICP备14008679号