Educational Codeforces Round 170 (Rated for Div. 2) solutions (A-E)

ACM
6.8k words

链接：Educational Codeforces Round 170 (Rated for Div. 2)

A - Two Screens

签到模拟题。

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;

//#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif 

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=100;

char str[2][maxn+5];

void solve(void){
	scanf("%s%s",str[0]+1,str[1]+1);
    int n=strlen(str[0]+1),m=strlen(str[1]+1);
    int len=1;
    while (str[0][len]==str[1][len]&&len<=n&&len<=m) len++;
    if (len>1)
        printf("%d\n",n+m-(len-1)+1);
    else
        printf("%d\n",n+m);
}

int main(){
	int t=1;
	scanf("%d",&t);
	while (t--)
		solve();
//		cout<<(solve()?"YES":"NO")<<endl;
	return 0;
}

B - Binomial Coefficients, Kind Of

观察发现直接输出 2k2^k 即可。

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

//#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif 

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxt=1e5;
const ll mod=(1e9)+7;

int t;

ll n[maxt+5],k[maxt+5];

ll qpow(ll a,ll b,ll mod){
    a%=mod;
    ll res=1;
    while (b>0) {
        if (b&1)
            res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

void solve(void){
	cin>>t;
    for (int i=1;i<=t;i++)
        cin>>n[i];
    for (int i=1;i<=t;i++)
        cin>>k[i];
    for (int i=1;i<=t;i++){
        cout<<qpow(2LL,k[i],mod)<<endl;
    }
	
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int t=1;
//	cin>>t;
	while (t--)
		solve();
//		cout<<(solve()?"YES":"NO")<<endl;
	return 0;
}


C - New Game

排序然后双指针模拟。

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

//#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif 

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=2e5;

int n,k;
int a[maxn+5];


void solve(void){
	cin>>n>>k;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);

    int l=0;
    int type=0;
    int ans=0;
    for (int i=1;i<=n;i++){
        if (a[i]!=a[i-1])
            type++;
        if (a[i]-a[i-1]>1)
            l=i-1,type=1;
        while (type>k){
            l++;
            if (a[l]!=a[l+1])
                type--;
        }
        ans=max(ans,i-l);
    }
    cout<<ans<<endl;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int t=1;
	cin>>t;
	while (t--)
		solve();
//		cout<<(solve()?"YES":"NO")<<endl;
	return 0;
}

D - Attribute Checks

看见 m≤5000m\leq 5000 猜到起码是一个 O(m2)O(m^2) 的dp。设 dp[i][j]dp[i][j] 表示智力和力量分别为 ii 、jj 时能通过的最大属性检查次数。因为对于每个相同 i+ji+j 的 dp[i][j]dp[i][j]，他们到达的时间点都是一致的，无非是得到的属性点的分配问题。

那直接对每个确定的总属性点 i+ji+j，算他们与总属性点 i+j+1i+j+1 之间，过了多少次属性检查，对属性检查的要求排个序，然后模拟即可。复杂度O(m2log⁡n)O(m^2 \log n)，但是这个 log⁡\log 应该是比较小的，因为是多个总长度为 nn 的不同数组分批排序。

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

#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif 

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=2e6;
const int maxm=5000;

int n,m;
vector<int> req[maxm+5][2];

int dp[maxm+5][maxm+5];

void solve(void){
    cin>>n>>m;
    int now=0;
    for (int i=1,x;i<=n;i++){
        cin>>x;
        if (x==0)
            now++;
        else
            req[now][x>0].push_back(abs(x));
    }
    for (int i=0;i<=m;i++){
        sort(req[i][0].begin(),req[i][0].end());
        sort(req[i][1].begin(),req[i][1].end());
    }
    int ans=0;
    for (int len=1;len<=m;len++){
        int x=len,y=len-x;
        while (x>=0){
            dp[x][y]=max(x>=1?dp[x-1][y]:0,y>=1?dp[x][y-1]:0);
            x--;
            y=len-x;
        }
        x=len,y=len-x;
        int i=0,j=req[len][0].size()-1;
        while (x>=0){
            while (j>=0&&req[len][0][j]>x)
                j--;
            while (i<req[len][1].size()&&req[len][1][i]<=y)
                i++;
            dp[x][y]+=(j+1)+(i);
            debug(x,y,dp[x][y]);
            if (len==m)
                ans=max(dp[x][y],ans);
            x--;
            y=len-x;
        }
    }
	cout<<ans<<endl;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int t=1;
//	cin>>t;
	while (t--)
		solve();
//		cout<<(solve()?"YES":"NO")<<endl;
	return 0;
}


E - Card Game

首先，要让第一个人赢，除了1外，每种花色中，第一个人的数量一定是小等于第二个人的（如果大于，那多出来的牌只能被1花色击败）。

设从花色2∼n2\sim n，每种花色 ii 中，数量都有

res[i]=cnt_2[i]-cnt_1[i]>0 & i\in[2,n]\\

而这些普通的花色，2多出来的，都要和花色1中，1多于2的来互补，也就是说

−res[1]=cnt1[i]−cnt2[i]=∑i=2nres[i]-res[1]=cnt_1[i]-cnt_2[i]=\sum_{i=2}^n res[i]

2∼n2\sim n的普通花色，每种情况都是一样的。我们设任意一种花色中，在给定牌号为 1∼i(i∈[1,m])1\sim i(i\in[1,m])时，2比1多jj个牌，且1每张牌都有对应的2的更小牌，情况数是dp[i][j]dp[i][j]。ii 的情况显然可以从 i−1i-1 转移过来，且只有两种情况，一种是牌分配给1，一种是牌分配给2，而且因为 ii 一定比 1∼i−11\sim i-1 大，所以不需要特别限制“1每张牌都有对应的2的更小牌”。

dp[i][j]=dp[i−1][j−1]+dp[i−1][j+1]dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]

然后要用这个来推总的情况数，暴力枚举每种加法和肯定是不行。我们设 g[i][j]g[i][j] 表示2∼i2\sim i 中，总共2比1多了 jj 张牌的情况数，有

g[i][j]=∑k=0jg[i−1][k]×dp[m][j−k]g[i][j]=\sum_{k=0}^jg[i-1][k]\times dp[m][j-k]

最终答案就是二者互补的答案，也就是枚举花色1中1比2多kk的情况

ans=∑k=0mdp[m][k]×g[n][k]ans=\sum_{k=0}^m dp[m][k]\times g[n][k]

是一个很精彩的dp套dp。

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

//#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif 

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=500;
const ll mod=998244353;

int n,m;

ll dp[maxn+5][maxn+5];
ll g[maxn+5][maxn+5];

void solve(void){
	cin>>n>>m;
    dp[0][0]=1;
    for (int i=1;i<=m;i++)
        for (int j=0;j<=i;j++){
            if (j)
                dp[i][j]+=dp[i-1][j-1],dp[i][j]%=mod;
            dp[i][j]+=dp[i-1][j+1],dp[i][j]%=mod;
        }
    g[1][0]=1;
    for (int i=2;i<=n;i++)
        for (int j=0;j<=m;j++)
            for (int k=0;k<=j;k++)
                g[i][j]+=g[i-1][k]*dp[m][j-k]%mod,g[i][j]%=mod;
    ll ans=0;
    for (int k=0;k<=m;k++)
        ans+=dp[m][k]*g[n][k]%mod,ans%=mod;
	cout<<ans<<endl;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int t=1;
//	cin>>t;
	while (t--)
		solve();
//		cout<<(solve()?"YES":"NO")<<endl;
	return 0;
}