Codeforces Round #831 (Div. 1 + Div. 2)

1.Problem - D - Codeforces

首先是一个结论就是如果除了起点终点以外你发现只要是还多一个格子你是可以把所有牌都任意移动的。

然后这个问题就很好解决了。你每次需要把最大的牌移动到终点所以你得把这些他上面的牌都移动开即可。

const int N = 1e5 + 100;
int n, m ,k;
int a[N];
void slove()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= k; i++)
    {
        cin >> a[i];
        a[i] = k - a[i];
    }
    vector<bool>st(k);
    int sz = 0;
    for(int i = 1, j = 0; j < k; j++)
    {
        while(!st[j]){
            st[a[i++]] = true;
            sz++;
        }
        if(sz > n * m -3){
            cout <<"TIDAK"<< "\n";
            return;
        }
        st[j] = false;
        sz--;
    }
    cout << "YA" << "\n";
}

2.Problem - E - Codeforces

首先大值往上给肯定是更好的。

任意一个点的值肯定是子树中的最小值的时候才是可以取的。

然后考虑父亲是否会产生价值。首先如果是一条链，整条链肯定是都可以产生价值的。

如果是有多个儿子，父亲是肯定不产生价值的。这很好理解。你父亲最后一个取还是最小值。

一开始我认为整棵子树都能产生价值但是第一个例子就是错的。

所以就考虑子树的贡献。子树的贡献很明显是可以相加的。这是很好理解的。你赋值的时候肯定是从最左子树到最右子树从小到大赋值

嘛。所以这以此点为根的另一个可以产生的价值就是所有子树价值相加，然后两者取最大值即可。

const int N = 1e5 + 100;
int n, f[N], d[N];
vector<int>b[N];
void dfs(int u)
{
    d[u] = 1;
    for(auto v : b[u])
    {
        dfs(v);
        d[u] = max(d[v] + 1, d[u]);
        f[u] += f[v];
    }
    f[u] = max(f[u], d[u]);
}
void slove()
{
    cin >> n;
    for(int i = 2; i <= n ; i++)
    {
        int fa;
        cin >> fa;
        b[fa].pb(i);
    }
    dfs(1);
    cout << f[1] << endl;
}