2022杭电多校（一）

2022杭电多校（一）

一、比赛小结

比赛链接：2022杭电多校 (hdu.edu.cn)

二、题目分析及解法（基础题）

1001、String

题目链接：Problem - 7138 (hdu.edu.cn)

题意：

有一串长度 $n(n\le 10^6)$ 的字符串，我们定义关于 $G$ 的函数 $F_G$ 为满足以下条件的正整数 $x$ 的数量：

1. $1\le x\le G_{len}$

2. $G[1，x]=G[G_{len}-x+1，G_{len}]$

3. 区间 $[1，x]$ 和 $[G_{len}-x+1，G_{len}]$ 的 LCS 长度大于 0 并且可被 k 整除

求 $\prod _{i=1}^n(F_{S[1,\dots ,i]}+1)(\mathrm{mod}998244353)$

题解：

其实是一道简单的字符串题目，但比赛时过的人很少，我们考虑 $[1,n]$ 和 $[i,n]$ 的最长公共前缀，exkmp 可以快速求出。并设为 $[1,x]$ 和 $[i,i+x-1]$ ，那么考虑其交叉部分，即 $[i,x]$ 。我们发现可以截取出 $[i,i-1+t\ast k]$ ，那么考虑其贡献，为 $ans[]$ 数组进行贡献 +1 ，朴素实现会超时，利用模 k 意义下的差分即可解决。

代码：

#include 
#define int long long
using namespace std;
const int mod = 998244353;
const int maxn = 1e6 + 5;
int n, k;
int res[maxn];
int exnext[maxn];
char s[maxn];
void getexnext() {
  int i = 0, j, pos;
  exnext[0] = n;
  while (s[i] == s[i + 1] && i + 1 < n) i++;
  exnext[1] = i;
  pos = 1;
  for (i = 2; i < n; i++) {
    if (exnext[i - pos] + i < exnext[pos] + pos)
      exnext[i] = exnext[i - pos];
    else {
      j = exnext[pos] + pos - i;
      if (j < 0) j = 0;
      while (i + j < n && s[j] == s[j + i]) j++;
      exnext[i] = j;
      pos = i;
    }
  }
}
signed main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    cin >> s;
    cin >> k;
    n = strlen(s);
    memset(res, 0, sizeof res);
    getexnext();
    for (int i = 0; i < n; i++)
      if (exnext[i] >= i - 1 + k) {
        int p1 = 2 * i - 1 + k;
        int len = (exnext[i] - i) / k * k;
        if (p1 < n) res[p1]++;
        if (p1 + len < n) res[p1 + len]--;
      }
    int ans = 1;
    for (int i = 0; i < n; i++) {
      ans = (ans * (res[i] + 1)) % mod;
      if (i + k < n) res[i + k] += res[i];
    }
    cout << ans << endl;
  }
  return 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

1002、Dragon slayer

题目链接：Problem - 7139 (hdu.edu.cn)

题意：

有一个 $n\times m$ 的长方形区域，英雄要去屠龙，但区域内有些墙壁，英雄可以让一堵墙永远消失，英雄想知道，至少使用几次超能力，可以屠龙。

题解：

这里的 $n、m$ 都小于 15 ，乱搞就行， BFS + 状压

代码：

#include 
#define pii pair<int, int>
using namespace std;

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int n, m, k;
int xs, xt, ys, yt;
int res;
struct e {
  int x1, y1, x2, y2;
} edge[20];
bool ans[20][20];

bool judge(int x1, int y1, int x2, int y2, int state) {
  if (x1 == x2) {
    if (y1 > y2) swap(y1, y2);
    for (int i = 0; i < k; i++)
      if (!(state & (1 << i)) && y2 == edge[i].y1 &&
          (edge[i].x1 <= x1 && x1 < edge[i].x2))
        return true;
  }
  if (y1 == y2) {
    if (x1 > x2) swap(x1, x2);
    for (int i = 0; i < k; i++)
      if (!(state & (1 << i)) && x2 == edge[i].x1 &&
          (edge[i].y1 <= y1 && y1 < edge[i].y2))
        return true;
  }
  return false;
}

bool bfs(int state) {
  queue<pii> q;
  q.push({xs, ys});
  while (!q.empty()) {
    pii cur = q.front();
    q.pop();
    int xx = cur.first, yy = cur.second, nx, ny;
    for (int i = 0; i < 4; i++) {
      nx = xx + dx[i], ny = yy + dy[i];
      if (nx < 0 || nx >= n || ny < 0 || ny >= m || ans[nx][ny]) continue;
      if (!judge(xx, yy, nx, ny, state)) {
        ans[nx][ny] = true;
        q.push({nx, ny});
      }
    }
  }
  return ans[xt][yt];
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    cin >> n >> m >> k;
    cin >> xs >> ys >> xt >> yt;
    res = k;
    for (int i = 0; i < k; i++)
      cin >> edge[i].x1 >> edge[i].y1 >> edge[i].x2 >> edge[i].y2;
    for (int state = 0; state < (1 << k); state++) {
      int cnt = 0, tmp = state;
      while (tmp) {
        if (tmp & 1) cnt++;
        tmp >>= 1;
      }
      if (cnt >= res) continue;
      memset(ans, false, sizeof ans);
      ans[xs][ys] = true;
      if (bfs(state)) res = cnt;
    }
    cout << res << endl;
  }
  return 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

1003、BackPack

题目链接：Problem - 7140 (hdu.edu.cn)

题意：

有 n 个物品和一个容量为 m 的背包，每个物品有两个属性：体积 v 和 价值 w ，问：是否存在一种选择方案使得所选物品的体积总和等于背包容量，如果存在，那么这些背包物品的价值的最大异或和是多少

题解：

一道略微复杂的 dp题，朴素做法是，令 $d{p}_{i,j,k}$ 为考虑前 $i$ 个物品，体积为 $j$ ，异或和为 $k$ 的方案是否存在，那么有

$dp[i+1][j][k]=dp[i+1][j][k]|dp[i][j-v[i+1]][k\oplus v[i+1]]$

然后就可以利用 Biteset 暴力优化来解决这道题，也有的做法是用 set 来优化暴力 2022"杭电杯"中超联赛·第一场 - CarryNotKarry

实际操作时，是令 $f_{i,j,k}$ 表示前 $i$ 个物品，异或和为 $j$ ，体积为 $k$ 的情况是否存在，那么有 $f_{i+1,j}=f_{i,j}\vee (f_{i,j\oplus v_{i+1}}<<w_i)$ ，然后配合滚动数组和 Bitset

代码：

#include 
using namespace std;
const int maxn = 1050;
int n, m;
int v[maxn], w[maxn];
bitset<1050> f[maxn], g[maxn];  // 滚动数组，节省开支
int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    cin >> n >> m;
    int ans = -1;
    for (int i = 0; i < 1024; ++i) f[i].reset();
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < 1024; j++) g[j] = (f[j] << v[i]);
      for (int j = 0; j < 1024; j++) f[j] |= g[j ^ w[i]];
    }
    for (int i = 0; i < 1024; i++)
      if (f[i][m]) ans = i;
    cout << ans << endl;
  }
  return 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

1004、Ball

题目链接：Problem - 7141 (hdu.edu.cn)

题意：

在 $m\times m$ 的棋盘上有 $n(n\le 2000)$ 个点，现在问你，有多少种选法，可以选出三个点，使其组成的三角形（可退化）的中间大小的边的长度是素数 （此处使用切比雪夫距离）

题解：

其实也是一道简单题，但现场赛只有50+过了，不过做题时也确实有些精巧的黑科技。考虑到 $n$ 比较小，可以先求出两两距离，然后先选取出两个点，使其长度为素数，然后再找一个点，使得这个点可以补出较长边和较短边。具体实现可以通过 bitset 来搞。

代码：

#include 
#define int long long
#define pii pair<int, int>
using namespace std;
const int maxn = 2020;
const int maxm = 200020;
int n, m;

int prime[maxm], pn;
bool isp[maxm];
void table() {
  pn = 0;
  memset(isp, true, sizeof isp);
  isp[0] = isp[1] = false;
  for (int i = 2; i < maxm; i++) {
    if (isp[i]) prime[pn++] = i;
    for (int j = 0; j < pn && (i * prime[j] < maxm); j++) {
      isp[i * prime[j]] = false;
      if (i % prime[j] == 0) break;
    }
  }
}

pii p[maxn];
int d(pii a, pii b) {
  return abs(a.first - b.first) + abs(a.second - b.second);
}
struct edge {
  int a, b;
  int dis;
} e[maxn * maxn];

bitset<2020> dis[maxn];
signed main() {
  //   freopen("in.txt", "r", stdin);
  //   freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  table();
  while (_--) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) dis[i].reset();
    for (int i = 1; i <= n; i++) cin >> p[i].first >> p[i].second;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
      for (int j = i + 1; j <= n; j++) e[cnt++] = {i, j, d(p[i], p[j])};
    sort(e, e + cnt, [](edge u, edge v) { return u.dis < v.dis; });
    int ans = 0;
    for (int i = 0; i < cnt; i++) {
      if (isp[e[i].dis]) ans += (dis[e[i].a] ^ dis[e[i].b]).count();
      dis[e[i].a][e[i].b] = 1;
      dis[e[i].b][e[i].a] = 1;
    }
    cout << ans << endl;
  }
  return 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

1009、Laser

题目链接：Problem - 7146 (hdu.edu.cn)

题意：

在二维平面有 $n$ 个敌人，激光武器可以发射米字型射线，问是否可以只用一个武器来摧毁所有敌人

题解：

这道题挺暴力的，给出两个敌人就可以大致确定范围（12个可选内容），然后对可选范围进行枚举即可，答案提供了另一个角度，就是先由一个点确定一条直线，再由另外另一个点确定这条线上的三个交点是否合法。实际上这两个思路殊途同归，都是讨论了 12 个可选点的合法情况。

代码：

#include 
using namespace std;
const int maxn = 1e6 + 6;
int x[maxn], y[maxn], a[maxn], b[maxn];
int n;
bool pd(int x, int y) {
  if (x == 0 || y == 0 || x == y || x + y == 0) return true;
  return false;
}
bool check(int xx, int yy) {
  for (int i = 1; i <= n; ++i)
    if (!pd(xx - x[i], yy - y[i])) return false;
  return true;
}
bool check() {
  bool flag = true;
  int xx = x[1], yy = y[1];
  for (int i = 2; i <= n; ++i) {
    if (x[i] == xx) continue;
    flag = false;
    if (check(xx, y[i])) return true;
    if (check(xx, y[i] + (x[i] - xx))) return true;
    if (check(xx, y[i] - (x[i] - xx))) return true;
    break;
  }
  if (flag) return true;
  return false;
}
int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  int _;
  cin >> _;
  while (_--) {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
    for (int i = 1; i <= n; ++i) x[i] = a[i], y[i] = b[i];
    if (check()) {
      puts("YES");
      continue;
    }
    for (int i = 1; i <= n; ++i) x[i] = b[i], y[i] = a[i];
    if (check()) {
      puts("YES");
      continue;
    }
    for (int i = 1; i <= n; ++i) x[i] = a[i] + b[i], y[i] = a[i] - b[i];
    if (check()) {
      puts("YES");
      continue;
    }
    for (int i = 1; i <= n; ++i) x[i] = a[i] - b[i], y[i] = a[i] + b[i];
    if (check()) {
      puts("YES");
      continue;
    }
    puts("NO");
  }
  return 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

1011、Random

题目链接：Problem - 7148 (hdu.edu.cn)

题意：

N数字，随机生成[0，1] ，做M操作， $\frac{1}{2}$ 概率删除最大值，$\frac{1}{2}$ 概率删除最小值， 计算期望值，模 $10^9+7$

题解：

输出 $\frac{1}{2}\times (N-M)(\mathrm{mod}2)$ 即可

代码：

#include 
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int inv2 = (mod + 1) / 2;
int n, m;
signed main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    cin >> n >> m;
    cout << (n - m) * inv2 % mod << endl;
  }
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1012、Alice and Bob

题目链接：Problem - 7149 (hdu.edu.cn)

题意：

Alice 和 Bob 在玩游戏，规则为：初始时黑板上 m 个数字，分别位于 $1\sim n$ 之间，如果黑板上还有数字，并且没有带值的数字0在黑板上，Alice 可以将黑板上剩余的数字分成两组。Bob 选择其中一组并擦除该组中的所有数字。然后将所有剩余的数字减去一。

在任何时候，如果有一个值为0在黑板上，Alice 获胜;否则，如果黑板上的所有数字都被擦除，则Bob 获胜。 请确定如果爱丽丝和鲍勃都以最佳方式玩游戏，谁将赢得游戏。

题解：

对于 Alice 而言，最优策略是“对半分”，即尽量将每个相同的数都对分到两个组里，这样，对于数字 $i$ ，如果它的个数为 $a[i]$ 个，那么它想要减到 $0$ 则至少需要 $\log i$ 步，只要存在某个 $i$ ，使得 $a[i]\ge (1<<\log i)$ 即可。

代码：

#include 
#define int long long
using namespace std;
const int maxn = 1e6 + 6;
int n;
int a[maxn], sum[maxn];
signed main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    cin >> n;
    for (int i = 0; i <= n; i++) cin >> a[i];
    sum[n] = a[n];
    for (int i = n - 1; i >= 0; i--) sum[i] = a[i] + sum[i + 1] / 2;
    if (sum[0])
      cout << "Alice\n";
    else
      cout << "Bob\n";
  }
  return 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

三、题目分析及解法（进阶题）

还不太会（

1004、Path

1005、Grammar

1006、Travel plan

1007、Treasure

1008、Walk