2022牛客多校（二）

2022牛客多校（二）

一、比赛小结

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

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

C、Link with Nim Game

题目链接：C-Link with Nim Game

题意：

有 n 堆石头，第 i 堆石头有 ai 个。Alice 和 Bob 轮流进行操作，Alice 先。每次操作可以从某一堆石头中取出正整数个石头，无法完成操作者输。在双方都采取最优策略的情况下，必败的一方希望尽可能慢的结束游戏，必胜的一方希望尽可能快的结束游戏。

求“游戏结束时进行的操作数量”和“第一轮可能进行的操作种类数”

题解：

两个问题都不是特别好处理，我们先用 nim 推些结论。若当前局面的石头数异或和为 0 ，则为必败局面，若当前局面的石头数异或和不为 0 ，则为必胜局面。仔细分析的话，他们的选取石头还是限制性挺高的，必胜者一方面需要让当前局面变成异或和为 0 的情况，一方面想快速将石子拿完。必败者则一方面需要让当前局面变成异或和不是 0 ，一方面想慢点拿完石头。

事实上，对于必败者，他可以通过选取一堆并拿走一颗石头，进而让必胜者也只能那走一块石头，可以考虑 lowbit 来思考。这样来看，问题就明了了。

若初始局面为必败态，则 ans1 为所有石头的和， ans2 约为石头堆数（需要用 lowbit 的限制筛掉一些）。若初始局面为必胜态，则 ans1 为所有石头和 - 先手第一次拿走的，ans2 可由相应情况来计数。

代码：

对于集合 s 的元素 e 和对应的a[i] 有：a[i] -= 1 等价于 a[i] ^= e

#include 
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
int n;
int a[maxn];
int sum, xsum;
// lose
void lose() {
  set<int> s, t;
  for (int i = 1; i <= n; i++) s.insert(a[i] ^ (a[i] - 1));
  for (int x : s)
    for (int i = 1; i <= n; i++)
      if (a[i] - (a[i] ^ x) > 1) {
        t.insert(x);
        break;
      }
  for (int x : t) s.erase(x);
  int ans = 0;
  for (int i = 1; i <= n; i++)
    if (s.count(a[i] ^ (a[i] - 1))) ans++;
  cout << sum << " " << ans << "\n";
}
// win
void win() {
  int mx = 0;
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int tmp = (a[i] ^ xsum);
    if (tmp < a[i]) {
      a[i] = a[i] - tmp;
      if (a[i] > mx) {
        mx = a[i];
        ans = 0;
      }
      if (a[i] == mx) ans++;
    }
  }
  cout << sum - mx + 1 << " " << ans << "\n";
}
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;
    sum = 0, xsum = 0;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      sum += a[i];
      xsum ^= a[i];
    }
    if (xsum == 0)
      lose();
    else
      win();
  }
  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

D、Link with Game Glitch

题目链接：D-Link with Game Glitch

题意：

$k\ast a_i$ 个物品 $b_i$ 可以换取 $k\ast \omega \ast c_i$ 个物品 $d_i$ ，求最大的 $\omega (0\le \omega \le 1)$ 使得，不存在一种换取方式，取出无限种每类物品。

题解：

很简单的一道图论题，从 $b_i$ 向 $d_i$ 连一条权为 $\omega \frac{c_i}{a_i}$ 的边，再对权取 $-\log$ ，于是问题转化为二分+判负环

代码：

#include 
using namespace std;
const int maxn = 1e3 + 5;
const double eps = 1e-10;
int n, m;
double dis[maxn];
int cnt[maxn];
bool vis[maxn];
struct edge {
  int v;
  double w;
  edge(int _v = 0, double _w = 0) : v(_v), w(_w) {}
};
vector<edge> e[maxn];
// 有负环返回 false
bool spfa(double mid) {
  memset(dis, 0x3f, sizeof dis);
  memset(vis, 0, sizeof vis);
  memset(cnt, 0, sizeof cnt);
  queue<int> q;
  for (int i = 1; i <= n; i++) q.push(i), vis[i] = true;
  while (!q.empty()) {
    int now = q.front();
    q.pop();
    vis[now] = 0;
    for (int i = 0; i < e[now].size(); i++) {
      int v = e[now][i].v;
      double w = e[now][i].w;
      if (dis[v] > dis[now] + w + mid) {
        dis[v] = dis[now] + w + mid;
        cnt[v]++;
        if (cnt[v] == n) return false;
        if (!vis[v]) {
          q.push(v);
          vis[v] = true;
        }
      }
    }
  }
  return true;
}
int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int b, d;
    double a, c;
    cin >> a >> b >> c >> d;
    e[b].push_back({d, -log(c / a)});
  }
  double l = 0, r = 1;
  while (abs(r - l) >= eps) {
    double mid = (l + r) / 2;
    if (spfa(-log(mid)))
      l = mid;
    else
      r = mid;
  }
  cout << fixed << setprecision(10) << r << 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

E、Falfa with Substring

题目链接：E-Falfa with Substring

题意：

定义字符串 S 的 bit-value 是 S 中 bit 的子串数量，定义 $F_{n,k}$ 为 bit-value 为 k 且长度为 n 的字符串数量（字符集为 ‘a’ 到‘z’）

求 $F_{n,0},F_{n,1},F_{n,2},\dots ,F_{n,n}$ ，(n ≤ $10^6$, 模 998244353)

题解：

这道题目问的是恰好的数量，但我们会的是至少的数量，所以可以考虑容斥。我们可以考虑先构造 k 个 “bit” ，然后让剩下的去进行排列组合，那么有 $f_k=26^{n-3k}\left(\genfrac{}{}{0ex}{}{n-2k}{k}\right)$ ，实际上我们至考虑 $k\le \frac{n}{3}$ 即可，设 $g_k$ 为恰好 $k$ 个的数量，则有：

$f(k)=\sum _{k\le j\le n}\left(\genfrac{}{}{0ex}{}{j}{k}\right)g(j)$

$g(k)=\sum _{k\le j\le n}(-1{)}^{j-k}(\genfrac{}{}{0ex}{}{j}{k})f(j)$

稍作变形，发现有卷积的形式：

$k!g(k)=\sum _{k\le j\le n}j!f(j)\times \frac{(-1{)}^{j-k}}{(j-k)!}$

令 $P_i=i!F(i)$ ， $Q_i=\frac{(-1{)}^{n-i}}{(n-i)!}$ ， $R_{n+i}=i!G_i$ ，则：

$R_k=\sum _{i+j=k}{P}_i\times Q_j$

代码：

#include 
#define int long long
using namespace std;
namespace poly {
typedef long long ll;
const int mod = 998244353;
const int maxn = 1.2e6 + 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
const int maxn = 1e6 + 10;
const int mod = 998244353;

int n, k;
int fc[maxn], ifc[maxn];
int f[maxn], g[maxn];

void init(int n) {
  fc[0] = 1ll;
  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 C(int n, int m) {
  if (m < 0 || n - m < 0) return 0;
  return fc[n] * ifc[m] % mod * ifc[n - m] % mod;
}

void solve() {
  cin >> n;
  init(n);
  k = n / 3;
  for (int i = 0; i <= k; i++)
    f[i] = C(n - 2 * i, i) * poly::quickpow(26, n - 3 * i) % mod;
  for (int i = 0, sign = 1; i <= k; i++, sign = -sign) {
    f[i] = f[i] * fc[i] % mod;
    g[k - i] = sign * ifc[i];
  }
  poly::polymul(f, g, f, 2 * k, 2 * k);
  for (int i = 0; i <= k; i++) f[i + k] = f[i + k] * ifc[i] % mod;
  for (int i = 0; i <= k; i++) cout << f[k + i] << " \n"[n == i];
  for (int i = k + 1; i <= n; i++) cout << 0 << " \n"[n == i];
}

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();
  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

G、Link with Monotonic Subsequence

题目链接：G-Link with Monotonic Subsequence

题意：

给定 $n$ ，现让你构造一个长为 $n$ 的排列，使得排列 $p$ 满足： max ⁡ { L I S ( p ) , L D S ( p ) } \max \{LIS(p),LDS(p)\} max{LIS(p),LDS(p)} 为所有排列中最小的

题解：

分块构造，设块大小为 $len=\sqrt{n}$ 。每个块内均为连续上升的序列，让最大的序列块在最前面，较小的序列块放后面。

Dliworth 定理

lds§ = 最小上升子序列分划数，lis§ = 最小下降子序列分划数

这个定理是组合学三大存在性定理之一，另外两个是 Ramsey 定理和 Hall 定理

【组合数学】组合存在性定理 三个组合存在性定理

⇒ l i s ( p ) × l d s ( p ) ≥ n ⇒ max ⁡ { l i s ( p ) , l d s ( p ) } ≥ ⌈ n ⌉ \Rarr lis(p)\times lds(p)\ge n\Rarr \max \{ lis(p),lds(p)\}\ge \lceil \sqrt n \rceil ⇒lis(p)×lds(p)≥n⇒max{lis(p),lds(p)}≥⌈n ​⌉

代码：

#include 
using namespace std;
const int maxn = 1e6 + 5;
int n;
int a[maxn];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    cin >> n;
    int num = ceil(sqrt(n));
    int head = num * num - (num - 1);
    int cnt = 0;
    for (int i = 0; i < num; i++) {
      for (int j = 0; j < num; j++) {
        if (head + j > n) continue;
        a[cnt++] = head + j;
      }
      head -= num;
    }
    for (int i = 0; i < cnt; i++) cout << a[i] << " ";
    cout << 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

H、Take the Elevator

题目链接：H-Take the Elevator

题意：

k 层楼，n 个人，第 i 个人想从 ai 楼到 bi 楼。电梯同一时间最多载 m

人，每一时间单位走一层，可以随时向下，但只能到 1 楼才能向上。求

最短时间使得所有人到达他/她想去的楼层。

题解：

很显然的一道贪心题，有两个最优子问题：一是谁需要上电梯，二是优先让谁上电梯。第一个问题好解决，电梯上行时让需要上行的人上电梯，电梯下行时让需要下行的人上电梯，上下其实本质类似。对于第二个问题，我们拿上行举例，我们发现电梯承载人数关于时间的积分是定值，所以说电梯同时承载的人越多，时间就越少，因此，应该让所上楼层较高的人优先上楼梯。

具体地，先考虑上行，设每个人的行程为一条线段 $[l_i,r_i]$ ，若在某个楼层，与之相交的线段不超过 m 个，那么都可以上电梯，若超过了 m 个，那么让 $r$ 比较大的上电梯，下行同理。

代码：

#include 
#define int long long
using namespace std;
const int maxn = 5e5 + 10;
int n, m;
int k, a[maxn], b[maxn], tmp[maxn];
int cnt, up[maxn], down[maxn], suf[maxn];
signed main() {
  cin >> n >> m >> k;
  tmp[++cnt] = k, tmp[++cnt] = 1;
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
    tmp[++cnt] = a[i], tmp[++cnt] = b[i];
  }
  sort(tmp + 1, tmp + cnt + 1);
  cnt = unique(tmp + 1, tmp + cnt + 1) - tmp - 1;
  for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(tmp + 1, tmp + cnt + 1, a[i]) - tmp;
    b[i] = lower_bound(tmp + 1, tmp + cnt + 1, b[i]) - tmp;
    if (a[i] < b[i])
      up[a[i]]++, up[b[i]]--;
    else
      down[b[i]]++, down[a[i]]--;
  }
  for (int i = 1; i <= cnt; i++) up[i] += up[i - 1], down[i] += down[i - 1];
  int ans = 0;
  for (int i = cnt - 1; i >= 1; i--) {
    suf[i] = (max(up[i], down[i]) + m - 1) / m;
    suf[i] = max(suf[i], suf[i + 1]);
    ans += 2ll * suf[i] * (tmp[i + 1] - tmp[i]);
  }
  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

#include 
#define int long long
using namespace std;
const int maxn = 2e6 + 5;
int n, m, k;
int pre1[maxn], pre2[maxn];
map<int, int> up, down;
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 >> m >> k;
  up.clear(), down.clear();
  for (int i = 1; i <= n; i++) {
    int a, b;
    cin >> a >> b;
    if (a < b) {
      up[b]++;
      up[a]--;
    } else {
      down[a]++;
      down[b]--;
    }
  }
  int cnt = 0, rest = 0;  //电梯还剩多少位置
  for (auto it = up.rbegin(); it != up.rend(); it++) {
    while (rest < it->second) {
      pre1[++cnt] = it->first;
      rest += m;
    }
    rest -= it->second;
  }
  cnt = 0, rest = 0;
  for (auto it = down.rbegin(); it != down.rend(); it++) {
    while (rest < it->second) {
      pre2[++cnt] = it->first;
      rest += m;
    }
    rest -= it->second;
  }
  int ans = 0;
  for (int i = 1; i <= n && (pre1[i] || pre2[i]); i++)
    ans += max(pre1[i], pre2[i]) - 1;
  cout << 2 * 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

I、let fat tension

题目链接：I-let fat tension

题意：

给定 $X_1,X_2,...,X_n\in {\mathbb{R}}^k,Y_1,Y_2,...,Y_n\in {\mathbb{R}}^d$ 。

定义：$le(i,j)=\frac{X_i\cdot X_j}{|X_i|\cdot |X_j|}$ ， $Y_i^{new}=\sum _{j=1}^{n}le(i,j)Y_j$

对 $i=1,2,...,n$，求 $Y_i$ (n ≤ 10000; k, d ≤ 50)

题解：

朴素做法的话，应该是 $O(n^{2}k+n^{2}d)$ 会超时，因此我们想一下优化，计算单个 $le(i,j)$ 的值是 $O(k)$ ，计算单个 $le(i,j)Y_j$ 的值是 $O(d)$ ,因此我们思考一下它这个新定义的函数的实际涵义，发现： $X\in {\mathbb{R}}^{n\times k},Y\in {\mathbb{R}}^{n\times d}$ ，而答案所求为 $X{X}^{T}Y$ 于是我们发现，利用矩阵乘法的结合律时间复杂度为 $O(nkd+nkd)$

代码：

#include 
using namespace std;
const int maxn = 10005;
const int maxk = 55;
double a[maxn][maxk], b[maxk][maxn], c[maxn][maxk];
double e[maxk][maxk], f[maxn][maxk];
int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int n, k, d;
  cin >> n >> k >> d;
  for (int i = 1; i <= n; i++) {
    double sum = 0;
    for (int j = 1; j <= k; j++) {
      cin >> a[i][j];
      sum = sum + a[i][j] * a[i][j];
    }
    sum = 1.0 / sqrt(sum);
    for (int j = 1; j <= k; j++) {
      a[i][j] = a[i][j] * sum;
      b[j][i] = a[i][j];
    }
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= d; j++) cin >> c[i][j];
  for (int i = 1; i <= k; i++)
    for (int j = 1; j <= d; j++) {
      double sum = 0;
      for (int t = 1; t <= n; t++) sum = sum + b[i][t] * c[t][j];
      e[i][j] = sum;
    }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= d; j++) {
      double sum = 0;
      for (int t = 1; t <= k; t++) sum = sum + a[i][t] * e[t][j];
      f[i][j] = sum;
    }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= d; j++) cout << f[i][j] << " \n"[j == d];
  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

J、Link with Arithmetic Progression

题目链接：J-Link with Arithmetic Progression

题意：

给出一个序列，求其线性回归方程

题解：

已知 $(x_i,y_i)i=1,2,\dots ,n$ ，求其线性回归方程 $\hat{y}=A\hat{x}+B$

令 $\bar{x}=\frac{{\sum }_{i=1}^n{x}_i}{n},\bar{y}=\frac{{\sum }_{i=1}^n{y}_i}{n}$ ，则有：

$A=\frac{{\sum }_{i=1}^n{x}_i{y}_i-n\bar{x}\bar{y}}{{\sum }_{i=1}^n{x}_i^2-n\bar{x}\bar{x}}$ ，$B=\bar{y}-A\bar{x}$

代码：

#include 
#define double long double
using namespace std;
const int maxn = 1e5 + 5;
int n;
double a[maxn];
double sx, sy, sxx, sxy, A, B;
double res;
namespace GTI {
char gc(void) {
  const int S = 1 << 16;
  static char buf[S], *s = buf, *t = buf;
  if (s == t) t = buf + fread(s = buf, 1, S, stdin);
  if (s == t) return EOF;
  return *s++;
}
int gti(void) {
  int a = 0, b = 1, c = gc();
  for (; !isdigit(c); c = gc()) b ^= (c == '-');
  for (; isdigit(c); c = gc()) a = a * 10 + c - '0';
  return b ? a : -a;
}
}  // namespace GTI
using GTI::gti;
int main() {
  int _;
  _ = gti();
  while (_--) {
    sx = sy = sxx = sxy = B = A = res = 0;
    n = gti();
    for (int i = 1; i <= n; i++) {
      a[i] = gti();
      sy += a[i];
      sx += (double)i;
      sxy += (double)i * a[i];
      sxx += (double)i * (double)i;
    }
    B = ((double)n * sxy - sx * sy) / ((double)n * sxx - sx * sx);
    A = (sy * sxx - sx * sxy) / (n * sxx - sx * sx);
    for (int i = 1; i <= n; i++)
      res += (a[i] - A - B * (double)i) * (a[i] - B * (double)i - A);
    cout << fixed << setprecision(15) << 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
43
44

K、Link with Bracket Sequence I

题目链接：K-Link with Bracket Sequence I

题意：

link 有一个括号序列 a ，它是一个有效序列的 b 的子序列，其长度分别为 n 和 m 。现在给出 a，n，m (n<=m<=200)，求 b 可能的方案数

题解：

其实跟括号序列相关的题目绝大多数都是 dp 题，有时可以用组合数学里的知识对其进行优化，这道题也比较显然是个 dp 题。那么我们来提取一下有关变量，并推导其递推式。分析后我们可以得到：子序列长度 i ，原序列长度 j ，以及子序列所匹配到原序列的对应位置 k 是三个相关变量，且这三个变量足以完成此题。

具体地，设 $d{p}_{i,j,k}$ 为 b 的前 $i$ 个匹配至 a 的前 $j$ 个，并且这 $i$ 个序列中未能匹配的左括号有 $k$ 个。然后我们发现有两种转移，

当 $a[j+1]{=}^{\prime }{(}^{\prime }$ 时，可由 $d{p}_{i,j,k}\to d{p}_{i+1,j+1,k+1}$ ，

当 $a[j+1]{=}^{\prime }{)}^{\prime }$ 时，可由 $d{p}_{i,j,k}\to d{p}_{i+1,j+1,k-1}$

另外，当无法匹配时有如下转移：

$d{p}_{i,j,k}\to d{p}_{i+1,j,k+1}/d{p}_{i+1,j,k-1}$

代码：

#include 
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 220;
int n, m;
char s[maxn];
int dp[maxn][maxn][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;
    cin >> s + 1;
    memset(dp, 0, sizeof dp);
    dp[0][0][0] = 1;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j <= i; j++) {
        for (int k = 0; k <= i; k++) {
          if (k > 0) {
            if (s[j + 1] == ')') {
              dp[i + 1][j + 1][k - 1] += dp[i][j][k];
              dp[i + 1][j + 1][k - 1] %= mod;
            } else {
              dp[i + 1][j][k - 1] += dp[i][j][k];
              dp[i + 1][j][k - 1] %= mod;
            }
          }
          if (s[j + 1] == '(') {
            dp[i + 1][j + 1][k + 1] += dp[i][j][k];
            dp[i + 1][j + 1][k + 1] %= mod;
          } else {
            dp[i + 1][j][k + 1] += dp[i][j][k];
            dp[i + 1][j][k + 1] %= mod;
          }
        }
      }
    }
    cout << dp[m][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
35
36
37
38
39
40
41
42
43
44
45

L、Link with Level Editor I

题目链接：L-Link with Level Editor I

题意：

有 n 个世界，每个世界有一个 m 个点 l 条有向边的图。从第一个世界的编号为 1 的点出发，每个世界可以不动或可以走一条边，到达下一个点 u，然后跳到下一个世界的点 u，如果跳到点 m 则胜利。$n\le 10^4,m\le 2\times 10^3,\sum l\le 10^6$

求一个最短的子段，使得其可胜利。

题解：

这个题一时分析不出是 dp 题还是图论题。但题里面有个条件，就是 $\sum l\le 10^6$ ，这个信息很关键。假如我们不考虑最短，仅考虑是否连通，例如判断 $(l,r)$ 子段是否连通 ，那么将会产生一个 $O(\sum l)$ 的朴素算法，再去枚举的话，朴素算法就是 $O(n^2\sum l)$ 十分巨大，因此我们考虑优化，有些量经过了累次计算。

我们发现其实这些节点是满足最优子结构、无后效性的，那么我们考虑如何 dp ，选取哪些量进行 dp 。先从朴素情况入手，假设第 $i$ 个世界的 $nod{e}_1$ 跳到第 $j$ 个世界后所覆盖的点集为 $se{t}_{i,j}$ ，那么从 $se{t}_{i,j}\to se{t}_{i,j+1}$ 时，只需考虑 $j\to j+1$ 世界对应的连边，我们建立一个映射表：$d{p}_{i,j}$ 表示第 $i$ 个世界的节点 $j$ 最近可由哪个世界跳转而来，并将这个最小步数存至此变量中。那么有： d p i + 1 , j = min ⁡ { d p i , j , d p i , k + 1 } ,   ( i , k ) → ( i + 1 , j ) ∈ E dp_{i+1,j}=\min \{dp_{i,j},dp_{i,k}+1\}, \ (i,k)\rarr (i+1,j) \in E dpi+1,j​=min{dpi,j​,dpi,k​+1}, (i,k)→(i+1,j)∈E ,那么此时再利用滚动数组优化第一维即可

不过说实话，这个复杂度比较迷，不过数据比较弱，刚好跑过了。

代码：

#include 
using namespace std;
const int maxn = 1e4 + 5;
const int inf = 0x3f3f3f3f;
int n, m;
int dp[2][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 ans = inf;
  memset(dp, 0x3f, sizeof dp);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    dp[(i & 1) ^ 1][1] = 0;
    for (int j = 2; j <= m; j++) dp[i & 1][j] = dp[(i & 1) ^ 1][j] + 1;
    int l;
    cin >> l;
    while (l--) {
      int u, v;
      cin >> u >> v;
      dp[i & 1][v] = min(dp[i & 1][v], dp[(i & 1) ^ 1][u] + 1);
    }
    ans = min(ans, dp[i & 1][m]);
  }
  if (ans == inf)
    cout << -1 << endl;
  else
    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

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

不会做X

A、Falfa with Polygon

B、light

F、NIO with String Game