2022牛客多校（四）

2022牛客多校（四）

一、比赛小结

比赛链接： "蔚来杯"2022牛客暑期多校训练营4

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

A、Task Computing

题目链接：A-Task Computing

题意：

从 $n$ 个任务中选 $m$ 个元素 $(a_1,a_2,\dots ,a_m)$ 出来并任意排序，收益是 $\sum _{i=1}^m{\omega }_{a_i}\prod _{j=0}^{i-1}{p}_{a_j}$ ,求最大收益

题解：

对于这个复杂的多元和式，我们先比较一下双元关系，我们考虑中间相邻的两个下标 $x$ 和 $y$ ：

$R_x=\sum _{i=1}^{x-1}{\omega }_{a_i}\prod _{j=0}^{i-1}{p}_{a_j}+{\omega }_{a_x}\prod _{j=0}^{x-1}{p}_{a_j}+{\omega }_{a_y}{p}_{a_x}\prod _{j=0}^{x-1}{p}_{a_j}+\sum _{i=y+1}^m{\omega }_{a_i}\prod _{j=0}^{i-1}{p}_{a_j}$

$R_y=\sum _{i=1}^{x-1}{\omega }_{a_i}\prod _{j=0}^{i-1}{p}_{a_j}+{\omega }_{a_y}\prod _{j=0}^{x-1}{p}_{a_j}+{\omega }_{a_x}{p}_{a_y}\prod _{j=0}^{x-1}{p}_{a_j}+\sum _{i=y+1}^m{\omega }_{a_i}\prod _{j=0}^{i-1}{p}_{a_j}$

那么对于最优解里，相邻的下标一定满足

$R_x-R_y=({\omega }_{a_x}+{\omega }_{a_y}{p}_{a_x}-{\omega }_{a_y}-{\omega }_{a_x}{p}_{a_y}){\prod }_{j=0}^{x-1}{p}_{a_j}\ge 0$

所以我们可以按照这个关系排个偏序，那么最终答案一定是这个偏序里的一个子序列，剩下的问题 dp 可以解决

设 $d{p}_{i,j}$ 表示从后往前考虑了 $i$ 个任务，选择了 $j$ 个任务的最优收益，初始值 $d{p}_{m+1,0}=0$ 转移方程为： d p i , j = max ⁡ { d p i + 1 , j , d p i + 1 , j − 1 × p i + ω i } dp_{i,j}=\max \{ dp_{i+1,j},dp_{i+1,j-1}\times p_i+\omega_i\} dpi,j​=max{dpi+1,j​,dpi+1,j−1​×pi​+ωi​}

答案为 $d{p}_{1,m}$

代码：

#include 
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
struct node {
  double w, p;
  bool operator<(const node &a) const { return w * (1 - a.p) > a.w * (1 - p); }
} a[maxn];
int n, m;
double dp[maxn][25];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i].w;
  for (int i = 1; i <= n; i++) cin >> a[i].p, a[i].p /= 10000;
  sort(a + 1, a + 1 + n);
  memset(dp, -inf, sizeof dp);
  dp[n + 1][0] = 0;
  for (int i = n; i >= 1; i--) {
    dp[i][0] = 0;
    for (int j = 0; j <= m; j++)
      dp[i][j + 1] = max(dp[i + 1][j + 1], a[i].w + a[i].p * dp[i + 1][j]);
  }
  cout << fixed << setprecision(10) << dp[1][m] << 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

C、Easy Counting Problem

题目链接：C-Easy Counting Problem

题意：

统计长度为 $n$ 且数位 $i$ 出现至少 $c_i$ 次的数字串数量，数字串由 $\omega$ 个不同的数码组成。

题解：

由 EDG 得出，答案为

$ans=[\frac{x^n}{n!}]\prod _{k=0}^{\omega -1}(\exp (x)-\sum _{i=0}^{c_k-1}\frac{x^i}{i!})$

鉴于 $\omega$ 比较小，可以将这个求积式暴力展开，令 $y=\exp (x),f_k={\sum }_{i=0}^{c_k-1}\frac{x^i}{i!}$

那么这个积式就可以变成一个关于 $y$ 的多项式，系数为 $f_k$ 的乘积，暴力展开为 $\sum _i(\prod _j{f}_j\exp (x{)}^i)$

代码：

#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)
//     ;
//   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 maxm = 1e7 + 10;
const int mod = 998244353;

int w, s;
int c[15];
int dp[15][maxn];
int tmp[maxn];
int tot = 1ll << 17;
int fc[maxm], ifc[maxm];

void init(int n) {
  fc[0] = 1;
  for (int i = 1; i <= n; i++) fc[i] = fc[i - 1] * i % mod;
  ifc[n] = poly::quickpow(fc[n], mod - 2);
  for (int i = n - 1; i >= 0; i--) ifc[i] = ifc[i + 1] * (i + 1) % mod;
}

int solve(int n) {
  int res = 0;
  for (int j = 0; j <= w; j++) {
    int inv = j ? poly::quickpow(j, mod - 2) : 0;
    int pow = poly::quickpow(j, n);
    for (int i = 0; i < tot && n - i >= 0; i++) {
      int a = dp[j][i] * pow % mod * ifc[n - i] % mod;
      pow = pow * inv % mod;
      res = (res + a) % mod;
    }
  }
  res = res * fc[n] % mod;
  return res;
}

signed main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  init(maxm - 2);
  poly::init();
  cin >> w;
  s = 0;
  for (int i = 0; i < w; i++) {
    cin >> c[i];
    s += c[i];
  }
  dp[1][0] = 1;
  for (int i = 0; i < c[0]; i++) dp[0][i] = (mod - ifc[i]);
  poly::NTT(dp[0], tot, 1);
  poly::NTT(dp[1], tot, 1);
  for (int i = 1; i < w; i++) {
    for (int j = 0; j < c[i]; j++) tmp[j] = (mod - ifc[j]);
    for (int j = c[i]; j < tot; j++) tmp[j] = 0;
    poly::NTT(tmp, tot, 1);
    for (int j = w; j > 0; j--) {
      for (int k = 0; k < tot; k++)
        dp[j][k] = (dp[j - 1][k] + dp[j][k] * tmp[k]) % mod;
    }
    for (int k = 0; k < tot; k++) dp[0][k] = dp[0][k] * tmp[k] % mod;
  }
  for (int j = 0; j <= w; j++) poly::NTT(dp[j], tot, -1);
  int q;
  cin >> q;
  while (q--) {
    int x;
    cin >> x;
    if (s > x)
      cout << "0\n";
    else
      cout << solve(x) << 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
259
260
261
262
263
264

D、Jobs (Easy Version)

题目链接：D-Jobs (Easy Version)

题意：

有 $n$ 个公司，第 $i$ 个公司有 $m_i$ 个工作，每个工作对三个能力分别有数值要求，必须三个能力都达标才能胜任这份工作。一个人只要能胜任一个公司的任意一份工作就可以去这个公司工作。能力的数值不超过400。

询问 $q$ 次，每次询问一个三元组，代表一个人三个能力的数值，求这个人可以去多少个公司工作。

题解：

注意到能力的数值不超过400，所以可以乱搞 ，开一个长度为 $n$ 的 bitset ，以及 400*400*400 大小的空间，每个节点放一个 bitset ，记录这个节点是否满足要求。

代码：

#include 
using namespace std;
const int maxm = 401;
const int mod = 998244353;

int g[maxm][maxm][maxm], pc[1 << 10];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  for (int i = 1; i < (1 << 10); ++i) pc[i] = pc[i >> 1] + (i & 1);

  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; ++i) {
    int k;
    cin >> k;
    while (k--) {
      int a, b, c;
      cin >> a >> b >> c;
      g[a][b][c] |= (1 << i);
    }
  }

  for (int i = 0; i + 1 < maxm; ++i)
    for (int j = 0; j < maxm; ++j)
      for (int k = 0; k < maxm; ++k) g[i + 1][j][k] |= g[i][j][k];

  for (int j = 0; j + 1 < maxm; ++j)
    for (int i = 0; i < maxm; ++i)
      for (int k = 0; k < maxm; ++k) g[i][j + 1][k] |= g[i][j][k];

  for (int k = 0; k + 1 < maxm; ++k)
    for (int i = 0; i < maxm; ++i)
      for (int j = 0; j < maxm; ++j) g[i][j][k + 1] |= g[i][j][k];

  int seed, lastans = 0;
  cin >> seed;
  std::mt19937 rng(seed);
  std::uniform_int_distribution<> u(1, 400);
  int ans = 0, cnt = 0;
  while (q--) {
    int IQ = (u(rng) ^ lastans) % 400 + 1;  // The IQ of the i-th friend
    int EQ = (u(rng) ^ lastans) % 400 + 1;  // The EQ of the i-th friend
    int AQ = (u(rng) ^ lastans) % 400 + 1;  // The AQ of the i-th friend
    lastans = pc[g[IQ][EQ][AQ]];            // The answer to the i-th friend
    ans = (ans * seed % mod + lastans) % mod;
  }
  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

H、Wall Builder II

题目链接：H-Wall Builder II

题意：

给n个1*1的矩形，n-1 个 1*2 的矩形，n-2 个 1*3 的矩形 …，1 个 1*n 的矩形，把这些矩形拼成一个大矩形，求大矩形的最小周长。

题解：

面积是可知的，对其进行因数分解，然后逐个 check 。check 时贪心地放就行， $n$ 比较小 $(n\le 100)$ ，可以乱搞。

代码：

#include 
using namespace std;
const int maxn = 200;
int n;
int cnt[maxn];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    cin >> n;
    for (int i = 1; i <= n; i++) cnt[i] = n - i + 1;
    int S = n * (n + 1) * (n + 2) / 6;
    int a = sqrt(S);
    while (S % a != 0) a--;
    int b = S / a;
    cout << (a + b) * 2 << endl;
    if (a < b) swap(a, b);
    for (int i = 0; i < b; i++) {
      int tmp = a;
      for (int j = n; j >= 1 && tmp; j--)
        while (cnt[j] && j <= tmp) {
          cout << a - tmp << " " << i << " " << a - tmp + j << " " << i + 1
               << endl;
          cnt[j]--;
          tmp -= j;
        }
    }
  }
  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

K、NIO’s Sword

题目链接：K-NIO’s Sword

题意：

玩家初始有一把攻击力为0的剑，需要依次击杀 n 个敌人，仅当攻击力模 n 与 i 同余才能击杀第 i 个敌人。玩家可以升级剑，每次升级相当于在当前攻击力后面添加一个数字，问最少需要几次升级。

题解：

问题由独立的子问题构成，每次操作可以由 $v\to 10\times v+u$ ，升级 $k$ 次意味着 $(i-1)\times 10^k+r\equiv i(\mathrm{mod}n)$ ，对这个问题独立求解即可，注意特判 $n=1$

代码：

#include 
#define int long long
using namespace std;
int n;
signed main() {
  //  freopen("in.txt", "r", stdin);
  //  freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  if (n == 1) {
    cout << 0;
    return 0;
  }
  int A = 0ll;
  int cnt = 0ll, ans = 0ll;
  while (cnt < n) {
    // 进攻完 i = cnt  准备进攻 i = cnt + 1
    // 已有 A = cnt  (mod n)
    int x = (1ll - 9ll * cnt % n + n) % n;
    if (0ll <= x && x <= 9ll) {
      A = (10ll * A + x) % n;
      cnt++;
      ans++;
      continue;
    }
    int y = (1ll - 99ll * cnt % n + n) % n;
    if (0ll <= y && y <= 99ll) {
      A = (100ll * A + y) % n;
      cnt++;
      ans += 2ll;
      continue;
    }
    int z = (1ll - 999ll * cnt % n + n) % n;
    if (0ll <= z && z <= 999ll) {
      A = (1000ll * A + z) % n;
      cnt++;
      ans += 3ll;
      continue;
    }
    int w = (1ll - 9999ll * cnt % n + n) % n;
    if (0ll <= w && w <= 9999ll) {
      A = (10000ll * A + w) % n;
      cnt++;
      ans += 4ll;
      continue;
    }
    int v = (1ll - 99999ll * cnt % n + n) % n;
    if (0ll <= v && v <= 99999ll) {
      A = (100000ll * A + v) % n;
      cnt++;
      ans += 5ll;
      continue;
    }
    int u = (1ll - 999999ll * cnt % n + n) % n;
    if (0ll <= u && u <= 999999ll) {
      A = (1000000ll * A + u) % n;
      cnt++;
      ans += 6ll;
      continue;
    }
    int t = (1ll - 9999999ll * cnt % n + n) % n;
    if (0ll <= t && t <= 9999999ll) {
      A = (10000000ll * A + t) % n;
      cnt++;
      ans += 7ll;
      continue;
    }
  }
  cout << ans;
  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

L、Black Hole

题目链接：L-Black Hole

题意：

求边长为 $a$ 的凸正 $n$ 面体收缩 $k$ 次后的面数和边长，一次收缩定义为作该几何体所有面中心的三维凸包。

1 ≤ n ≤ 200, 1 ≤ a ≤ 1000, 1 ≤ k ≤ 20, 1 ≤ T ≤ 100

题解：

凸正多面体只有5种 ，欧拉公式：V+F-E=2

取凸正多面体一个顶点，设其向外有n(n≥3)条棱；

再取凸正多面体一个面，设其为正m(m≥3)边形；则V，F，E，n，m均为正整数

由于这个顶点附近的角必满足加起来小于360°(否则就平了)，有：

$n\cdot (180-\frac{360}{m})<360\Rightarrow 1-\frac{2}{m}<\frac{2}{n}$ ，

该式子只有 5 个解，考虑用V，F表示边数：$E=\frac{nV}{2}=\frac{mF}{2}$

代入欧拉公式： F=4,8,20,6,12 ，其顶点数分别为：V=4,6,12,8,20

发现在收缩的定义下：正四面体→正四面体，正八面体→正六面体，正六面体→正八面体，正十二面体→正二十面体，正二十面体→正十二面体

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aPDEwNJz-1663160733509)(file:///C:/Users/lenovo/AppData/Roaming/marktext/images/2022-09-14-15-49-25-image.png?msec=1663141784253)]

代码：

#include 
using namespace std;
const long double PI = acosl(-1);

int n, k;
long double a;

void shrink(int &n, long double &a) {
  int N = -1;
  long double A;
  if (n == -1) return;
  if (n == 4) {
    N = 4;
    A = a / 3;
  }
  if (n == 6) {
    N = 8;
    A = a / sqrtl(2);
  }
  if (n == 8) {
    N = 6;
    A = sqrtl(2) * a / 3;
  }
  if (n == 12) {
    N = 20;
    A = a * (3 * sqrtl(5) + 5) / 10;
  }
  if (n == 20) {
    N = 12;
    A = a * (sqrtl(5) + 1) / 6;
  }
  n = N, a = A;
}

int main() {
  int _;
  cin >> _;
  while (_--) {
    cin >> n >> a >> k;
    while (k--) shrink(n, a);
    if (n == -1)
      cout << "impossible\n";
    else
      cout << fixed << setprecision(12) << "possible " << n << " " << a << 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

M、Monotone Chain

题目链接：M-Monotone Chain

题意：

给定一条折线，求一条有向直线使得折线上的各点在直线上的投影是单调的。

题解：

其实题目很简单，对于折线上的每条线段，其要求的有向直线的角度位于一个长度为 $\pi$ 的区间中，那么对所有线段求一个交集即可

代码：

#include 

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ai3 = array<int, 3>;
using al3 = array<ll, 3>;
mt19937 mrnd(std::random_device{}());

int rnd(int mod) { return mrnd() % mod; }

// region 计算几何基础
using cgt = ll;
const cgt EPS = 0;
const cgt PI = acosl(-1);

inline int sign(cgt a) { return a < -EPS ? -1 : a > EPS; }

inline int cmp(cgt a, cgt b) { return sign(a - b); }

struct P {
  cgt x, y;

  P() {}

  P(cgt _x, cgt _y) : x(_x), y(_y) {}

  P operator+(P p) const { return {x + p.x, y + p.y}; }

  P operator-(P p) const { return {x - p.x, y - p.y}; }

  P operator*(cgt d) const { return {x * d, y * d}; }

  P operator/(cgt d) const { return {x / d, y / d}; }

  P operator-() const { return {-x, -y}; }

  bool operator<(P p) const {
    int c = cmp(x, p.x);
    if (c) return c == -1;
    return cmp(y, p.y) == -1;
  }

  bool operator==(P p) const { return cmp(x, p.x) == 0 && cmp(y, p.y) == 0; }

  cgt distTo(P p) const { return (*this - p).abs(); }

  cgt distTo2(P p) const { return (*this - p).abs2(); }

  cgt alpha() const { return atan2(y, x); }

  cgt abs() const { return sqrt(abs2()); }

  cgt abs2() const { return x * x + y * y; }

  // 逆时针转90
  P rot90() const { return {-y, x}; }

  P unit() const { return *this / abs(); }

  // 1: x轴上方, [0, PI), 0: x轴下方, [-PI, 0)
  int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }

  // 逆时针转
  P rot(cgt ang) const {
    return {x * cos(ang) - y * sin(ang), x * sin(ang) + y * cos(ang)};
  }

  friend std::istream &operator>>(std::istream &is, P &a) {
    ll _x, _y;
    cin >> _x >> _y;
    a.x = _x, a.y = _y;
    return is;
  }

  friend std::ostream &operator<<(std::ostream &os, const P &a) {
    return os << "(" << a.x << ", " << a.y << ")";
  }
};

struct L {
  // ps[0] -> ps[1]
  P ps[2];

  L() {}

  L(P a, P b) {
    ps[0] = a;
    ps[1] = b;
  }

  P &operator[](int i) { return ps[i]; }

  P dir() const { return ps[1] - ps[0]; }

  L push() const {
    P delta = (ps[1] - ps[0]).rot90().unit() * EPS;
    return {ps[0] + delta, ps[1] + delta};
  }
};

#define dot(p1, p2) ((p1).x * (p2).x + (p1).y * (p2).y)
#define det(p1, p2) ((p1).x * (p2).y - (p1).y * (p2).x)
#define cross(p1, p2, p3) \
  ((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y))
#define crossOp(p1, p2, p3) sign(cross(p1, p2, p3))
#define scalar(p1, p2, p3) \
  ((p2.x - p1.x) * (p3.x - p1.x) + (p2.y - p1.y) * (p3.y - p1.y))
#define scalarOp(p1, p2, p3) sign(scalar(p1, p2, p3))

// 直线 p1p2, q1q2 是否相交
bool isLL(P p1, P p2, P q1, P q2) {
  cgt a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
  return sign(a1 + a2) != 0;
}

// 直线 p1p2, q1q2 交点
P getLL(P p1, P p2, P q1, P q2) {
  cgt a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
  return (p1 * a2 + p2 * a1) / (a1 + a2);
}

// 直线 l1, l2 交点
P getLL(L l1, L l2) { return getLL(l1[0], l1[1], l2[0], l2[1]); }

// 区间 [l1, r1], [l2, r2] 是否重叠
bool intersect(cgt l1, cgt r1, cgt l2, cgt r2) {
  if (l1 > r1) swap(l1, r1);
  if (l2 > r2) swap(l2, r2);
  return !(cmp(r1, l2) == -1 || cmp(r2, l1) == -1);
}

// 线段 p1p2, q1q2 是否相交(重叠 => 相交, 端点 => 相交)
bool isSS(P p1, P p2, P q1, P q2) {
  return intersect(p1.x, p2.x, q1.x, q2.x) &&
         intersect(p1.y, p2.y, q1.y, q2.y) &&
         crossOp(p1, p2, q1) * crossOp(p1, p2, q2) <= 0 &&
         crossOp(q1, q2, p1) * crossOp(q1, q2, p2) <= 0;
}

// 线段 p1p2, q1q2 是否严格相交(重叠 !=> 相交, 端点 !=> 相交)
bool isSSStrict(P p1, P p2, P q1, P q2) {
  return crossOp(p1, p2, q1) * crossOp(p1, p2, q2) < 0 &&
         crossOp(q1, q2, p1) * crossOp(q1, q2, p2) < 0;
}

// m 是否在 [a, b] 之间
bool isMiddle(cgt a, cgt b, cgt m) {
  return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}

// m 是否在 以a, b为对角线的矩形内, 含边界
bool isMiddle(P a, P b, P m) {
  return isMiddle(a.x, b.x, m.x) && isMiddle(a.y, b.y, m.y);
}

// q 是否在线段 p1p2 上(在端点上 => 在线段上)
bool onSeg(P p1, P p2, P q) {
  return crossOp(p1, p2, q) == 0 && isMiddle(p1, p2, q);
}

// q 是否严格在线段 p1p2 上(在端点上 !=> 在线段上)
bool onSegStrict(P p1, P p2, P q) {
  return crossOp(p1, p2, q) == 0 &&
         sign(dot(q - p1, p1 - p2) * sign(dot(q - p2, p1 - p2))) < 0;
}

// q 到 直线 p1p2 的投影(垂足) 要求: p1 != p2
P proj(P p1, P p2, P q) {
  P dir = p2 - p1;
  return p1 + dir * (dot(dir, q - p1) / dir.abs2());
}

// q 以 直线 p1p2 为对称轴的反射
P reflect(P p1, P p2, P q) { return proj(p1, p2, q) * 2 - q; }

// q 到 线段 p1p2 的最小距离
cgt nearest(P p1, P p2, P q) {
  if (p1 == p2) return p1.distTo(q);
  P h = proj(p1, p2, q);
  if (isMiddle(p1, p2, h)) return q.distTo(h);
  return min(p1.distTo(q), p2.distTo(q));
}

// 线段 p1p2, q1q2 的距离
cgt disSS(P p1, P p2, P q1, P q2) {
  if (isSS(p1, p2, q1, q2)) return 0;
  return min(min(nearest(p1, p2, q1), nearest(p1, p2, q2)),
             min(nearest(q1, q2, p1), nearest(q1, q2, p2)));
}

// 直线平行(无方向)
bool parallel(L l0, L l1) { return sign(det(l0.dir(), l1.dir())) == 0; }

// 直线同向(有方向)
bool sameDir(L l0, L l1) {
  return parallel(l0, l1) && sign(dot(l0.dir(), l1.dir())) == 1;
}

// endregion

const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
const int N = 1e5 + 10;

int n;
P a[N];

void solve() {
  vector<P> b;
  for (int i = 1; i <= n - 1; i++) {
    P p = a[i + 1] - a[i];
    if (p == P{0, 0}) continue;
    b.push_back(p);
  }

  if (b.empty()) {
    cout << "YES"
         << "\n";
    cout << "0 0 1 0"
         << "\n";
    return;
  }

  sort(b.begin(), b.end(), [](auto &a, auto &b) {
    int qa = a.quad(), qb = b.quad();
    if (qa != qb) return qa < qb;
    return sign(det(a, b)) > 0;
  });

  int m = b.size();
  b.resize(2 * m);
  for (int i = 0; i < m; i++) b[i + m] = b[i];
  int j = 0;
  for (int i = 0; i < m; i++) {
    j = max(j, i);
    while (j + 1 < i + m && sign(det(b[i], b[j + 1])) >= 0) j++;
    if (j - i + 1 == m) {
      cout << "YES"
           << "\n";
      P ans = b[i].rot90();
      cout << "0 0"
           << " " << ans.x << " " << ans.y << "\n";
      return;
    }
  }

  cout << "NO"
       << "\n";
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  solve();
  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
259
260
261

N、Particle Arts

题目链接：N-Particle Arts

题意：

初始时有 $n$ 个粒子，这些粒子会相互碰撞，每次碰撞时，粒子 $a、b$ 会变成 $a\&b、a|b$ 。可以证明最后粒子们会趋于稳定，求此时的均值和方差

题解：

稳定时必有 $a\&b=a、a|b=b$ 这种情况，将这些粒子降序排列，并拆成二进制格式，对每一位则必然是前面连续的 1 ，后面是连续的 0 。这样的话，贪心地填就行。

代码：

#include 
#define int long long
using namespace std;
int n, sum1, sum2;
int cnt[20];
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    sum1 += x;
    for (int j = 0, p = 1; j <= 15; j++, p <<= 1)
      if (x & p) cnt[j]++;
  }
  for (int i = 1; i <= n; i++) {
    int tmp = 0;
    for (int j = 0, p = 1; j <= 15; j++, p <<= 1)
      if (cnt[j]) {
        cnt[j]--;
        tmp += p;
      }
    sum2 += tmp * tmp;
  }
  sum2 = n * sum2 - sum1 * sum1;
  int n2 = n * n;
  int g = __gcd(n2, sum2);
  cout << sum2 / g << "/" << n2 / g << 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

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

不会做X

B、2D Internet Angel

E、Jobs (Hard Version)

F、Palindromic Tree

G、Wall Builder I

I、Three Body

J、Counting Fish Again