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

作者：凡人多烦事01 | 2024-02-10 20:54:28

踩

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