比赛链接https://codeforces.com/contest/1995

A. Diagonals

题意

给定一个$n*n$ 的矩阵， 定义对角线为$i+j$ 相同的值，其中$i$为行号，$j$为列号 。

给你k个棋子要放在这么一个$n*n$ 的矩阵中， 问最少需要占据多少个对角线。

思路

对角线的长度为 $n,n-1,n-1,n-2,n-2,…,1,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
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n,k;
    cin>>n>>k;
    if(k == 0) {
        cout<<0<<endl;
        return ;
    }
    int cnt =1;
    k -= n;
    int t = n-1;
    int f = 0;
    while(k>0){
        k -= t;
        cnt++;
        if(f) t--;
        f ^= 1;
    }
    cout<<cnt<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

B. Bouquet

由于简单版本和困难版本差距不大，这边直接上hard vision

题意

有一个花店， 花店里有一些花，我们按照花所含有的花瓣数量来对花分类。你总共有x金币。

你可以花费k个金币购买一个拥有k个花瓣的花，并且你购买的花中，任意两朵花的花瓣数量相差不大于$1$ 。 问你最多能获得多少花瓣。

思路

我们使用map来记录每个花瓣的花有多少朵 ， 显而易见， 若购买k花瓣的花，那么便只能再购买k+1花瓣的花 。所以我们枚举k为花店中每一种花的花瓣数量， 在每次枚举中，我们只考虑购买 k 和k+1的情况，最终在枚举的每种情况下取MAX即可。我们按照如下贪心策略来购买花，就可以保证买到的花瓣数量尽可能多。

  1. 尽可能多地购买k花瓣的花（直到没钱买或者把所有的花都买完了）
  2. 尽可能多地购买k+1花瓣的花（直到没钱买或者把所有的花都买完了）
  3. 尽可能多地将一些k花瓣的花换成k+1花瓣的花（每换一个花需要额外1金币， 并且要求有足够的k+1花瓣的花）

按照如上思路就可以得到“只够买k和k+1花瓣的花的情况下， 最多购买多少花瓣” ，将所有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
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n,m;
    cin>>n>>m;
    map<int,int> mp;
    vector<int> a(n+1),b(n+1);
    rep(i,1,n){
        cin>>a[i];
    }
    rep(i,1,n){
        cin>>b[i];
    }
    rep(i,1,n) mp[a[i]] = b[i];
    int ans = 0;
    for(auto [x,y] : mp){
        if(y==0) continue;
        int sum = 0;
        int mm = m;
        int t1 = min(y,mm/x);
        mm -= t1 * x;
        int y2 = mp[x+1];
        int t2 = min(y2,mm/(x+1));
        mm -= t2 * (x+1);
        y2 -= t2;
        int t3 = min(mm,min(y2,t1));
        sum = t1 * x + t2 * (x+1) + t3;
        ans = max(ans,sum);
    }
    cout<<ans<<'\n';
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

C. Squaring

题意

给一个长度为$n$的数组$a_1,a_2,..,a_n$ ， 每次操作你可以选择一个数$i$, 令$a_i = a_i ^2$ ，请问最少需要多少次操作，能让数组a变为单调不减数列。若无论如何都无法实现，那么输出-1

思路

可以很容易想到，我们从左到右遍历数组，不断检查每一个数是否大于等于上一个数，若出现$ai < a{i-1}$ 就对$ai$进行操作，直到满足$a{i} \ge a_{i-1}$ 。

特判：只有当存在$ai = 1 ,a{i-1} > 1$ 时， 无论如何都无法令$ a_{i-1}\le a_i$ ，此时要输出-1 。

本题的难点在于在对一个数进行操作时，我们很容易就会发生超出longlong范围的情况，因此我们不能直接比较两个数的大小，而应该将他们作为$a^p ,b^q$ 的形式，直接比较二者的大小。

错解：

起初我很容易想到了一个”解法“， 即若判断 $a^p, b^q$ 的大小关系， 可以比较 $a^{\frac{1}{q}} $ 和$b^{\frac{1}{p}}$ 的大小关系， 于是便成功WA5了。。。

正解：

本题我们要用到每次操作都是平方的特性，即$a^p ,b^q$中的$p,q$ 都是2的次幂， 假设 $ a{i-1}^p > a{i}$ , 我们可以先令二者的幂相同，即设$c$ ,满足$c^p = a{i}$ , 于是为了令$a^p{i-1} \le ai^q =(c^p)^q = (c^q)^p$ ， 于是我们只需要找到一个$q$ ,使得恰有$c^q \ge a{i-1}$ 即可, 也即$ai ^ {\frac{q}{p}} \ge a{i-1}$ ， 又因为我们每次进行操作为乘方操作， 所以有$p,q$ 都是2的次幂 ， 设$p = 2^x,q = 2^y$ , 那么$a_i^{\frac{q}{p}} = a_i^{2^{y-x}}$ ， 此处的$y-x$ 即为我们要对$a_i$ 进行的操作次数。

那么会出现下面两种情况：

  1. $ai \le a{i-1}$ ，那么我们不断对$ai$ 进行乘二操作， 直到进行完$cnt$ 次操作后，$a_i \ge a{i-1}$ ，此时对$a_i$ 进行的总次数即为$q = p + cnt$
  2. $ai > a{i-1}$ ，那么我们不断对$ai$ 进行除以二操作， 直到进行完$cnt$ 次操作后，恰好$a_i \ge a{i-1}$ , 此时$a_i$ 进行的总次数即为$q = p - cnt$

代码

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
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
#define endl '\n'
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
struct node {
    int x;
    int ope = 0;
};
void solve(){
    int n;
    cin>>n;
    vector<int> a(n+5);
    int ans = 0;
    vector<node> b(n+5);
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }
    for(int i = 2;i<=n;i++){
        if(a[i] < a[i-1] && a[i] == 1){
            cout<<-1<<'\n';
            return ;
        }
    }
    for(int i = 1;i<=n;i++){
        b[i] = {a[i],0};
    }
    for(int i = 2;i<=n;i++){
        int x1 = a[i-1];
        int q1 = b[i-1].ope;
        int x2 = a[i];
        int q2 = b[i].ope;
        if(x1 > x2){
            int xx = x2;
            int t = 0;
            while(xx < x1){
                xx *= xx;
                t++;
            }
            b[i].ope = b[i-1].ope + t;
        }else if(x1 == x2){
            b[i].ope = b[i-1].ope;
        }else{
            if(b[i-1].x == 1) {
                b[i].ope = 0;
                continue;
            }
            int t = 0;
            int xx = x1;
            while(xx < x2){
                xx *= xx;
                t++;
            }
            if(xx>x2) t--;
            b[i].ope = max(0LL,b[i-1].ope-t);
        }
        ans += b[i].ope;
    }
    cout<<ans<<'\n';
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

D. Cases

题意

给你一个长度为$n$的只含有前$c$种字母的字符串$S$，你可以将这个字符串切割为一些子串，并使得每一子串的长度都不大于$k$ , 定义切割后的字符串的价值为选取每一个子串的最后一个字符，将其放入集合set中，最终set的大小 ， 即所有子串最后一个字符的种类数量。

问给定$n,c,k,S$ ，最小价值为多少。

思路

题意可以理解为， 我们尽可能少地选择一些字母， 要求相邻的被选择的字母之间距离不大于k。

也即： 任选一个长度为k的子串，其中必须包含至少一个我们所选择的字母。

我们判断一个长度为k的子串中有没有某一个字符，可以使用前缀和来判断，我们用$sum[i][j]$ 表示前i个字符中，有多少个字符j

if(sum[i+k][j] - sum[i][j]==0)

我们提取所有的长度为k的子串，将他们没出现过的字母状态进行二进制表示后存储起来，表示“只选择这些字母，会出现错误”。设对应的二进制码为msk，那么就令bad[msk] = 1 .

较容易得知，如果我们在选择一个组合之后，会发生错误，那么我们再从中去掉一些后，同样会出现错误。（如若选择AC 两种字母会出现相邻的被选择的字母之间距离大于k ,那么如果我们只选择A 或者C ，就一定也会导致相邻的被选择的字母之间距离大于k

例如样例：

1
2
6 3 2
ABCABC

我们提取出长度为2的子串后，得到AB, BC, CA, AB,BC , 取反后得到C ,A ,B ,C,A , 即如果选择其中一种组合或其子集(A或B或C或空) ，会出现错误。

在处理完bad数组后， 我们选出含有1最少的i，并且bad[i] == 0 ， 于是$i$中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
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int sum[300005][20];
void solve(){
    int n,c,k;
    cin>>n>>c>>k;
    string str; 
    cin>>str;str = " " + str;
    for(int j = 0;j<c;j++) sum[0][j] = 0;
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<c;j++){
            sum[i][j] = sum[i-1][j] + (str[i] == j + 'A');
        }
    }

    vector<bool> bad((1<<c));
    for(int i= 0;i<=n-k;i++){
        int msk = 0;    
        for(int j = 0;j<c;j++){
            if(sum[i+k][j] ==  sum[i][j] ){
                msk |= (1<<j);
            }
        }
        bad[msk] = 1;
    }
    bad[(1 << (str.back() - 'A'))^((1<<c)-1)] = 1;
    for(int i =(1<<c)-1;i>=0;i--){
        for(int j=0;j<c;j++){
            bad[i] = bad[i] | bad[i | (1<<j)];
        }  
    }
    int res = INF;
    for(int i = 0;i<(1<<c);i++){
        if(!bad[i]){
            int cnt = __builtin_popcount(i);
            res = min(res,cnt);
        }
    }
    cout<<res<<endl;

}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}