Educational Codeforces Round 164 (Rated for Div. 2)

做完才发现AB题都是读假题

CF1954A Painting the Ribbon

本题就是要找出均分后的最大值

直接就是n/m向上取整

(n+m-1)/m即答案，需要特判一下罢也许

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
const int N=1e6+100;
int a[N];
void Totoro()
{
    int n,m,k;
    cin>>n>>m>>k;
//要使得颜色尽可能分散
//所以说颜色要尽可能不一样
if(n==1)
{
    cout<<"NO"<<'\n';
    return ;
}
if(m==1)
{
    cout<<"NO"<<'\n';
    return ;
}

int mi = (n + m - 1) / m;
int p = n - mi;
    if(p<=k)
    {
       cout<<"NO"<<'\n'; 
    }
    else
    {
        cout<<"YES"<<'\n';
    }
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        Totoro();
    }
    return 0;
}

CF1954B Make It Ugly

题意是如果两边相等可以把中间变成两边的，结尾和开头肯定改变不了，只需要让两个连续不同的挨在一起就可以

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
const int N=1e6+100;
int a[N];
int b[N];
void Totoro()
{
    int n;
    cin>>n;
    bool flag=0;
    int maxn=0;
    rep(i,1,n)
    {
        cin>>a[i];
        if(a[i]!=a[i-1]&&i!=1)
        {
            flag=1;
        }    
    }
if(!flag)
{
    cout<<-1<<'\n';
    return ;
}
int minn=1e18;
int c=0;
rep(i,1,n)
{
    if(a[i]!=a[1])
    {
        minn=min(minn,min(n-i,i-1));
        if(c)
        {
            minn=min(minn,i-c-1);
        }
        c=i;
    }
    else
    {
        continue;
    }
}
cout<<minn<<'\n';
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        Totoro();
    }
    return 0;
}

CF1954C Long Multiplication

这题其实就是让两个数字尽可能接近

如果一位数大，那么把剩下的大的都给另一位数，就是一个小贪心

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
const int N=1e6+100;
void Totoro()
{
    string s1;
    string s2;
    cin>>s1>>s2;
    int n=s1.length();
    s1=" "+s1;
    s2=" "+s2;
    int sum1=0;
    int sum2=0;
    int flag=0;
rep(i,1,n)
{
    if(s1[i]!=s2[i])
    {
        flag=i;
        break;
    }
}
if(!flag)
{
    rep(i,1,n)
    {
        cout<<s1[i];
    }
    cout<<'\n';
    rep(i,1,n)
    {
        cout<<s2[i];
    }
    cout<<'\n';
    return ;
}
if(s1[flag]<s2[flag])
{
 swap(s1,s2);   
}
rep(i,flag+1,n)
{
    if(s1[i]>s2[i])
    {
        swap(s1[i],s2[i]);
    }
}
    rep(i,1,n)
    {
        cout<<s1[i];
    }
    cout<<'\n';
    rep(i,1,n)
    {
        cout<<s2[i];
    }
    cout<<'\n';

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

CF1954D Colored Balls

本题是一个鸽巢原理，如果要分组，两个数一定不同，如果存在绝对众数，那么一定是绝对众数，如果不是就是总体的和/2.

f[j]表示和为j以i为结尾的子序列。

所以我们可以给各种颜色小球的数量排个序,然后枚举数量最多的小球有多少个,用背包统计之前选了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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
const int N=1e6+100;
const int p=998244353;
int a[N];
int f[N];
void Totoro()
{
  int n;
  cin>>n;
  int sum=0;
    rep(i,1,n)
    {
        cin>>a[i];
        sum+=a[i];
    }
sort(a+1,a+1+n);
f[0]=1;
ll ans=0;
rep(i,1,n)
{
    rep(j,0,sum-a[i])
    {
        ans+=(a[i]>j?a[i]:(j+a[i]+1)/2)*f[j]%p;
    }
    //01背包逆序
    frep(j,sum,a[i])
    {
f[j]=(f[j]+f[j-a[i]])%p;
    }
}
cout<<ans%p<<'\n';
}
signed main()
{
    int t=1;
    //cin>>t;
    while(t--)
    {
        Totoro();
    }
    return 0;
}