CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Magic Mirror
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
#include <cstdio>
#include <cstring>
int T;
char s[20], a[20] = "JESSIE", b[20] = "jessie";
bool o;
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%s", s);
if (strlen(s) != 6)
{
printf("Dare you say that again?\n");
continue;
}
o = true;
for (int i = 0; i < 6; i++)
if ((s[i] != a[i]) && (s[i] != b[i]))
{
o = false;
break;
}
if (o)
printf("Good guy!\n");
else
printf("Dare you say that again?\n");
}
}
Mathematical Curse
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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int t, n, m, k;
long long a[1010];
char s[10];
long long mx[1010][10], mn[1010][10];
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
scanf("%s", s);
memset(mx, 0, sizeof(mx));
memset(mn, 0, sizeof(mn));
mx[0][0] = mn[0][0] = k;
for (int i = 1; i <= n; i++)
for (int j = 1; (j <= m) && (j <= i); j++)
{
mx[i][0] = mn[i][0] = k;
if (s[j - 1] == '+')
mx[i][j] = mx[i - 1][j - 1] + a[i], mn[i][j] = mn[i - 1][j - 1] + a[i];
else if (s[j - 1] == '-')
mx[i][j] = mx[i - 1][j - 1] - a[i], mn[i][j] = mn[i - 1][j - 1] - a[i];
else if (s[j - 1] == '*')
{
if (a[i] >= 0)
mx[i][j] = mx[i - 1][j - 1] * a[i], mn[i][j] = mn[i - 1][j - 1] * a[i];
else
mx[i][j] = mn[i - 1][j - 1] * a[i], mn[i][j] = mx[i - 1][j - 1] * a[i];
}
else
{
if (a[i] >= 0)
mx[i][j] = mx[i - 1][j - 1] / a[i], mn[i][j] = mn[i - 1][j - 1] / a[i];
else
mx[i][j] = mn[i - 1][j - 1] / a[i], mn[i][j] = mx[i - 1][j - 1] / a[i];
}
if (i > j)
mx[i][j] = max(mx[i][j], mx[i - 1][j]), mn[i][j] = min(mn[i][j], mn[i - 1][j]);
}
printf("%lld\n", mx[n][m]);
}
}
Password
1
Sequence
1
Jiu Yuan Wants to Eat
链剖+双标记维护区间和，区间取反操作等价于区间乘 -1 后区间加 -1 。
时限卡的有点紧，线段树用 vector 建的时候卡时限 2832ms/3000ms，改成数组也要跑 2448ms/3000ms。
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
#include <cstdio>
#include <vector>
using namespace std;
typedef unsigned long long ll;
const int N = 1e5 + 9;
struct Node
{
int l, r;
ll mul, add, sum;
void upd(ll m, ll a)
{
mul *= m;
add = add * m + a;
sum = sum * m + a * (r - l + 1);
}
void up(const Node &lc, const Node &rc) { sum = lc.sum + rc.sum; }
void down(Node &lc, Node &rc) { lc.upd(mul, add), rc.upd(mul, add), mul = 1, add = 0; }
} v[N << 2];
struct SegmentTree
{
SegmentTree(int l, int r) { build(l, r); }
void build(int l, int r, int rt = 1)
{
v[rt] = {l, r};
if (l == r)
return;
int m = v[rt].r + v[rt].l >> 1;
build(l, m, rt << 1), build(m + 1, r, rt << 1 | 1), v[rt].up(v[rt << 1], v[rt << 1 | 1]);
}
void upd(int l, int r, ll mul, ll add, int rt = 1)
{
if (l <= v[rt].l && v[rt].r <= r)
return v[rt].upd(mul, add);
v[rt].down(v[rt << 1], v[rt << 1 | 1]);
int m = v[rt].r + v[rt].l >> 1;
if (m >= r)
upd(l, r, mul, add, rt << 1);
else if (m < l)
upd(l, r, mul, add, rt << 1 | 1);
else
upd(l, m, mul, add, rt << 1), upd(m + 1, r, mul, add, rt << 1 | 1);
v[rt].up(v[rt << 1], v[rt << 1 | 1]);
}
Node ask(int l, int r, int rt = 1)
{
if (l <= v[rt].l && v[rt].r <= r)
return v[rt];
v[rt].down(v[rt << 1], v[rt << 1 | 1]);
int m = v[rt].l + v[rt].r >> 1;
if (m >= r)
return ask(l, r, rt << 1);
if (m < l)
return ask(l, r, rt << 1 | 1);
return v[0].up(ask(l, m, rt << 1), ask(m + 1, r, rt << 1 | 1)), v[0];
}
};
struct Graph
{
struct Vertex
{
vector<int> o, i; //相关出边和入边编号
int siz, dep, top, dfn; //树链剖分中使用，依次代表子树节点数、深度、所在链的顶端节点、dfs序
};
typedef pair<int, int> Edge;
vector<Vertex> v; //点集
vector<Edge> e; //边集
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
v[ed.first].o.push_back(e.size());
v[ed.second].i.push_back(e.size());
e.push_back(ed);
}
int ch(int u, int i = 0) { return e[v[u].o[i]].second; } //u的第i个孩子节点
int fa(int u, int i = 0) { return e[v[u].i[i]].first; } //u的第i个父节点
};
struct Diagram : Graph
{
SegmentTree data; //暂用树状数组作为默认数据结构
Diagram(const Graph &g, int root) : Graph(g.v.size()), data(0, g.v.size() - 1)
{
build(root, g);
int cnt = v[root].dfn = v[root].dep = 1;
dfs(v[root].top = root, cnt);
}
void build(int u, const Graph &g) //无向图dfs建树，且重边在最前，u为根节点
{
v[u].siz = 1;
for (int i = 0, k, to; i < g.v[u].o.size(); ++i)
if (k = g.v[u].o[i], to = g.e[k].second, !v[to].siz) //没访问过的点siz默认0
{
build(to, g);
v[u].siz += v[to].siz;
Graph::add(g.e[k]);
if (v[ch(u)].siz < v[to].siz) //重边移到最前
swap(v[u].o.front(), v[u].o.back());
}
}
void dfs(int u, int &cnt)
{
for (int i = 0, to; i < v[u].o.size(); ++i)
{
v[to = ch(u, i)].dfn = ++cnt;
v[to].top = i ? to : v[u].top;
v[to].dep = v[u].dep + 1;
dfs(to, cnt);
}
}
Node ask(int x, int y)
{
Node ans;
ans.sum = 0;
for (; v[x].top != v[y].top; x = fa(v[x].top))
{
if (v[v[x].top].dep < v[v[y].top].dep)
swap(x, y);
ans.up(ans, data.ask(v[v[x].top].dfn, v[x].dfn));
}
if (v[x].dep < v[y].dep)
swap(x, y);
return ans.up(ans, data.ask(v[y].dfn, v[x].dfn)), ans;
}
void upd(int x, int y, ll mul, ll add)
{
for (; v[x].top != v[y].top; x = fa(v[x].top))
{
if (v[v[x].top].dep < v[v[y].top].dep)
swap(x, y);
data.upd(v[v[x].top].dfn, v[x].dfn, mul, add);
}
if (v[x].dep < v[y].dep)
swap(x, y);
data.upd(v[y].dfn, v[x].dfn, mul, add);
}
};
int main()
{
for (int n; ~scanf("%d", &n);)
{
Graph g(n + 1);
for (int i = 2, b; i <= n; ++i)
scanf("%d", &b), g.add({b, i});
Diagram d(g, 1);
scanf("%d", &n);
for (int i = 0, u, v; i < n; ++i)
{
ll x;
scanf("%llu%d%d", &x, &u, &v);
if (x == 1)
scanf("%llu", &x), d.upd(u, v, x, 0);
else if (x == 2)
scanf("%llu", &x), d.upd(u, v, 1, x);
else if (x == 3)
d.upd(u, v, -1, -1);
else
printf("%llu\n", d.ask(u, v).sum);
}
}
}
Modular Production Line
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
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N = 100009, NPOS = -1, INF = 1e18;
struct Ranker : vector<ll>
{
void init()
{
sort(begin(), end()), resize(unique(begin(), end()) - begin());
}
int ask(ll x) const
{
return lower_bound(begin(), end(), x) - begin();
}
};
struct Graph
{
struct Vertex
{
vector<int> a /*,b*/; //相关出边和入边编号
//int siz,dep,top,dfn;//树链剖分中使用，依次代表子树节点数、深度、所在链的顶端节点、dfs序
};
struct Edge
{
int from, to;
ll dist, cap; //边长、容量，图论算法使用
};
vector<Vertex> v; //点集
vector<Edge> e; //边集
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
if (ed.from == ed.to)
return; //如果有需要请拆点
v[ed.from].a.push_back(e.size());
//v[ed.to].b.push_back(e.size());
e.push_back(ed);
}
};
struct EdmondKarp : Graph
{
ll flow, cost;
vector<ll> f;
EdmondKarp(int n) : Graph(n) {}
void add(Edge ed)
{
Graph::add(ed);
swap(ed.from, ed.to), ed.cap = 0, ed.dist *= -1;
Graph::add(ed);
}
void ask(int s, int t)
{
vector<int> p(v.size(), NPOS);
for (f.assign(e.size(), flow = cost = 0);;)
{
vector<ll> d(v.size(), INF);
vector<int> flag(v.size(), d[s] = 0);
for (deque<int> q(flag[s] = 1, s); !q.empty(); q.pop_front())
for (int u = q.front(), i = flag[u] = 0, k, to; i < v[u].a.size(); ++i)
if (k = v[u].a[i], to = e[k].to,
e[k].cap > f[k] && d[to] > d[u] + e[k].dist)
{
d[to] = d[u] + e[k].dist, p[to] = k;
if (!flag[to])
q.push_back(to), flag[to] = 1;
}
if (d[t] == INF)
return;
ll _f = INF;
for (int u = t; u != s; u = e[p[u]].from)
_f = min(_f, e[p[u]].cap - f[p[u]]);
for (int u = t; u != s; u = e[p[u]].from)
cost += _f * e[p[u]].dist, f[p[u]] += _f, f[p[u] ^ 1] -= _f;
flow += _f;
}
}
};
int t, n, m, k, x[N], y[N], w[N];
int main()
{
for (scanf("%d", &t); t--;)
{
Ranker rk;
scanf("%d%d%d", &n, &k, &m);
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &x[i], &y[i], &w[i]);
rk.push_back(x[i]);
rk.push_back(++y[i]);
}
rk.init();
EdmondKarp g(rk.size() + 2);
for (int i = 0; i < rk.size(); ++i)
g.add({i, i + 1, 0, k});
for (int i = 0; i < m; ++i)
g.add({rk.ask(x[i]), rk.ask(y[i]), -w[i], 1});
g.add({rk.size() + 1, 0, 0, k});
g.ask(rk.size() + 1, rk.size());
printf("%lld\n", -g.cost);
}
}
Give Candies
答案是$2^{n-2}$，用费马小定理把指数对 M-1 取模后进行运算避免更多的高精度运算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#define mul(a, b, c) (1LL * (a) * (b) % (c))
typedef int ll;
const ll M = 1e9 + 7;
ll pow(ll a, ll b, ll m)
{
ll r = 1;
for (a %= m; b; b >>= 1, a = mul(a, a, m))
if (b & 1)
r = mul(r, a, m);
return r;
}
char s[100009];
int t, n;
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%s", s);
for (int i = n = 0; s[i]; ++i)
n = mul(n, 10, M - 1) + s[i] - '0';
printf("%d\n", pow(2, n + M - 2, M));
}
}
String and Times
拉一个后缀数组的板子跑掉了。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct SufArr
{
vector<int> sa, rk, h;
SufArr(const vector<int> &s, int m) : sa(s.size(), 0), rk(s), h(s.size(), 0)
{
vector<int> cnt(s.size() + m, 0);
for (int i = 0; i < s.size(); ++i)
++cnt[rk[i]];
for (int i = 1; i < m; ++i)
cnt[i] += cnt[i - 1];
for (int i = 0; i < s.size(); ++i)
sa[--cnt[rk[i]]] = i;
for (int k = 1, j = 0; k <= s.size() && j < s.size() - 1; k <<= 1)
{
for (int i = 0; i < s.size(); ++i)
{
if (j = sa[i] - k, j < 0)
j += s.size();
h[cnt[rk[j]]++] = j;
}
cnt[0] = sa[h[0]] = j = 0;
for (int i = 1; i < s.size(); ++i)
{
if (rk[h[i]] != rk[h[i - 1]] || rk[h[i] + k] != rk[h[i - 1] + k])
cnt[++j] = i;
sa[h[i]] = j;
}
swap(rk, sa), swap(sa, h);
}
for (int i = 0, k = 0, j = rk[0]; i < s.size() - 1; ++i, ++k)
for (; ~k && s[i] != s[sa[j - 1] + k]; j = rk[sa[j] + 1], --k)
h[j] = k;
}
};
struct SparseTable
{
typedef int ll;
vector<vector<ll>> f;
SparseTable(const vector<ll> &a) : f(log2(a.size()) + 1, a)
{
for (int k = 0; k + 1 < f.size(); ++k)
for (int i = 0; i + (1 << k) < a.size(); ++i)
f[k + 1][i] = min(f[k][i], f[k][i + (1 << k)]);
}
ll ask(int l, int r)
{
int k = log2(r - l + 1);
return min(f[k][l], f[k][r + 1 - (1 << k)]);
}
};
ll cal(SufArr &sa, SparseTable &st, int k) //原串中至少出现k次的子串数量
{
ll ans = 0;
if (k > 1)
for (int l = 2, r = k; r < sa.h.size(); ++l, ++r)
ans += max(st.ask(l, r) - sa.h[l - 1], 0);
else
for (int i = 1; i < sa.h.size(); ++i)
ans += sa.h.size() - 1 - sa.sa[i] - sa.h[i];
return ans;
}
char s[2000009];
int main()
{
for (int a, b; ~scanf("%s%d%d", s, &a, &b);)
{
SufArr sa(vector<int>(s, s + strlen(s) + 1), 'Z' + 1);
SparseTable st(sa.h);
printf("%lld\n", cal(sa, st, a) - cal(sa, st, b + 1));
}
}
Save the Room
1
2
3
4
5
6
#include <stdio.h>
int main()
{
for (int a, b, c; ~scanf("%d%d%d", &a, &b, &c);)
printf(a % 2 && b % 2 && c % 2 ? "No\n" : "Yes\n");
}
Participate in E-sports
交了个高精度开根号上去。
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
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
struct Wint : vector<int> //继承vector
{
static const int width = 9, base = 1e9;
Wint(unsigned long long n = 0) //普通初始化，当整型数和Wint同时运算时会提升至Wint
{
for (; n; n /= base)
push_back(n % base);
}
explicit Wint(const string &s) //字符串初始化函数，未判断字符串合法情况
{
for (int len = int(s.size() - 1) / width + 1, b, e, i = 0; i < len; ++i)
for (e = s.size() - i * width, b = max(0, e - width), push_back(0); b != e; ++b)
back() = back() * 10 + s[b] - '0';
trim(0);
}
Wint &trim(bool up = 1) //去前导0，是否需要进位，很常用的小函数，为方便返回自身
{
for (int i = 1; up && i < size(); ++i)
{
if ((*this)[i - 1] < 0)
--(*this)[i], (*this)[i - 1] += base;
if ((*this)[i - 1] >= base)
(*this)[i] += (*this)[i - 1] / base, (*this)[i - 1] %= base;
}
while (!empty() && back() <= 0)
pop_back();
for (; up && !empty() && back() >= base; (*this)[size() - 2] %= base)
push_back(back() / base);
return *this;
}
friend istream &operator>>(istream &is, Wint &n)
{
string s; //懒
return is >> s, n = Wint(s), is;
}
friend ostream &operator<<(ostream &os, const Wint &n)
{
if (n.empty())
return os.put('0');
os << n.back();
char ch = os.fill('0');
for (int i = n.size() - 2; ~i; --i)
os.width(n.width), os << n[i];
return os.fill(ch), os;
}
friend bool operator<(const Wint &a, const Wint &b)
{
if (a.size() != b.size())
return a.size() < b.size();
for (int i = a.size() - 1; ~i; --i)
if (a[i] != b[i])
return a[i] < b[i];
return 0;
}
friend bool operator>(const Wint &a, const Wint &b)
{
return b < a;
}
friend bool operator<=(const Wint &a, const Wint &b)
{
return !(a > b);
}
friend bool operator>=(const Wint &a, const Wint &b)
{
return !(a < b);
}
Wint &operator+=(const Wint &b)
{
if (size() < b.size())
resize(b.size()); //保证有足够的位数
for (int i = 0; i < b.size(); ++i)
(*this)[i] += b[i];
return trim(); //单独进位防自运算
}
friend Wint operator+(Wint a, const Wint &b)
{
return a += b;
}
Wint &operator++() //前置版本
{
return *this += 1; //懒
}
Wint operator++(int) //后置版本
{
Wint b(*this);
return ++*this, b;
}
Wint &operator-=(const Wint &b) //a<b会使a变为0
{
if (size() < b.size())
resize(b.size()); //保证有足够的位数
for (int i = 0; i < b.size(); ++i)
(*this)[i] -= b[i];
return trim(); //单独进位防自运算
}
friend Wint operator-(Wint a, const Wint &b)
{
return a -= b;
}
Wint &operator--() //前置版本
{
return *this -= 1; //懒
}
Wint operator--(int) //后置版本
{
Wint b(*this);
return --*this, b;
}
Wint &operator*=(const Wint &b) //高精度乘法，常规写法
{
Wint c;
c.assign(size() + b.size(), 0);
for (int j = 0, k, l; j < b.size(); ++j)
if (b[j]) //稀疏优化，特殊情况很有效
for (int i = 0; i < size(); ++i)
{
unsigned long long n = (*this)[i];
for (n *= b[j], k = i + j; n; n /= base)
c[k++] += n % base;
for (l = i + j; c[l] >= base || l + 1 < k; c[l++] %= base)
c[l + 1] += c[l] / base;
}
return swap(c), trim(0);
}
/*
Wint& operator*=(const Wint &b)//一种效率略高但对位宽有限制的写法
{
vector<unsigned long long> n(size()+b.size(),0);//防爆int
//乘法算完后统一进位效率高，防止乘法溢出（unsigned long long范围0~1.8e19）
//位宽为9时size()不能超过18（十进制162位），位宽为8时size()不能超过1800（十进制14400位）等等。
for(int j=0; j!=b.size(); ++j)
if(b[j])//稀疏优化，特殊情况很有效
for(int i=0; i!=size(); ++i)
n[i+j]+=(unsigned long long)(*this)[i]*b[j];
for(int i=1; i<n.size(); ++i)//这里用<防止位数0，单独进位防自运算
n[i]+=n[i-1]/base,n[i-1]%=base;
return assign(n.begin(),n.end()),trim(0);
}
Wint& operator*=(const Wint &b)//fft优化乘法，注意double仅15位有效数字，调小Wint::width不超过2，计算自2*log2(base)+2*log2(len)<53
{
vector<ll> ax(begin(),end()),bx(b.begin(),b.end());
ax=FFT(size()+b.size()).ask(ax,bx);
for(int i=1; i<ax.size(); ++i)
ax[i]+=ax[i-1]/base,ax[i-1]%=base;
return assign(ax.begin(),ax.end()),trim(0);
}
Wint& operator*=(const Wint &b)//ntt优化，Wint::width不超过2
{
vector<ll> ax(begin(),end()),bx(b.begin(),b.end());
ax=FNTT(size()+b.size(),(7<<26)+1,3).ask(ax,bx);
for(int i=1; i<ax.size(); ++i)
ax[i]+=ax[i-1]/base,ax[i-1]%=base;
return assign(ax.begin(),ax.end()),trim(0);
}
*/
friend Wint operator*(Wint a, const Wint &b)
{
return a *= b;
}
Wint &operator/=(Wint b)
{
Wint r, c, d = b.base / (b.back() + 1);
*this *= d, b *= d, c.assign(size(), 0);
for (int i = size() - 1; ~i; --i)
{
r.insert(r.begin(), (*this)[i]);
unsigned long long s = 0;
for (int j = b.size(); j + 1 >= b.size(); --j) //b.size()==0肯定第一行就出问题的
s = s * b.base + (j < r.size() ? r[j] : 0);
for (d = c[i] = s / b.back(), d *= b; r < d; r += b)
--c[i];
r -= d;
}
return swap(c), trim(0); //r为加倍后的余数，可通过高精度除低精度得到真正余数，此处略
}
friend Wint operator/(Wint a, const Wint &b)
{
return a /= b;
}
Wint &operator%=(const Wint &b)
{
return *this -= *this / b * b;
}
friend Wint operator%(Wint a, const Wint &b)
{
return a %= b;
}
//开平方，改自ZJU模板
bool cmp(long long c, int d, const Wint &b) const
{
if ((int)b.size() - (int)size() < d + 1 && c)
return 1;
long long t = 0;
for (int i = b.size() - 1, lo = -(base << 1); lo <= t && t <= 0 && ~i; --i)
if (t = t * base - b[i], 0 <= i - d - 1 && i - d - 1 < size())
t += (*this)[i - d - 1] * c;
return t > 0;
}
Wint &sub(const Wint &b, long long k, int d)
{
int l = b.size() + d;
for (int i = d + 1; i <= l; ++i)
{
long long tmp = (*this)[i] - k * b[i - d - 1];
if (tmp < 0)
{
(*this)[i + 1] += (tmp - base + 1) / base;
(*this)[i] = tmp - (tmp - base + 1) / base * base;
}
else
(*this)[i] = tmp;
}
for (int i = l + 1; i < size() && (*this)[i] < 0; ++i)
{
(*this)[i + 1] += ((*this)[i] - base + 1) / base;
(*this)[i] -= ((*this)[i] - base + 1) / base * base;
}
return trim(0);
}
friend Wint sqrt(Wint a)
{
Wint n;
n.assign(a.size() + 1 >> 1, 0);
for (int i = n.size() - 1, l, r; ~i; --i)
{
for (l = 0, r = a.base, n[i] = l + r >> 1; r - l > 1; n[i] = l + r >> 1)
{
if (n.cmp(n[i], i - 1, a))
r = n[i];
else
l = n[i];
}
a.sub(n, n[i], i - 1), n[i] += l + r >> 1;
}
for (int i = 0; i < n.size(); ++i)
n[i] >>= 1;
return n.trim(0);
}
/*
friend Wint sqrt(const Wint &a)//常规牛顿迭代实现的开平方算法，慢但是好敲
{
Wint b=a,c=(b+1)/2;
while(b!=c)swap(b,c),c=(b+a/b)/2;
return c;
}
friend Wint sqrt(const Wint &a)
{
Wint ret,t;
ret.assign((a.size()+1)>>1,0);
for(int i=ret.size()-1,l,r; ~i; --i)
{
for(l=0,r=a.base; r-l>1;)
{
ret[i]=l+(r-l)/2;
t=ret*ret;
if(a<t)r=ret[i];
else l=ret[i];
}
if(!l&&i==ret.size()-1)ret.pop_back();
else ret[i]=l;
}
return ret;
}
*/
};
int check(Wint n)
{
Wint sn = sqrt(n);
return sn * sn == n;
}
int main()
{
int t;
for (cin >> t; t--;)
{
Wint n;
cin >> n;
int ans = check(n) * 2 + check(n * (n - 1) / 2);
cout << (ans == 0 ? "League of Legends\n" : ans == 1 ? "Clash Royale\n" : ans == 2 ? "Hearth Stone\n" : "Arena of Valor\n");
}
}
Transport Ship
拆成 01 背包。
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
#include <stdio.h>
#include <string.h>
const int N = 511, S = 32767 >> 1, M = 1e9 + 7;
int t, n, q, m, v[N], f[N][S];
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d%d", &n, &q);
for (int i = m = 0, V, C; i < n; ++i)
{
scanf("%d%d", &V, &C);
for (int i = 0; i < C; ++i)
v[++m] = (1 << i) * V;
}
for (int i = f[0][0] = 1; i <= m; ++i)
for (int s = 0; s < S; ++s)
if (f[i][s] = f[i - 1][s], s >= v[i])
f[i][s] = (f[i][s] + f[i - 1][s - v[i]]) % M;
for (int i = 0, s; i < q; ++i)
{
scanf("%d", &s);
printf("%d\n", f[m][s]);
}
}
}
Poor God Water
矩阵乘一下。
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
#include <cstdio>
#include <algorithm>
#define mul(a, b, c) (1LL * (a) * (b) % (c))
using namespace std;
typedef long long ll;
const ll N = 9, M = 1e9 + 7;
struct Matrix
{
static int n;
ll a[N][N];
Matrix(ll k = 0)
{
for (int i = 0; i < n; ++i)
fill(a[i], a[i] + n, 0), a[i][i] = k;
}
ll *operator[](int n)
{
return a[n];
}
};
int Matrix::n = N;
Matrix operator*(const Matrix &a, const Matrix &b)
{
Matrix r(0);
for (int i = 0; i < r.n; ++i)
for (int j = 0; j < r.n; ++j)
for (int k = 0; k < r.n; ++k)
r.a[i][j] = (r.a[i][j] + mul(a.a[i][k], b.a[k][j], M)) % M;
return r;
}
Matrix pow(Matrix a, ll b)
{
Matrix r(1);
for (; b; b >>= 1, a = a * a)
if (b & 1)
r = r * a;
return r;
}
int main()
{
ll t, n, ans;
for (scanf("%lld", &t); t--;)
{
scanf("%lld", &n);
if (n < 3)
{
printf("%d\n", n == 1 ? 3 : 9);
continue;
}
Matrix A, P;
for (int i = 0; i < N; ++i)
A[i][0] = 1;
P[0][3] = P[0][6] = 1;
P[1][0] = P[1][3] = P[1][6] = 1;
P[2][0] = P[2][3] = 1;
P[3][1] = P[3][4] = P[3][7] = 1;
P[4][1] = P[4][7] = 1;
P[5][1] = P[5][4] = 1;
P[6][5] = P[6][8] = 1;
P[7][2] = P[7][8] = 1;
P[8][2] = P[8][5] = 1;
A = pow(P, n - 2) * A;
for (int i = ans = 0; i < N; ++i)
ans = (ans + A[i][0]) % M;
printf("%lld\n", ans);
}
}