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

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

A - Two Screens #

签到模拟题。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
//#undef LOCAL_DEBUG
5
#ifdef LOCAL_DEBUG
6
#include "debug.h"
7
#else
8
#define debug(...) (void)0
9
#define debug_array(arr, len) (void)0
10
#define debug_container(container) (void)0
11
#endif
12

13
typedef unsigned long long ull;
14
typedef long long ll;
15
typedef pair<int,int> P;
16
const int maxn=100;
17

18
char str[2][maxn+5];
19

20
void solve(void){
21
  scanf("%s%s",str[0]+1,str[1]+1);
22
    int n=strlen(str[0]+1),m=strlen(str[1]+1);
23
    int len=1;
24
    while (str[0][len]==str[1][len]&&len<=n&&len<=m) len++;
25
    if (len>1)
26
        printf("%d\n",n+m-(len-1)+1);
27
    else
28
        printf("%d\n",n+m);
29
}
30

31
int main(){
32
  int t=1;
33
  scanf("%d",&t);
34
  while (t--)
35
    solve();
36
//    cout<<(solve()?"YES":"NO")<<endl;
37
  return 0;
38
}

B - Binomial Coefficients, Kind Of #

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

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
//#undef LOCAL_DEBUG
5
#ifdef LOCAL_DEBUG
6
#include "debug.h"
7
#else
8
#define debug(...) (void)0
9
#define debug_array(arr, len) (void)0
10
#define debug_container(container) (void)0
11
#endif
12

13
typedef unsigned long long ull;
14
typedef long long ll;
15
typedef pair<int,int> P;
16
const int maxt=1e5;
17
const ll mod=(1e9)+7;
18

19
int t;
20

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

23
ll qpow(ll a,ll b,ll mod){
24
    a%=mod;
25
    ll res=1;
26
    while (b>0) {
27
        if (b&1)
28
            res=res*a%mod;
29
        a=a*a%mod;
30
        b>>=1;
31
    }
32
    return res;
33
}
34

35
void solve(void){
36
  cin>>t;
37
    for (int i=1;i<=t;i++)
38
        cin>>n[i];
39
    for (int i=1;i<=t;i++)
40
        cin>>k[i];
41
    for (int i=1;i<=t;i++){
42
        cout<<qpow(2LL,k[i],mod)<<endl;
43
    }
44

45
}
46

47
int main(){
48
  std::ios::sync_with_stdio(false);
49
  std::cin.tie(nullptr);
50
  std::cout.tie(nullptr);
51
  int t=1;
52
//  cin>>t;
53
  while (t--)
54
    solve();
55
//    cout<<(solve()?"YES":"NO")<<endl;
56
  return 0;
57
}

C - New Game #

排序然后双指针模拟。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
//#undef LOCAL_DEBUG
5
#ifdef LOCAL_DEBUG
6
#include "debug.h"
7
#else
8
#define debug(...) (void)0
9
#define debug_array(arr, len) (void)0
10
#define debug_container(container) (void)0
11
#endif
12

13
typedef unsigned long long ull;
14
typedef long long ll;
15
typedef pair<int,int> P;
16
const int maxn=2e5;
17

18
int n,k;
19
int a[maxn+5];
20

21

22
void solve(void){
23
  cin>>n>>k;
24
    for (int i=1;i<=n;i++)
25
        cin>>a[i];
26
    sort(a+1,a+n+1);
27

28
    int l=0;
29
    int type=0;
30
    int ans=0;
31
    for (int i=1;i<=n;i++){
32
        if (a[i]!=a[i-1])
33
            type++;
34
        if (a[i]-a[i-1]>1)
35
            l=i-1,type=1;
36
        while (type>k){
37
            l++;
38
            if (a[l]!=a[l+1])
39
                type--;
40
        }
41
        ans=max(ans,i-l);
42
    }
43
    cout<<ans<<endl;
44
}
45

46
int main(){
47
  std::ios::sync_with_stdio(false);
48
  std::cin.tie(nullptr);
49
  std::cout.tie(nullptr);
50
  int t=1;
51
  cin>>t;
52
  while (t--)
53
    solve();
54
//    cout<<(solve()?"YES":"NO")<<endl;
55
  return 0;
56
}

D - Attribute Checks #

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

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

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
#undef LOCAL_DEBUG
5
#ifdef LOCAL_DEBUG
6
#include "debug.h"
7
#else
8
#define debug(...) (void)0
9
#define debug_array(arr, len) (void)0
10
#define debug_container(container) (void)0
11
#endif
12

13
typedef unsigned long long ull;
14
typedef long long ll;
15
typedef pair<int,int> P;
16
const int maxn=2e6;
17
const int maxm=5000;
18

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

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

24
void solve(void){
25
    cin>>n>>m;
26
    int now=0;
27
    for (int i=1,x;i<=n;i++){
28
        cin>>x;
29
        if (x==0)
30
            now++;
31
        else
32
            req[now][x>0].push_back(abs(x));
33
    }
34
    for (int i=0;i<=m;i++){
35
        sort(req[i][0].begin(),req[i][0].end());
36
        sort(req[i][1].begin(),req[i][1].end());
37
    }
38
    int ans=0;
39
    for (int len=1;len<=m;len++){
40
        int x=len,y=len-x;
41
        while (x>=0){
42
            dp[x][y]=max(x>=1?dp[x-1][y]:0,y>=1?dp[x][y-1]:0);
43
            x--;
44
            y=len-x;
45
        }
46
        x=len,y=len-x;
47
        int i=0,j=req[len][0].size()-1;
48
        while (x>=0){
49
            while (j>=0&&req[len][0][j]>x)
50
                j--;
51
            while (i<req[len][1].size()&&req[len][1][i]<=y)
52
                i++;
53
            dp[x][y]+=(j+1)+(i);
54
            debug(x,y,dp[x][y]);
55
            if (len==m)
56
                ans=max(dp[x][y],ans);
57
            x--;
58
            y=len-x;
59
        }
60
    }
61
  cout<<ans<<endl;
62
}
63

64
int main(){
65
  std::ios::sync_with_stdio(false);
66
  std::cin.tie(nullptr);
67
  std::cout.tie(nullptr);
68
  int t=1;
69
//  cin>>t;
70
  while (t--)
71
    solve();
72
//    cout<<(solve()?"YES":"NO")<<endl;
73
  return 0;
74
}

E - Card Game #

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

设从花色 $2\sim n$ ，每种花色 $i$ 中，数量都有

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

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

-res[1]=cnt_1[i]-cnt_2[i]=\sum_{i=2}^n res[i]

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

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

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

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

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

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

是一个很精彩的dp套dp。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
//#undef LOCAL_DEBUG
5
#ifdef LOCAL_DEBUG
6
#include "debug.h"
7
#else
8
#define debug(...) (void)0
9
#define debug_array(arr, len) (void)0
10
#define debug_container(container) (void)0
11
#endif
12

13
typedef unsigned long long ull;
14
typedef long long ll;
15
typedef pair<int,int> P;
16
const int maxn=500;
17
const ll mod=998244353;
18

19
int n,m;
20

21
ll dp[maxn+5][maxn+5];
22
ll g[maxn+5][maxn+5];
23

24
void solve(void){
25
  cin>>n>>m;
26
    dp[0][0]=1;
27
    for (int i=1;i<=m;i++)
28
        for (int j=0;j<=i;j++){
29
            if (j)
30
                dp[i][j]+=dp[i-1][j-1],dp[i][j]%=mod;
31
            dp[i][j]+=dp[i-1][j+1],dp[i][j]%=mod;
32
        }
33
    g[1][0]=1;
34
    for (int i=2;i<=n;i++)
35
        for (int j=0;j<=m;j++)
36
            for (int k=0;k<=j;k++)
37
                g[i][j]+=g[i-1][k]*dp[m][j-k]%mod,g[i][j]%=mod;
38
    ll ans=0;
39
    for (int k=0;k<=m;k++)
40
        ans+=dp[m][k]*g[n][k]%mod,ans%=mod;
41
  cout<<ans<<endl;
42
}
43

44
int main(){
45
  std::ios::sync_with_stdio(false);
46
  std::cin.tie(nullptr);
47
  std::cout.tie(nullptr);
48
  int t=1;
49
//  cin>>t;
50
  while (t--)
51
    solve();
52
//    cout<<(solve()?"YES":"NO")<<endl;
53
  return 0;
54
}

A - Two Screens#

B - Binomial Coefficients, Kind Of#

C - New Game#

D - Attribute Checks#

E - Card Game#

A - Two Screens #

B - Binomial Coefficients, Kind Of #

C - New Game #

D - Attribute Checks #

E - Card Game #