Codeforces Round 1106 (Div. 2) ABC

字数

449 字

阅读时间

3 分钟

A. Another Puzzle from Papyrus

简要思路

不一定有序，且 $c>=1$ ，两个尝试：

• 不重排，直接处理
• 重排后处理

输出最小值

代码

void solve()
{
    int n, c;
    cin >> n >> c;
    vector<int> a(n), b(n);
    for (int &i : a) cin >> i;
    for (int &i : b) cin >> i;
    int ans1 = 0, ans2 = 0;
    for (int i = 0; i < n && ans1 >= 0; i++)
    {
        if (a[i] >= b[i]) ans1 += a[i] - b[i];
        else ans1 = -1;
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (int i = 0; i < n && ans2 >= 0; i++)
    {
        if (a[i] >= b[i]) ans2 += a[i] - b[i];
        else ans2 = -1;
    }
    cout << min(ans1 == -1 ? 1e9 : ans1, (ans2 == -1 ? 1e9 : ans2 + c)) << endl;
}

B. Crimson Triples

思路

暴力尝试，发现 b 一定是最小的，观察发现 $a\mathrm{\%}b=0,c\mathrm{\%}b=0$ 那么 $a$ 和 $c$ 的取值就是 $\lfloor \frac{n}{b}\rfloor$ 个

代码

int n;
cin >> n;
int ans = 0;
for(int i = 0; i <= n; i++){
	int t = n / b;
	ans += t * t;
}
cout << ans << endl;

C. Village Guilds

简要思路

当前结点的 $an{s}_u=1+\sum _{v\in subTree(u)}an{s}_v+(min(d_1,d_2)-dept{h}_u)$

其中 $an{s}_v$ 表示以 $v$ 为根结点的子树的答案

$d_1{d}_2$ 表示当前结点 $u$ 的所有子树中，每个子树的最大深度的最大值前两名

代码

const int N = 2e5 + 10;
vector<int> g[N];
vector<int> depth, ans, subTreeDepth;

void dfs(int u, int d)
{
    depth[u] = d;
    subTreeDepth[u] = d;
    int tans = 0;        // 所有直接子节点的ans累加
    int mxd[2] = {d, d}; // 子树中最深的两个点的深度
    for (int v : g[u])
    {
        dfs(v, d + 1);
        subTreeDepth[u] = max(subTreeDepth[u], subTreeDepth[v]);
        if (subTreeDepth[v] > mxd[1])
            mxd[1] = subTreeDepth[v];
        if (mxd[0] < mxd[1])
            swap(mxd[0], mxd[1]);
        tans += ans[v];
    }

    ans[u] = 1 + tans + (min(mxd[0], mxd[1]) - depth[u]);
}

void solve()
{
    int n;
    cin >> n;
    // init
    for (int i = 0; i <= n; i++)
        g[i].clear();
    depth.resize(n + 1, 0);
    ans.resize(n + 1, 0);
    subTreeDepth.resize(n + 1, 0);
    for (int i = 2; i <= n; i++)
    {
        int v;
        cin >> v;
        g[v].push_back(i);
    }
    
    dfs(1, 1);
    cout << ans[1] << endl;
}

贡献者

lulaalu

文件历史

最后编辑于 1 分钟前查看完整历史

5389c-add