题解 【第五届传智杯 决赛】

kkksc03 · 2023-04-05 10:56:50 · 个人记录

A 时效「月岩笠的诅咒」

题解

注意到题目所求等价于询问 a,b 的小数点部分是否相同。这里提供三个常见思路：

• 直接以浮点数形式读入 a,b，比较其小数部分，即比较 a-\lfloor a\rfloor 和 b-\lfloor b\rfloor 是否相同。然而由于题设输入数据精确到了小数点后 12 位，且整数部分的范围也较大，因此这样做会爆精度。
• 以字符串来处理。即分别读入两个字符串，比较其小数点后面的部分是否相同。
• 以长整型来处理。直接读入小数点后面的部分比较就行。

代码

版本 1：

#include<bits/stdc++.h>
using namespace std;
string a, b;
int main(){
    cin >> a >> b;
    int u = a.find('.');
    int v = b.find('.');
    puts(a.substr(u) == b.substr(v) ? "YES" : "NO");
    return 0;
}

版本 2：

#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
int main(){
    i64 a1, a2, b1, b2;
    scanf("%lld.%lld", &a1, &a2);
    scanf("%lld.%lld", &b1, &b2);
    puts(a2 == b2 ? "YES" : "NO");
    return 0;
}

B 不死「火鸟　−凤翼天翔−」

题解

容易发现，从 (x_0,y_0) 出发，走了奇偶两步后，能到达的位置只有：

因此考虑以 2 为步距。按照一共走的步数是奇数步还是偶数步来讨论。

• 在一共走了偶数步的情况下，题目转化为每步可以沿着 x 轴或者 y 轴方向走 2 个单位长度。那么此时 (x_0,y_0) 走到 (x, y) 的最少步数显然是 \dfrac{|x_0-x|}{2}+\dfrac{|y_0-y|}{2}，在 x_0-x 或者 y_0-y 是奇数的情况下无解。
• 在一共走了奇数步的情况下，考虑最后一步（奇数步）是怎么走的。把这一步扣除则回到了走偶数步的情况。

代码

#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647 - 1;
int qread(){
    int w=1,c,ret;
    while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
int dis(int a1, int b1, int a2, int b2){
    int dx = abs(a2 - a1);
    int dy = abs(b2 - b1);
    if(dx % 2 == 1 || dy % 2 == 1) return INF;
    return dx + dy;
}
int main(){
    int a1 = qread(), b1 = qread();
    int a2 = qread(), b2 = qread();
    int ans = INF;
    ans = min(ans, dis(a1, b1, a2, b2));
    ans = min(ans, 1 + dis(a1, b1, a2 - 1, b2 - 1));
    ans = min(ans, 1 + dis(a1, b1, a2 + 1, b2 + 1));
    printf("%d\n", ans >= INF ? -1 : ans);
    return 0;
}

C 藤原「灭罪寺院伤」

题解

容易发现沿着竖直方向移动与沿着水平方向移动，是可以独立考虑的。最终的答案就是沿着竖直方向移动的最小步数加上沿着水平方向移动的最小步数。

在这两个方向上，问题都可以转化为：

• 有 n 个区间 [a_i,b_i] 互相嵌套。每次可以将一个区间 [a,b] 变为 [a-1,b-1] 或者 [a+1,b+1]，但是要时刻保持嵌套状态。现在要将 [a_n,b_n] 变成 [a_{\mathrm{end}},b_{\mathrm{end}}]，问最小步数。

容易发现，

• 若 [a_{\mathrm{end}},b_{\mathrm{end}}]\subseteq [a_i,b_i] 则 [a_i,b_i] 不需要移动；
• 若 a_{\mathrm{end}}\le a_i 则至少要向左移动 a_i-a_{\mathrm{end}} 距离；
• 若 b_{\mathrm{end}}\ge b_i 则至少要向右移动 b_{\mathrm{end}}-b_i 距离。

并且容易构造出这样一个最优方案。

代码

#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
const int MAXN= 1e5 + 3;
int n, xe, ye, X1[MAXN], Y1[MAXN], X2[MAXN], Y2[MAXN];
i64 solve(int e, int *P1, int *P2){
    i64 ret = 0;
    up(1, n, i){
        if(e <= P1[i]) ret += P1[i] - e;
        if(e >= P2[i]) ret += e - P2[i];
    }
    return ret;
}
int qread(){
    int w=1,c,ret;
    while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
int main(){
    n = qread(), xe = qread(), ye = qread();
    up(1, n, i){
        X1[i] = qread(), X2[i] = X1[i] + i - 1;
        Y2[i] = qread(), Y1[i] = Y2[i] - i + 1;
    }
    i64 ans = solve(xe, X1, X2) + solve(ye, Y1, Y2);
    printf("%lld\n", ans);
    return 0;
}

D 不死「徐福时空」

题解

按照题设模拟即可，没有太大难度。

代码

#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
const int MAXN= 1e5 + 3;
const int MAXM= 100 + 3;
int ans = 0;
void insert_sort(int n, int *A){
    for(int i = 0;i < n;++ i){
        int p = i, a = A[i];
        for(int j = i - 1;j >= 0;-- j) if(A[j] > A[i]) -- p; else break;
        for(int j = i    ;j >  p;-- j) A[j] = A[j - 1];
        A[p] = a, ans += i - p + 1;
    }
}
void shell_sort(int n, int m, int *A, int *M){
    int *B = new int[n];
    for(int j = 0;j < m;++ j){
        int l = M[j];
        for(int i = 0;i < l;++ i){
            int m = 0;
            for(int j = i;j < n;j += l) B[m ++] = A[j];
            insert_sort(m, B), m = 0;
            for(int j = i;j < n;j += l) A[j] = B[m ++];
        }
    }
}
int n, m, P[MAXN], Q[MAXM];
int main(){
    cin >> n >> m;
    for(int i = 0;i < n;++ i) cin  >> P[i];
    for(int i = 0;i < m;++ i) cin  >> Q[i];
    shell_sort(n, m, P, Q);
    cout << ans << endl;
    for(int i = 0;i < n;++ i) cout << P[i] << " \n"[i == n - 1];
    return 0;
}

E 灭罪「正直者之死」

题解

可以证明，在数列 [a_1,a_2,\cdots ,a_p] 满足 u\le a_i\le v 的情况下（u<0<v），可以通过改变求和的顺序使得计算过程中零时变量始终在 [u,v] 范围内，充要条件即为 u\le \sum a_i\le v。

必要性显然。下面证明充分性。

假定当前零时变量的值为 x，剩下来的还没有加到 x 里面的数字，按照它们与 0 的大小关系可以分为两类：大于等于 0 的部分和小于 0 的部分。

• 如果 v\ge x\ge 0，假设剩余的元素存在 a<0，由 u\le a\le v 则一定有 u\le a<0，于是 u\le x+a\le v。如果不存在 a<0，那么把所有剩下来的元素都加到 x 上也肯定不会超过 v，因为此时 x 的值就等于 \sum a_i，而由条件这是不超过 v 的；
• 如果 u\le x< 0，假设剩余的元素存在 a\ge 0，由 u\le a\le v 则一定有 0\le a\le v，于是 u\le x+a\le v。如果不存在 a\ge 0，那么把所有剩下来的元素都加到 x 上也肯定不会小于 u，因为此时 x 的值就等于 \sum a_i，而由条件这是不小于 u 的。

因此题目等价于，选出尽可能多的数字，使得这些数字的和在 [-2^{k-1},2^{k-1}) 内。可以使用背包。

设 f_{i,j} 表示在考虑前 i 个数的情况下，凑出一些元素，这些元素的和为 j，这些元素个数的最大值。容易得到状态转移方程：

值得注意的是，可能存在 j 中途大于 v（或者小于 u）而在最后回到 [u,v] 范围内的情况，因此 j 的范围应当是 [nu,nv]。当然，有理论证明，一组合法的选数方案内的元素（即这些元素的值域为 [u,v]，且和的值域也为 [u,v]），在随机排列的情况下，这些元素的前缀和的值域的期望是 [u\sqrt n,v\sqrt n]。因此将整个数列进行若干次随机打乱，并且每次把 j 的值域设定为 [u\sqrt n,v\sqrt n]，最终有极大概率得到正确结果。

当然在这里数据范围没有考察这一点。写一个平凡的 \mathcal O(n^22^k) 做法即可。

这部分的 m 只有 b 个。此时我们可以在加入一个新的 a 之后暴力地维护每个 m 的答案。具体而言，我们对每个 m 都开一个桶，即用 C[m,i] 存储模 m 后余 i 的 a 的个数。每次加入一个新的 a 后，枚举 m 的值，让 C[m,a\bmod m] 的值增加 1。对于每个查询操作 [l_0,r_0]，直接暴力地查询 C[m,l_0\sim r_0] 这部分元素之和即可。

容易发现时间复杂度为 \mathcal O(nb+qb)，空间复杂度为 \mathcal O(b^2)。

情形二：\bm{m> b}

这部分的 m 较多，[l_0,r_0] 的长度也比较大，不便于直接维护 C[m,i] 的值。但是此时 \left\lfloor\dfrac{a}{m}\right\rfloor 的值不太大，可以去考虑统计 [l_0+im,r_0+im],\ i=0,1,2,\cdots,\left\lfloor\dfrac{v}{m}\right\rfloor 内的 a 的值有多少个。我们在值域上使用数据结构进行统计。

我们一共会在值域上插入 n 个数字，查询次数最多一共有 q\left\lfloor\dfrac{v}{b}\right\rfloor 次，所以我们希望找到一个查询效率高，但是修改效率可以低一些的数据结构。于是考虑分块，块长为 t。我们在每个块内维护前缀和，以及维护以块为单位的另一个前缀和。每次插入一个数字 a，需要花费 \mathcal O(t+v/t) 的效率来更新这些前缀和，但是查询时可以 \mathcal O(1) 地回答每个询问。取 t=\sqrt v 时效率最高。

容易发现在取 b=\sqrt v 的情况下，可以得到一个优秀的时间复杂度 \mathcal O(q\sqrt v)。

代码

#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
const int MAXN= 1e5 + 3;
const int MAXQ= 5e5 + 3;
const int BLOK= 1200 + 1;
const int MAXM= MAXN / BLOK + 3;
int C[BLOK + 3][BLOK + 3], v = 100000, b = v / BLOK;
int L[MAXQ], R[MAXQ], X[MAXQ], Y[MAXQ], M[MAXQ], T[MAXQ], A[MAXN];
int P[MAXN], Q[MAXN], S[MAXM];
int qread(){
    int w=1,c,ret;
    while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
vector <int> O[MAXN];
int main(){
    int n = qread(), z = qread();
    up(1, n, i) A[i] = qread();
    up(1, z, i){
        L[i] = qread(), R[i] = qread();
        X[i] = qread(), Y[i] = qread(), M[i] = qread();
        O[L[i] - 1].push_back(-i);
        O[R[i]    ].push_back( i);
    }
    up(1, n, i){
        int a = A[i], t = a / BLOK;
        {
            up(1, BLOK, j) C[j][a % j] ++;
            int l = t * BLOK;
            int r = min(v, t * BLOK + BLOK - 1);
            up(a, r, j) P[j] ++;
            up(t, b, j) Q[j] ++;
        }
        for(auto &o : O[i]){
            int d = abs(o), f = o > 0 ? 1 : -1;
            int m = M[d], x0, y0, w = 0;
            int x = X[d] % m;
            int y = Y[d] % m;
            if(x == y) continue;
            if(x < y){
                x0 = m - y, y0 = m - x - 1, T[d] += i * f, f *= -1;
            } else {
                x0 = m - x, y0 = m - y - 1;
            }
            if(x0 > y0) continue;
            if(m <= BLOK){
                up(x0, y0, j) w += C[m][j];
            } else {
                for(int l = x0, r = y0;l <= v;l += m, r += m){
                    r = min(r, v);
                    int p = l / BLOK;
                    int q = r / BLOK;
                    if(p == q){
                        w += P[r];
                        if(l % BLOK != 0) w -= P[l - 1];
                    } else {
                        w += P[r] + Q[q - 1];
                        if(l % BLOK != 0) w -= P[l - 1];
                        if(p        != 0) w -= Q[p - 1];
                    }
                }
            }
            T[d] += f * w;
        }
    }
    up(1, z, i)
        printf("%d\n", T[i]);
    return 0;
}