2023牛客暑期多校训练营4

2023-09-08 14:51 由 scoxty 发表于 #其他

A.Bobo String Construction

题意:

给定一个01串t，构造一个长度为n的01串s，时的t + s + t中t只在首和尾出现。

分析：

结论，s取全0或者全1。
①t全0或者全1，那我s和t取相反的即可。
②t既包含0又包含1，首先t不可能是s的子串，那我们只需考虑t是否可以由t的后缀加上s再加上t的前缀得到。假设对于当前的串s全0且存在t的后缀加上s加上t的前缀等于t，那么我们将s变为全1则一定不等于t，当前串s全为1同理。
综上，我们只需要分别判断s全为0和全为1即可。

代码：

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

int check(string &s, string &s2) {
    int cnt = 0;
    for (int i = 0; i < s.size(); i ++) {
        if (s.substr(i, s2.size()) == s2)
            cnt ++;
    }
    return cnt;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int t;
    cin >> t;
    
    while (t --) {
        int n;
        string s, s0, s1;
        cin >> n >> s;
        
        for (int i = 0; i < n; i ++) {
            s0 += '0';
            s1 += '1';
        }
        
        string s3 = s + s0 + s;
        
        if (check(s3, s) == 2)
            cout << s0 << endl;
        else
            cout << s1 << endl;
            
    }
    
    return 0;
}

F.Election of the King

题意：

有n个人竞选国王，\(a_i\)表示第i个人的从政理念，每轮通过投票淘汰一位竞选者，每个人将投给与自己从政理念相差最大的人。
票数最多的将被淘汰，如果票数相同淘汰值最大的，如果值相同则淘汰编号最大的。

分析：

由于每个人投的是与自己执政理念相差最大的人，因此每个人要么投给值最大的要么投给值最小的，最终的决定权将落在值中间的那个人。可以将所有人优先按值从小到大排序，若值相同则按编号从小到大排序，最后不断让中间那个来决定淘汰谁即可。

代码：

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

const int N = 1e6 + 5;
struct P {
    int a, id;
}p[N];

bool cmp(P &A, P &B) {
    if (A.a != B.a) 
        return A.a < B.a;
    else 
        return A.id < B.id;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i ++) {
        cin >> p[i].a;
        p[i].id = i;
    }
    
    sort(p + 1, p + 1 + n, cmp);
    
    int l = 1, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        
        if (abs(p[mid].a - p[l].a) > abs(p[mid].a - p[r].a))
            l ++;
        else if (abs(p[mid].a - p[l].a) < abs(p[mid].a - p[r].a))
            r --;
        else {
            r --;
        }
    }
    
    cout << p[l].id;
    
    return 0;
}

J.Qu'est-ce Que C'est?

题意:

给定n和m，求能构造出满足下面条件的序列的数量。
①每个数在[-m, m]的范围内
②任意长度大于等于2的区间和>=0

分析:

考虑dp。
状态定义：f[i][j]表示前i个数中后缀最小值为j的方案数。
状态转移：
①j >= 0，能够转移过来的前一个状态后缀最小值的下限为j - m，因此f[i][j] = \(\sum_{k = j - m}^m f[i - 1][k]\)
②j < 0，由于要满足长度大于2的区间和>=0，所以最小后缀只有可能是第i个数自己，能够转移过来的前一个状态后缀最小值的下限即为-j，因此f[i][j] = \(\sum_{k = -j}^m f[i - 1][k]\)
答案即为：\(\sum_{j = -m}^m f[n][j]\)

代码：

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

const int N = 5010, M = 10010, mod = 998244353;
int f[N][M], s[N][M]; // s优化求和部分

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 2 * m; i >= 0; i --) {
        f[1][i] = 1;
        s[1][i] = s[1][i + 1] + 1;
    }
    
    for (int i = 2; i <= n; i ++) {
        for (int j = -m; j <= m; j ++) {
            if (j < 0) {
                f[i][j + m] = s[i - 1][-j + m];
            } else {
                f[i][j + m] = s[i - 1][j - m + m];
            }
        }
        
        // 优化求和
        for (int j = m; j >= -m; j --) {
            s[i][j + m] = (s[i][j + m] + s[i][j + m + 1] + f[i][j + m]) % mod;
        }
    }
    
    cout << s[n][0];
    
    return 0;
}

L.We are the Lights

题意：

n × m的灯阵，初始全灭。每次操作可将某一行或者某一列的灯全开/全关。问q次操作过后有多少台灯亮着。

分析：

可以发现只有最后一步才决定灯的状态，因此我们可以倒着去维护亮着灯的数量。

代码：

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

const int N = 1e6 + 5;
typedef long long LL;
bool row[N], col[N];
struct Q {
    string s, op;
    int idx;
}q[N], q2[N];
LL cnt, cntr, cntc;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int n, m, t;
    cin >> n >> m >> t;
    
    for (int i = 0; i < t; i ++) {
        string s, op;
        int idx;
        cin >> s >> idx >> op;
        
        q[i] = {s, op, idx};
    }
    
    for (int i = t - 1; i >= 0; i --) {
        string s = q[i].s, op = q[i].op;
        int idx = q[i].idx;
        
        if (s == "row" && !row[idx]) {
            row[idx] = true;
            q2[cnt ++] = {s, op, idx};
        } else if (s == "column" && !col[idx]) {
            col[idx] = true;
            q2[cnt ++] = {s, op, idx};
        }
    }
    
    LL res = 0;
    
    for (int i = cnt - 1; i >= 0; i --) {
        string s = q2[i].s, op = q2[i].op;
        int idx = q2[i].idx;
        
        if (s == "row") {
            if (op == "on") {
                res += (m - cntc);
                cntr ++;
            } else {
                if (res > 0)
                    res -= cntc;
            }
        } else if (s == "column") {
            if (op == "on") {
                res += (n - cntr);
                cntc ++;
            } else {
                if (res > 0)
                    res -= cntr;
            }
        }
    }
    
    cout << res;
    
    return 0;
}