Codeforces Round #698 (Div. 2)_codeforces 698div2

A
给出一个非递减的数组，问最少用几种颜色染色，使得每一个颜色中的数严格递增
明显只要不是同一个数，就可以用同一种颜色染，因此记录最多出现的数

#include <bits/stdc++.h>
using namespace std;
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define ll long long
inline ll read(){ll f=1;ll x=0;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f; }
inline ll quick_pow(ll a,ll b,ll mod) {ll ans=1,base=a;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod;}
inline ll inv(ll x,ll p){return quick_pow(x,p-2,p);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const double pi=acos(-1.0);
const ll inf = LONG_LONG_MAX;
const ll mod = 998244353;
const ll maxn = 110;
void solve()
{
    int a[maxn];
    int n;
    cin >> n;
    int maxx = 0;
    map<int,int> m;
    rep(i,1,n)
    {
        scanf("%d", &a[i]);
        m[a[i]]++;
        maxx = max(maxx, m[a[i]]);
    }
    cout << maxx << '\n';
    return;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
    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

B
q次询问一个元素是否能由多个十进制中带有d的数的和组成。
当一个数大于等于10d的时候必定有解，任何数都可以由(d10 + x) + nd组成
举例，当d = 7时，明显70-77是合法的。在到达77的时候，可以变化为70 + 7，此时明显(70,70+7) + 7也就是77-84合法，以此类推。
当小于10d的时候，不断减d。如果可以使得个位数为0，一定合法，因为可以在任意一个数中加上剩余得数使得合法。
举例，d = 7,num = 58。当num减四次d的时候，则变成了7 + 7 + 7 + 7 + 30，明显7+30 = 37是合法的，则可以变成7+7+7+37。

#include <bits/stdc++.h>
using namespace std;
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define ll long long
inline ll read(){ll f=1;ll x=0;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f; }
inline ll quick_pow(ll a,ll b,ll mod) {ll ans=1,base=a;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod;}
inline ll inv(ll x,ll p){return quick_pow(x,p-2,p);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const double pi=acos(-1.0);
const ll inf = LONG_LONG_MAX;
const ll mod = 998244353;
const ll maxn = 1e4+10;

void solve()
{
    int q,d;
    cin >> q >> d;
    while(q--)
    {
        int tmp;
        cin >> tmp;
        bool flag = false;
        if(tmp >= 10 * d)
            puts("YES");
        else
        {
            while(tmp > 0)
            {
                if(tmp % 10 == d)
                {
                    puts("YES");
                    flag = true;
                    break;
                }
                tmp -= d;
            }
            if(!flag)
                puts("NO");
        }
    }
    return;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
    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

C
由数组a给出n对相反数，给出变化后的数组d，变化为di=∑2nj=|ai−aj|。问能否由d数组反推出唯一的a数组
可以由第一个样例分析
a = -1,1,-3,3
d = 8,8,12,12
看第一个数1。自身的相反数会对他产生一个贡献，即2a1，第二个数及其相反数也会对其产生贡献由于即|a1-a2|+|a1-(-a2)|
不妨假设a2大于a1，那么产生的结果就是a2-a1+a2+a1 = 2a2。因此不同的数aj对自身ai的贡献等于2max(ai,aj)。
因此对数组排序并去相反数后，最大的数的贡献即是数组长度(假设为n)乘这个数再乘2，次大的数的贡献是(n-1)乘次大值乘2，再加上最大值乘2,以此类推。

#include <bits/stdc++.h>
using namespace std;
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define ll long long
inline ll read(){ll f=1;ll x=0;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f; }
inline ll quick_pow(ll a,ll b,ll mod) {ll ans=1,base=a;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod;}
inline ll inv(ll x,ll p){return quick_pow(x,p-2,p);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const double pi=acos(-1.0);
const ll inf = LONG_LONG_MAX;
const ll mod = 998244353;
const ll maxn = 1e5+10;
ll a[maxn], d[maxn];
void solve()
{
    int n;
    cin >> n;
    rep(i, 1, 2*n)
        scanf("%lld", &d[i]);
    sort(d + 1, d + 1 + 2 * n);
    int tot=unique(d+1,d+1+2*n)-d-1;
	if(tot != n) {
        puts("NO");
        return;
    }
    ll suf = 0;
    bool flag = true;
    /*for (int i = 1;i <= n;i++)
        {
            cout << d[i] << " ";
        }
    cout << '\n';*/
    per(i,n,1)
    {
        if((d[i] - suf) % (2*i) ||d[i] <= suf )
        {
            flag = false;
            break;
        }
        a[i] = (d[i] - suf) / (2 * i);
        suf += 2 * a[i];
    }
    if(flag)puts("YES");
    else
        puts("NO");
    /*for (int i = 1;i <= n;i++)
        cout << a[i] << " ";
    cout << '\n';*/
    return;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
    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
选两个数，产生一个2*x-y的数，问是否能产生一个k
相当于产生x + x - y
考虑两个数的情况，由于两个数的差值一定是两个数最大公因数的倍数，因此两个数辗转相减能得到他们的最大公因数。多个数则是多个数的最大公因数，则最小单位就是这n个数差的最大公因数。
由于本题可以存在负数，因此只要任意找其中一个数验证即可

#include <bits/stdc++.h>
using namespace std;
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define ll long long
inline ll quick_pow(ll a,ll b,ll mod) {ll ans=1,base=a;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod;}
inline ll inv(ll x,ll p){return quick_pow(x,p-2,p);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const double pi=acos(-1.0);
const ll inf = LONG_LONG_MAX;
const ll mod = 998244353;
const ll maxn = 1e5 + 10;
void solve()
{
    ll n, k;
    cin >> n >> k;
    ll a[n + 2];
    rep(i, 1, n)
    {
        cin >> a[i];
    }
    ll factor = a[2]-a[1];
    rep(i,3,n)
    {
        factor = __gcd(factor, a[i] - a[i - 1]);
    }
    if((k-a[1])%factor == 0)
        puts("YES");
    else
        puts("NO");
    return;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
    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

后续待补