CVBB ACM Team

A

题意：有n个字符串，给定相邻两个字符串的公共前缀长度，输出这n个字符串的一种可能情况 题解：第一个字符串全部是a，下一个字符串生成时在公共前缀长度之外的字符进行修改即可。

点击以显示 ⇲

点击以隐藏 ⇱

#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
    int t = 0;
    cin>>t;
    int a[200];
    while(t--){
        int n;
        cin>>n;
        for (int i = 0; i < n; ++i) {
            cin>>a[i];
        }
        char s[200][60] = {};
        for (int i = 0; i < 50; ++i) {
            s[0][i] = 'a';
        }
        cout<<s[0]<<endl;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < a[i - 1]; ++j) {
                s[i][j] = s[i-1][j];
            }
            for (int j = a[i-1]; j < 50; ++j) {
                s[i][j] = (s[i-1][j] - 'a' + 1) % 26 + 'a';
            }
            cout<<s[i]<<endl;
        }
    }

B1 & B2

题意需要从海滩游到海岛上，给定初始时波浪高度等于0时的水深分布，波浪高度在0-k-0-k之间连续变动，已知最深能够游的水深D，求是否可以游到小岛

题解设波浪高度为k-0-k，维护到达位置i时，可能的波浪时间范围[l, r]。位置i+1时，波浪的范围为[l+1, r+1]和 [k - (D - d[i]), k + (D - d[i])]的交，如果长度为0则不可游到。特别的，如果D大于d[i]+k则时间范围为[0,2k-1]，即整个长度

特别要注意D - d[i]小于0的情况。这里pretest没有测结果B2 System test的时候WA了

点击以显示 ⇲

点击以隐藏 ⇱

#include <bits/stdc++.h>
 
using namespace std;
 
 
int d[300005];
int main(){
    int t = 0;
    cin>>t;
    while(t--){
        int n, k, l;
        cin>>n>>k>>l;
 
        for (int i = 1; i <= n; ++i) {
            cin>>d[i];
        }
 
        int t1 = 0, t2 = 2*k-1;
        bool ok = true;
        for (int i = 1; i <= n; ++i) {
            if(l - d[i] >= k){
                t1 = 0, t2 = 2*k-1;
            }
 
            else{
 
                if(l < d[i]){
                    ok = false;break;
                }
                int tt1 = k - (l - d[i]);
                int tt2 = k + (l - d[i]);
 
                t1++, t2++;
 
                if(tt2 < t1 || tt1 > t2)  {
                    ok = false;
                    break;
                }
                t1 = max(tt1, t1);
                t2 = min(tt2, t2);
            }
        }
 
        cout<<(ok ? "Yes" : "No")<<endl;
    }
}

C

题意给定AB两个a-t组成的字符串，每次可以将A字符串的一种字符改成另一种比其大的字符。求将A字符串改为B字符串的最小步数。如果不存在解输出-1

题解可以等效为建立一个字符构成的有向图。从t至a遍历字符，如果a-c需要连边而存在b-c的边，则选择连a-b的边。

点击以显示 ⇲

点击以隐藏 ⇱

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t = 0;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string a, b;
        cin >> a >> b;
        bool ok = true;
        for (int i = 0; i < n; ++i) {
            if (a[i] > b[i]) {
                ok = false;
                break;
            }
        }
        if (!ok) {
            cout << -1 << endl;
            continue;
        }
        set<int> to[22] = {};
        int toa[22][22] = {};
 
        bool have[22] = {};
        for (int i = 0; i < n; ++i) {
            if (a[i] != b[i]) {
                to[a[i] - 'a'].insert(b[i] - 'a');
                toa[a[i] - 'a'][b[i] - 'a'] = 1;
            }
        }
        int cnt = 0;
        bool passed[22];
        for (int i = 19; i >= 0; --i) {
            if (to[i].empty())continue;
            bool hh = false;
            for (int j = 19; j > i; j--) {
                bool ha = false;
                for (int k : to[j]) {
                    if (toa[i][k]) {
                        ha = true;
                        break;
                    }
                }
                if (toa[i][j]) {
                    ha = true;
                }
 
                if (ha) {
                    to[i].insert(j);
                    for (int k : to[j]) {
                        to[i].insert(k);
                        toa[i][k] = 0;
                    }
                    toa[i][j] = 1;
                    to[i].insert(j);
                    hh = true;
                }
            }
            for (int j = 0; j < 20; ++j) {
                cnt += toa[i][j];
            }
 
        }
 
        cout << (cnt) << endl;
    }
 
}

CVBB ACM Team

用户工具

站点工具

目录

A

B1 & B2

C

页面工具