Codeforces Round #698 (Div. 2)

https://codeforces.ml/contest/1478

A. Nezzar and Colorful Balls

题意

给出一个不下降序列，要求将其分成尽可能少的严格上升子序列。

解答

直接求出每个数字的最大次数即可

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N=256;
int n,T;
int a[N];
int main()
{
    int i;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        for(i=1;i<=n;i++) 
            scanf("%d",&a[i]);
        int cnt=1,ans=1;
        for(i=2;i<=n;i++) {
            if(a[i]==a[i-1]) ans=max(ans,++cnt);
            else cnt=1;
        }
        ans=max(ans,cnt);

        printf("%d\n",ans);
    }
    return 0;
}

B. Nezzar and Lucky Number

思路

x是否为包含d的数之和。

1.首先考虑x很大的情况，当x大于等于d×10的时候，x=d×10显然成立，当x大于d×10时，必然存在两个位数中包含d的数之和为x，其中一个十位为d，另一个个位为d则必然存在满足条件的解；

2.当x小于d×10时，d只能出现在个位，将10×d以内的d的所有倍数的个位存下来，
与x判断如果x的个位没有出现过则无法得到；

• 如果x的个位出现过但是x小于d的倍数中最小的与x个位相同的数则同样无法得到；
• 只有x大于等于它时，可以通过改变十位的值相加得到x。

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t, q, d, a, y, i;
    cin >> t;
    while (t--) {
        cin >> q >> d;
        while (q--) {
            cin >> a;
            y = a % d;
            while ((y - d) % 10 && y < 10 * d)
                y += d;
            if (y > a)
                cout << "NO" << endl;
            else
                cout << "YES" << endl;
        }
    }
    return 0;
}

C. Nezzar and Symmetric Array

思路

由题意可以知道d数组一定由n对相同的数组成。

假设原来数组中的正数由a1、a2、a3、a4组成(且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

由此可推得: di=2×i×ai+2×∑nj ai。(j=i+1)
(最后注意特判一下是否存在ai为0的情况，此类不满足要求)

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
ll d[maxn<<1];
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=2*n;i++)
            scanf("%lld",&d[i]);
        sort(d+1,d+2*n+1);
        int ok=1; ll sum=0;
        for(int i=2*n;i&&ok;i-=2)
        {
            if(d[i]!=d[i-1]) ok=0;
            if(i>2&&d[i]==d[i-2]) ok=0;
            ll cur=d[i]-sum;
            if(cur<=0||cur%i) ok=0;
            sum+=2LL*cur/i;
        }
        puts(ok?"YES":"NO");
    }
}

D Nezzar and Board

思路

因为2*x-y=x+x-y,相当于加上和任意数的差，所以只需要判断一下数组中的任意一个是否能够加上多少称为k。
加上多少的这个数就是所有数差的gcd。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n,k;
        scanf("%lld%lld",&n,&k);
        vector<ll>a(n);
        ll w=0;
        cin>>a[0];
        for(int i=1;i<n;i++) scanf("%lld",&a[i]),w=__gcd(w,abs(a[0]-a[i]));
        puts((k-a[0])%w?"NO":"YES");
    }
}

太难了！！！