[考试总结]ZROI-21-CSP7连-DAY3 总结

#T1 斯诺克

#题意简述

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

#大体思路

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

#Code

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

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

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

#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;
}

[考试总结]ZROI-21-CSP7连-DAY3 总结

上一篇:将自己喜欢的网页保存为单个文件包括图片(mhtml文件)


下一篇:selenium用css、xpath表达式进行元素定位