标签：typedef const int long ABC311 cycle define

ABC311

A.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f; // 无穷大
const int MOD = 1e9 + 7;    // 取余
const int N = 2e5 + 10;     // 初始N
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define endl '\n'
int n, m;
void solve()
{
    cin >> n;
    string s;
    int a = 0, b = 0, c = 0;
    cin >> s;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'A')
            a++;
        if (s[i] == 'B')
            b++;
        if (s[i] == 'C')
            c++;
        if (a >= 1 && b >= 1 && c >= 1)
        {
            cout << i + 1 << endl;
            return;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--)
        solve();
    return 0;
}

View Code

B.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f; // 无穷大
const int MOD = 1e9 + 7;    // 取余
const int N = 110 + 10;     // 初始N
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define endl '\n'
int n, m;
char g[N][N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];
    int ans = 0, mx = 0;
    for (int j = 1; j <= m; j++)
    {
        int cnt = 0;
        for (int i = 1; i <= n; i++)
            if (g[i][j] == 'o')
                cnt++;
        if (cnt == n)
        {
            ans++;
            mx = max(mx, ans);
        }
        else
            ans = 0;
    }
    cout << mx << endl;
}

View Code

C.

无向图求一个有向环并输出环，用dfs搜索，每次记录父节点后通过（赛时写的太麻烦了，简单点可以从任意一个点遍历，记录下父节点就行了）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f; // 无穷大
const int MOD = 1e9 + 7;    // 取余
const int N = 2e5 + 10;     // 初始N
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define endl '\n'
vector<int> G[N];
int st[N], path[N], cycle_start, cycle_end;
bool dfs(int v, int p)
{
    st[v] = 1;
    path[v] = p;
    for (int u : G[v])
    {
        if (st[u])
        {
            cycle_start = u;
            cycle_end = v;
            return true;
        }
        else if (!st[u] && dfs(u, v))
            return true;
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        int a;
        cin >> a;
        G[i].push_back(a);
    }
    memset(st, 0, sizeof(st));
    memset(path, 0, sizeof(path));

    cycle_start = -1;
    for (int i = 1; i <= N && cycle_start == -1; i++)
        if (!st[i] && dfs(i, 0))
            break;

    vector<int> cycle;
    for (int v = cycle_end; v != cycle_start; v = path[v])
        cycle.push_back(v);
    cycle.push_back(cycle_start);
    reverse(cycle.begin(), cycle.end());

    cout << cycle.size() << "\n";
    for (int v : cycle)
        cout << v << " ";
    cout << "\n";
    return 0;
}

View Code

D.

牛客之前好像有过类似题，从冰开始可以一直滑到墙，写个while，最后ans统计一下就行

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f; // 无穷大
const int MOD = 1e9 + 7;    // 取余
const int N = 300 + 10;     // 初始N
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define endl '\n'
int n, m;
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
bool vis[N][N], pass[N][N];
char g[N][N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];

    vis[2][2] = true;
    pass[2][2] = true;

    queue<PII> q;
    q.emplace(2, 2);
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 4; k++)
        {
            int x0 = x, y0 = y;
            while (g[x0][y0] == '.')
            {
                pass[x0][y0] = true;
                x0 += dx[k];
                y0 += dy[k];
            }
            x0 -= dx[k];
            y0 -= dy[k];
            if (!vis[x0][y0])
            {
                vis[x0][y0] = true;
                q.emplace(x0, y0);
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (pass[i][j])
                ans++;
    cout << ans << endl;
    return 0;
}

View Code

E.

听群友提示才看出来的，之前没写过，做法：二维前缀和+二分

只要每次枚举边长mid，然后对右下角x,y，到左上角x-mid+1,y-mid+1，求二位前缀和，判断和是不是为0

true：l=mid，答案就是边长

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f; // 无穷大
const int MOD = 1e9 + 7;    // 取余
const int N = 3000 + 10;    // 初始N
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define endl '\n'
int n, m, k;
int c[N][N];
void solve()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++)
    {
        int x, y;
        cin >> x >> y;
        c[x][y]++;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            c[i][j] += c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1];

    auto binary_search = [&](int x, int y)
    {
        int l = 0, r = min(x, y) + 1;
        while (l + 1 != r)
        {
            int mid = l + r >> 1;
            int a = x - mid + 1, b = y - mid + 1; // 左上角
            int sum = c[x][y] - c[x][b - 1] - c[a - 1][y] + c[a - 1][b - 1];
            if (!sum)
                l = mid;
            else
                r = mid;
        }
        return l;
    };

    LL ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans += binary_search(i, j);
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--)
        solve();
    return 0;
}

View Code

后面就不会了0.o

标签：typedef,const,int,long,ABC311,cycle,define
From： https://www.cnblogs.com/crismiao/p/17574759.html