Educational Codeforces Round 137 (Rated for Div. 2)（A~D）

浪漫主义狗

发布于 2023-09-04 14:54:15

2290

发布于 2023-09-04 14:54:15

文章被收录于专栏：HAUE_LYS'BlogHAUE_LYS'Blog

本文最后更新于 320 天前，其中的信息可能已经有所发展或是发生改变。

A. Password

Origional Link

题目大意：

给定 n 个 0\sim 9 之间不能使用的数字，保证剩余的数大于 2。
任意两个数子组合，每个数字可使用两次，组成一个四位密码。
求在剩余的可选数字中，能组成的密码数量。

思想：

签到题。
任意两个数字可组成的密码数量固定为 6。
则总数量为剩余数字中的两两组合的数量乘 6。
即设剩余的数的数量为 x = 10 - n，总密码数为 \frac{x\times (x - 1)}{2}.

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

void solve(){

    int n; cin >> n;
    for(int i = 0; i < n; i ++){
        int x; cin >> x;
    }
    n = 10 - n;
    cout << 6 * n * (n - 1) / 2 << endl;

}

int main(){

    IOS;

    int _ = 1;

    cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

B. Permutation Value

Origional Link

题目大意：

给定一个长度为 n 的排列。
定义其一个连续的子序列也为一种排列。
构造一个排列使得满足上述条件的子序列的数量最少。
输出任意满足条件的序列即可。

思想：

构造。
只需要将 1 提到最前面，然后倒序输出剩余数即可。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

void solve(){

    int n; cin >> n;
    cout << 1 << ' ';
    for(int i = n; i >= 2; i --) cout << i << ' ';
    cout << endl;

}

int main(){

    IOS;

    int _ = 1;

    cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

C. Save the Magazines

Origional Link

题目大意：

给定一个长为 n 且只包含 0,1 的字符串 s，1 表示 a_i 有盖，反之则无。
接下来给出 a_i 个箱子内部所的含杂志数量，雨会淋湿没有盖盖子的箱子里的所有杂志。
每个有盖子的箱子仅可操作一次，将盖子移动到 a_i-1 上。
求最佳方案下最大能保护的杂志数量。

思想：

贪心。
对于某个连续的 1 的区间 (i,j)，我们可以移动的盖子范围在 a_{i-1}\sim j，那么在区间 (i-1,j) 中必然存在一个箱子没有盖子。
故需要将区间 (i-1,j) 中所含杂志数量最少的箱子的盖子移除，提供给没有盖子的箱子。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

int a[N];

void solve(){

    int n; cin >> n;
    string s; cin >> s;
    for(int i = 0; i < n; i ++) cin >> a[i];

    LL sum = 0;

    int pos = s.find("1");

    // cout << pos << endl;
    if(pos == -1){
        cout << 0 << endl;
        return ;
    }

    for(int i = pos; i < n; i ++){
        if(s[i] == '1'){
            int cnt = 1;
            int t = a[i];
            sum += t;
            for(int j = i + 1; j < n; j ++){
                if(s[j] == '0') break;
                else cnt ++;
                t = min(t, a[j]);
                sum += a[j];
            }
            if(i - 1 >= 0){
                int p = a[i - 1];
                if(p > t) sum += p - t;
            }
            i += cnt - 1;
        }
    }

    cout << sum << endl;

}

int main(){

    IOS;

    int _ = 1;

    cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

D. Problem with Random Tests

Origional Link

题目大意

给定一个只包含 0,1 的序列。
可以通过一个字串与其按位“或”运算得到一个新的 0,1 序列。
求如何操作使得该序列的二进制数最大。

思想：

贪心，枚举。
该题的数据具有随机性。
贪心发现，两个字符一定是从某一点位置开始，其中一个字符右移几个位置，然后或运算。
那么我们需要从第一个出现的 0 的位置开始“或”运算，然后暴力匹配即可。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

int a[N];

void solve(){

    int n; cin >> n;
    string s; cin >> s;
    s = " " + s;

    int pos = 1;
    bool flag = false;

    for(int i = 1; i <= n ; i ++ ){
        if(s[i] == '1') flag = true;
        if(flag && s[i] == '0'){
            pos = i;
            break;
        }
    }

    int st = pos;
    int len = n - pos + 1;
    string ans = s;

    for(int i = 1; i < st ; i ++ ){
        for(int j = i + len - 1; j <= n ; j ++ ){
            string temp = s;
            for(int k = n - len + 1, u = i ; u <= j ; u ++ , k ++ ) 
                if(s[u] == '1') temp[k] = '1';
            ans = max(ans, temp);
        }
    }

    flag = false;
    for(int i = 1; i <= n ; i ++ ){
        if(ans[i] == '1') flag = true;
        if(flag) cout << ans[i];
    }
    if(!flag) cout << 0;
    cout << endl;
}

int main(){

    IOS;

    int _ = 1;

    // cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2022-10-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除

cin