2025寒假专场10

compaq · 2025-01-26 10:18:04 · 题解

空闲连续天

入门，模拟

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e3 + 10;

int n, m;
int f[N];
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char c;
            cin >> c;
            if (c == 'o') f[j]++;
        }
    }
    int res = 0, maxn = 0;
    for (int i = 1; i <= m; i++) {
        if (f[i] == n) res++;
        else {
            maxn = max(maxn, res);
            res = 0;
        }
    }
    maxn = max(maxn, res);
    cout << maxn;
    return 0;
}

二维码

入门，模拟

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100 + 10;

int n, m, res;
char g[N][N];
bool check(int x, int y, int u) {
    bool f = true;
    if (u == 1) {
        for(int i = x; i <= x + 2; i++) {
            for(int j = y; j <= y + 2; j++) {
                if (g[i][j] != '#') {
                    f = false;
                    break;
                }
            }
            if (!f) break;
        }
        for (int i = 0; i <= 3; i++) {
            if (g[x + i][y + 3] != '.' || g[x + 3][y + i] != '.') {
                f = false;
                break;
            }
        }
    }
    else{
        for(int i = x - 2; i <= x; i++) {
            for(int j = y - 2; j <= y; j++) {
                if(g[i][j] != '#') {
                    f = false;
                    break;
                }
            }
            if (!f) break;
        }
        for (int i = 0; i <= 3; i++) {
            if (g[x - i][y - 3] != '.' || g[x - 3][y - i] != '.') {
                f = false;
                break;
            }
        }
    }
    return f;
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) 
            cin >> g[i][j];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!check(i, j, 1)) continue;
            int x = i + 8, y = j + 8;
            if (x <= n && y <= m) {
                if (check(x, y, 2)) {
                    cout << i << ' ' << j << endl;
                }
            }
        }
    }
    return 0;
}

买家卖家

当价格d越高时, 可能的商贩数量x就会越多, 而顾客数量y就会越少; 发现这个单调性后我们就可以考虑用二分来实现;

如果对于价格mid, x < y, 那我们就增大价格mid直到x>=y;

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
int s[N], b[N];
bool check(int u) {
    int numb = 0, nums = 0;
    for (int i = 1; i <= n; i++) 
        if (s[i] <= u) nums++;

    for (int i = 1; i <= m; i++) 
        if (b[i] >= u) numb++;

    if (nums >= numb) return true;

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

合法字符串

典型的括号类的 dp 。

• 若s_i == ')', 则$ dp[i][j] = dp[i - 1][j + 1]

。若s_i == '?'，则分别加上是 (的方案和 )的方案即可, 即