AtCoder Beginner Contest 366

D.三维前缀和板子，预处理可以选择不容斥查询的时候只能容斥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

int a[N][N][N];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                cin >> a[i][j][k];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                a[i][j][k] += a[i][j][k - 1];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                a[i][j][k] += a[i][j - 1][k];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                a[i][j][k] += a[i - 1][j][k];
            }
        }
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int x1, x2, y1, y2, z1, z2;
        cin >> x1 >> x2 >> y1 >> y2 >> z1 >> z2;
        int res = a[x2][y2][z2] - a[x1 - 1][y2][z2] - a[x2][y1 - 1][z2] -
                  a[x2][y2][z1 - 1] + a[x1 - 1][y1 - 1][z2] +
                  a[x1 - 1][y2][z1 - 1] + a[x2][y1 - 1][z1 - 1] - a[x1 - 1][y1 - 1][z1 - 1];
        cout<<res<<endl;
    }
}


E.给你一个二维平面上的 NN 点 (x1,y1),(x2,y2),…,(xN,yN)(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N) 和一个非负整数 DD 。求 (x,y)(x, y) 使得 ∑i=1N(∣x−xi∣+∣y−yi∣)≤D\displaystyle \sum_{i=1}^N (|x-x_i|+|y-y_i|) \leq D 的整数对的个数。

Constraints

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 0≤D≤1060 \leq D \leq 10^6
  • −106≤xi,yi≤106-10^6 \leq x_i, y_i \leq 10^6
  • (xi,yi)≠(xj,yj)(x_i, y_i) \neq (x_j, y_j) for i≠ji \neq j.
  • All input values are integers.

Sol:考虑横纵坐标显然独立，根据数据范围我们可以枚举一维，快速查询另一维。我们需要快速得到的是一个一维的点到n个点的绝对值距离之和，这在曼哈顿距离专题是很典的东西，我们只需要提前计算前缀和，查询的时候二分即可。此时我们还需要处理另一维，同样也可以继续二分，显然绝对值求和这个式子关于y是凹函数，但这样需要讨论并且左右两次二分比较麻烦。

  • 对于求<=val的值的个数，如果val不大，我们可以先求等于val的数量，然后求一遍前缀和就可以了

左右两次二分的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
void solve() {
    cin >> n >> m;
    vector<int> vx(n + 1), vy(n + 1);
    for (int i = 1; i <= n; i++) cin >> vx[i] >> vy[i];
    //  deb(vx);
    // deb(vy);
    sort(alls(vx));
    sort(alls(vy));
    vector<int> prex(n + 1), sufx(n + 2), prey(n + 1), sufy(n + 2);
    for (int i = 1; i <= n; i++) {
        prex[i] += vx[i] + prex[i - 1];
        prey[i] += vy[i] + prey[i - 1];
    }
    for (int i = n; i >= 1; i--) {
        sufx[i] += vx[i] + sufx[i + 1];
        sufy[i] += vy[i] + sufy[i + 1];
    }
    deb(vx);
    deb(prex);
    deb(sufx);
    deb(vy);
    deb(prey);
    deb(sufy);
    int ans = 0;
    for (int x = -2e6; x <= 2e6; x++) {
        auto it = lower_bound(alls(vx), x);
        int tmp = 0;
        if (it == vx.end()) {
            tmp = n * x - prex[n];
        } else {
            int cnt = it - vx.begin() - 1;
            tmp = cnt * x - prex[cnt] + sufx[cnt + 1] - (n - cnt) * x;
        }

        int you = m - tmp;
        if (you < 0)
            continue;
        deb(x, tmp, you);
        auto check = [&](int y) {
            auto it = lower_bound(alls(vy), y);
            int val = 0;
            if (it == vy.end()) {
                val = n * y - prey[n];
            } else {
                int cnt = it - vy.begin() - 1;
                val = cnt * y - prey[cnt] + sufy[cnt + 1] - (n - cnt) * y;
            }
            return val <= you;
        };

        int st = vy[(n + 1) / 2];
        if (check(st) == 0)
            continue;
        int l = st, r = 2e6;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid))
                l = mid;
            else
                r = mid - 1;
        }
        deb(st, r);
        ans += r - st + 1;
       // int ql = l;
        l = -2e6, r = st;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        deb(l, st);
        ans += st - l + 1;
       // int qr = r;
        ans -= 1;
        // auto cal=[&](int cx,int cy){
        //     int res=0;
        //     for(int i=1;i<=n;i++){
        //         res+=abs(vx[i]-cx)+abs(vy[i]-cy);
        //     }
        //     return res;
        // };
        // for(int i=ql;i<=qr;i++){
        //     //cerr<<"**************************"<<endl;
        //     int res=cal(x,i);
        //     if(res>m){ cerr<<"**************************"<<endl;deb("acm!!!",x,i,res);}
        // }
    }
    cout << ans << endl;
}

利用trick的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
void solve() {
    cin >> n >> m;
    vector<int> vx(n + 1), vy(n + 1);
    for (int i = 1; i <= n; i++) cin >> vx[i] >> vy[i];

    sort(alls(vx));
    sort(alls(vy));
    vector<int> prex(n + 1), sufx(n + 2), prey(n + 1), sufy(n + 2);
    for (int i = 1; i <= n; i++) {
        prex[i] += vx[i] + prex[i - 1];
        prey[i] += vy[i] + prey[i - 1];
    }
    for (int i = n; i >= 1; i--) {
        sufx[i] += vx[i] + sufx[i + 1];
        sufy[i] += vy[i] + sufy[i + 1];
    }
    int ans = 0;
    auto check = [&](int y) {
        auto it = lower_bound(alls(vy), y);
        int val = 0;
        if (it == vy.end()) {
            val = n * y - prey[n];
        } else {
            int cnt = it - vy.begin() - 1;
            val = cnt * y - prey[cnt] + sufy[cnt + 1] - (n - cnt) * y;
        }
        return val;
    };
    vector<int> cnt(1e6 + 5);
    for (int i = -2e6; i <= 2e6; i++) {
        int res = check(i);
        if (res <= 1e6)
            cnt[res]++;
    }
    for (int i = 1; i <= 1e6; i++) cnt[i] += cnt[i - 1];
    for (int x = -2e6; x <= 2e6; x++) {
        auto it = lower_bound(alls(vx), x);
        int tmp = 0;
        if (it == vx.end()) {
            tmp = n * x - prex[n];
        } else {
            int cnt = it - vx.begin() - 1;
            tmp = cnt * x - prex[cnt] + sufx[cnt + 1] - (n - cnt) * x;
        }

        int you = m - tmp;
        if (you < 0)
            continue;

        ans += cnt[you];
    }
    cout << ans << endl;
}

F.给你 NN 个线性函数 f1,f2,…,fNf_1, f_2, \ldots, f_N ，其中 fi(x)=Aix+Bif_i(x) = A_i x + B_i .从N个中选k个函数并进行复合，求由 KK 组成的序列 p=(p1,p2,…,pK)p = (p_1, p_2, \ldots, p_K) 中 fp1(fp2(…fpK(1)…))f_{p_1}(f_{p_2}(\ldots f_{p_K}(1) \ldots )) 的最大可能值。

Constraints

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^{5}
  • 1≤K≤min(N,10)1 \leq K \leq \text{min}(N,10)
  • 1≤Ai,Bi≤501 \leq A_i, B_i \leq 50 (1≤i≤N)(1 \leq i \leq N)
  • All input values are integers.

Sol：不难想到一个可能是一个O(nk)O(nk)的dp，先贪心考虑这个问题怎么最优，发现可以用交换法推公式，然后按某种标准排序，也就是内层嵌套的顺序是存在调整优化空间的。我们认为按照这个标准排序后,fj(fi(suf))<fi(fj(suf))(i<j)f_{j}(f_{i}(suf))<f_{i}(f_{j}(suf))(i<j)。所以我们只有先确定内层的情况，才能求出外层，所以需要倒着dp。dp[i][j]dp[i][j]表示当前考虑i-n这些位置选了j个函数，转移考虑选与不选即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool cmp(pii c, pii d) {
    return c.sec * (1 - d.fs) > d.sec * (1 - c.fs);
}
void solve() {
    cin >> n >> m;
    vector<pii> v(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i].fs >> v[i].sec;
    sort(v.begin() + 1, v.end(), cmp);
    int k = min(10LL, m);
    vector<vector<int>> dp(n + 2, vector<int>(k + 1, 0));
    dp[n+1][0]=1;
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = dp[i + 1][j];
            if(j)dp[i][j] = max(dp[i][j], v[i].fs * dp[i + 1][j - 1] + v[i].sec);
        }
    }
    cout<<dp[1][k]<<endl;
}

G.给你一个简单的无向图，图中有 NN 个顶点和 MM 条边。 ii -th 边双向连接顶点 uiu_i 和 viv_i 。给出构造：每个点赋值点权，要求满足：

  • 对于出度至少为 11 的每个顶点 vv ，写在其相邻顶点上的数字（不包括 vv 本身）的总 XOR 为 00 。

Constraints

  • 1≤N≤601 \leq N \leq 60
  • 0≤M≤N(N−1)/20 \leq M \leq N(N-1)/2
  • 1≤ui<vi≤N1 \leq u_i < v_i \leq N
  • (ui,vi)≠(uj,vj)(u_i, v_i) \neq (u_j, v_j) for i≠ji \neq j.
  • All input values are integers.

Sol:考虑高斯消元解异或方程组,本题特殊之处在于:对于无穷多解的情况需要输出构造一种非零解(这里特指每个变量都不为0).考虑为自由变量赋正整数值,且尽可能异或不为0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
int gauss(vector<vector<int>>& a, int n, vector<int>& solution) {
    vector<int> freevar;           // 记录自由变量对应的列
    vector<int> pivot(n + 1, -1);  // 记录每一行的主元所在的列
    solution.assign(n + 1, 0);
    int r = 1;
    for (int c = 1; c <= n; c++) {
        int t = r;
        // 找到当前列中的主元
        for (int i = r; i <= n; i++) {
            if (a[i][c]) {
                t = i;
                break;
            }
        }
        if (!a[t][c]) {
            freevar.push_back(c);
            continue;  // 当前列没有主元，继续到下一列
        }
        pivot[r] = c;  // 第 r 行的主元在 c 列
        if (t != r) {  // 交换行，将主元行放在第 r 行
            for (int i = c; i <= n + 1; i++)
                swap(a[r][i], a[t][i]);
        }
        // 消去主元下方的所有行
        for (int i = r + 1; i <= n; i++) {
            if (a[i][c])
                for (int j = n + 1; j >= c; j--) a[i][j] ^= a[r][j];
        }
        r++;
    }

    // 检查是否有解
    for (int i = r; i <= n; i++) {
        if (a[i][n + 1])
            return 0;  // 无解
    }
    int tot = 0;
    int rksz = r - 1;  // 这是系数矩阵的秩
    // 自由变量根据题目要求情况去赋值
    for (auto i : freevar) solution[i] = 1LL << tot, tot++;
    //------------------------------
    for (int i = rksz; i >= 1; i--) {
        int sum = a[i][n + 1];
        for (int j = 1; j <= n; j++) {
            if (j == pivot[i]) {
                continue;
            }  // 如果不是主元所在的列
            sum ^= (a[i][j] * solution[j]);  // 右边已经求出来的，左边自由变量遗留
        }
        solution[pivot[i]] = sum;  // 求解对应的主元变量
    }
    assert(rksz <= n);
    if (rksz < n)
        return 2;  // 无穷多解
    return 1;      // 唯一解
}
void solve() {
    int n, m;
    cin >> n >> m;
    vector b(n + 1, vector<int>(n + 2));
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        b[u][v] = b[v][u] = 1;
    }
    vector<int> sol(n + 1);
    int t = gauss(b, n, sol);
    if (t == 0)
        cout << "No" << endl;
    else {
        for (int i = 1; i <= n; i++)
            if (sol[i] < 1) {
                cout << "No" << endl;
                return;
            }
        cout << "Yes" << endl;
        for (int i = 1; i <= n; i++) cout << sol[i] << " ";
    }
}