Editorial for Codeforces Round #748 (Div.3)

Alex • 2023-04-22 12:19 • 杂文

1593A - Elections

解法：模拟
**时间复杂度 O(1), 空间复杂度 O(1)

#include
using namespace std;
#define endl '/n'
const int N = 4E5 + 5;

void solve() {
    int a, b, c;
    int mx = 0;
    cin >> a >> b >> c;
    mx = max(max(a, b), c);
    int f = (mx == a) + (mx == b) + (mx == c);
    
    if (f > 1) {
        mx += 1;
        cout << mx - a << " " << mx - b << " " << mx - c << endl;
    }else {
        
        if (mx == a) {
            cout << 0 << " ";
        }else cout << mx - a + 1 << " ";
        if (mx == b) {
            cout << 0 << " ";
        } else cout << mx - b + 1 << " ";
        if (mx == c) {
            cout << 0 << endl;
        }else cout << mx - c + 1 << endl;
        
    }
    
}

int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t --) {
        solve();
    }
    
    return 0;
}

1593B - Make it Divisible by 25

解法：能够被25整除的数，其末尾分为00，25，50，75四种情况。分别考虑这四种情况，从后向前寻找对应字符，减去寻找过程中的无用字符即为答案，取min即可。
时间复杂度 O(N)，空间复杂度 O(N)

#include
using namespace std;
#define endl '/n'
const int N = 4E5 + 5;

void solve() {
    
    string s;
    cin >> s;
    int ret = 20;
    int d = 0;
    int n = s.size();
    for (int i = s.size() - 1; i >= 0; -- i) {
        if (s[i] != '0' && s[i] != '5') continue;
        for (int j = i - 1; j >= 0; -- j) {
            if (s[i] == '0') {
                if (s[j] == '0' || s[j] == '5') {
                    ret = min(ret, i - j - 1 + n - i - 1);
                    break;
                }
            } 
            else {
                if (s[j] == '2' || s[j] == '7') {
                    ret = min(ret, i - j - 1 + n - i - 1);
                    break;
                }
            }
        }
    }
    cout << ret << endl;
    
}

int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t --) {
        solve();
    }
    
    return 0;
}

1593C - Save More Mice

解法：模拟 & 贪心，让离洞最近的老鼠先入洞
时间复杂度 O(N * log N)，空间复杂度 O(N)

#include
using namespace std;
#define endl '/n'
const int N = 4E5 + 5;

void solve() {
    int n, k;
    cin >> n >> k;
    vector a;
    for (int i = 0; i < k; ++ i) {
        int t;
        cin >> t;
        a.push_back(t);
    }
    sort(a.begin(), a.end(), [](int& x, int& y) {
        return x > y;
    });
    
    int ret = 0;
    int c = 0;
    for (int i = 0; i < a.size(); ++ i) {
        if (c >= a[i]) break;
        if (a[i] == n) 
            ++ ret;
        else {
            c += n - a[i];
            ++ ret; 
        } 
    }
    cout << ret << endl;
    
}

int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t --) {
        solve();
    }
    
    return 0;
}

1593D1 - All are Same

解法：
1.若存在一个数 K 能使所有数通过相减而相等，则 k 必定是这个数列相邻两项不同的数的差值的因子，这里可以使用这个数列的最大值和最小值的差值即 K | (max - min)。
2.存在数列 A1 A2 A3 ... An ,其差值为 A12 A23 ... A(n - 1)(n), 则 K 可表示为 K = gcd{A12, A23, ..., A(n - 1)(n)};
两种方法本质相同

第一种：时间复杂度 O(N * $/sqrt{N}$ )，空间复杂度 O(N)

第二种：时间复杂度 O(N * log N), 空间复杂度 O(N)

// 第一种
#include
using namespace std;
#define endl '/n'
void solve() {
    int n;
    cin >> n;
    vector a;
    for (int i = 0; i < n; ++ i) {
        int t;
        cin >> t;
        a.push_back(t);
    }
    sort(a.begin(), a.end());
    vector divs; // 记录 d 的所有因子 
    int d = a[n - 1] - a[0];
    for (int i = 1; i * i <= d; ++ i) {
        if (d % i == 0) {
            divs.push_back(i);
            if (i * i != d) {
                divs.push_back(d / i);
            }
        }
    }
    int ret = -1;
    for (int& x : divs) {
        unordered_map cnt;
        for (int i = 0; i < n; ++ i) {
            cnt[(a[i] % x + x) % x] ++; // 此操作为取 a[i] 的正模数 
        }
        for (auto& p : cnt) {
            if (p.second == n) ret = max(ret, x); 
        }       
    }
    cout << ret << endl;
    
}

int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t -- ) {
        solve();
    }
    return 0;
}

// 第二种

#include
using namespace std;
#define endl '/n'
void solve() {
    int n;
    cin >> n;
    vector a;
    for (int i = 0; i < n; ++ i) {
        int t;
        cin >> t;
        a.push_back(t);
    }
    sort(a.begin(), a.end());
    int d = 0;
    for (int i = 1; i < n; ++ i) {
        int x = a[i] - a[i - 1];
        d = __gcd(d, x);
    }
    if (d) cout << d << endl;
    else cout << -1 << endl;
}

int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t -- ) {
        solve();
    }
    
    return 0;
}

1593D2 - Half of Same

**解法：参照D1 题第一种方法，枚举一个可行方案最大值和最小值 **
**时间复杂度 O(N * N * $/sqrt{N}$ )，空间复杂度 O(N) **

#include
using namespace std;
#define endl '/n'
int solve(int i, int j, vector& a) {
    int d = a[j] - a[i];
    int n = a.size();
    vector divs;
    for (int i = 1; i * i <= d; ++ i) {
        if (d % i == 0) {
            divs.push_back(i);
            if (i * i != d) {
                divs.push_back(d / i);
            }
        }
    }
    int ret = -1;
    for (int& x : divs) {
        unordered_map cnt;
        for (int i = 0; i < n; ++ i) {
            cnt[(a[i] % x + x) % x] ++;
        }
        for (auto& p : cnt) {
            if (2 * p.second >= n) ret = max(ret, x);
        } 
    }
    return ret;
    
    
}

void solve() {
    int n;
    cin >> n;
    vector a;
    unordered_map cnt;
    for (int i = 0; i < n; ++ i) {
        int t;
        cin >> t;
        a.push_back(t);
        cnt[t] ++;
    }
    sort(a.begin(), a.end());
    for (int& x : a) {
        if (cnt[x] >= n / 2) {
            cout << -1 << endl;
            return;
        }
    }
    int ans = -1;
        // 枚举可行方案的 最大值 和 最小值
        // i 为最小值下标， j 为最大值下标
    for (int i = 0; i <= n / 2; ++ i) {

        for (int j = i + 1; j < n; ++ j) {
            ans = max(ans, solve(i, j, a));
        }
        
    }
    cout << ans << endl;
} 

int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t --) {
        solve();
    }
    
    return 0;
}

1593E - Gardener and Tree

解法：建图后，TOP 序处理
时间复杂度 O(N)

#include
using namespace std;
#define endl '/n'
const int N = 1e6 + 5;

int h[N], e[N], ne[N], d[N], idx; 

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;

}
int q[N];
void solve() {
    
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++ i) {
        h[i] = -1;
    }
    for (int i = 1; i <= n; ++ i) {
        d[i] = 0;
    }
    idx = 0;
    for (int i = 0; i < n - 1; ++ i) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
        d[a] ++;
        d[b] ++;
    }
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; ++ i) {
        if (d[i] == 1) {
            q[++ tt] = i;
            -- d[i];
        }
    } 
    int cnt = 0;
    while (hh <= tt) {
        int sz = tt - hh + 1;
        for (int i = 0; i < sz; ++ i) {
            int t = q[hh ++];
            for (int i = h[t]; ~i; i = ne[i]) {
                int j = e[i];
                if (d[j] == 0) continue;
                if (-- d[j] == 1) {
                    q[++ tt] = j;
                }
            }
        }
        if (++ cnt == k) break;
    }
    
    int ret = tt - hh + 1;
    for (int i = 1; i <= n; ++ i) {
        if (d[i] > 1) {
            ++ ret;
            // cout << i << endl;   
        }
    }
    cout << ret << endl;    
}

int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t --) {
        solve();
    }
    
    return 0;
}

1593F - Red-Black Number

解法：动态规划或记忆化搜索

记忆化搜索：可知对于一个数列的每一位要么是红，要么是黑，如果直接暴力搜索，一共 2 ^ 40 种情况
设 dfs(track, u, a, b, k) 为前 u - 1 个中，红色数 % A = a, 黑色数 % B = b, 已经选了 k 个红色位数
此时考虑第 u 位情况，若最终 a = b = 0，且 1 < k < n则合法，记录 abs(n - k - k) 最小的答案序列即可。

动态规划：设 dp[n][a][b][k],为前 n - 1 位，红色数 % A = a, 黑色数 % B = b, 已经选了 k 个红位数的情况
有 dp[n + 1][(a * 10 + s[n] - '0') % A][b][k + 1] = dp[n][a][b][k] | ((long long)1 << n);
dp[n + 1][a][(b * 10 + s[n] - '0') % B][k] = dp[n][a][b][k];

时间复杂度 O(N * A * B * N), 空间复杂度 O(N ^ 4)

// 记忆化搜索

#include
using namespace std;
#define endl '/n'
const int N = 100;
string s, ret;
int A, B;
int tmp;
bool vis[N][N][N][N];
bool dfs(string& track, int u, int a, int b, int k) {
    if (track.size() == s.size()) {
        if (a != 0 || b != 0 || k == 0 || k >= (int)s.size()) return false;
        if (abs((int)s.size() - k - k) < tmp) {
            ret = track;
            tmp = abs((int)s.size() - k - k);
        }
        return true;
    }
    if (vis[u][a][b][k]) return false;
    vis[u][a][b][k] = 1;
    track += "R";
    bool flag = dfs(track, u + 1, (a * 10 + (s[u] - '0')) % A, b, k + 1);
    track.pop_back();
    track += "B";
    flag |= dfs(track, u + 1, a, (b * 10 + (s[u] - '0')) % B, k);
    track.pop_back(); 
    return flag;
    
}
void solve() {
    memset(vis, 0, sizeof vis);
    tmp = 1e9;
    int n;
    cin >> n >> A >> B;

    cin >> s;
    string u;
    
    bool flag = dfs(u, 0, 0, 0, 0);
    if (flag) cout << ret << endl;
    else cout << -1 << endl;
}
int main() {
    ios_base::sync_with_stdio(0); 
        cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t --) {
        solve();
    }
}


// 动态规划
#include
using namespace std;
#define endl '/n'
#define ll long long
const int N = 50;
long long dp[N][N][N][N];
void solve() {
    // dp[n][a][b][k]
    string s;
    int n, A, B;
    cin >> n >> A >> B >> s;
    memset(dp, -1, sizeof dp);
    dp[0][0][0][0] = 0;
    for (int i = 0; i < n; ++ i) {
        for (int k = 0; k < n; ++ k) {
            for (int a = 0; a < A; ++ a) {
                for (int b = 0; b < B; ++ b){
                    if (dp[i][a][b][k] != -1) {
                        dp[i + 1][(a * 10 + (s[i] - '0')) % A][b][k + 1] = dp[i][a][b][k] | (1ll << i);
                        dp[i + 1][a][(b * 10 + (s[i] - '0')) % B][k] = dp[i][a][b][k]; 
                    }
    
                
                }
            }
        }
    }
    int mi = 1e9;
    long long msk;
    for (int k = 1; k < n; ++ k) {
        if (dp[n][0][0][k] != -1 && abs(n - k - k) < abs(n - mi - mi)) {
            mi = k;
            msk = dp[n][0][0][k];
        }
    }
    if (mi == 1e9) cout << -1 << endl;
    else {
        string ret(n, 'B');
        for (int i = 0; i < n; ++ i) {
            if (msk >> i & 1) ret[i] = 'R';
        }
        cout << ret << endl;
    }
    
}
int main() {
        ios_base::sync_with_stdio(0); 
        cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t --) {
        solve();
    }
}

1593G - Changing Brackets

解法：
已知：
1.同一类型的括号正反互转开销为 0
2.对于一个下标从 1 开始的字符串，若其为有效字符串必然其奇数位的圆括号数量 = 偶数为圆括号数量且奇数位方括号数量 = 偶数位方括号数量

则要使其成为有效括号，必然使其奇数位圆括号的数量 = 偶数位圆括号数量。（此等式换为方括号也行）
这里用前缀和
时间复杂度 O(N), 空间复杂度 O(N)

#include
using namespace std;
#define endl '/n'
const int N = 1E6 + 5;
int pre[N][2];
// pre[i][0] 为第前 i 位，偶数位上的圆括号数量，pre[i][1] 为前 i 位，奇数位圆括号数量
void solve() {
    string s;a
    cin >> s;
    int n = s.size();
    int q;
    cin >> q;
    for (int i = 1; i <= n; ++ i) {
        pre[i][0] = pre[i - 1][0];
        pre[i][1] = pre[i - 1][1];
        if (s[i - 1] == '(' || s[i - 1] == ')') {
            pre[i][i % 2] ++;
        }
    }
    while (q --) {
        int a, b;
        cin >> a >> b;
                // 答案为使 奇数位圆括号数量 = 偶数位圆括号数量，即差值
        cout << abs((pre[b][0] - pre[a - 1][0]) - (pre[b][1] - pre[a - 1][1])) << endl;
    }
    
}

int main() {
    ios_base::sync_with_stdio(0); 
        cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t --) {
        solve();
    }
    return 0;
}

版权声明：
作者：Alex
链接：https://www.techfm.club/p/42421.html
来源：TechFM
文章版权归作者所有，未经允许请勿转载。

THE END

二维码

一图抵千言《ARouter简明扼要原理分析》

< <上一篇

Java–自定义异常

下一篇>>

搜索内容

Editorial for Codeforces Round #748 (Div.3)

1593A - Elections

1593B - Make it Divisible by 25

1593C - Save More Mice

1593D1 - All are Same

1593D2 - Half of Same

1593E - Gardener and Tree

1593F - Red-Black Number

1593G - Changing Brackets

取消回复

共有 0 条评论

Ads