2022 CCPC Henan Provincial Collegiate Programming Contest（补题）

H、旋转水管

这道题比赛的时候想用bfs去写，最后T了，赛后听别人说好像用bfs要剪枝？这道题用dfs还是很省力的。分析题目可以发现走过的没有必要去走，所以dfs每个地方不会超过两遍。方法也是直接不断往后走就行。后面看代码吧。

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int N = 1e5 + 10;

char g[3][N];
bool st[3][N];
int n = 4, m, ex, ey;
// 1 是往下走，2是往左走，3是往上走，4是往右走
bool dfs(int x, int y, int k)
{
    if (x == 3 && y == ey)
        return true;
    if (x < 1 || x > 2 || y < 1 || y > m || st[x][y])
        return false;
        
    st[x][y] = true;
    bool t;
    if (g[x][y] == 'I')
    {
        if (k == 1)
            t = dfs(x + 1, y, 1);
        else if (k == 2)
            t = dfs(x, y - 1, 2);
        else if (k == 3)
            t = dfs(x - 1, y, 3);
        else
            t = dfs(x, y + 1, 4);
    }
    else
    {
        if (k == 1 || k == 3)
        {
            t = (dfs(x, y - 1, 2) || dfs(x, y + 1, 4));
        }
        else if (k == 2 || k == 4)
        {
            t = (dfs(x - 1, y, 3) || dfs(x + 1, y, 1));
        }
    }
    
    st[x][y] = false;
    return t;
}

void solve()
{
    cin >> m >> ex >> ey;
    for (int i = 1; i <= 2; i++)
    {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++)
        {
            st[i][j] = false;
            g[i][j] = s[j - 1];
        }
    }

    if (dfs(1, ex, 1))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;

    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

J - Mex Tree

这道题要画一下图，鉴于文字表达不够完全，并且手边没有画图的工具，所以暂时推荐大佬的博客供大家参考。

有时间补上

大佬博客

#include <bits/stdc++.h>

using namespace std;

#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
//#define For(i, k, n) for (int i = k; i < n; i ++)
//#define FOR(i, k, n) for (int i = k; i <= n; i ++)
#define P acos(-1);
typedef long long LL;
#define PII pair<int, int>
#define PDD pair<double, double>
#define Pll pair<LL, LL>
typedef unsigned long long ULL;
const double eps = 1e-7;
const int N = 1e6 + 10, M = 1e6 + 10, mod = 1000000007;
const int inf = 0x3f3f3f3f;
int dx[4] = {0, 1, -1, 0}, dy[4] = {1, 0, 0, -1};
int lowbit(int x) { return (x & -x); };

int n, siz[N], mi[N], v[N];
vector<int> g[N];
int ans[N];

void dfs(int u, int fa)
{
    siz[u] = 1;
    mi[u] = inf;
    for (int v : g[u])
    {
        if (v == fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
        mi[u] = min(mi[u], mi[v]);
    }

    if (mi[u] > u) ans[u] = n - siz[u];
    mi[u] = min(mi[u], u);
}

void solve() 
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> v[i];

    for (int i = 2; i <= n; i ++ ) 
    {
        int fa; 
        cin >> fa;
        g[v[fa]].push_back(v[i]);
        g[v[i]].push_back(v[fa]);
    }

    dfs(0, 0);
    for (int v : g[0] ) ans[0] = max(ans[0], siz[v]);
    for (int i = 0; i < n; i ++ ) cout << ans[i] << " ";
    cout << n << '\n';
}

int main()
{
    IOS 
    int T = 1;
    // cin >> T;
    while (T -- )
    {
        solve();
    }
    return 0;
}