Codeforces Round #698 (Div. 2)_codeforces round 698 (div. 1)

A：Nezzar and Colorful Balls

  给你一个序列，你可以选择一个严格递增序列划分成一组，问你最少只需要划分几组。典型的贪心问题，划分成一组时尽可能地把能加入的元素都加入当前的序列中。

#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
int a[110],vis[110];
int main()
{
    close;
    int T;cin>>T;
    while(T--)
    {
        int n;cin>>n;
        for(int i=1;i<=n;++i) cin>>a[i];
        memset(vis,0,sizeof(vis));
        int ans=0;
        while(1)
        {
            bool ok=false;int cur=0;
            for(int i=1;i<=n;++i)
                if(!vis[i] && a[i]>cur) cur=a[i],vis[i]=1,ok=true;
            if(ok) ans++;
            else break;
        }
        cout<<ans<<endl;
    }
}
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

B：Nezzar and Lucky Number

  给定一个数$d$，当$a_i$在他的十进制表示中，$d$出现了至少一次，这个数就是幸运数字。而题目要求的是求解对于给定的元素$x$，这个数是否本身是幸运数字或者可以表示为一系列幸运数字的和。
  我们首先要发现这样一个规律：①当$x\ge 10\ast d$时一定是“YES”。因为当两个数的十位数不同时，他们的差最小是2，最大是18。$[d\ast 10,d\ast 10+9]$区间的数是幸运数字，而大于这些数的时候，总能通过这些幸运数字加上若干个$d$形成（因为上述的幸运区间的跨度是10，恒大于$d$，因此能做到全覆盖）。②而当$x<10\ast d$的时候情况就有些许复杂，造成该现象的原因是一些个位出现了$d$的数字造成构成的数字不是$d$的倍数（例如$d=3$时，$16=13+3$）我们暴力判断即可。

#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
bool Judge(int x,int d)
{
    if(x<=0) return false;
    while(x){if(x%10==d) return true;return false;}
}
bool Solve(int x,int d)
{
    if(x>=d*10 || Judge(x,d)) return true;
    while(x>0){x-=d;if(Judge(x,d)) return true;}
    return  false;
}
int main()
{
    close;int T;cin>>T;
    while(T--)
    {
        int q,d;cin>>q>>d;
        for(int i=1;i<=q;++i) 
        {
            int x;cin>>x;
            if(Solve(x,d)) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
}
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

C：Nezzar and Symmetric Array

  给定序列$d$，满足$d_i={\sum }_{j=1}^{2n}|a_i-a_j|$；而序列$a$满足：①$2n$个元素互不相同；②对于任意的元素$a_i$,一定在原序列中存在$-a_i$.问这样的序列$a$是否存在。
  我们可以通过计算比较出序列$d$的值和点坐标的关系。例如下面的八个点：

八个点关于坐标原点两两对称，我们计算后面四个点的$d_i$，分别是：$$d_1=(x_1+x_2+x_3+x_4)\ast 2$$$$d_2=(x_2+x_2+x_3+x_4)\ast 2$$$$d_3=(x_3+x_3+x_3+x_4)\ast 2$$$$d_4=(x_4+x_4+x_4+x_4)\ast 2$$很容易发现可以从最后一个方程开始，依次倒推去解$x_4,x_3,x_2,x_1$,只要能有正整数解，同时各个解互不相同，说明这个答案是成立的，即我们能找到这样的序列$a$.

#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
const int maxn=2e5+100;
typedef long long ll;
ll a[maxn];int n;
bool solve()
{
    sort(a+1,a+2*n+1);
    for(int i=1;i<=2*n;i+=2)
        if(a[i]&1 || a[i]!=a[i+1]) return false;
    if(a[2*n]%(2*n)!=0) return false;
    ll last=a[2*n]/(n*2),sum=last;
    if(last==0) return false;
    for(int i=n-1;i>0;--i)
    {
        if((a[2*i]-sum*2)%(2*i)!=0) return false;
        ll cur=(a[2*i]-sum*2)/(2*i);
        if(cur>=last || cur<=0) return false;
        last=cur;sum+=cur;
    }
    return true;
}
int main()
{
    close;int T;cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=2*n;++i)  cin>>a[i];
        if(solve()) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}
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

D：Nezzar and Board

  题目的意思是给定$n$个不同的数$x_i$，能否通过不断选取$x,y$，并加入新的元素$2x-y$的方式，最后构造出$k$.
  这个题本质上是在考察扩展欧几里得算法：对于$a,b$来说，一定能找到$q,r$使得$a=q\ast b+r$成立。而求解最大公因数就是采用辗转相除的方式，算法的终点就是$a==gcd,b==0$.得到0对于这个题是毫无意义的，而gcd应该是我们能够得到的最小的数。而$2x-y$本质上就是在模拟辗转相除，例如令$y=qx+r$，那么经过不断地变化我们能够得到$r(q为偶数)或者-x+r(q为奇数)$，而前面的$x$有或者无都不影响gcd的求解，即$gcd(-x+r,x)==gcd(r,x)$。因此，我们只要找到上述所有相邻元素的差值，并求解gcd，就是在求解变换的最小步长。只要$(k-a[1])\%ste{p}_{min}==0$，则该变换能够做到。

#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
const int maxn=2e5+100;
ll a[maxn];
int main()
{
    close;int T;cin>>T;
    while(T--)
    {
        ll n,k;cin>>n>>k;
        for(int i=1;i<=n;++i) cin>>a[i];
        sort(a+1,a+n+1);
        ll min_minus=0;
        for(int i=1;i<n;++i) min_minus=__gcd(min_minus,a[i+1]-a[i]);
        if((k-a[1])%min_minus==0) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

E：Nezzar and Binary String

  题目的意思是给定起始字符串和终止字符串，然后给出q组区间，每次先比较该区间是否都是相同的数字，然后可以对该区间进行修改，但修改的个数必须严格小于长度的一半，问最终能否达到终止字符串。
  这个题的关键在于反向思维，给你终止字符串，反向给你询问区间，你先修改这个区间使其变成相同的数字，然后再由对方判断，最终如果能到达起始字符串就输出“YES”，反向思维的好处是在于这种情况下做出的修改的方式是唯一的。需要注意一个细节，但询问的区间长度是偶数时，而恰好0,1的数量各占一半，这种情况没有办法作出修改，一定无法让区间全为一种数字，直接输出“NO”。
  区间覆盖成一种数字可以采用线段树的方式，最终的复杂度是$O((n+q)logn)$.

#include<bits/stdc++.h>
#define close ios::sync_with_stdio(false)
using namespace std;
const int maxn=2e5+100;
int before[maxn],after[maxn],tree[maxn*4],mark[maxn*4],n,q;
char be[maxn],af[maxn];
struct Rec{
    int l,r;
}rec[maxn];
void push_down(int p,int len)
{ 
	if(mark[p]==-1) return;
    mark[2*p]=mark[p];mark[2*p+1]=mark[p];
	tree[2*p]=mark[p]*(len-len/2);
	tree[2*p+1]=mark[p]*(len/2);
	mark[p]=-1;
}
void build(int l=1,int r=n,int p=1)
{
	if(l==r) tree[p]=after[l];
	else{
		int mid=(l+r)/2;
		build(l,mid,2*p);
		build(mid+1,r,2*p+1);
		tree[p]=tree[p*2]+tree[p*2+1];
	}
}
void update(int l,int r,int d,int p=1,int cl=1,int cr=n)
{
	if(l>cr || r<cl) return;
	if(l<=cl && cr<=r) 
	{
		tree[p]=d*(cr-cl+1);
		if(cr>cl) mark[p]=d;
	}  
	else{
		int mid=(cl+cr)/2;
		push_down(p,cr-cl+1);
		update(l,r,d,p*2,cl,mid);
		update(l,r,d,p*2+1,mid+1,cr);
		tree[p]=tree[p*2]+tree[p*2+1]; 
	} 
}
int query(int l,int r,int p=1,int cl=1,int cr=n)
{
	if(l>cr || r<cl) return 0;
	if(l<=cl && cr<=r) return tree[p];
	else{
		int mid=(cl+cr)/2;
		push_down(p,cr-cl+1);
		return query(l,r,2*p,cl,mid)+query(l,r,2*p+1,mid+1,cr);
	}
}
bool solve()
{
    scanf("%d%d",&n,&q);
    scanf("%s",be);scanf("%s",af);
    for(int i=0;i<n;++i) before[i+1]=be[i]-'0',after[i+1]=af[i]-'0';
    for(int i=0;i<=4*n+10;++i) mark[i]=-1;
    build();
    for(int i=1;i<=q;++i) scanf("%d%d",&rec[i].l,&rec[i].r);
    for(int i=q;i>0;--i)
    {
        int cur=query(rec[i].l,rec[i].r),len=rec[i].r-rec[i].l+1;
        if(len%2==0){
            if(cur*2==len) return false;
            if(cur*2>len) update(rec[i].l,rec[i].r,1);
            else update(rec[i].l,rec[i].r,0);
        }
        else{
            if(cur*2>len) update(rec[i].l,rec[i].r,1);
            else update(rec[i].l,rec[i].r,0);
        }
    }
    for(int i=1;i<=n;++i)
        if(query(i,i)!=before[i]) return false;
    return true;
}
int main()
{
    close;int T;scanf("%d",&T);
    while(T--)
    {
        if(solve()) printf("YES\n");
        else printf("NO\n");
    }
}
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

F：Nezzar and Nice Beatmap

  题目要求给出一个序列，使得序列中任意三个连续的顶点$A,B,C$，构成的三角形（可以退化成一条边）中，$\angle B<90^{\circ }$。
  这道题可以理解成一个三角形的定理：三角形中最多有一个钝角或者直角，而且一定是最长边所对应的角。因此，我们可以任选一个点作为起点，每轮迭代都找一条最长的边，那么这条边与其他边所夹的角一定是锐角。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e3+100;
struct Point{
    ll x,y;
}P[maxn];
int vis[maxn];
double GetDistance(int i,int j) {return sqrt((P[i].x-P[j].x)*(P[i].x-P[j].x)+(P[i].y-P[j].y)*(P[i].y-P[j].y));}
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%lld%lld",&P[i].x,&P[i].y);
    memset(vis,0,sizeof(vis));
    printf("1");vis[1]=1;
    int cur_id=1;
    for(int i=2;i<=n;++i)
    {
        double max_dis=0.0;int next_id;
        for(int i=1;i<=n;++i)
        {
            if(vis[i]) continue;
            double cur_dis=GetDistance(cur_id,i);
            if(cur_dis>max_dis) max_dis=cur_dis,next_id=i;
        }
        printf(" %d",next_id);
        cur_id=next_id;vis[next_id]=1;
    }
}
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