[数据结构与算法]Codeforces Round #800 (Div. 2) A~E

Codeforces Round #800 (Div. 2)

[Link](Dashboard - Codeforces Round #800 (Div. 2) - Codeforces)

A. Creep

题意

? 让你用$a$个$0$和$b$个$1$构造一个$01$串，该串的前缀$0,1$数量差的绝对值最小

思路

• 贪心

? 贪心来看能抵消就抵消因此$0,1$相间隔放，后面无法间隔就放剩下的即可。

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T -- ) {
        int x, y; cin >> x >> y;
        n = x + y;
        for (int i = 0; i < n; i ++) {
            if (x && i % 2 == 0) cout << 0, x --;
            else if (y && i % 2) cout << 1, y --;
            else if (x) cout << 0, x --;
            else cout << 1, y --;
        }
        cout << '\n';
    }
    return 0;
}

B. Paranoid String

题意

? 给你一个$0,1$串，你有两种操作，$1$. 选择相邻$01$编程一个$1$、$2$. 选择相邻的$10$变成一个$0$，问你有多少个数对$(l,r)$使得$[s_l,s_r]$通过若干次操作后变成长度为$1$的串。

思路

• 枚举、思维

? 对于统计多少个数对我们考虑枚举每个$i$和$i$前面哪些位置可以构成数对

1. 首先$i$和它自己可以构成数对

2. 如果$i$和$i?1$一样的话无论前面选到哪怎么操作最后至少会留下两个相邻的一样的数，因此没有贡献

3. 如果$i$和$i?1$不一样的话，$i$和前面任意一个位置构成点对都合法，因为前面的所有情况只会分成两类 ：

   1. $i$之前顺利合并了由于$i$和$i?1$不同因此它们也可以合并

   2. $i$之前无法顺利合并则意味着剩下的均是$i?1$这个字符，$i$和它们依次合并即可

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T -- ) {
        cin >> n;
        string str; cin >> str;
        LL res = n;
        for (int i = 1; i < str.size(); i ++)
            if (str[i] != str[i - 1])
                res += i;
        
        cout << res << '\n';
    }
    return 0;
}

C. Directional Increase

题意

你有一个长度为$n$的全零数组$a$，一开始你在$1$，每次你可以进行以下操作的一种：

1. 从当前挪到前一个位置当前位置值减一，如果当前不在$1$
2. 从当前挪到后一个位置当前值加一，如果当前不在$n$

给你一个数组$b$，问你能否通过若干次操作将$a$变成$b$并且你最后位于$1$这个位置

思路

• 思维

? 首先观察一下性质，由于右移加一左移减一因此$b$数组和应该为$0$，先右移再左移，也就是先加再减，因此$b$数组前缀和的每个位置应该$\ge 0$，然后到右边某个位置之后我们就要往回走了这个时候前缀和一定是$0$（整体只有左右操作因此是$0$），并且由于回去了所以后面的位置应该都是零。

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 2e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T -- ) {
        cin >> n;
        for (int i = 1; i <= n; i ++) cin >> a[i];        
        bool ok = true, ok0 = false;
        int s = 0;
        for (int i = 1; i <= n; i ++) {
            s += a[i];
            if (ok0 && s != 0) ok = false;
            if (s < 0) ok = false;
            if (s == 0) ok0 = true;
        }
        if (s != 0) ok = false;
        cout << (ok ? "YES" : "NO") << '\n';
    }
    return 0;
}

• 模拟

? 没抓住关键点这些性质的话，我们也可以模拟来做，首先右边最后一个不为$0$的位置$r$一定是我们往左走的点，并且$[2,r]$最后都会往左走一次，因此我们统一$+1$将操作抵消，剩下的就之后相邻两项之间移动所产生的代价了。从$r?1$往前枚举每一个位置，对于当前位置由于他会往右走一次$+1$，因此给他$?1$，这样就只剩下反复横跳的次数了，每横跳一次相当于它加一右边减一，因此我们将当前位置加上前一个位置的值相当于把反复横跳的代价抵消掉了，由于再往前走的所有的位置的操作只会让当前位置减所以当当前位置操作完的值应该$\ge 0$，判断每一个点即可。

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 2e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T -- ) {
        cin >> n;
        int s = 0;
        for (int i = 1; i <= n; i ++) cin >> a[i], s += a[i];
                       
        int r = 1;
    
        for (int i = n; i; i --) 
            if (a[i] != 0) {
                r = i;
                break;
            }
        for (int i = 2; i <= r; i ++) a[i] ++;
        int v = a[r];
        bool ok = true;
        if (v > 0) ok = false;
        for (int i = r - 1; i >= 1; i --) {
            a[i] --;
            a[i] += v;
            v = a[i];
            if (v > 0) {
                ok = false;
                break;
            }
        }
        if (v != 0) ok = false;
       
        cout << (ok ? "YES" : "NO") << '\n';
    }
    return 0;
}

D. Fake Plastic Trees

题意

? 给你一颗有根树根为$1$，每个点的点权$a$初始为$0$，对于每个点最终取值应该$[l_{a_i},r_{a_i}]$，每次你可以选择一个点$v$，并且将$1\to v$的最短路径上加上一个非递减序列，问你最少需要多少次操作让每个$a_i$均落在对应的取值区间内。

思路

• 贪心，$dp$

? 首先对于每个点我们来看如何让他落在对应的取值区间内，1. 它的在消灭以他为根的子树的所有结点的时候顺带将他消灭了 2. 我们操作一次将他消灭。

? 因此我们从根开始搜，对于每个结点统计出以他为根的子树最多可以消灭多少数，对于某个结点$u$，将它的所有子节点最多能够消除的数相加为$s$，如果$s\ge l_u$则说明在消灭它的子树的时候可以可以顺带将他消灭到，贪心来看能不操作就不操作，因此以$u$为根的子树最多能消灭的数即$s$，如果$s<l_u$则说明需要操作一次，由于它越大它的父节点就越可能被抵消掉因此让$s=r_u$并且操作加一即可，回溯的时候统计操作数即可

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 2e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
PII a[N];
int res;
int dfs(int u, int fa) {
    int s = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue ;        
        s += dfs(j, u);
    }
    if (s >= a[u].x) return min(s, a[u].y);
    else {
        res ++;
        return a[u].y;
    }  
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int T;
    cin >> T;
    while (T -- ) {
        cin >> n;
        for (int i = 1; i <= n; i ++) h[i] = - 1;
        for (int i = 2; i <= n; i ++) {
            int x; cin >> x;
            add(x, i), add(i, x);
        }
        for (int i = 1; i <= n; i ++) cin >> a[i].x >> a[i].y;
        res = 0;
        dfs(1, 0);

        cout << res << '\n';
    }
    return 0;
}

E. Keshi in Search of AmShZ

题意

给你一个$n$个点$m$条边的有向图，一开始你在$1$号点，每次你有两种操作：

1. 任选一条边将他删除掉
2. 走一步，但是是随机走无法规定方向

问你从$1$号点走到$n$号点最坏情况下通过最优操作需要操作多少次

思路

• $dp$，最短路

? 首先我们设$dis{t}_u$: 从点$u$走到点$n$的最少操作次数，假设对于某个点$u$，它的直接后继有$a_1,a_2,...,a_k$这些点且$dis{t}_{a_1}>dis{t}_{a_2}>...>dis{t}_{a_k}$，那么对于$u$来说选择$a_k$的的花费就是$k$，因为要将$a_{[1,k?1]}$都删掉并且走到$a_k$，对于选择$a_2$的花费是$2$，需要将$a_1$删掉并且走到$a_2$，由于$a_{[3,k]}$的权值都小于$a_2$因此最坏情况下考虑只会走到$a_2$，因此对于某个点$u$的最优解就是$dis{t}_u=min(dis{t}_u,dis{t}_k+大于dis{t}_k的后记结点数)k\in (后继节点)$

? 显然我们可以反向建图倒着$dp$，设$cn{t}_u:为u的后继结点个数$，之后我们可以跑一个$dijkstra$，，由于每次都是取出当前$dist$最小的数，假设取的为$u$则对于它的后继$v$如果更新完就要将$cnt[v]$–，这样每次更新的时候$cnt$中寸的恰好是大于某个$dist$的后继节点的个数，因此跑一遍$dijkstra$的过程就做完了我们的$dp$

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 2e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N], cnt[N];
int dist[N];
bool st[N];
void dijkstra() {
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    memset(dist, 0x3f, sizeof dist);
    dist[n] = 0;
    pq.push({0, n});
    while (pq.size()) {
        auto t = pq.top(); pq.pop();
        if (st[t.y]) continue ;
        st[t.y] = true;
        for (int i = h[t.y]; ~i; i = ne[i]) {
            int j = e[i];
            dist[j] = min(dist[j], t.x + cnt[j]);
            cnt[j] --;
            pq.push({dist[j], j});
        }
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i ++) {
        int x, y; cin >> x >> y;
        add(y, x), cnt[x] ++;
    }
    dijkstra();
    cout << dist[1] << '\n';
    return 0;
}