比赛链接：Dashboard - Educational Codeforces Round 164 (Rated for Div. 2) - Codeforces

A

签到题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m,k;
        cin>>n>>m>>k;
        if(n/m*(m-1)+max(n%m-1,0)>k)cout<<"YES\n";
        else cout<<"NO\n";

    }
    return 0;
}

B

题意：给出一个长为 $n$ 的数组 $a$ ，现在需要删除几个元素，使得最后的数组不满足以下条件：通过数次操作选择相等的 $a_{i-1}$ 与 $a_{i+1}$ ，将 $a_i$ 替换为这个数后，整个数组变得相等。

最后得到的数一定是 $a[1]$ 或者 $a[n]$ ，模拟发现要删除的元素个数就是连续的最小长度的 $a[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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;

void solve()
{
    int n;
    cin>>n;
    int a[n+5];
    for(int i=1;i<=n;i++)cin>>a[i];
    if(a[1]!=a[n])
    {
        cout<<"0\n";
        return;
    }

    int st=a[1];
    int ans=3e5+5;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {   
        if(a[i]==st)cnt++;
        else
        {
            if(cnt==0)
            {
                cout<<"0\n";
                return;
            }
            ans=min(ans,cnt);
            cnt=0;
        }
    }
    ans=min(ans,cnt);
    if(ans>=n)cout<<"-1\n";
    else cout<<ans<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

C

题意：给出两个长度相等的数 $x,y$ ，可以交换相同数位上的数，最后要使得 $x\times y$ 最大。

注意到 $x+y$ 是一个定值，要使 $x\times y$ 最大，那么就要使 $x,y$ 尽可能接近。假设 $x>y$ ，那么从高位枚举，使 $x$ 某一位上的数比 $y$ 相同位小即可。

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
#include<bits/stdc++.h>
using namespace std;

void solve()
{
    string x,y;
    cin>>x>>y;

    int s;
    int len=x.length();
    int pos=-1;
    for(int i=0;i<len;i++)
    {
        if(x[i]==y[i])continue;
        s=x[i]>y[i];
        pos=i;
        break;
    }

    if(pos==-1)
    {
        cout<<x<<endl<<y<<endl;
        return ;
    }

    for(int i=pos+1;i<len;i++)
    {
        if(s==1)
        {
            if(x[i]>y[i])swap(x[i],y[i]);
        }
        else
        {
            if(x[i]<y[i])swap(x[i],y[i]);
        }
    }

    cout<<x<<endl<<y<<endl;

}

int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

math

D

题意：有 $n$ 种不同的颜色，每种颜色的球有 $a_i$ 个。现在选某几种颜色的所有球视为一类，那么共有 $2^n$ 类，并将其分组，分组规则如下：每一组不超过两个球，且不能有相同颜色的球，且要使分的组数尽可能少。求所有类的分组的个数的总和。$a_1+…+a_n\leq 5000$

考虑对于某一类，如何分组最优。假设数量最多的球的个数是 $a_n$ ，总和是 $sum$ 。

  1. 若 $a_n\geq sum-a_n$，那么组数就是就是 $a_n$ 。具体方法为每一个 $a_n$ 配一个其他颜色的球。
  2. 若 $a_n\leq sum-a_n$ ，那么组数就是 $\lceil sum/2\rceil$ 。

因此可以采用如下方法进行统计：利用背包现将所有组合按照 $\lceil sum/2\rceil$ 进行统计，然后再补偿 $a_n\geq sum-a_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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int a[5005];
int dp[5005];

signed main()
{
    int n;
    cin>>n;
    int sum=0;
    int ans=0;
    for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];

    memset(dp,0,sizeof(dp));
    dp[0]=1;
    
    for(int i=1;i<=n;i++)
    {
        for(int j=sum;j>=a[i];j--)
        {
            dp[j]=(dp[j]+dp[j-a[i]])%mod;
        }
    }

    for(int i=1;i<=sum;i++)
    {
        ans=(ans+(i+1)/2*dp[i]%mod)%mod;
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<a[i];j++)
        {
            ans=(ans+(a[i]-(j+a[i]+1)/2)*dp[j]%mod)%mod;
        }
    }
    cout<<ans;
    return 0;
}

math

E

题意：有 $n$ 个怪兽，每个怪兽的生命值是 $a_i$ 。通过连锁反应进行攻击：每次选择一个没死的怪兽作为攻击起点，对其进行 $k$ 点攻击，然后攻击朝左边和右边扩散，都造成 $k$ 点攻击，直到遇到一个已经死亡的怪兽才停下来。对于 $k=1,2,…,max\ a_i$ ，分别求出最少杀死所有怪物的施法次数。

考虑 $k=1$ 的情况，可以发现攻击的次数即为 $\sum max(0,a_i-a_{i-1})$ 。可以考虑将其转换成一个至于本身有关的多项式，即转化为 $\sum c_ia_i$ 。关于系数 $c_i$ ，可以有如下方式确定：初始 $c_i=0$ ，若 $a_i>a_{i-1}$ ，$c_i++$ ，若 $a_i<a_{i+1}$ ，$c_i–$ 。

对于 $k>1$ 的情况，只需将 $a_i$ 变成 $\lceil a_i/k\rceil$ 即可。

关于统计答案对于某一个 $k$ ，可以观察到 $\lceil a_i/k\rceil$ 是根据 $k$ 分段的，即按照以下方式统计：
$$
1\times \sum_{i=1,…,k} c_i+2\times\sum_{i=k+1,…,2k}c_i+…
$$

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
#include<bits/stdc++.h>
using namespace std;
#define LL long long

int main()
{
    int n;
    cin>>n;
    int a[n+2];
    int mx=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        mx=max(mx,a[i]);
    }

    int ad[mx+1]={0};
    for(int i=1;i<=n;i++)
    {
        int c=0;
        if(i==1 || a[i]>a[i-1])c++;
        if(i<n && a[i]<a[i+1])c--;
        ad[a[i]]+=c;
    }

    for(int i=1;i<mx;i++)ad[i+1]+=ad[i];

    for(int k=1;k<=mx;k++)
    {
        LL ans=0;
        for(int val=1,l=1;l<=mx;l+=k,val++)
        {
            ans+=1LL*val*(ad[min(l+k-1,mx)]-ad[l-1]);
        }
        cout<<ans<<" ";
    }
    return 0;
}

math