Codeforces Round 791 (Div. 2) 过题

Codeforces Round 791 (Div. 2) 过题

https://codeforces.com/contest/1679

A. AvtoBus

题意

汽车的轮胎可能有4个或者6个，对于给定的每个n（n表示轮胎数量），给出汽车的数量的极小值和极大值，不可能就输出-1 ### 题解

纯纯的签到题 平板上写了个 // Created on iPad.

#include <iostream>
using namespace std;
#define int long long
signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        if (n % 2 == 1)
        {
            cout << -1 << endl;
            continue;
        }
        n /= 2; // n = 2a+3b
        int ans = 0;
        if (n % 2 == 1)
            n -= 3, ans++;
        if (n < 0)
        {
            cout << -1 << endl;
            continue;
        }
        cout << ans + n / 6 * 2 + n % 6 / 2 << " ";
        cout << ans + n / 2 << endl;
    }
}

AC了。

B. Stone Age Problem

题意

题意大概是：给定一个 长度为 n 的 数组 a 和 q 次操作。每次操作可能为

  1. 把 数组a 中的一个元素的值 变成 x 。
  2. 把 数组 a 的所有元素变成 x 。
  3. 询问 数组 a 的所有元素和 sum(a[1∼n]) 。

题解

我们用 布尔变量 all 和 数值 变量 v 来表示 "数组 a 是否全部被变成 数值 v "。如果 数组 全部被 变为 v 了，我们再用 一个映射 d[i] 来表示， 在 all 为真的情况下，a[i] 的 数值被 操作 1 变为了 多少。之后就是模拟写代码了。

C. Rooks Defenders

题意

问题被转化为: 给定一个元素全为 0 的二维数组 a[][] ，和 q 次操作，每次操作可能为:

  1. 给定 x, y ，将 a[x][y] 变成 1 (题目保证在操作之前 a[x][y] 是 0 ).
  2. 给定 x, y ，将 a[x][y] 变成 0 （题目保证在操作之前 a[x][y] 是 1 ）.
  3. 给定 x_{1}, y_{1}, x_{2}, y_{2} ，询问是否有 " a 的 x_{1} x_{2} 行 每行都至少存在一个 1 " 或 " a 的 y_{1} y_{2} 列 每列都至少存在一个 1 " 。 这题本质上是 "单点值修改，区间和查询"，可以用树状数组。

题解

单点修改区间查询的问题。可以用树状数组/线段树维护某一段区间内多少行/列上有多少个车。

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5, INF = 0x3f3f3f3f;
struct Node{
    int l, r, v, sum;
}tr1[maxn * 4], tr2[maxn * 4];
int n, q;

void pushup(Node tr[], int u){
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(Node tr[], int u, int l, int r){
    tr[u] = {l, r};
    if (l == r) return;
    int mid = l + r >> 1;
    build(tr, u << 1, l, mid);
    build(tr, u << 1 | 1, mid + 1, r);
}

int query(Node tr[], int u, int l, int r){
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if (l <= mid) sum += query(tr, u << 1, l, r);
    if (r > mid) sum += query(tr, u << 1 | 1, l, r);
    return sum;
}

void modify(Node tr[], int u, int x, int v){
    if (tr[u].l == tr[u].r){
        tr[u].v += v;
        tr[u].sum = (tr[u].v > 0);
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) modify(tr, u << 1, x, v);
    else modify(tr, u << 1 | 1, x, v);
    pushup(tr, u);
}

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> n >> q;
    build(tr1, 1, 1, n), build(tr2, 1, 1, n);
    while(q--){
        int op;
        cin >> op;
        if (op == 1){
            int x, y;
            cin >> x >> y;
            modify(tr1, 1, x, 1);
            modify(tr2, 1, y, 1);
        }
        else if (op == 2){
            int x, y;
            cin >> x >> y;
            modify(tr1, 1, x, -1);
            modify(tr2, 1, y, -1);            
        }
        else{
            int x0, y0, x1, y1;
            cin >> x0 >> y0 >> x1 >> y1;
            if (query(tr1, 1, x0, x1) == x1 - x0 + 1 || query(tr2, 1, y0, y1) == y1 - y0 + 1)
                cout << "Yes" << '\n';
            else cout << "No" << '\n';
        }
    }

}

D. Toss a Coin to Your Graph...

题意

给出一个有向图，求图中所有长度为k的路径经过的点中最大的点权最小是多少。

题解

二分答案,每次都只用小于等于mid的边建图,然后判断图中是否有长度为k的路径或有环即可,可以用拓扑排序判环和DP

E. Typical Party in Dorm

题意

给出一个字符串,其中有些位置是?，每次询问给出一个集合,每个?的位置可以用集合中任意的字母代替产生很多不同的字符串,所有产生的串中回文串总数是多少?

题解

首先我们用类似马拉车算法的初始化方法给在字符之间插入一下#,以便我们直接枚举回文中心.

我们处理每个回文中心对于询问状态的贡献.

用状态压缩的方法表示询问中的字符集,我们枚举回文中心,然后处理对于每个回文中心每个回文半径至少需要哪些字母(状压表示)才能使当前的回文中心和回文半径合法(当然也可能怎样都不合法).这部分处理是O(n^2)的,然后用子集和DP处理一下就可以得到某个当前串对每个询问集合会产生多少贡献.

然后我们发现最后的结果不仅和集合中包含哪些字母有关,还和集合的大小有关,所以我们可以分别处理每个状态在不同集合大小情况下对答案的贡献,这样处理询问的时候就可以O(1)查询了. 总复杂度应该是O(17n^2)