2022杭电多校（三）

2022杭电多校（三）

一、比赛小结

比赛链接：Problems (hdu.edu.cn)

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

1001、Equipment Upgrade

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

题意：

一共有 $n$ 级，在第 $i$ 级时，升级到 $i+1$ 级的概率为 $p_i$ ，且要被花费 $c_i$ 元，并且还有 $(1-p_i)\frac{{\omega }_j}{{\sum }_{k=1}^i{\omega }_k}$ 的概率降到第 $i-j$ 级，求从 $0$ 级升到 $n$ 级的期望花费。

题解：

我们先来推下式子：

$E_n=0$

$E_i=c_i+p_i\cdot E_{i+1}+\frac{1-p_i}{{\sum }_{j=1}^i{\omega }_j}\cdot (\sum _{j=1}^i{\omega }_j\cdot E_{i-j})$

$E_{i+1}=\frac{E_i-c_i-\frac{1-p_i}{{\sum }_{j=1}^i{\omega }_j}\cdot ({\sum }_{j=1}^i{\omega }_j\cdot E_{i-j})}{p_i}$

然后设 $E_i=a_i\cdot E_0+b_i$ ，则有：

$a_0=1,b_0=0$

$a_{i+1}=\frac{a_i-\frac{1-p_i}{{\sum }_{j=1}^i{\omega }_j}\cdot ({\sum }_{j=1}^i{\omega }_j\cdot a_{i-j})}{p_i}$

$b_{i+1}=\frac{b_i-c_i-\frac{1-p_i}{{\sum }_{j=1}^i{\omega }_j}\cdot ({\sum }_{j=1}^i{\omega }_j\cdot b_{i-j})}{p_i}$

这个递推有卷积的形式，因此可以用 分治+NTT 来做，分治NTT已经变成常识了（悲

代码：

#include 
#define int long long
using namespace std;
namespace poly {
typedef long long ll;
const int mod = 998244353;
const int maxn = 1e6 + 10;
ll invi[maxn];
// 记得先init()!!!!!!!!!
void init() {
  invi[1] = 1;
  for (int i = 2; i < maxn; i++) {
    invi[i] = (mod - mod / i) * invi[mod % i] % mod;
  }
}
// 快速幂
ll quickpow(ll x, ll y) {
  ll ans = 1;
  while (y) {
    if (y & 1) ans = ans * x % mod;
    y >>= 1;
    x = x * x % mod;
  }
  return ans;
}
// 二次剩余
ll modsqrt(ll x) {
  if (mod == 2) return x % mod;
  if (quickpow(x, mod - 1 >> 1) != 1) return -1;
  ll ans = 0;
  if (mod % 4 == 3)
    ans = quickpow(x, mod + 1 >> 2);
  else {
    ll b;
    for (b = rand() % mod; quickpow(b, mod - 1 >> 1) == 1; b = rand() % mod)
      ;
    ll i = mod - 1 >> 1, k = 0;
    do {
      i >>= 1;
      k >>= 1;
      if ((quickpow(x, i) * quickpow(b, k) + 1) % mod == 0) k += (mod - 1 >> 1);
    } while (i % 2 == 0);
    ans = quickpow(x, i + 1 >> 1) * quickpow(b, k >> 1) % mod;
  }
  if (ans * 2 > mod) ans = mod - ans;
  return ans;
}
// 蝴蝶变换
void change(ll* a, int len) {
  static int rev[maxn];
  rev[0] = 0;
  for (int i = 0; i < len; i++) {
    rev[i] = (rev[i >> 1] >> 1);
    if (i & 1) rev[i] |= len >> 1;
  }
  for (int i = 0; i < len; i++)
    if (i < rev[i]) swap(a[i], a[rev[i]]);
}
// flag=1 -> NTT , flag=-1 -> INTT , O(nlogn)
void NTT(ll* a, int len, int flag) {
  change(a, len);
  for (int h = 2; h <= len; h <<= 1) {
    ll uni = quickpow(3, (mod - 1) / h);  // 3 为 mod = 998244353 的原根
    if (flag == -1) uni = quickpow(uni, mod - 2);
    for (int i = 0; i < len; i += h) {
      ll w = 1;
      for (int j = i; j < i + h / 2; j++) {
        ll u = a[j] % mod;
        ll v = w * a[j + h / 2] % mod;
        a[j] = (u + v) % mod;
        a[j + h / 2] = (u - v + mod) % mod;
        w = w * uni % mod;
      }
    }
  }
  if (flag == -1) {
    ll inv = quickpow(len, mod - 2);
    for (int i = 0; i < len; i++) a[i] = a[i] * inv % mod;
  }
}
// 多项式乘法，n m 分别为 a b 最高次数
void polymul(ll* a, ll* b, ll* ans, int n, int m) {
  static ll tpa[maxn], tpb[maxn];
  memcpy(tpa, a, sizeof(ll) * (n + 1));
  memcpy(tpb, b, sizeof(ll) * (m + 1));
  int len = 1;
  for (; len < n + 1; len <<= 1)  // n + m + 1 !!! 本题特殊
    ;
  memset(tpa + n + 1, 0, sizeof(ll) * (len - n));
  memset(tpb + m + 1, 0, sizeof(ll) * (len - m));
  NTT(tpa, len, 1);
  NTT(tpb, len, 1);
  for (int i = 0; i <= len; i++) ans[i] = tpa[i] * tpb[i] % mod;
  NTT(ans, len, -1);
}

// // 多项式求逆，ans为最终答案数组, O(nlogn)
// void polyinv(ll* a, ll* ans, int len) {
//   static ll tp[maxn];
//   memset(tp, 0, sizeof(ll) * (len << 1));
//   memset(ans, 0, sizeof(ll) * (len << 1));
//   ans[0] = quickpow(a[0], mod - 2);
//   for (int h = 2; h <= len; h <<= 1) {
//     memcpy(tp, a, sizeof(ll) * h);
//     NTT(tp, h << 1, 1);
//     NTT(ans, h << 1, 1);
//     for (int i = 0; i < (h << 1); i++)
//       ans[i] = ans[i] * ((2 + mod - tp[i] * ans[i] % mod) % mod) % mod;
//     NTT(ans, h << 1, -1);
//     memset(ans + h, 0, sizeof(ll) * h);
//   }
// }
// // 多项式除法，a / b = ans1, a % b = ans2
// void polydiv(ll* a, ll* b, ll* ans1, ll* ans2, int n, int m) {
//   static ll tp0[maxn];
//   int len = 1;
//   for (; len < n - m + 1; len <<= 1)
//     ;
//   memset(tp0, 0, sizeof(ll) * len);
//   for (int i = 0; i <= n; i++) ans1[n - i] = a[i];
//   for (int i = 0; i <= m; i++) ans2[m - i] = b[i];
//   for (int i = n - m + 1; i <= m; i++) ans2[i] = 0;
//   polyinv(ans2, tp0, len);
//   polymul(ans1, tp0, tp0, n, n - m);
//   for (int i = 0; i <= n - m; i++) ans1[i] = tp0[n - m - i];
//   polymul(b, ans1, ans2, m, n - m);
//   for (int i = 0; i < m; i++) ans2[i] = (a[i] - ans2[i] + mod) % mod;
// }
// // 多项式求导
// void qiudao(ll* a, ll* ans, int len) {
//   for (int i = 1; i < len; i++) ans[i - 1] = a[i] * i % mod;
//   ans[len - 1] = 0;
// }
// // 多项式积分
// void jifen(ll* a, ll* ans, int len) {
//   for (int i = len - 1; i; i--) ans[i] = a[i - 1] * invi[i] % mod;
//   ans[0] = 0;  // 积分常数C
// }
// // 多项式ln，a[0]!=0，O(nlogn)
// void polyln(ll* a, ll* ans, int len) {
//   static ll tp1[maxn];
//   qiudao(a, tp1, len);
//   memset(tp1 + len, 0, sizeof(ll) * len);
//   polyinv(a, ans, len);
//   NTT(ans, len << 1, 1);
//   NTT(tp1, len << 1, 1);
//   for (int i = 0; i < (len << 1); i++) tp1[i] = tp1[i] * ans[i] % mod;
//   NTT(tp1, len << 1, -1);
//   jifen(tp1, ans, len);
// }
// // 多项式exp，a[0]==0，O(nlogn)
// void polyexp(ll* a, ll* ans, int len) {
//   static ll tp2[maxn];
//   memset(tp2, 0, sizeof(ll) * (len << 1));
//   memset(ans, 0, sizeof(ll) * (len << 1));
//   ans[0] = 1;
//   for (int h = 2; h <= len; h <<= 1) {
//     polyln(ans, tp2, h);
//     tp2[0] = ((a[0] + 1) % mod - tp2[0] + mod) % mod;
//     for (int i = 1; i < h; i++) tp2[i] = (a[i] - tp2[i] + mod) % mod;
//     memset(tp2 + h, 0, sizeof(ll) * h);
//     NTT(ans, h << 1, 1);
//     NTT(tp2, h << 1, 1);
//     for (int i = 0; i < (h << 1); i++) ans[i] = ans[i] * tp2[i] % mod;
//     NTT(ans, h << 1, -1);
//     memset(ans + h, 0, sizeof(ll) * h);
//   }
// }
// // 多项式开根，O(nlogn)
// void polysqrt(ll* a, ll* ans, int len) {
//   static ll tp3[maxn], tp4[maxn];
//   memset(tp3, 0, sizeof(ll) * (len << 1));
//   memset(tp4, 0, sizeof(ll) * (len << 1));
//   memset(ans, 0, sizeof(ll) * (len << 1));
//   ans[0] = modsqrt(a[0]);  // 二次剩余
//   ll inv2 = quickpow(2, mod - 2);
//   for (int h = 2; h <= len; h <<= 1) {
//     polyinv(ans, tp3, h);
//     memcpy(tp4, a, sizeof(ll) * h);
//     NTT(tp3, h << 1, 1);
//     NTT(tp4, h << 1, 1);
//     NTT(ans, h << 1, 1);
//     for (int j = 0; j < (h << 1); j++)
//       ans[j] =
//           (ans[j] * ans[j] % mod + tp4[j]) % mod * inv2 % mod * tp3[j] % mod;
//     NTT(ans, h << 1, -1);
//     memset(ans + h, 0, sizeof(ll) * h);
//   }
// }

}  // namespace poly
typedef long long ll;
const int maxn = 1e6 + 10;
const int mod = 998244353;

int n;
int c[maxn], w[maxn];
int p[maxn], pre[maxn], invp[maxn];
int ea[maxn], eb[maxn];
int fa[maxn], fb[maxn];
int ta[maxn], tb[maxn], tw[maxn];

void solve(int l, int r) {
  if (l == r) {
    if (l) {
      ea[l + 1] = ((ea[l] - (1ll - p[l]) * fa[l] % mod * pre[l]) % mod + mod) *
                  invp[l] % mod;
      eb[l + 1] =
          ((eb[l] - c[l] - (1ll - p[l]) * fb[l] % mod * pre[l]) % mod + mod) *
          invp[l] % mod;
    }
    return;
  }
  int mid = (l + r) >> 1;
  solve(l, mid);
  // !!!important
  for (int i = 0; i < maxn && i <= 2 * (r - l); i++) ta[i] = tb[i] = tw[i] = 0;
  for (int i = l; i <= mid; i++) ta[i - l] = ea[i], tb[i - l] = eb[i];
  for (int i = 1; i <= r - l; i++) tw[i] = w[i];
  poly::polymul(ta, tw, ta, r - l, r - l);
  poly::polymul(tb, tw, tb, r - l, r - l);
  for (int i = mid + 1; i <= r; i++) {
    fa[i] = (fa[i] + ta[i - l]) % mod;
    fb[i] = (fb[i] + tb[i - l]) % mod;
  }
  solve(mid + 1, r);
}

signed main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  poly::init();
  int _;
  cin >> _;
  while (_--) {
    cin >> n;
    for (int i = 0; i < n; i++) {
      int x;
      cin >> x >> c[i];
      p[i] = x * poly::invi[100] % mod;
      invp[i] = 100ll * poly::invi[x] % mod;
    }
    for (int i = 1; i < n; i++) {
      cin >> w[i];
      pre[i] = (pre[i - 1] + w[i]) % mod;
    }
    for (int i = 1; i < n; i++) pre[i] = poly::quickpow(pre[i], mod - 2);
    for (int i = 0; i <= n; i++) fa[i] = fb[i] = 0;
    ea[0] = 1, eb[0] = 0;
    ea[1] = 1, eb[1] = (mod - c[0]) % mod;
    solve(0, n - 1);
    int ans = (mod - eb[n]) * poly::quickpow(ea[n], mod - 2) % mod;
    cout << (ans + mod) % mod << 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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258

1002、Boss Rush

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

题意：

小Q有 $n$ 个技能，每个技能点击后需要再过 $t_i$ 时间才能点击其他技能，对于每个技能 $i$ ，点击后的 $le{n}_i$ 时间内均会造成伤害 $d_{i,j}$ ，boss 的血量为 $H$ ，问最早多久可以打败 boss

题解：

其实感觉题目有些问题，题解的意思似乎是不考虑顺序，这里的 $n$ 比较小 $(n\le 15)$ ，可以乱搞，二分+状压可以轻松做出

代码：

#include 
#define int long long
using namespace std;
const int maxn = 20;
const int maxm = 1e5 + 5;
int t[maxm], len[maxm];
int d[maxn][maxm];
int tim[1 << maxn], dp[1 << maxn];
int n, hp;
bool check(int x) {
  memset(dp, -1, sizeof(dp));
  dp[0] = 0;
  for (int st = 0; st < 1 << n; st++) {
    int w = dp[st];
    if (w >= hp) return 1;
    if (w < 0 || tim[st] > x) continue;
    for (int i = 0; i < n; i++)
      if (!(st >> i & 1))
        if (tim[st] + len[i] - 1 <= x)
          dp[st | (1 << i)] = max(dp[st | (1 << i)], w + d[i][len[i] - 1]);
        else
          dp[st | (1 << i)] = max(dp[st | (1 << i)], w + d[i][x - tim[st]]);
  }
  return 0;
}
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 >> hp;
    int ans = -1;
    int l = 0, r = 0;
    for (int i = 0; i < n; i++) {
      cin >> t[i] >> len[i];
      r += t[i] + len[i];
      for (int j = 0; j < len[i]; j++) cin >> d[i][j];
      for (int j = 1; j < len[i]; j++) d[i][j] += d[i][j - 1];
    }
    for (int st = 1; st < (1 << n); st++)
      tim[st] = tim[st - (st & -st)] + t[__builtin_ctz(st & -st)];
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (check(mid))
        r = (ans = mid) - 1;
      else
        l = mid + 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

1003、Cyber Language

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

题意：

给一堆句子，句子中包含几个单词，输出单词的首字母大写

题解：

~~

代码：

#include 
using namespace std;
string s;
int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  int _;
  cin >> _;
  getchar();
  while (_--) {
    getline(cin, s);
    int len = s.length();
    for (int i = 0; i < len; i++)
      if (i == 0 || s[i - 1] == ' ') cout << (char)toupper(s[i]);
    cout << endl;
  }
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1008、Laser Alarm

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

空间中有 $n$ 条线段 $n\le 50$ ，求一个与线段交点最多的平面

题解：

由于 $n$ 比较小，所以可以乱搞，三点确定一个平面，所以我们枚举所有三点对即可，然后遍历计数
代码：

#include 
using namespace std;
const int maxn = 55;
struct node {
  int x, y, z;
  node(int _x = 0, int _y = 0, int _z = 0) : x(_x), y(_y), z(_z) {}
  node operator-(const node& p) const {
    return node(x - p.x, y - p.y, z - p.z);
  }
  node operator*(const node& p) const {
    return node(y * p.z - z * p.y, z * p.x - x * p.z, x * p.y - y * p.x);
  }
  int operator^(const node& p) const { return x * p.x + y * p.y + z * p.z; }
  bool operator==(const node& p) const {
    return x == p.x && y == p.y && z == p.z;
  }
} p[maxn * 2];
int ptoplane(const node& a, const node& b, const node& c, const node& p) {
  return ((b - a) * (c - a)) ^ (p - a);
}
bool colinear(const node& a, const node& b, const node& p) {
  node t = (a - b) * (b - p);
  return !t.x && !t.y && !t.z;
}
int n;
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;
    for (int i = 1; i <= n * 2; i++) cin >> p[i].x >> p[i].y >> p[i].z;
    int ans = 1;
    for (int i = 1; i <= n * 2; i++) {
      for (int j = 1; j < i; j++) {
        if (p[i] == p[j]) continue;
        for (int k = 1; k < j; k++) {
          if (p[i] == p[j] || p[i] == p[k] || p[j] == p[k]) continue;
          if (colinear(p[i], p[j], p[k])) continue;
          int now = 0;
          for (int l = 1; l <= n; l++) {
            int x = ptoplane(p[i], p[j], p[k], p[l * 2 - 1]);
            int y = ptoplane(p[i], p[j], p[k], p[l * 2]);
            if (!x || !y || (x < 0 && y > 0) || (x > 0 && y < 0)) now++;
          }
          ans = max(ans, now);
        }
        int now = 0;
        for (int k = 1; k <= n; k++) {
          if (colinear(p[i], p[j], p[k * 2 - 1]) ||
              colinear(p[i], p[j], p[k * 2]))
            now++;
        }
        ans = max(ans, now);
      }
    }
    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
60
61
62
63

1009、Package Delivery

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

题意：

小Q有 $n$ 个包裹，每个包裹都有一个区间时间，小Q必须在截至前拿走包裹，每次小Q最多可以拿 $k$ 个，问小Q最少去邮局多少次

题解：

贪心即可，或者说尽量拖延就行，关注每个包裹的截至时间，在这个时间拿走包裹，顺便拿走其他截至时间早的就行。

下面这个算法看似是 $O(n^2)$ 的，实际上线性时间内可以通过

代码：

#include 
#define pii pair<int, int>
using namespace std;
const int maxn = 1e5 + 5;
int n, k;
int ql[maxn], qr[maxn];
pii p[maxn];
bool vis[maxn];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    memset(vis, 0, sizeof vis);
    priority_queue<pii, vector<pii>, greater<pii>> q;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
      cin >> p[i].first >> p[i].second;
      ql[i] = qr[i] = i;
    }
    sort(ql + 1, ql + 1 + n,
         [](int a, int b) { return p[a].first < p[b].first; });
    sort(qr + 1, qr + 1 + n,
         [](int a, int b) { return p[a].second < p[b].second; });
    int res = 0;
    for (int i = 1, j = 1; i <= n; i++) {
      if (vis[qr[i]]) continue;
      while (j <= n && p[ql[j]].first <= p[qr[i]].second) {
        q.push({p[ql[j]].second, ql[j]});
        j++;
      }
      for (int l = 1; l <= k; l++) {
        if (q.empty()) break;
        vis[q.top().second] = true;
        q.pop();
      }
      res++;
    }
    cout << res << endl;
  }
}
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

1011、Taxi

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

题意：

有 $n$ 个城镇，每个城镇有一个坐标，小Q有张VIP卡，假如小Q从 $(x^{\prime },y^{\prime })$ 前往 $(x_k,y_k)$ ，那么VIP卡可以帮他报销 min ⁡ { ∣ x ′ − x k ∣ + ∣ y ′ − y k ∣ , ω k } \min \{|x'-x_k|+|y'-y_k|, \omega_k \} min{∣x′−xk​∣+∣y′−yk​∣,ωk​} 元。小Q想要去充分利用他的VIP卡，给出 $q$ 个询问，每次询问给出一个坐标，要求找到VIP打折最多的一个地点。

题解：

这题用到了一些关于切比雪夫距离的一些技巧。没有 $\omega$ 的限制的话，其实是一道很经典的问题。

max ⁡ { ∣ x ′ − x i ∣ + ∣ y ′ − y i ∣ } = max ⁡ { max ⁡ { x ′ − x i , − x ′ + x i } + max ⁡ { y ′ − y i , − y ′ + y i } } = max ⁡ { [ ( x ′ + y ′ ) + ( − x i − y i ) ] , [ ( x ′ − y ′ ) + ( − x i + y i ) ] , [ ( − x ′ + y ′ ) + ( x i − y i ) ] , [ ( − x ′ − y ′ ) + ( x i + y i ) ] } \max \{ |x'-x_i|+|y'-y_i| \} \\ =\max \{ \max\{x'-x_i,-x'+x_i\}+\max\{ y'-y_i, -y'+y_i\}\}\\=\max\{[(x'+y')+(-x_i-y_i)],[(x'-y')+(-x_i+y_i)],[(-x'+y')+(x_i-y_i)],[(-x'-y')+(x_i+y_i)]\} max{∣x′−xi​∣+∣y′−yi​∣}=max{max{x′−xi​,−x′+xi​}+max{y′−yi​,−y′+yi​}}=max{[(x′+y′)+(−xi​−yi​)],[(x′−y′)+(−xi​+yi​)],[(−x′+y′)+(xi​−yi​)],[(−x′−y′)+(xi​+yi​)]} 于是，记录 $(-x_i-y_i),(-x_i+y_i),(x_i-y_i),(x_i+y_i)$ 的最大值即可 $O(1)$ 内查询，现考虑加入 $\omega$ 的影响

先按 $\omega$ 的大小对这些点排一个序，并记录一下区间后缀的距离最大值，进行分治二分即可

代码：

#include 
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n, q;
struct node {
  int x, y;
  int w;
} p[maxn];
int a[maxn], b[maxn], c[maxn], d[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 >> q;
    for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y >> p[i].w;
    sort(p + 1, p + n + 1,
         [](const node &a, const node &b) { return a.w < b.w; });
    a[n + 1] = b[n + 1] = c[n + 1] = d[n + 1] = -inf;
    for (int i = n; i > 0; i--) {
      a[i] = max(a[i + 1], -p[i].x - p[i].y);
      b[i] = max(b[i + 1], -p[i].x + p[i].y);
      c[i] = max(c[i + 1], p[i].x - p[i].y);
      d[i] = max(d[i + 1], p[i].x + p[i].y);
    }
    while (q--) {
      int x, y;
      cin >> x >> y;
      int ans = 0;
      int l = 1, r = n, mid;
      while (l <= r) {
        mid = (l + r) >> 1;
        int tmp = max(max(x + y + a[mid], x - y + b[mid]),
                      max(-x + y + c[mid], -x - y + d[mid]));
        if (p[mid].w < tmp) {
          l = mid + 1;
          ans = max(ans, p[mid].w);
        } else {
          r = mid - 1;
          ans = max(ans, tmp);
        }
      }
      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

1012、Two Permutations

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

题意：

给出两个排列和一个序列，求两个排列组合成这个序列的方案数，两个排列的长均为 $n$ ，序列长为 $2n$ ，每次总是将排列 $P、Q$ 的最左端放进序列 $S$ 的最右侧。 $n\le 3\times 10^5$

题解：

很显然是一道 dp 题，那么该怎么去 dp 呢。表面上看，状态似乎是 $n^2$ ，但实际上，有很多无效的状态，根据数据规模，其状态应该是 $O(n)$ 级别的。设 $d{p}_{i,j}$ 表示匹配至序列 $S$ 的第 $i$ 位， 并且最后一次匹配来源于 $j=1/2$ ，那么有递归式： $d{p}_{i,j}=judg{e}_1\times d{p}_{i-1,j}+judg{e}_2\times d{p}_{i-1,j\oplus 1}$

代码：

#include 
using namespace std;
const int mod = 998244353;
const int maxn = 3e5 + 5;
int p[maxn], q[maxn];
int s[maxn * 2];
int n;
int dp[2 * maxn][2];
int dfs(int i, int j, int flag) {
  // 匹配完 p_i, q_j 的方案数， flag 0 \ 1 代表从 p \ q 进入新匹配
  if (i <= 0 && j <= 0) return 1;
  if (dp[i + j][flag] != -1) return dp[i + j][flag];
  int ans = 0;
  if (p[i] == s[i + j] && i > 0) ans = (ans + dfs(i - 1, j, 0)) % mod;
  if (q[j] == s[i + j] && j > 0) ans = (ans + dfs(i, j - 1, 1)) % mod;
  return dp[i + j][flag] = ans;
}
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 (_--) {
    memset(dp, -1, sizeof(dp));
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 1; i <= n; i++) cin >> q[i];
    for (int i = 1; i <= 2 * n; i++) cin >> s[i];
    cout << dfs(n, n, 0) << 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

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

不会X

1004、Divide the Sweets

1005、Spanning Tree Game

1006、Dusk Moon

1007、Shallow Moon

1010、Range Reachability Query