526互联

AT_abc 复盘合集

发布时间 2023-12-12 21:31:48作者: CCF_IOI

AT_abc301 复盘

A

一眼水，只需要遍历一遍数组，记录哪一个胜利场数先打到 \((n + 1) / 2\) 就好了。

AC code：

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

int n, c1, c2;
string s;

int main(){
    cin >> n >> s;
    for (int i = 0; i < n; i++){
        if (s[i] == 'T') c1++;
        else c2++;
        if (c1 >= (n + 1) / 2) return cout << "T", 0;
        if (c2 >= (n + 1) / 2) return cout << "A", 0;   
    }
    return 0;
}

B

依旧很水，只需要看当前与下一个数之间的趋势，然后输出就好。

注意边界，如果输出一个区间包含前面但不含后面的话，最后一个数要单独输出。

AC code：

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

int n;
int a[105];

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++){
        if (a[i] < a[i + 1]){
            for (int j = a[i]; j < a[i + 1]; j++) cout << j << " ";
        }
        else {
            for (int j = a[i]; j > a[i + 1]; j--) cout << j << " ";
        }
    }
    cout << a[n] << endl;
    return 0;
}

C

依旧是字符串，先记录下每一个字母的出现情况和两个字符串中 @ 的数量。之后遍历一遍字母，如果缺失（两个字符串字母出现次数不同）的字母是 atcoder 中的一个，那么记录需要的 @ 的数量。

最后判断所需 @ 符是否超过字符串已有的，或者两个字符串剩的 @ 符不同。

AC code：

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

string s, t;
int cnts, cntt;
int ms[30], mt[30];

int main(){
    cin >> s >> t;
    for (int i = 0; i < s.size(); i++){
        if (s[i] == '@') cnts++;
        if (t[i] == '@') cntt++;
        if (s[i] != '@') ms[s[i] - 'a']++;
        if (t[i] != '@') mt[t[i] - 'a']++;
    }
    for (char i = 'a'; i <= 'z'; i++){
        if (ms[i - 'a'] != mt[i - 'a']){
            if (i == 'a' || i == 't' || i == 'c' || i == 'o' || i == 'd' || i == 'e' || i == 'r'){
                if (ms[i - 'a'] < mt[i - 'a']) cnts -= (mt[i - 'a'] - ms[i - 'a']);
                else cntt -= (ms[i - 'a'] - mt[i - 'a']);
            }
            else return cout << "No", 0;
        }
    }
    if (cnts < 0 || cntt < 0 || cnts - cntt != 0) return cout << "No", 0;
    cout << "Yes";
    return 0;
}

D

算是比较水的 D，只要先记录初始的数，特判一下是否大于 \(n\)。然后从高位到低位去看每一个 ? 是否能变成 \(1\)，如果能，就加上这个数二进制还原回来的数，否则跳过。

注意：不开 long long 见祖宗。

AC code：

// LUOGU_RID: 139228615
#include <bits/stdc++.h>
#define int long long
using namespace std;

string s;
int n, sum, cnt = 1;
int a[65];

signed main(){
    cin >> s >> n;
    for (int i = s.size() - 1; i >= 0; i--) a[i] = cnt, cnt *= 2;
    for (int i = 0; i < s.size(); i++) sum += (s[i] == '1') ? a[i] : 0;
    if (sum > n) return cout << -1, 0;
    for (int i = 0; i < s.size(); i++){
        if (s[i] == '?' && sum + a[i] <= n) sum += a[i];
    }
    cout << sum << endl;
    return 0;
}

E

跟我们出的题很像，直接状压dp + 最短路就行，只不过这里不需要最短路，直接 BFS。

考虑状压dp，设置状态为：走到第 \(i\) 个猴子的位置且状态为 \(j\)，如果 \(j\) 的第 \(k\) 位为 \(1\) 则走到了第 \(k\) 个点，值为当前状态所花时间的最小值。basecase：设起点为 0 号猴子，终点为 \(cnt+1\) 号猴子，则 basecase 为 \(dp_{0,1<<cnt}=0\)。answer：当 \(dp_{cnt + 1,j} \le t\) 时，\(j\) 中包含 \(1\) 的个数的最大值。

坑点不多，注意在装完终点后，真正猴子的数量为 \(cnt-1\)。

AC code:

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

int h, w, t, sx, sy, ex, ey;
vector<pair<int, int>> v;
string s[305];

signed main(){
    cin >> h >> w >> t;
    for (int i = 0; i < h; i++){
        cin >> s[i];
        for (int j = 0; j < w; j++){
            if (s[i][j] == 'S') sx = i, sy = j;
            else if (s[i][j] == 'G') ex = i, ey = j;
            else if (s[i][j] == 'o') v.push_back({i, j}); 
        }
    }
    
    return 0;
}

AT_abc312 复盘

A

一眼过去直接 \(if\) 秒了

AC code:

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

string s;

int main(){
    cin >> s;
    if (s == "ACE" || s == "BDF" || s == "CEG" || s == "DFA" || s == "EGB" || s == "FAC" || s == "GBD") cout << "Yes";
    else cout <<" No";
    return 0;
}

B

直接暴力枚举左上角的点，然后去判断整一个矩阵是否满足要求。

注意边界。

AC code：

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

int n, m;
string s[105];

bool check(int x, int y){
    for (int i = x; i <= x + 2; i++){
        for (int j = y; j <= y + 2; j++){
            if (s[i][j] == '.') return 0;
        }
    }
    for (int i = x; i <= x + 3; i++){
        if (s[i][y + 3] == '#') return 0;
    }
    for (int i = y; i <= y + 3; i++){
        if (s[x + 3][i] == '#') return 0;
    }
    for (int i = x + 6; i <= x + 8; i++){
        for (int j = y + 6; j <= y + 8; j++){
            if (s[i][j] == '.') return 0;
        }
    }
    for (int i = x + 5; i <= x + 8; i++){
        if (s[i][y + 5] == '#') return 0;
    }
    for (int i = y + 5; i <= y + 8; i++){
        if (s[x + 5][i] == '#') return 0;
    }
    return 1;
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i <= n - 9; i++){
        for (int j = 0; j <= m - 9; j++){
            if (check(i, j)) cout << i + 1 << " " << j + 1 << endl;
        }
    }
    return 0;
}

C

一眼二分答案，直接二分最低的价格就好了，\(check\) 里面就写满足卖家的数量和买家的数量是否满足条件。

注意：二分的有边界要设为 \(10^{9} + 1\)，不然可能取不到极限 1e9。

AC code:

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

int n, m;
int a[200005], b[200005];

bool check(int mid){
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= n; i++){
        if (a[i] <= mid) cnt1++;
    }
    for (int i = 1; i <= m; i++){
        if (b[i] >= mid) cnt2++;
    }
    return cnt1 >= cnt2;
}

signed main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    int l = 1, r = 1e9 + 1;
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

D

根据题面很容易想到用递归，由小的可以推出来大的，显然可以推出一个递推或者说 \(dp\) 式子。
不难想到可以用 \(dp_{i,j}\) 表示第 \(i\) 个数前面有 \(j\) 个右括号，其中最后答案为 \(dp_{n, n/2}\)。
转移方程就是分类讨论，? 和 ( 和 )，其中 ? 为左括号和右括号之和再模上 \(998244353\)。转移方程不难，只要想到当前情况是由这一个带右括号，或者不带右括号转移过来的就行了。

注意：在计算右括号部分的时候记得特判一下前面有没有右括号，不然会 RE。

AC code：

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

const int mod = 998244353;
string s;
int dp[3005][3005];

int main(){
    cin >> s;
    s = ' ' + s;
    int len = s.size() - 1;
    if (len % 2 == 1) return cout << "0", 0;
    dp[0][0] = 1;
    for (int i = 1; i <= len; i++){
        for (int j = 0; j * 2 <= i; j++){
            if (s[i] == '?') dp[i][j] = ((j ? dp[i - 1][j - 1] : 0) + dp[i - 1][j]) % mod;
            else if (s[i] == '(') dp[i][j] = dp[i - 1][j];
            else dp[i][j] = j ? dp[i - 1][j - 1] : 0;
        }
    }
    cout << dp[len][len / 2];
    return 0;
}

F

二分答案。很容易想到直接三层枚举（实际为两层），仔细一想，其实第二层枚举拉环罐头的具有单调性，开罐器越多，拉环罐头开得越多，我们可以枚举普通罐头，然后拉环罐头和开罐器总和一定，之后二分拉环罐头的个数，求出最大值。在这之前很容易想到贪心一下，给权值从大到小排序。

WA code：

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

int n, m, t, x, ans;
int sa[200005], sb[200005], sc[200005];
vector<int> a, b, c;

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> t >> x;
        if (t == 0) a.push_back(x);
        if (t == 1) b.push_back(x);
        if (t == 2) c.push_back(x); 
    }
    sort(a.begin(), a.end(), greater<int>());
    sort(b.begin(), b.end(), greater<int>());
    sort(c.begin(), c.end(), greater<int>());
    for (int i = 0; i < a.size(); i++) sa[i + 1] = sa[i] + a[i];
    for (int i = 0; i < b.size(); i++) sb[i + 1] = sb[i] + b[i];
    for (int i = 0; i < c.size(); i++) sc[i + 1] = sc[i] + c[i];
    for (int i = 0; i <= a.size() && i <= m; i++){
        int l = 0, r = n - i;
        while (l + 1 < r){
            int mid = l + r >> 1;
            if (sc[n - i - mid] >= mid) l = mid;
            else r = mid - 1;
        }
        ans = max(ans, sa[i] + sb[l]);
    }
    cout << ans << endl;
    return 0;
}