「考试总结」ZROI-21-CSP7连-DAY3 总结

发表于 更新于 分类于
ZROI-21-CSP7连-DAY3 总结

#T1 斯诺克

#题意简述

\(7\) 种物品，第 \(i\) 种物品的价值为 \(i\)，有 \(a_i\) 个，必须按照价值自小到大地选，特别的，必须将第 \(1\) 种选完才能向后选，选第 \(1\) 种时可以得到一个额外价值 \(x\)，可以在当前 \(a_i>0(i\ne1)\) 的物品价值中任选。

#大体思路

显然只要有就一定可以都选上，附加权值直接贪心的选最大的即可。

#Code

1
2
3
4
5
6
7
8
9
10
11
12
int rcnt, a[8], res, mx;

int main() {
    for (int i = 1; i <= 7; ++ i) {
        scanf("%d", &a[i]);
        res += a[i] * i;
        if (a[i]) mx = i;
    }
    res += a[1] * mx;
    printf("%d", res);
    return 0;
}

#T2 翻转

#题意简述

给定一个 \(n\times m(n,m\leq17)\) 的 \(01\) 矩阵，每次操作可以将如下图范围的图形做异或操作，图形可以不全（在边界），但中心点必须位于矩阵中。

问至少需要操作多少次才能将矩阵全部变为 \(0\)。

#大体思路

不难发现

  • 对于一个位置最多被操作一次；
  • 对于两个操作位置相同的操作聚合，结果相同；

于是可以想到自上而下的确定情况，注意到如果将第一行的状态确定，每次只对已经确定的行的下一行进行操作，那么下面怎么变换都是确定的了，于是不难得到以下算法：用二进制枚举第一行的每个点的操作状态，对原图进行修改，并在改后的图上进行模拟/统计即可，时间复杂度为 \(O(nm\cdot2^m)\).

#Code

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
const int N = 200010;
const int INF = 0x3fffffff;

template <typename T>
inline T Min(const T a, const T b) {return a < b ? a : b;}

int n, m, ans = INF, mp[20][20], tmp[20][20];

inline int bitcount(int x) {
    int cnt = 0;
    while (x) cnt += (x & 1), x >>= 1;
    return cnt;
}

int get_res(int x) {
    int res = 0;
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j)
        tmp[i][j] = mp[i][j];
    for (int i = 0; i < m; ++ i)
      if (x & (1 << i)) {
          tmp[1][i + 1] ^= 1, tmp[1][i] ^= 1;
          tmp[1][i + 2] ^= 1, tmp[2][i + 1] ^= 1;
      }
    for (int i = 1; i < n; ++ i)
      for (int j = 1; j <= m; ++ j)
        if (tmp[i][j]) {
            ++ res; tmp[i][j] ^= 1;
            tmp[i + 1][j] ^= 1;
            tmp[i + 1][j - 1] ^= 1;
            tmp[i + 1][j + 1] ^= 1;
            tmp[i + 2][j] ^= 1;
        }
    for (int i = 1; i<= m; ++ i)
      if (tmp[n][i]) return INF;
    return res + bitcount(x);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j) {
          char c; cin >> c;
          if (c == 'X') mp[i][j] = 1;
          else mp[i][j] = 0;
      }
    for (int i = 0; i < 1 << m; ++ i)
      ans = Min(ans, get_res(i));
    cout << ans;
    return 0;
}

#T3 数对

#题意简述

给定两个数列 \(\{a_1,a_2,\dots,a_n\}\) 和 \(\{b_1,b_2,\dots,b_m\}(n,m\leq10^5,1\leq a_i,b_i\leq2^30)\)，问有多少数对 \((a_i,b_j)(1\leq i\leq n,1\leq j\leq m)\)，满足 \(\text{bitcount}(a_i\text{ xor }b_j)=2\).

#大体思路

\(\text{bitcount}(a_i\text{ xor }b_j)=2\) 意味着 \(a_i,b_j\) 在二进制下只有两位不同，维护一个 Hash，每次枚举不同的位置中的一位 \(k\)，先查询 Hash 中每个 \(b_j\text{ xor }2^k\) 出现的次数，再将每个 \(a_i\text{ xor }2^k\) 加入 Hash，不难发现这样统计每对数字刚好被统计一次，即得答案。时间复杂度 \(O(30\cdot n)\)，\(30\) 为枚举 \(k\) 的复杂度。

#Code

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
const int N = 20000010;
const int MOD = 19260817;
const int INF = 0x3fffffff;

struct Hash {int val, tot, nxt;} h[N];

int n, m, a[N], b[N], head[N], cnt;
ll ans;

inline void insert(int x, int c) {
    int hx = x % MOD, p = head[hx];
    while (p && h[p].val != x) p = h[p].nxt;
    if (h[p].val == x) h[p].tot += c;
    else {
        h[++ cnt].val = x, h[cnt].tot = c;
        h[cnt].nxt = head[hx], head[hx] = cnt;
    }
}

inline int Count(int x) {
    int hx = x % MOD, p = head[hx];
    while (p && h[p].val != x) p = h[p].nxt;
    if (h[p].val == x) return h[p].tot;
    else return 0;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i)
      scanf("%d", &a[i]);
    for (int i= 1; i <= m; ++ i)
      scanf("%d", &b[i]);
    for (int i = 1; i <= 30; ++ i) {
        int k = 1 << (i - 1);
        for (int j = 1; j <= m; ++ j)
          ans += Count(b[j] ^ k);
        for (int j = 1; j <= n; ++ j)
          insert(a[j] ^ k, 1);
    }
    printf("%lld", ans);
    return 0;
}

#T4 回文串

#题意简述

定义一个字符串的价值是它的回文子串的个数。现给定一字符串 \(s(|s|\leq10^5)\)，可以任一改变一个字符，问可得到的最大价值。

#大体思路

考虑改变一个位置会造成的影响：失去一些回文子串、得到新的回文子串。

在考虑改变造成的影响前，我们需要先得到在每个位置的回文半径，可以用 Manacher 求，当然也可以用 Hash+二分完成，这里直接用的 Hash。然后，我们再来考虑造成的影响。

对于每个回文中心 \(i，j(i\leq j)\) 和其对应的回文半径 \(r\)，考虑得到新的回文子串时对应的改变位置要么是 \(x=i-r\) 要么是 \(y=j+r\)，且一定是改成对应的另一个的字符，否则对于这个回文中心，不会造成价值增加。

对于奇回文，\(i=j\)，对于偶回文，\(j=i+1\)。

之后同样可以用 Hash+二分求得不包括 \(x\) 和 \(y\) 的新增半径（即为新增的回文子串的数量），用数组 \(f_{i,c}\) 进行存储，其中 \(f\) 的意义是 “将第 \(i\) 个位置变为 \(c\) 字符增加的回文子串的数量”。

下面来考虑修改 \(x\) 失去的回文串数量，显然对于当前回文中心 \(i,j\)，若 \(i-r+1\leq x\leq i\)，那么减少的个数为 \(r-(i-x)=r-i+x\)，若 \(j\leq x\leq j+r-1\)，那么减少的个数为 \(j+r-1-(x-1)=j+r-x\)，发现这两个贡献对于修改位置 \(x\) 都可以拆分成两部分：\(r-i\) 和 \(x\)、\(r+j\) 和 \(-x\)，其中仅关于 \(i,j,r\) 的部分与修改哪里无关，于是可以维护一个数组 \(fl_x\)，记录这一部分的贡献，这里的区间加法可以用差分处理；再来看 \(x\) 与 \(-x\)，同样可以维护差分数组 \(fk_x\)，对 \(fk\) 只做区间加 \(1\) 与加 \(-1\)，最后统计贡献可以统一乘上 \(x\)。

综上我们对于修改的影响都已经解决了，最后枚举修改位置及修改后的字符，将贡献取最大值与初始价值相加即得答案。时间复杂度为 \(O(n\log n+26\cdot n)\).

#Code

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
#define ll long long
#define ull unsigned long long

const int N = 200010;
const ull BASE = 9973;
const ull MOD = 1e9 + 7;
const int INF = 0x3fffffff;

template <typename T>
inline T Min(const T a, const T b) {return a < b ? a : b;}

template <typename T>
inline T Max(const T a, const T b) {return a > b ? a : b;}

int n, p[N], h[N], hr[N]; char s[N], sr[N];
ll f[N][26], fk[N], fl[N], init_val;

inline void init_hash(char *S, int *H) {
    int len = strlen(S); H[0] = 1;
    for (int i = 0; i < len; ++ i)
      H[i + 1] = (1ull * H[i] * BASE % MOD + (ll)(S[i] - 'a')) % MOD;
}

inline ull getHash(int* H, int a, int b) {
    return ((1ull * H[b + 1] - 1ull * H[a] * p[b - a + 1] % MOD) + MOD) % MOD;
}

inline bool check(int a, int b, int c, int d) {
    return getHash(h, a, b) == getHash(hr, n - d - 1, n - c - 1);
}

int getRadius(int l, int r, int x, int y){
    int L = x, R = y, res = 0;
    while (L <= R) {
        int mid = (L + R + 1) >> 1;
        if (check(l - mid + 1, l, r, r + mid - 1))
          res = mid, L = mid + 1;
        else R = mid - 1;
    }
    return res;
}

signed main() {
    scanf("%s", s); n = strlen(s); p[0] = 1;
    for (int i = 0; i <= n; ++ i)
      p[i + 1] = (1ull * p[i] * BASE) % MOD;
    for (int i = 0; i < n; ++ i)
      sr[i] = s[n - i - 1];
    init_hash(s, h); init_hash(sr, hr);
    for (int i = 0; i < n; ++ i)
      for (int j = i; j <= i + 1; ++ j) {
          int r = 0; r = getRadius(i, j, 0, Min(i + 1, n - j));
          if (i == j) {
              fk[j + 1] += -1, fk[j + r] -= -1;
              fl[j + 1] += j + r, fl[j + r] -= j + r;
              fk[i - r + 1] += 1, fk[i] -= 1;
              fl[i - r + 1] += -(i - r), fl[i] -= -(i - r);
          } else {
              fk[j] += -1, fk[j + r] -= -1;
              fl[j] += j + r, fl[j + r] -= j + r;
              fk[i - r + 1] += 1, fk[i + 1] -= 1;
              fl[i - r + 1] += -(i - r), fl[i + 1] -= -(i - r);
          }
          int x = i - r, y = j + r; init_val += r;
          if (x < 0 || y >= n) continue;
          ++ r; r = getRadius(x - 1, y + 1, 0, Min(i + 1, n - j) - r);
          f[x][s[y] - 'a'] += r + 1;
          f[y][s[x] - 'a'] += r + 1;
      }
    ll best_change = 0, k = 0, l = 0;
    for (int i = 0; i < n; ++ i) {
        k += fk[i], l += fl[i];
        for (int j = 0; j < 26; ++ j)
          if (j + 'a' != s[i])
            best_change = Max(best_change, f[i][j] - (1ll * i * k + l));
    }
    printf("%lld\n", init_val + best_change);
    return 0;
}