Educational Codeforces Round 143 (Rated for Div. 2)

Author：我不会玩锐雯
发布时间：April 19, 2023
104views
No comments
16641字数
Categories： ACM技能点

比赛链接：https://codeforces.com/contest/1795

A. Two Towers

题意：给定两个栈，每个栈中有若干红色或蓝色方块。在两个栈之间移动方块，使得每个栈中任意两个相邻方块的颜色都不一样。问给出的情况是否有解？

解法：先把所有的方块移到一个栈中，若相邻方块颜色相同的位置不超过一次则有解。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T = 1;
int n, m;
char s[MAXN], t[MAXN];
void solve() {
    scanf("%d%d", &n, &m);
    scanf("%s%s", s, t);

    int cnt = 0;
    for(int i = 1; i < n; i++) {
        if(s[i] == s[i - 1]) cnt++;
    }
    if(t[m - 1] == s[n - 1]) cnt++;
    for(int i = m - 2; i >= 0; i--) {
        if(t[i] == t[i + 1]) cnt++;
    }

    if(cnt <= 1) puts("YES");
    else puts("NO");
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

B. Ideal Point

题意：给定若干个区间，问能否删除一些区间使得数字$k$在区间中出现最多次。

解法：限制了不超过50，可以直接删除所有不包含数字$k$的区间，然后暴力判断是否出现了最多次。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T = 1;
int n, k;
int l, r;
int a[MAXN];
void solve() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= 50; i++) a[i] = 0;
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &l, &r);
        if(l <= k && k <= r) {
            for(int j = l; j <= r; j++) a[j]++;
        }
    }

    for(int i = 1; i <= 50; i++) {
        if(i == k) continue;
        if(a[i] == a[k]) {
            puts("NO");
            return;
        }
    }
    puts("YES");
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

C. Tea Tasting

题意：给定$n$杯茶，每杯茶$a_i$毫升。给定$n$个人，第$i$个人每次喝茶$b_i$毫升，若茶不足$b_i$毫升则会喝完这杯茶。第$i$杯茶从第$i$个人开始依次往后喝，直到最后一个人或者这杯茶被喝完。问每个人最后喝了多少茶？

解法：很容易得到一个$O(n^2)$的做法：枚举每杯茶能被哪些人喝，将贡献记录到对应的人即可。下面进行优化，注意是依次往后喝，可以对$b_i$做一次前缀和记为$sum_i$。然后找到一个最小的$j$满足$sum_j - sum_{i-1} \ge a_i$，转换一下这个不等式得到$sum_j \ge a_i + sum_{i-1}$，通过二分查找可以很快的求得下标$j$。这意味着区间$[i,j]$中的人喝到了第$i$杯茶，其中区间$[i,j-1]$中的人喝了他们上限的茶，最后一个人$j$喝了仅剩的茶。可以维护一个$cnt_i$表示第$i$个人喝了几次他们上限的茶，维护一个$ans_i$表示第$i$个人喝了多少仅剩的茶，注意这里维护的一个是次数一个是总量。那么每个人喝的茶为：$cnt_i \times b_i + ans_i$，最终复杂度为$O(n \log n)$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T = 1;
int n;
LL a[MAXN], b[MAXN];
LL cnt[MAXN], ans[MAXN];
void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &b[i]);
        b[i] += b[i - 1];
        cnt[i] = ans[i] = 0;
    }

    for(int i = 1; i <= n; i++) {
        ///第i杯茶被区间[i,r]的人喝了
        int r = lower_bound(b + 1, b + 1 + n, a[i] + b[i - 1]) - b;
        cnt[i]++;
        cnt[r]--;
        ans[r] += a[i] - (b[r - 1] - b[i - 1]);
    }

    for(int i = 1; i <= n; i++) {
        cnt[i] += cnt[i - 1];
        printf("%lld ", cnt[i] * (b[i] - b[i - 1]) + ans[i]);
    }
    putchar(10);
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

D. Triangle Coloring

题意：给定$n$个顶点三元组，每个三元组中的顶点两两建立有正权值的边。现在把每个顶点染成红色或蓝色，要求每个顶点只有一种颜色且红、蓝色顶点的数量相等。定义染色权重为连接不同颜色顶点的边的权值之和。求有多少种染色方式能获得最大的染色权重。

解法：对于每个三元组只有两种染色模式。第一种模式三个顶点染同样的颜色，权重为0。第二种模式其中一个顶点的颜色和另外两个顶点的颜色不同，权重为该顶点边的权值之和。要使染色的权重最大，则每个三元组都应该选择第二种染色模式。

那现在我们可以选出一半的三元组染成红色有两个顶点，另一半的三元组染成蓝色有两个顶点即可满足顶点数量相等的要求。接着让每个三元组的染色方式总是贡献权值最大的两条边，定义$c_i$表示第$i$个三元组的染色方式。

$c_i = 3$，三条边权值相等。
$c_i = 2$，两条边权值相等且小于第三边。
$c_i = 1$，两条边权值相等且大于第三边，三条边权值都不相等。

最终的方案数为：$C_{n}^{n/2} \prod \limits_{i=1}^{n} c_i$

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
LL a[MAXN];
int M = 998244353;
LL fact[MAXN];
LL inv[MAXN];
LL fast_power(LL a, LL n, LL p) {
    LL ans = 1;
    a %= p;
    while(n) {
        if(n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}
void init() {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i % M;
    }

    inv[n] = fast_power(fact[n], M - 2, M);
    for (int i = n - 1 ; i >= 0; i--) {
        inv[i] = inv[i + 1] * (i + 1) % M;
    }
}
int main() {
    scanf("%d", &n);
    init();
    for(int i = 0; i < n; i++) scanf("%lld", &a[i]);

    LL ans = fact[n / 3] * inv[n / 6] % M * inv[n / 6] % M;
    for(int i = 0; i < n; i += 3) {
        if(a[i] == a[i + 1] && a[i] == a[i + 2]) {
            ans = ans * 3 % M;
            continue;
        }
        if(a[i] == a[i + 1] && a[i] < a[i + 2]) {
            ans = ans * 2 % M;
            continue;
        }
        if(a[i] == a[i + 2] && a[i] < a[i + 1]) {
            ans = ans * 2 % M;
            continue;
        }
        if(a[i + 2] == a[i + 1] && a[i + 2] < a[i]) {
            ans = ans * 2 % M;
            continue;
        }
    }

    printf("%lld\n", ans);
    return 0;
}

E. Explosions?

题意：有$n$个怪物，每个怪物的生命值为$h_i$。基础攻击每次消耗1MP，对目标造成1点伤害。魔法攻击消耗 $x$ MP，对目标造成$x$点伤害且如果目标死亡还会造成连锁伤害。连锁伤害：若目标当前有$h_i$点生命值且死于魔法攻击，则该目标对相邻位置的怪物造成$h_i-1$的伤害，连锁伤害会传递。现在先使用若干次基础攻击再使用一次魔法攻击来消灭所有的怪物，求需要消耗的最少MP。

解法：

造成的连锁伤害总是越多越好，因此最少的MP = 总的生命值 - 最大的连锁伤害。
需要使用一次魔法攻击来消灭所有的怪物，则需要先使用基础攻击使魔法攻击的目标怪物$p$左侧是严格递增的、右侧是严格递减的（在忽略首尾的0之后）。
考虑左边的部分，对于怪物$p$总是会选择使用$h_p$的魔法攻击，这样恰好击杀并产生连锁伤害。
- $h_{p-i} \gt h_p-i$，可以预先使用基础攻击使$h{p-i}$降为$h_p-i$满足连锁伤害的条件。
- $h_{p-i} \le h_p-i$，这时造成的伤害已经跟$p$没有关系了。
定义$dp_i$表示消灭第$i$只怪物左边能产生的连锁伤害的最大值，则有$dp_i = dp_j + sum$，其中$j$是最右边无法满足$h_j$恰好递减1的下标，$sum$是可以连续递减部分的总和。想要快速的求出下标$j$，单调栈是非常适合的数据结构。
右边和左边是对称的处理方式。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T = 1;
int n;
int h[MAXN];
LL dpL[MAXN], dpR[MAXN];
struct node {
    int id;
    int val;
};
void solveLeft() {
    dpL[0] = 0;
    stack<node> st;
    for(int i = 1; i <= n; i++) {
        node now = node {i, h[i] - i};
        while(!st.empty() && st.top().val > now.val) st.pop();

        int l = max(0, i - h[i]);//l是不能直接由i影响的最大下标
        if(!st.empty()) l = max(l, st.top().id);
        LL len = i - l;//等差下降的长度
        dpL[i] = h[i] * len - len * (len - 1) / 2;//等差下降部分的贡献
        if(l >= 1 && len < h[i]) dpL[i] += dpL[l];//还能往左走

        st.push(now);
    }
}
void solveRight() {
    dpR[n + 1] = 0;
    stack<node> st;
    for(int i = n; i > 0; i--) {
        node now = node {i, h[i] - (n - i + 1)};
        while(!st.empty() && st.top().val > now.val) st.pop();

        int r = min(n + 1, i + h[i]);
        if(!st.empty()) r = min(r, st.top().id);
        LL len = r - i;
        dpR[i] =  h[i] * len - len * (len - 1) / 2;
        if(r <= n && len < h[i]) dpR[i] += dpR[r];

        st.push(now);
    }
}
void solve() {
    scanf("%d", &n);
    LL sum = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &h[i]);
        sum += h[i];
    }

    solveLeft();
    solveRight();

    LL ans = (LL) INF * INF;
    for(int i = 1; i <= n; i++) {
        ans = min(ans, sum - dpL[i] - dpR[i] + h[i] * 2);
    }
    printf("%lld\n", ans);
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

F. Blocking Chips

题意：给定一棵大小为 $1 \le n \le 2 \cdot 10^5$ 的树和若干个起点，每个起点依次进行移动，访问过的结点不能再次访问，问总共最多能移动多少次？

解法：可以移动的步数具有单调性，可以二分求解能移动的最大的总步数。给定总步数，可以求得每个起点需要移动的步数。随机选定根结点，从层级较深的起点开始考虑。如果往子结点移动可以满足条件则优先往子结点移动，否则移动一步到父结点，问题转移到父结点上。对于每个结点，往子结点移动是否可以满足条件，进行一次DFS预处理即可。

优先队列写法，较复杂

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T = 1;
int n, k;
int a[MAXN];
int u, v;
struct node {
    int id;
    int root;//根结点id
    int level;//层级
    bool colored;//是否已染色
    vector<int> edge;//边
    int aim;//需要移动的步数
    int maxlen;//可访问的孩子的最长链
    bool lazy;//标记maxlen是否已失效

    bool operator <(const node& a)const {
        return level < a.level;
    }
} tree[MAXN];

void dfs(int id, int root) {
    tree[id].root = root;
    tree[id].level = tree[root].level + 1;

    tree[id].maxlen = 0;
    int sonSize = tree[id].edge.size();
    for(int i = 0; i < sonSize; i++) {
        int sonId = tree[id].edge[i];
        if(sonId == root) continue;
        if(tree[sonId].lazy) dfs(sonId, id);
        if(!tree[sonId].colored) { //初始化maxlen
            tree[id].maxlen = max(tree[id].maxlen, tree[sonId].maxlen + 1);
        }
    }
    tree[id].lazy = false;
}
void initTree(int step) {
    tree[0].colored = true;
    for(int i = 1; i <= n; i++) {
        tree[i].id = i;
        tree[i].level = 0;
        tree[i].colored = false;
        tree[i].aim = 0;
        tree[i].lazy = true;
    }
    for(int i = 1; i <= k; i++) {
        tree[a[i]].colored = true;
        tree[a[i]].aim = step / k;
        if(step % k >= i) tree[a[i]].aim++;
    }
    dfs(1, 0);
}

struct qnode {
    int id, level;

    bool operator <(const qnode& a)const {
        if(level != a.level)return level < a.level;
        return id > a.id;
    }
};
priority_queue<qnode> pq;
void up(int id) {
    while(!tree[id].lazy) {
        tree[id].lazy = true;
        id = tree[id].root;
    }
}
void gotoRoot(int nowId) {
    int rootId = tree[nowId].root;
    tree[rootId].colored = true;
    tree[rootId].aim = tree[nowId].aim - 1;
    up(rootId);
}
bool check(int step) {
    initTree(step);
    while(!pq.empty()) pq.pop();
    for(int i = 1; i <= k; i++) pq.push(qnode {a[i], tree[a[i]].level});
    while(!pq.empty()) {
        int nowId = pq.top().id;
        pq.pop();
        if(tree[nowId].lazy) dfs(nowId, tree[nowId].root);//当前结点需要更新
        if(tree[nowId].maxlen >= tree[nowId].aim) continue;//当前点可以向下走

        int rootId = tree[nowId].root;
        if(tree[rootId].colored) return false;//父结点已经被访问了
        gotoRoot(nowId);//往父结点走一步
        pq.push(qnode {rootId, tree[rootId].level});
    }
    return true;
}
int erfen() {
    int l = 0, r = n;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}
void solve() {
    scanf("%d", &n);
    for(int i = 0; i <= n; i++) tree[i].edge.clear();
    for(int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        tree[u].edge.push_back(v);
        tree[v].edge.push_back(u);
    }

    scanf("%d", &k);
    for(int i = 1; i <= k; i++) scanf("%d", &a[i]);

    printf("%d\n", erfen());
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

递归写法

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T = 1;
int n, k;
int a[MAXN];
vector<int> edge[MAXN];

int req[MAXN];//需要移动的步数
bool use[MAXN];//是否被使用
int maxlen[MAXN];//子结点最远距离
bool dfs(int id, int root) {
    int sonSize = edge[id].size();
    for(int i = 0; i < sonSize; i++) {
        int sonId = edge[id][i];
        if(sonId == root) continue;
        if(!dfs(sonId, id)) return false;//子结点无法满足条件
        if(!use[sonId]) maxlen[id] = max(maxlen[id], maxlen[sonId] + 1);
    }

    if(maxlen[id] >= req[id]) return true;//可以往子结点走
    if(root == 0 || use[root]) return false;//父结点已经被访问了
    use[root] = true;//往父结点走
    req[root] = req[id] - 1;
    return true;
}
bool check(int step) {
    for(int i = 0; i <= n; i++) {
        use[i] = false;
        req[i] = maxlen[i] = 0;
    }
    for(int i = 1; i <= k; i++) {
        req[a[i]] = step / k;
        if(step % k >= i) req[a[i]]++;
        use[a[i]] = true;
    }
    return dfs(1, 0);
}
int erfen() {
    int l = 0, r = n;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}
void solve() {
    scanf("%d", &n);
    for(int i = 0; i <= n; i++) edge[i].clear();
    int u, v;
    for(int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    scanf("%d", &k);
    for(int i = 1; i <= k; i++) scanf("%d", &a[i]);

    printf("%d\n", erfen());
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

G. Removal Sequences

题意：给定一个简单无向图，不包含自环和重边。每个结点具有点权，只有当结点的点权等于结点的度数时才可以删除该结点。删除一个结点也会删除该结点的边。保证至少存在一个合法的结点序列可以删除所有的结点。如果在两个不同的结点序列中，结点 $x$ 与结点 $y$ 的相对位置不同，则称这样的结点对是好的。求给定的无向图中有多少好的结点对？

解法：

保证至少存在一个合法的序列，那么最初必然存在这样的一个结点集合 $s$ 。集合 $s$ 中结点的权值都等于结点的度数，也就是不用做任何操作就满足可删除的条件。且集合中任意两个结点不相邻，因为任意结点相邻在删除一个结点后都将导致另一个结点无法删除。
在删除集合中的一个或多个结点后可能会导致某个结点变得可删除，换句话说：有些结点要能删除必须先删除某些特定的结点。从这里可以看出，虽然是无向图，但是删除的顺序并不是那么无向。
建立有向图，如果结点 $u$ 从结点 $v$ 出发可达，则表示要删除结点 $u$ ，必须先删除结点 $v$ 。可以广搜一遍无向图来建立该有向图。
有向图中结点 $u$ 和结点 $v$ 不可达，则该顶点对是好的。问题到这转换成了无环有向图中可达顶点对的数量。
一个朴素的方案是为每个结点维护一个bitset，表示从哪些结点出发可到达当前结点，广搜来传播更新标志位。这个方案时间复杂度是$O(n + m)$的，问题在于$10^{10}$个标志位需要1G的内存。一个有趣的优化是这样的，分批计算。每一次只计算64个结点从哪些结点是可达的，优化后的时间复杂度是$O(\frac{n}{64} \times (n + m))$的，但内存问题得到了解决，换而言之这是一个时间换空间的方案。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T = 1;
int n, m;
int a[MAXN];

int u, v;
vector<vector<int>> node;

bool visit[MAXN];
int degree[MAXN];
queue<int> q;
vector<pair<int, int>> edge;//有向边
unsigned LL mask[MAXN];

void init() {
    while(!q.empty()) {
        q.pop();
    }
    for(int i = 0; i < n; i++) {
        mask[i] = 0;
        visit[i] = false;
        degree[i] = node[i].size();
        if(degree[i] == a[i]) q.push(i);
    }
    edge.clear();
}
void solve() {
    scanf("%d%d", &n, &m);
    node.clear();
    node.resize(n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        --u;
        --v;
        node[u].push_back(v);
        node[v].push_back(u);
    }

    init();
    while(!q.empty()) {//建立有向图
        int u = q.front();
        q.pop();
        visit[u] = true;
        for(int v : node[u]) {
            if(visit[v]) continue;
            --degree[v];
            edge.push_back({u, v});
            if(degree[v] == a[v]) q.push(v);
        }
    }

    LL ans = n * 1LL * (n + 1) / 2;//总的顶点对数
    //mask[i] 表示在这一轮循环中，能到达第 i 个顶点的顶点数
    for(int l = 0; l < n; l += 64) {
        int r = min(n, l + 64);
        for(int i = l; i < r; i++) mask[i] = ((unsigned LL) 1) << (i - l);
        for(int i = edge.size() - 1; i >= 0; i--) {//逆序遍历
            mask[edge[i].first] |= mask[edge[i].second];
        }
        for(int i = 0; i < n; i++) {
            ans -= __builtin_popcountll(mask[i]);
            mask[i] = 0;
        }
    }

    printf("%lld\n", ans);
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

版权属于：小影
本文链接：http://kindkidll.com/index.php/archives/215/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

Last modification：April 19th, 2023 at 10:03 am

如果觉得我的文章对你有用，请随意赞赏

Educational Codeforces Round 143 (Rated for Div. 2)

我不会玩锐雯 • 2023 年 04 月 19 日

比赛链接：https://codeforces.com/contest/1795

A. Two Towers

解法：先把所有的方块移到一个栈中，若相邻方块颜色相同的位置不超过一次则有解。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T = 1;
int n, m;
char s[MAXN], t[MAXN];
void solve() {
    scanf("%d%d", &n, &m);
    scanf("%s%s", s, t);

    int cnt = 0;
    for(int i = 1; i < n; i++) {
        if(s[i] == s[i - 1]) cnt++;
    }
    if(t[m - 1] == s[n - 1]) cnt++;
    for(int i = m - 2; i >= 0; i--) {
        if(t[i] == t[i + 1]) cnt++;
    }

    if(cnt <= 1) puts("YES");
    else puts("NO");
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

B. Ideal Point

题意：给定若干个区间，问能否删除一些区间使得数字$k$在区间中出现最多次。

解法：限制了不超过50，可以直接删除所有不包含数字$k$的区间，然后暴力判断是否出现了最多次。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T = 1;
int n, k;
int l, r;
int a[MAXN];
void solve() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= 50; i++) a[i] = 0;
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &l, &r);
        if(l <= k && k <= r) {
            for(int j = l; j <= r; j++) a[j]++;
        }
    }

    for(int i = 1; i <= 50; i++) {
        if(i == k) continue;
        if(a[i] == a[k]) {
            puts("NO");
            return;
        }
    }
    puts("YES");
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

C. Tea Tasting

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T = 1;
int n;
LL a[MAXN], b[MAXN];
LL cnt[MAXN], ans[MAXN];
void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &b[i]);
        b[i] += b[i - 1];
        cnt[i] = ans[i] = 0;
    }

    for(int i = 1; i <= n; i++) {
        ///第i杯茶被区间[i,r]的人喝了
        int r = lower_bound(b + 1, b + 1 + n, a[i] + b[i - 1]) - b;
        cnt[i]++;
        cnt[r]--;
        ans[r] += a[i] - (b[r - 1] - b[i - 1]);
    }

    for(int i = 1; i <= n; i++) {
        cnt[i] += cnt[i - 1];
        printf("%lld ", cnt[i] * (b[i] - b[i - 1]) + ans[i]);
    }
    putchar(10);
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

D. Triangle Coloring

$c_i = 3$，三条边权值相等。
$c_i = 2$，两条边权值相等且小于第三边。
$c_i = 1$，两条边权值相等且大于第三边，三条边权值都不相等。

最终的方案数为：$C_{n}^{n/2} \prod \limits_{i=1}^{n} c_i$

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
LL a[MAXN];
int M = 998244353;
LL fact[MAXN];
LL inv[MAXN];
LL fast_power(LL a, LL n, LL p) {
    LL ans = 1;
    a %= p;
    while(n) {
        if(n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}
void init() {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i % M;
    }

    inv[n] = fast_power(fact[n], M - 2, M);
    for (int i = n - 1 ; i >= 0; i--) {
        inv[i] = inv[i + 1] * (i + 1) % M;
    }
}
int main() {
    scanf("%d", &n);
    init();
    for(int i = 0; i < n; i++) scanf("%lld", &a[i]);

    LL ans = fact[n / 3] * inv[n / 6] % M * inv[n / 6] % M;
    for(int i = 0; i < n; i += 3) {
        if(a[i] == a[i + 1] && a[i] == a[i + 2]) {
            ans = ans * 3 % M;
            continue;
        }
        if(a[i] == a[i + 1] && a[i] < a[i + 2]) {
            ans = ans * 2 % M;
            continue;
        }
        if(a[i] == a[i + 2] && a[i] < a[i + 1]) {
            ans = ans * 2 % M;
            continue;
        }
        if(a[i + 2] == a[i + 1] && a[i + 2] < a[i]) {
            ans = ans * 2 % M;
            continue;
        }
    }

    printf("%lld\n", ans);
    return 0;
}

E. Explosions?

解法：

造成的连锁伤害总是越多越好，因此最少的MP = 总的生命值 - 最大的连锁伤害。
需要使用一次魔法攻击来消灭所有的怪物，则需要先使用基础攻击使魔法攻击的目标怪物$p$左侧是严格递增的、右侧是严格递减的（在忽略首尾的0之后）。
考虑左边的部分，对于怪物$p$总是会选择使用$h_p$的魔法攻击，这样恰好击杀并产生连锁伤害。
- $h_{p-i} \gt h_p-i$，可以预先使用基础攻击使$h{p-i}$降为$h_p-i$满足连锁伤害的条件。
- $h_{p-i} \le h_p-i$，这时造成的伤害已经跟$p$没有关系了。
定义$dp_i$表示消灭第$i$只怪物左边能产生的连锁伤害的最大值，则有$dp_i = dp_j + sum$，其中$j$是最右边无法满足$h_j$恰好递减1的下标，$sum$是可以连续递减部分的总和。想要快速的求出下标$j$，单调栈是非常适合的数据结构。
右边和左边是对称的处理方式。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T = 1;
int n;
int h[MAXN];
LL dpL[MAXN], dpR[MAXN];
struct node {
    int id;
    int val;
};
void solveLeft() {
    dpL[0] = 0;
    stack<node> st;
    for(int i = 1; i <= n; i++) {
        node now = node {i, h[i] - i};
        while(!st.empty() && st.top().val > now.val) st.pop();

        int l = max(0, i - h[i]);//l是不能直接由i影响的最大下标
        if(!st.empty()) l = max(l, st.top().id);
        LL len = i - l;//等差下降的长度
        dpL[i] = h[i] * len - len * (len - 1) / 2;//等差下降部分的贡献
        if(l >= 1 && len < h[i]) dpL[i] += dpL[l];//还能往左走

        st.push(now);
    }
}
void solveRight() {
    dpR[n + 1] = 0;
    stack<node> st;
    for(int i = n; i > 0; i--) {
        node now = node {i, h[i] - (n - i + 1)};
        while(!st.empty() && st.top().val > now.val) st.pop();

        int r = min(n + 1, i + h[i]);
        if(!st.empty()) r = min(r, st.top().id);
        LL len = r - i;
        dpR[i] =  h[i] * len - len * (len - 1) / 2;
        if(r <= n && len < h[i]) dpR[i] += dpR[r];

        st.push(now);
    }
}
void solve() {
    scanf("%d", &n);
    LL sum = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &h[i]);
        sum += h[i];
    }

    solveLeft();
    solveRight();

    LL ans = (LL) INF * INF;
    for(int i = 1; i <= n; i++) {
        ans = min(ans, sum - dpL[i] - dpR[i] + h[i] * 2);
    }
    printf("%lld\n", ans);
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

F. Blocking Chips

题意：给定一棵大小为 $1 \le n \le 2 \cdot 10^5$ 的树和若干个起点，每个起点依次进行移动，访问过的结点不能再次访问，问总共最多能移动多少次？

优先队列写法，较复杂

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T = 1;
int n, k;
int a[MAXN];
int u, v;
struct node {
    int id;
    int root;//根结点id
    int level;//层级
    bool colored;//是否已染色
    vector<int> edge;//边
    int aim;//需要移动的步数
    int maxlen;//可访问的孩子的最长链
    bool lazy;//标记maxlen是否已失效

    bool operator <(const node& a)const {
        return level < a.level;
    }
} tree[MAXN];

void dfs(int id, int root) {
    tree[id].root = root;
    tree[id].level = tree[root].level + 1;

    tree[id].maxlen = 0;
    int sonSize = tree[id].edge.size();
    for(int i = 0; i < sonSize; i++) {
        int sonId = tree[id].edge[i];
        if(sonId == root) continue;
        if(tree[sonId].lazy) dfs(sonId, id);
        if(!tree[sonId].colored) { //初始化maxlen
            tree[id].maxlen = max(tree[id].maxlen, tree[sonId].maxlen + 1);
        }
    }
    tree[id].lazy = false;
}
void initTree(int step) {
    tree[0].colored = true;
    for(int i = 1; i <= n; i++) {
        tree[i].id = i;
        tree[i].level = 0;
        tree[i].colored = false;
        tree[i].aim = 0;
        tree[i].lazy = true;
    }
    for(int i = 1; i <= k; i++) {
        tree[a[i]].colored = true;
        tree[a[i]].aim = step / k;
        if(step % k >= i) tree[a[i]].aim++;
    }
    dfs(1, 0);
}

struct qnode {
    int id, level;

    bool operator <(const qnode& a)const {
        if(level != a.level)return level < a.level;
        return id > a.id;
    }
};
priority_queue<qnode> pq;
void up(int id) {
    while(!tree[id].lazy) {
        tree[id].lazy = true;
        id = tree[id].root;
    }
}
void gotoRoot(int nowId) {
    int rootId = tree[nowId].root;
    tree[rootId].colored = true;
    tree[rootId].aim = tree[nowId].aim - 1;
    up(rootId);
}
bool check(int step) {
    initTree(step);
    while(!pq.empty()) pq.pop();
    for(int i = 1; i <= k; i++) pq.push(qnode {a[i], tree[a[i]].level});
    while(!pq.empty()) {
        int nowId = pq.top().id;
        pq.pop();
        if(tree[nowId].lazy) dfs(nowId, tree[nowId].root);//当前结点需要更新
        if(tree[nowId].maxlen >= tree[nowId].aim) continue;//当前点可以向下走

        int rootId = tree[nowId].root;
        if(tree[rootId].colored) return false;//父结点已经被访问了
        gotoRoot(nowId);//往父结点走一步
        pq.push(qnode {rootId, tree[rootId].level});
    }
    return true;
}
int erfen() {
    int l = 0, r = n;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}
void solve() {
    scanf("%d", &n);
    for(int i = 0; i <= n; i++) tree[i].edge.clear();
    for(int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        tree[u].edge.push_back(v);
        tree[v].edge.push_back(u);
    }

    scanf("%d", &k);
    for(int i = 1; i <= k; i++) scanf("%d", &a[i]);

    printf("%d\n", erfen());
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

递归写法

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T = 1;
int n, k;
int a[MAXN];
vector<int> edge[MAXN];

int req[MAXN];//需要移动的步数
bool use[MAXN];//是否被使用
int maxlen[MAXN];//子结点最远距离
bool dfs(int id, int root) {
    int sonSize = edge[id].size();
    for(int i = 0; i < sonSize; i++) {
        int sonId = edge[id][i];
        if(sonId == root) continue;
        if(!dfs(sonId, id)) return false;//子结点无法满足条件
        if(!use[sonId]) maxlen[id] = max(maxlen[id], maxlen[sonId] + 1);
    }

    if(maxlen[id] >= req[id]) return true;//可以往子结点走
    if(root == 0 || use[root]) return false;//父结点已经被访问了
    use[root] = true;//往父结点走
    req[root] = req[id] - 1;
    return true;
}
bool check(int step) {
    for(int i = 0; i <= n; i++) {
        use[i] = false;
        req[i] = maxlen[i] = 0;
    }
    for(int i = 1; i <= k; i++) {
        req[a[i]] = step / k;
        if(step % k >= i) req[a[i]]++;
        use[a[i]] = true;
    }
    return dfs(1, 0);
}
int erfen() {
    int l = 0, r = n;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}
void solve() {
    scanf("%d", &n);
    for(int i = 0; i <= n; i++) edge[i].clear();
    int u, v;
    for(int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    scanf("%d", &k);
    for(int i = 1; i <= k; i++) scanf("%d", &a[i]);

    printf("%d\n", erfen());
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

G. Removal Sequences

解法：

保证至少存在一个合法的序列，那么最初必然存在这样的一个结点集合 $s$ 。集合 $s$ 中结点的权值都等于结点的度数，也就是不用做任何操作就满足可删除的条件。且集合中任意两个结点不相邻，因为任意结点相邻在删除一个结点后都将导致另一个结点无法删除。
在删除集合中的一个或多个结点后可能会导致某个结点变得可删除，换句话说：有些结点要能删除必须先删除某些特定的结点。从这里可以看出，虽然是无向图，但是删除的顺序并不是那么无向。
建立有向图，如果结点 $u$ 从结点 $v$ 出发可达，则表示要删除结点 $u$ ，必须先删除结点 $v$ 。可以广搜一遍无向图来建立该有向图。
有向图中结点 $u$ 和结点 $v$ 不可达，则该顶点对是好的。问题到这转换成了无环有向图中可达顶点对的数量。
一个朴素的方案是为每个结点维护一个bitset，表示从哪些结点出发可到达当前结点，广搜来传播更新标志位。这个方案时间复杂度是$O(n + m)$的，问题在于$10^{10}$个标志位需要1G的内存。一个有趣的优化是这样的，分批计算。每一次只计算64个结点从哪些结点是可达的，优化后的时间复杂度是$O(\frac{n}{64} \times (n + m))$的，但内存问题得到了解决，换而言之这是一个时间换空间的方案。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T = 1;
int n, m;
int a[MAXN];

int u, v;
vector<vector<int>> node;

bool visit[MAXN];
int degree[MAXN];
queue<int> q;
vector<pair<int, int>> edge;//有向边
unsigned LL mask[MAXN];

void init() {
    while(!q.empty()) {
        q.pop();
    }
    for(int i = 0; i < n; i++) {
        mask[i] = 0;
        visit[i] = false;
        degree[i] = node[i].size();
        if(degree[i] == a[i]) q.push(i);
    }
    edge.clear();
}
void solve() {
    scanf("%d%d", &n, &m);
    node.clear();
    node.resize(n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        --u;
        --v;
        node[u].push_back(v);
        node[v].push_back(u);
    }

    init();
    while(!q.empty()) {//建立有向图
        int u = q.front();
        q.pop();
        visit[u] = true;
        for(int v : node[u]) {
            if(visit[v]) continue;
            --degree[v];
            edge.push_back({u, v});
            if(degree[v] == a[v]) q.push(v);
        }
    }

    LL ans = n * 1LL * (n + 1) / 2;//总的顶点对数
    //mask[i] 表示在这一轮循环中，能到达第 i 个顶点的顶点数
    for(int l = 0; l < n; l += 64) {
        int r = min(n, l + 64);
        for(int i = l; i < r; i++) mask[i] = ((unsigned LL) 1) << (i - l);
        for(int i = edge.size() - 1; i >= 0; i--) {//逆序遍历
            mask[edge[i].first] |= mask[edge[i].second];
        }
        for(int i = 0; i < n; i++) {
            ans -= __builtin_popcountll(mask[i]);
            mask[i] = 0;
        }
    }

    printf("%lld\n", ans);
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

版权属于：小影
本文链接：http://kindkidll.com/index.php/archives/215/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

Educational Codeforces Round 143 (Rated for Div. 2)

A. Two Towers

B. Ideal Point

C. Tea Tasting

D. Triangle Coloring

E. Explosions?

F. Blocking Chips

G. Removal Sequences

Leave a Comment Cancel reply

【每日一题】4月7日树

handsome主题修改记录

链式前向星

红黑树入门

【每日一题】4月6日数码

牛客小白月赛26

2021牛客寒假算法基础集训营3

牛客小白月赛47

2020年4月蓝桥杯官方B组省赛模拟赛

单例模式

Educational Codeforces Round 143 (Rated for Div. 2)

A. Two Towers

B. Ideal Point

C. Tea Tasting

D. Triangle Coloring

E. Explosions?

F. Blocking Chips

G. Removal Sequences