第五场

D：

思路：

确定了 b 即可得到a， 得到 b 即为 c 的因子，复杂度为 根号下1e9，1e5 符合。

代码

void solved()
{
    int k, c, n;
    cin >> k >> c >> n;

    vector<int> all;

    for(int i = 1; i <= c / i; i++)
    {
        if(c % i == 0)
        {
            all.push_back(i);

            if(c / i != i)
            {
                all.push_back(c / i);
            }
        }
    }

    int ans = 0;

    for(auto b : all)
    {
        if(c - b == 0) continue;
        if((c - b) % k) continue;
        int a = (c - b) / k;
        if(gcd(a, b) < n)
        {
            continue;
        }

        ans++;
    }

    cout << ans << endl;


}

G

思路：

判断包含 k 个 4的区间内是否存在 1234，双指针即可找到所有包含k个4的区间，然后维护123出现的状态即可。

代码：

void solved()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];

    int l = 1;

    int ans = 1e9;

    for(int r = 1; r <= n; r++)
    {
//        cout << l << " " << r <<endl;

        c[a[r]]++;
        if(c[4] < m || c[1] == 0 || c[2] == 0 || c[3] == 0) continue;

        while(l <= r && c[4] >= m && c[1] && c[2] && c[3])
        {
            c[a[l]]--;
            l++;
        }

        l--;
        c[a[l]]++;

        if(c[4] >= m && c[1] && c[2] && c[3])
        ans = min(ans, r - l + 1);
    }

    cout << ans << endl;
}

C：

思路：

本图可以转换为竞赛图，通过合并 i和i+n，条件1满足不存在自环，条件2满足不存在重边，我们把无向边转化为有向边，则把图转化为竞赛图。因为竞赛图一定存在哈密顿路径，所以答案至少为 n- 1, 如果答案为 n，那么整个图是强连通的，那么图中所有强连通分量大小 >= 2。

跑一遍tarjan

代码

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    is_stk[u] = true;

    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];

        if(!dfn[j])
        {
            tarjan(j);

            low[u] = min(low[u], low[j]);
        }else if(is_stk[j])
        {
            low[u] = min(low[u], low[j]);
        }
    }


    if(dfn[u] == low[u])
    {
        int y;
        ++scc_cnt;

        do
        {
            y = stk.top();
            stk.pop();

            is_stk[y] = false;

            id[y] = scc_cnt;
            Size[scc_cnt] ++;
        }while(y != u);
    }

}


void solved()
{
    memset(h, -1 ,sizeof h);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            int x; cin >> x;
            if(x) add(i, j);
        }
    }

    for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i);

    for(int i = 1; i <= scc_cnt; i++)
    {
        if(Size[i] < 2)
        {
            cout << n - 1 << endl;
            return;
        }
    }
    cout << n << endl;

}