07-18 10:01 已编辑河南农业大学 C++ 发布于河南

关注

河南萌新联赛2024第（一）场：河南农业大学题解

概况

原本题目出了14道题作为预选，经过难度方面的考虑最终选择这12道题，在预估中难度分布还算比较平均

阶段一(基本编程技巧):A,H,K,I,F

阶段二(常见算法应用):C,D,G,J

阶段三(基础算法进阶):B,L

阶段四(高级算法应用):E

本场比赛主要面对大一升大二的同学，因此难度并不算很高，预想中比较强的可以九道甚至十道

本场比赛B题数据有些松弛，赛时进行了重测，深感抱歉

本场比赛的出题人们都没有任何出题经验，这次是第一次出题，做的不好的地方请大家谅解

A 造数

倒着考虑，当当前 $n$ 是偶数，使用 $÷2$ 操作，当当前 $n$ 为奇数时，使用 $-1$ 操作，

特判当 $n=2$ 时，使用 $-2$ 操作

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int x;
    cin >> x;
    int ans = 0;
    while (x)
    {
        if (x == 2)
            x -= 2;
        else if (x % 2)
            x--;
        else
            x /= 2;
        ans++;
    }
    cout << ans << endl;
}
int main()
{
    solve();
    return 0;
}

B 爱探险的朵拉

根据题意可知，朵拉只能选择一个点作为起始点直到探险结束。同时也可知，本题可能会存在一个或多个环。但我们可以将每个环看成一个集合，这样就可以消除环的影响。然后对于某一个关卡 $i$ ，当我们完成了该关卡时可以选择进行第 $a_i$ 个关卡，这相当于解决了第 $i$ 个关卡，第 $a_i$ 个关卡才会解锁。因此我们可以很容易想到拓扑序列。我们可以先对这 $n$ 个关卡进行拓扑排序，从而得到一个拓扑序列。但这个拓扑序列里面不会有构成环的关卡（包括自环）。然后我们将拓扑序列里面的每个点看成一个集合，将每一个环也看成一个集合，同时将每个集合看作一个点，并定义每个集合的点权值为该集合中点的个数。接着根据拓扑序列，若拓扑序靠前的点与拓扑序靠后的点之间有边相连，若两者位于不同的集合，则代表我们可以通过前者的答案来更新后者的答案，同样的对于一个环，若该环中的某个点的入度大于1，则证明该环所组成的集合也可以通过拓扑序列中的某些点进行更新。若该环中的点的入度全为1，则代表该环构成了一个封闭的连通块，即该环的答案就是组成该环的点的数量。最后将以上所有答案中取一个最大值，这个最大值就是本题的答案。

因为拓扑排序的时间复杂度为 $O(n m)$ ，而其中 $m$ 为边数；而后边的划分集合以及更新答案时每条边只遍历一次，时间复杂度也为 $O(n m)$ 。因此本题的总时间复杂度为 $O(n m)$ 。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
ll a[N];
vector<int> e;
queue<int> q;
int n;
int din[N], son[N], sz[N], tot[N], d[N];
int cnt = 0;
bool b[N];
void topo() // 拓扑排序
{
    for (int i = 1; i <= n; i++)
    {
        if (din[i] == 0)
        {
            q.push(i);
        }
    }
    while (q.size())
    {
        int u = q.front();
        q.pop();
        din[son[u]]--;
        if (din[son[u]] == 0)
        {
            q.push(son[u]);
        }
        e.push_back(u);
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        son[i] = a[i]; // 每个点只有一个出度，即只有一条出边。我们直接用son数组来存放，其实用a数组直接存放也可以。
        din[a[i]]++;   // 记录每个点的入度。
    }
    topo();
    cnt = n;
    for (auto u : e) // 将拓扑序列中的每个点作为一个新的集合，并求出该集合的点权值。
    {
        cnt++;
        tot[u] = cnt; // 将u所在的集合的编号赋值为cnt
        sz[cnt]++;    // 更新编号为cnt的集合的点权值。
    }
    for (int i = 1; i <= n; i++)
    {
        if (din[i] && b[i] == 0) // 将组成一个环的所有的点表示成一个集合，并求出该集合的点权值。
        {
            cnt++;
            b[cnt] = 1;
            int u = i;
            while (b[u] == 0)
            {
                b[u] = 1;
                sz[cnt]++;
                tot[u] = cnt;
                u = son[u];
            }
        }
    }
    for (int i = n + 1; i <= cnt; i++)
    {
        d[i] = sz[i]; // 每个集合的答案的初值为该集合中点的个数。
    }
    ll mx = 0;
    for (auto u : e)
    {
        int v = son[u];
        d[tot[v]] = max(d[tot[v]], d[tot[u]] + sz[tot[v]]); // 通过拓扑序中靠前的点的答案来更新靠后的点的答案。
        mx = max(mx, (ll)d[tot[v]]);                        // 更新答案的同时更新求解最终答案。
        mx = max(mx, (ll)d[tot[u]]);
    }
    for (int i = n + 1; i <= cnt; i++) // 利用构成封闭连通块的环来更新求解最终的答案。
    {
        if (b[i])
        {
            mx = max(mx, (ll)d[i]);
        }
    }
    cout << mx << "\n";
    return 0;
}

本题也可以先通过 tarjan 算法进行缩点并求出各强连通分量。然后建立新图，并建立一个超级源点 0，建边指向各连通分量，边权为被指向的连通分量的点集的大小，之后对新图进行拓扑排序。在拓扑序列中，若点 $i$ 在点 $j$ 之前且存在边 $i→j$ ，则代表我们可以通过点 $i$ 来更新点 $j$ 的答案。最后我们在所有的答案之中取一个最大值便可以得到最后的答案。

本题中tarjan算法的时间复杂度为 $O(n m)$ ，其中 $m$ 为边数；拓扑排序的时间复杂度为 $O(n m)$ ,更新答案时每条边只遍历一次，时间复杂度为 $O(n m)$ ，故本题的总时间复杂度为 $O(n m)$ 。

最后，本题做法很多，不限这两种。比如：先利用 tarjan算法求强连通分量，然后缩点，最后进行搜索；当然基环树加dp的做法也可以解题等等。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
int dfn[N], low[N], tot;
int stk[N], instk[N], top;
int scc[N], cnt, siz[N];
int idx = 1, nxt[N * 2], dian[N * 2], h[N];
ll quan[N * 2];

int n, a[N], din[N];
vector<int> e[N];
vector<int> en;
queue<int> q;
ll d[N];
void add(int a, int b)
{
    dian[++idx] = b;
    nxt[idx] = h[a];
    h[a] = idx;
}
void tarjan(int x)
{
    dfn[x] = low[x] = ++tot;
    stk[++top] = x;
    instk[x] = 1;
    for (int i = h[x]; i; i = nxt[i])
    {
        int y = dian[i];
        if (dfn[y] == 0)
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (instk[y])
        {
            low[x] = min(low[x], dfn[y]);
        }
    }
    if (low[x] == dfn[x])
    {
        int y;
        cnt++;
        do
        {
            y = stk[top--];
            instk[y] = 0;
            scc[y] = cnt;
            siz[cnt]++;
        } while (x != y);
    }
}
void topo_sort()
{
    for (int i = 0; i <= cnt; i++)
    {
        if (din[i] == 0)
        {
            d[i] = 0;
            q.push(i);
        }
    }
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (auto v : e[u])
        {
            din[v]--;
            if (din[v] == 0)
            {
                q.push(v);
            }
        }
        en.push_back(u);
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        add(i, a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        if (dfn[i] == 0)
        {
            tarjan(i);
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = h[i]; j; j = nxt[j])
        {
            int y = dian[j];
            if (scc[i] != scc[y])
            {
                e[scc[i]].push_back(scc[y]);
                din[scc[y]]++;
            }
        }
    }
    for (int i = 1; i <= cnt; i++)
    {
        e[0].push_back(i);
        din[i]++;
    }
    topo_sort();
    for (auto u : en)
    {
        for (auto v : e[u])
        {
            ll w = siz[v];
            if (d[v] < d[u] + w)
            {
                d[v] = d[u] + w;
            }
        }
    }
    ll mx = 0;
    for (int i = 1; i <= cnt; i++)
    {
        mx = max(mx, d[i]);
    }
    cout << mx << "\n";
    return 0;
}

C 有大家喜欢的零食吗

本题是二分图匹配板子题。大家可以学习一下，本题解为匈牙利算法求二分图最大匹配。时间复杂度 $O(nm)$ ，其中 $n$ 为点数， $m$ 为边数。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 5005;
int n, k, a, ans;
bool b[N];
int match[N];
vector<int> e[N];
bool dfs(int u)
{
    for (int v : e[u])
    {
        if (b[v])
        {
            continue;
        }
        b[v] = 1;
        if (match[v] == 0 || dfs(match[v]))
        {
            match[v] = u;
            return true;
        }
    }
    return false;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> k;
        for (int j = 1; j <= k; j++)
        {
            cin >> a;
            e[i].push_back(a);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        memset(b, 0, sizeof(b));
        if (dfs(i))
        {
            ans++;
        }
    }
    if (ans == n)
    {
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
        cout << n - ans << "\n";
    }
    return 0;
}

D 小蓝的二进制询问

要求区间 $\left[ l,r \right]$ 的1的个数，显然我们可以用前缀和去计算，即区间 $\left[ 1,r \right]$ 的个数减去区间 $\left[ 1,l-1 \right]$ 的个数作为答案。

下面考虑如何计算区间 $\left[ 1,r \right]$ 的个数：

我们按位考虑，从最低位开始，显然最低位上是01 01 01循环，也就是两种情况，我们在此基础上去考虑下一位，只看当前位的话仍然只有01两种情况，但是当我们结合上一位，一个0就是对应上一位的所有情况，1同理，那么这一位就是0 0 1 1，以此类推，设当前位是第k位，那在当前位上循环节就是 $2^{k 1}$ $\left( 2^{k}个0和2^{k}个1 \right)$ 每一位累加即可。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
const int N = 4e5 + 7;
const int mod = 998244353;
ll f(ll x, ll k)
{
    ll y = 1ll << (k + 1);
    ll ok = y / 2;
    x++;
    ll res = x / y * ok; // 循环节内部分
    ll r = x % y;
    r -= ok;
    if (r > 0)
        res += r; // 计算循环节多余部分
    return res;
}
void solve()
{
    ll l, r;
    cin >> l >> r;
    ll ans = 0;
    for (ll i = 61; i >= 0; i--)
    {
        ll p = (f(r, i) % mod - f(l - 1, i) % mod + mod) % mod;
        ans = (ans + p) % mod;
    }
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _;
    cin >> _;
    while (_--)
        solve();

    return 0;
}

E 奇妙的脑回路

考虑没有修改时的做法，如果一个点是不小于2的路径的回文中心，那么其所在回文串长度一定为奇数，则该点的相邻点中必有两个点对应字符相同。我们可以预处理出每个结点到根节点的路径上的满足要求的点的个数，通过求LCA的差分操作可以快速求出操作2的答案。

考虑操作一，我们容易观察到，通过对子树上结点都进行+1操作，结点性质(是否是回文中心)发生变化的点只有当前子树的根结点和它的父亲结点。充分考虑这一性质，我们可以用 $dp[N][26]$ 数组维护一个结点与周围结点权值差值的个数。 $dp[i][j]$ 表示结点 $i$ 与周围结点差值为 $j$ 的个数。同时再用一个数组 $s$ 表示当前结点与它的父亲结点的差值。这样我们在修改的时候就只需要更改 $s[i]$ 和 $dp$ 中差值的个数。之后遍历一遍差值判断当前点是否为回文中心，如果其性质(是否是回文中心)发生改变，对于子树上的所有结点来说，其到根结点的路径上的个数发生改变，相当于dfs序上的区间修改，我们可以使用树状数组或线段树维护这一答案。

本题总体复杂度为 $O(qlogn 26q)$

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
#define lowbit(x) (x & (-x))
using namespace std;
using ll = long long;
const int N = 2e5 + 7;
const int mod = 998244353;
vector<int> G[N];
int a[N];
int tr[N];
int dp[N][26];
int l[N], r[N];
int s[N];
int p[N][22];
int dep[N];
int tot;
string str[N];
struct Bit
{
    int n;
    void add(int now, int val)
    {
        for (int i = now; i <= n; i += lowbit(i))
            tr[i] += val;
    }
    int query(int now)
    {
        int ans = 0;
        for (int i = now; i; i -= lowbit(i))
            ans += tr[i];
        return ans;
    }
} T;
void dfs(int now, int fa)
{
    if (p != 0)
        s[now] = (a[now] - a[fa] + 26) % 26;
    dep[now] = dep[fa] + 1;
    l[now] = ++tot;
    p[now][0] = fa;
    for (int i = 1; i < 22; i++)
        p[now][i] = p[p[now][i - 1]][i - 1];
    for (auto it : G[now])
    {
        if (it == fa)
            continue;
        dfs(it, now);
    }
    r[now] = tot;
}

int LCA(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 21; i >= 0; i--)
        if (dep[p[x][i]] >= dep[y])
            x = p[x][i];
    if (x == y)
        return x;
    for (int i = 21; i >= 0; i--)
        if (p[x][i] != p[y][i])
            x = p[x][i], y = p[y][i];
    return p[x][0];
}
void calc(int x, int f)
{
    bool ok = 0;
    for (int i = 0; i < 26; i++)
        ok |= (dp[x][i] >= 2);
    T.add(l[x], ok * f);
    T.add(r[x] + 1, -ok * f);
}
void solve()
{
    int n;
    cin >> n;

    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        cin >> str[i], a[i] = str[i][0] - 'a';
    for (int i = 1; i <= n; i++)
        for (auto it : G[i])
            dp[i][(a[i] - a[it] + 26) % 26]++;
    dfs(1, 0);
    T.n = n;
    for (int i = 1; i <= n; i++)
        calc(i, 1);
    int q;
    cin >> q;
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int x;
            cin >> x;
            if (x != 1)
            {
                calc(x, -1);
                calc(p[x][0], -1);
                dp[x][s[x]]--;
                dp[p[x][0]][(26 - s[x]) % 26]--;
                s[x]++;
                s[x] %= 26;
                dp[x][s[x]]++;
                dp[p[x][0]][(26 - s[x]) % 26]++;
                calc(x, 1);
                calc(p[x][0], 1);
            }
        }
        else
        {
            int x, y;
            cin >> x >> y;
            int z = LCA(x, y);
            int ans = T.query(l[x]) + T.query(l[y]) - T.query(l[z]) - T.query(l[p[z][0]]);
            cout << ans << '\n';
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    solve();

    return 0;
}

F 两难抉择新编

$\sum^{n}_{i=1}\frac{n}{i} \leq n\ log_{2}n$ ，所以本题暴力即可。

时间复杂度 $O(nlog_2n)$ 。

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

int main()
{
    int n;
    cin >> n;
    long long sum = 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum ^= a[i];
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n / i; j++)
        {
            ans = max(ans, sum ^ a[i] ^ (a[i] + j));
            ans = max(ans, sum ^ a[i] ^ (1ll * a[i] * j));
        }
    }
    cout << ans << '\n';
    return 0;
}

G 旅途的终点

对于前 $k$ 个国家，我们直接先选择消耗神力，从第 $k 1$ 个国家开始我们就从我们选择消耗神力的 $k$ 个国家中选择出一个在不消耗神力的前提下，需要消耗的生命力最小的国家，并假设该国家为 $i$ ,需要消耗的生命力为 $a_i$ 。同时我们设我们当前所在的国家为 $j$ ,需要消耗的生命力为 $a_j$ 。若 $a_i>a_j$ ，则我们选择在第 $j$ 个国家消耗生命力，仍在第 $i$ 个国家消耗神力，这样可以保证我们的生命力消耗的最小；反之，则我们选择在第 $i$ 个国家消耗生命力，在第 $j$ 个国家消耗神力，以此来逐渐更新，保证答案最大。这个过程类似于一个反悔贪心的过程。最后当发现无法畅游某一个国家或可以旅行完全部国家时就代表找到答案了。

注意：本题中 $\sum_{i=1}^{n} a_i$ 的值会超出 long long 类型的数据范围，因为 $m$ 的取值范围没有超出 long long 类型故若找到答案之后立刻结束则可以保证不会超出 long long 的数据范围。当然，若使用 __int128 类型，则不必担心这个问题。

因为本题只遍历一遍，时间复杂度为 $O(n)$ ，而优先队列的每次pop和push的时间复杂度为 $O(logn)$ ，所以本题的时间复杂度为 $O(nlogn)$ 。

#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
ll n, m, k;
ll a[N];
priority_queue<ll, vector<ll>, greater<ll>> q;
int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    ll sum = 0;
    for (int i = 1; i <= n; i++)
    {
        q.push(a[i]);
        if (q.size() > k)
        {
            sum += q.top();
            q.pop();
        }
        if (sum >= m)
        {
            cout << i - 1 << "\n";
            return 0;
        }
    }
    cout << n << "\n";
    return 0;
}

H 两难抉择

使数组中总和增加最多即可。

#include "bits/stdc++.h"
using namespace std;
int main()
{
    int n;
    cin >> n;
    long long mx = 0, sum = 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        mx = max({mx, sum - a[i] + 1ll * a[i] * n, sum - a[i] + a[i] + n});
    }
    cout << mx << '\n';
}

I 除法移位

我们注意到，操作次数 $t$ 可以优化到 $n-1$ 及以下（之后的操作次数会造成循环），而且第 $i$ 次操作使得 $a_{(n-i) mod\ n 1}$ 作为分子。

显然：

$S(i)=\frac{ a_{(n-i)mod\ n 1}^2 }{ {\prod^{n}_{j=1}a_j} }$

我们知道，对于任何正整数 $a^2\leq b^2 \Leftrightarrow a\leq b$ ，所以我们只需要找到 $[0,min(n-1,t)]$ 范围内 $a_{(n-i) mod\ n 1}$ 的首次出现的最大值即可。

#include "bits/stdc++.h"
#define ll long long
#define endl '\n'
using namespace std;

int main()
{
    cin.tie(nullptr)->sync_with_stdio(0);
    int n, t;
    cin >> n >> t;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int nt = 0, nv = 0;
    for (int i = 0; i <= min(n - 1, t); i++)
    {
        if (a[(n - i) % n + 1] > nv)
        {
            nt = i;
            nv = a[(n - i) % n + 1];
        }
    }
    cout << nt << '\n';
    return 0;
}

J 最大矩阵匹配

本题有多种做法，较为常见的是动态规划。

我们将矩阵左右翻转，通过二维前缀和辅助，每次判断三个点是否为1即可判断动态规划转移。

时间复杂度 $O(nm)$ 。

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
const int N = 5e5 + 7;
const int mod = 998244353;

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<string> s(n + 1);
    for (int i = 1; i <= n; i++)
    {
        string str;
        cin >> str;
        reverse(str.begin(), str.end());
        s[i] = " " + str;
    }
    vector<vector<int>> sum(n + 1, vector<int>(m + 1, 0));
    auto dp = sum;
    auto h = sum, w = sum;
    // w.resize(m + 1,vector<int>(n + 1,0));
    int mx = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (s[i][j] == '1');
            if(sum[i][j]>0)mx = 1;
        }
    }
    // vector<vector<int>>h(n + 1),w(m + 1);

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            h[i][j] = h[i][j - 1] + (s[i][j] == '1');
            w[i][j] = w[i - 1][j] + (s[i][j] == '1');
        }
    }
    // int mx = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (s[i][j] == '1')
            {
                int p = dp[i - 1][j - 1] + 1;
                {
                    p--;
                    int now = sum[i - 1][j - 1] - sum[i - 1][j - p - 1] - sum[i - p - 1][j - 1] + sum[i - p - 1][j - p - 1];
                    if (now == p)
                    {
                        int nowx = h[i][j - 1] - h[i][j - 1 - p];
                        int nowy = w[i - 1][j] - w[i - 1 - p][j];
                        if (nowx == p && nowy == p)
                        {
                            mx = max(mx, p + 1);
                        }
                        // if(i==3&&j==3){
                        //     cout << nowx << " " << nowy << " " << p << '\n';
                        // }
                    }
                    p++;
                }
                int now = sum[i][j] - sum[i][j - p] - sum[i - p][j] + sum[i - p][j - p];
                if (now == p)
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    dp[i][j] = 1;
                }
            }
            else
            {
                dp[i][j] = 0;
            }
        }
    }
    cout << mx << '\n';
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;

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

接下来介绍一种看似暴力实际上复杂度正确的做法。

我们将矩阵翻折，转化为寻找左上角箭头矩阵 $[\nwarrow]$

对于一个长度为 $len$ 的符合条件的矩阵，只有一个点对应长度为 $len$ ，其他点的答案均为 $1$ 。

将这个矩阵划分成长度为 $len/2$ 的四个矩阵，如果每个矩阵都符合条件，那么有四个点对应长度为 $len/2$ ，其他点长度均为 $1$ 。

假如我们采取三重循环暴力枚举，前两层枚举点，第三层枚举边长，可以发现，符合条件的矩阵越小，需要枚举的边长总和反而越大（如上述两个矩阵，前者需要枚举一次 $len$ , 后者需要枚举 $2*len$ )。

如此，当输入全为1的01矩阵时，需要枚举的边长达到最大，几乎所有的点都需要枚举边长 $\{1,2\}$ 。

所以最坏时间复杂度为 $O(nm)$ 。

#include "bits/stdc++.h"
#define ll long long
#define endl '\n'
using namespace std;
constexpr int N = 5e3 + 10;

bool mp[N][N];
int s[N][N];
int get(int x1, int y1, int x2, int y2)
{
    return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            mp[n + 1 - i][j] = (c == '1');
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            s[i][j] = (mp[i][j] == 1);
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            for (int k = 1; k <= min(n, m); k++)
            {
                if (i + k - 1 > n || j + k - 1 > m)
                    break;
                if (mp[i + k - 1][j + k - 1] == 1 && mp[i][j + k - 1] == 1 && mp[i + k - 1][j] == 1 && get(i, j, i + k - 1, j + k - 1) == 3 * k - 2)
                {
                    ans = max(ans, k);
                }
                else
                {
                    break;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

当然，我们也可以用二维哈希加二分处理，二分边长暴力check。

时间复杂度 $O(nmlog_2(min(n,m))$ 。

（这个解法可能会卡常）

#include "bits/stdc++.h"
#define ll long long
#define uint unsigned int
#define endl '\n'
using namespace std;
constexpr int N = 5e3 + 10, base1 = 131, base2 = 233;

char mp[N][N];
uint h[N][N], p1[N], p2[N], s[N][N];
int n, m;

uint gethash(int x1, int y1, int x2, int y2)
{
    return h[x2][y2] - h[x2][y1 - 1] * p1[y2 - y1 + 1] - h[x1 - 1][y2] * p2[x2 - x1 + 1] + h[x1 - 1][y1 - 1] * p1[y2 - y1 + 1] * p2[x2 - x1 + 1];
}

uint gets(int x1, int y1, int x2, int y2)
{
    return s[x2][y2] - s[x2][y1 - 1] * p1[y2 - y1 + 1] - s[x1 - 1][y2] * p2[x2 - x1 + 1] + s[x1 - 1][y1 - 1] * p1[y2 - y1 + 1] * p2[x2 - x1 + 1];
}

void init(int n, int m)
{
    p1[0] = p2[0] = 1;
    for (int i = 1; i <= max(n, m); i++)
    {
        p1[i] = p1[i - 1] * base1;
        p2[i] = p2[i - 1] * base2;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            h[i][j] = h[i][j - 1] * base1 + mp[i][j];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            h[i][j] += h[i - 1][j] * base2;
        }
    }
    int k = min(n, m);
    for (int i = 1; i <= k; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            char c;
            if (i == k || j == 1 || (i + j == k + 1))
                c = '1';
            else
                c = '0';
            s[i][j] = s[i][j - 1] * base1 + c;
        }
    }
    for (int i = 1; i <= k; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            s[i][j] += s[i - 1][j] * base2;
        }
    }
}

bool check(int len)
{
    int k = min(n, m);
    for (int i = 1; i <= n - len + 1; i++)
    {
        for (int j = 1; j <= m - len + 1; j++)
        {
            uint cur = gethash(i, j, i + len - 1, j + len - 1);
            uint res = gets(k - len + 1, 1, k, len);
            if (cur == res)
                return 1;
        }
    }
    return 0;
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> mp[i][j];
        }
    }
    init(n, m);
    int l = 0, r = min(n, m);
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    cout << l << endl;

    return 0;
}

K 图上计数(Easy)

注意到可以断掉所有边，那贪心的去想就把所有边断掉之后我们可以任意组合。由于断掉所有边后只剩下大小为1的联通块，由于和固定为 $n$ ，那么将其尽可能均分后乘积最大。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
const int N = 4e5 + 7;
const int mod = 998244353;

void solve()
{
    ll n, m;
    cin >> n >> m;
    while (m--)
    {
        int x, y;
        cin >> x >> y;
    }
    cout << (n / 2) * (n - n / 2) << endl;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    solve();

    return 0;
}

L 图上计数(Hard)

本题只能断掉桥，同理，我们贪心的去断掉所有桥得到若干个连通块，将每个连通块的大小塞进数组里，那么题目就变为：选择一部分元素之和与剩下一部分之和乘积最大。这显然是一个可行性背包问题，正常情况下我们跑01可行性背包即可，但本题数据范围不允许。注意到所有元素之和是等于点的个数n，这就是说数组元素种类不会超过 $\sqrt{n}$ 个，那么可以直接跑多重背包。注意使用二进制或单调队列优化。

时间复杂度 $O(n\sqrt{n}$ ) 。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
using ll = long long;
const int N = 4e5 + 7;
const int mod = 998244353;
template <class T> // 求联通分量法
struct SCC
{
#define first fi
#define second se
    int n;
    std::vector<std::vector<std::pair<int, int>>> adj;
    std::vector<int> stk;
    std::vector<int> dfn, low, bel;
    std::vector<int> siz;
    std::vector<std::vector<int>> ans; // 存边双
    int cur, cnt;
    SCC() {}
    SCC(int n)
    {
        init(n);
    }
    void init(int n)
    {
        this->n = n;
        adj.assign(n + 1, {});
        ans.assign(0, {});
        dfn.assign(n + 1, -1);
        low.resize(n + 1, -1);
        bel.assign(n + 1, -1);
        siz.resize(n + 1, 0);
        stk.clear();
        cur = cnt = 0;
    }

    void add(int u, int v, int id = 0) // 记得存反边的编号
    {
        adj[u].push_back({v, id << 1});
        adj[v].push_back({u, id << 1 | 1});
    }
    void tarjan(int u, int last = 0)
    {
        dfn[u] = low[u] = cur++;
        stk.push_back(u);
        for (auto [v, id] : adj[u])
        {
            if (id == (last ^ 1))
                continue;
            if (dfn[v] == -1)
            {
                tarjan(v, id);
                low[u] = std::min(low[u], low[v]);
            }
            else
            {
                low[u] = std::min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u])
        {
            ++cnt;
            int y;
            vector<int> tempans;
            do
            {
                y = stk.back();
                bel[y] = cnt;
                stk.pop_back();
                tempans.push_back(y);
                siz[cnt]++;
            } while (y != u);
            ans.push_back(tempans);
        }
    }

    std::vector<int> work(int n)
    {
        vector<int> dp(n, 0);
        for (int i = 1; i <= n; i++)
        {
            if (dfn[i] == -1)
            {
                tarjan(i, 0);
            }
        }
        vector<int> v;
        vector<int> mp(n + 1, 0);
        for (auto j : ans)
        {
            v.push_back(j.size());
            mp[j.size()]++;
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());

        dp[0] = 1;
        ll res = 0;
        for (int i = 0; i < v.size(); i++)
        {
            int tot = mp[v[i]];

            for (int k = 1; k <= tot; k <<= 1)
            {
                tot -= k;
                int w = k * v[i];
                for (int j = (n + 1) / 2; j >= w; --j)
                {
                    dp[j] |= dp[j - w];
                }
            }
            if (tot)
            {
                int w = tot * v[i];
                for (int j = (n + 1) / 2; j >= w; --j)
                {
                    dp[j] |= dp[j - w];
                }
            }
        }
        for (int i = 0; i <= (n + 1) / 2; ++i)
        {
            if (dp[i])
                res = max(res, 1ll * (n - i) * i);
        }
        cout << res;
        return bel;
    }
};
void solve()
{
    int n, m;
    cin >> n >> m;
    SCC<int> g(n);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        g.add(u, v, i);
    }
    g.work(n);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    solve();

    return 0;
}

Thank you！！！

全部评论

推荐最新楼层

梺栨

西安理工大学算法工程师

D题题解中 x++ 是为什么啊

2 回复分享

发布于 07-18 01:38 陕西

Joker_zj

小丑学院数据其它

J题的dp[i][j]表示的是什么状态啊

点赞回复分享

发布于 07-19 16:54 湖南

牛客20220304118

长沙学院算法工程师

J题第一种解法是错的吧？

点赞回复分享

发布于 07-22 10:49 湖南

11-02 12:04

门头沟学院后端

挑战华为最晚入池

爱华信华等华！！！整个流程足足等了两个月终于走完流程了，许愿可以泡出来！目前也是符合1145+25h定律，丝滑入池TimeLine：9.13 一面10.18 二面10.31 主管面

out11Man：佬为啥这么晚才面完华为

晒一晒我的offer 华子oc时间线

点赞评论收藏

11-02 08:15

已编辑

门头沟学院 Java

回国还是留美

美团 Java后端开发 10w刀美硕

YamadaAnna：包留美的，你拿的美团招银，没一个不加班的。考虑一下未来吧，应届生的工资真不重要，10w刀税后6w，省省还是能活下去的。回国了35岁怎么办，难道35岁还能返美么，就算35岁还能在国内找到工作，难道打算一辈子9点10点下班么。你有能力在美利坚找到工作，回国如果不是哪个965大厂给你发个ssp，真不值得。等抽不中h1b，没办法了再回国吧。

点赞评论收藏