CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
\^&\^
签到
1
2
3
4
5
6
7
#include <stdio.h>
unsigned t, a, b;
int main()
{
for (scanf("%u", &t); t--; printf("%u\n", a & b ? a & b : 1))
scanf("%u%u", &a, &b);
}
array
因为数组中的值唯一，且在 1 到 n 的范围内，而询问的 r 和 k 也在 1 到 n 的范围内。 所以对于任意一个被操 作 1 修改过的值都不会成为询问的答案，而询问的结果也必然在 k 到 n ＋ 1 的范围内。 因为没有被修改过 值是唯一的，所以可以建立权值线段树，维护权值区间内的值所在下标的最大值。而询问则转化为不小 于 k 的值里面，下标超过 r 的最小权值是多少。 如何处理询问呢，一种较为暴力的解法是直接在线段树上 询问权值在 k 到 n+1 的范围内第一个下标超过 r 的权值是多少。但复杂度可能会被卡，需要减枝。 再加上 一个额外的判断就可以了，就是在递归查询完左子树内存不存在大于 r 的下标之后，如果不存在，则先 看一下右子树内的下标的最大值是否大于 r。如果不大于 r，则不必再进入右子树内查询，否则答案一定 在右子树内。在进左子树之前也利用同样的判断条件来判断是否有必要进入左子树，这样做可以保证单 次查询的复杂度是 O(log n) 的。 而对于操作 1，则等价于修改某个权值的下标为无穷大。操作复杂度也 是 O（log n )的。 综上所述，得到了一个复杂度为 O( m * log n )的在线算法，可以较快地通过此题。
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
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const int NPOS = -1, N = 1e5 + 9;
struct SegmentTree
{
struct Seg
{
int l, r;
ll max;
void upd(ll mul, ll add) { max = max * mul + add; }
friend Seg up(const Seg &lc, const Seg &rc) { return {lc.l, rc.r, std::max(lc.max, rc.max)}; }
};
struct Node : Seg
{
int lc, rc;
ll mul, add;
};
vector<Node> v;
SegmentTree(int l, int r) { build(l, r); }
void build(int l, int r)
{
int rt = v.size();
v.push_back({});
v[rt].Seg::operator=({l, r, -1});
v[rt].lc = v[rt].rc = NPOS;
v[rt].mul = 1, v[rt].add = 0;
}
void down(int rt)
{
int m = v[rt].l + v[rt].r >> 1;
if (v[rt].lc == NPOS)
v[rt].lc = v.size(), build(v[rt].l, m);
if (v[rt].rc == NPOS)
v[rt].rc = v.size(), build(m + 1, v[rt].r);
upd(v[v[rt].lc].l, v[v[rt].lc].r, v[rt].mul, v[rt].add, v[rt].lc);
upd(v[v[rt].rc].l, v[v[rt].rc].r, v[rt].mul, v[rt].add, v[rt].rc);
v[rt].mul = 1, v[rt].add = 0;
}
void upd(int l, int r, ll mul, ll add, int rt = 0)
{
if (l <= v[rt].l && v[rt].r <= r)
return v[rt].mul *= mul, v[rt].add = v[rt].add * mul + add, v[rt].upd(mul, add);
down(rt);
if (r <= v[v[rt].lc].r)
upd(l, r, mul, add, v[rt].lc);
else if (l >= v[v[rt].rc].l)
upd(l, r, mul, add, v[rt].rc);
else
upd(l, v[v[rt].lc].r, mul, add, v[rt].lc), upd(v[v[rt].rc].l, r, mul, add, v[rt].rc);
v[rt].Seg::operator=(up(v[v[rt].lc], v[v[rt].rc]));
}
int query(int k, int r, int rt = 0)
{
if (v[rt].l == v[rt].r)
return v[rt].l;
int ans = v[0].r + 1;
if (ans >= v[0].r + 1 && v[rt].lc != NPOS && v[v[rt].lc].r >= k && v[v[rt].lc].max > r)
ans = min(ans, query(k, r, v[rt].lc));
if (ans >= v[0].r + 1 && v[rt].rc != NPOS && v[v[rt].lc].r < v[0].r && v[v[rt].rc].max > r)
ans = min(ans, query(k, r, v[rt].rc));
return ans;
}
};
int t, n, m, ans, a[N];
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d%d", &n, &m);
SegmentTree t(1, n);
for (int i = 1, x; i <= n; ++i)
{
scanf("%d", &a[i]);
t.upd(a[i], a[i], 0, i);
}
for (int i = ans = 0, r, k; i < m; ++i)
{
scanf("%d%d", &k, &r);
if (k == 1)
t.upd(a[r ^ ans], a[r ^ ans], 0, n + 1);
else
{
scanf("%d", &k);
printf("%d\n", ans = t.query(k ^ ans, r ^ ans));
}
}
}
}
K-th occurrence
涉及到子串之间的关系的大量查询不难想到后缀自动机/后缀树，这里给出一个后缀自动机的做法。 对串$S$建后缀自动机，扒出 parent 树。 考虑将代表第$i$个前缀$S_1S_2\dots S_i$的点权值设为 ，对于后缀自动机上某个点代表的所有字符串，这些串 在原串中的第 次出现位置（最后一个字符的下标）即为其在 parent 树的子树上第 大的权值。 在 dfs 序上建持久化线段树即将其转化为一个经典问题：静态区间第 K 大。 在 parent 树上建倍增数组即可在$O(\log n)$内找到自动机上代表某子串的点，以其为根进行子树询问即 可。
队友做的，待补。
1
Path
先把每条边以$(u,v,w)$形式放进堆，堆按路径权值从小到大排序，然后每次取出堆顶，用 v 的出边扩展新的路径。但是一个点的出度可能会非常大（如菊花图），可以发现，将出边排序之后，每次只需要扩展当前点最小的出边，和扩展到当前点的边的下一条边即可。堆中需要记录当前结点，当前距离，上一节点距离，扩展到当前节点时下一条应该扩展的边。（注意，如果一次性扩展当前点连出去的所有权值相同的边，是会 TLE 的，实际上也是没有必要的。） 复杂度$O(k\log (m+k))$
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 9;
ll d[N];
int t, n, m, k, a[N];
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d%d%d", &n, &m, &k);
priority_queue<pair<ll, int>> q0;
priority_queue<int> q1;
vector<vector<pair<ll, int>>> g(n);
for (int i = 0, u, v, w; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
q0.push({-w, v - 1});
q1.push(w);
g[u - 1].push_back({w, v - 1});
}
for (int i = 0; i < k; ++i)
scanf("%d", &a[i]);
for (int i = 0; i < n; ++i)
sort(g[i].begin(), g[i].end());
for (int i = 1, mx = *max_element(a, a + k), x; i <= mx; ++i)
{
d[i] = -q0.top().first;
x = q0.top().second;
q0.pop();
for (int j = 0; j < g[x].size(); ++j)
{
ll y = g[x][j].second, dis = d[i] + g[x][j].first;
if (q1.size() == mx)
{
if (dis > q1.top())
break;
q1.pop();
}
q1.push(dis);
q0.push({-dis, y});
}
}
for (int i = 0; i < k; ++i)
printf("%lld\n", d[a[i]]);
}
}
huntian oy
队友做的，莫比乌斯反演。待补。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e6 + 9, inv = 166666668, M = 1e9 + 7;
int t, n, prime[N], a, b, cnt, q, isnprime[N];
ll sum[N];
void sieve()
{
sum[1] = isnprime[1] = 1;
for (ll i = 1; i < N; ++i)
{
if (!isnprime[i])
{
prime[++cnt] = i;
sum[i] = -1;
}
for (int j = 1; j <= cnt && prime[j] * i < N; j++)
{
if (i % prime[j] == 0)
{
isnprime[i * prime[j]] = 1;
sum[i * prime[j]] = 0;
break;
}
isnprime[i * prime[j]] = 1;
sum[i * prime[j]] = -sum[i];
}
}
for (int i = 1; i < N; ++i)
sum[i] = sum[i - 1] + sum[i] * i;
}
ll djsg(int n)
{
static map<int, ll> mp;
if (n < N)
return sum[n];
if (q = mp[n])
return q;
ll ret = 1;
for (int l = 2, r; l <= n; l = r + 1)
{
r = n / (n / l);
ret = (ret - djsg(n / l) * (1LL * (r - l + 1) * (l + r) / 2 % M) % M + M) % M;
}
return mp[n] = ret;
}
ll f(int n) { return (1LL * n * n % M * n % M - n + M) % M * inv % M; }
int main()
{
sieve();
for (scanf("%d", &t); t--;)
{
scanf("%d%d%d", &n, &a, &b);
ll ans = 0;
for (int l = 1, r; l <= n; l = r + 1)
{
r = n / (n / l);
ans = (ans + (djsg(r) - djsg(l - 1) + M) % M * f(n / l) % M) % M;
}
printf("%lld\n", ans);
}
}
Shuffle Card
签到
花絮：我校十一队和四川大学校队代码被查重了（显然是误杀）…签到题查重简直了…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int n, m, a[N], s[N], vis[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= m; ++i)
scanf("%d", &s[i]);
for (int i = m; i; --i)
if (!vis[s[i]])
printf("%d ", s[i]), vis[s[i]] = 1;
for (int i = 1; i <= n; ++i)
if (!vis[a[i]])
printf("%d ", a[i]);
}
Windows Of CCPC
签到
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
#include <bits/stdc++.h>
using namespace std;
char s[1 << 10][1 << 10];
int t, k;
void dfs(int x, int y, int n, char c = 'C')
{
if (n == 1)
{
s[x][y] = c;
return;
}
n >>= 1;
dfs(x, y, n, c);
dfs(x, y + n, n, c);
dfs(x + n, y + n, n, c);
dfs(x + n, y, n, c == 'C' ? 'P' : 'C');
}
int main()
{
dfs(0, 0, 1 << 10);
for (scanf("%d", &t); t--;)
{
scanf("%d", &k), k = 1 << k;
for (int i = 0; i < k; ++i, printf("\n"))
for (int j = 0; j < k; ++j)
printf("%c", s[i][j]);
}
}
Fishing Master
每条鱼都需要被抓上来并且煮足够的时间，而我们能在炖鱼的时候抓鱼，所以至少需要抓一条鱼的时间 和炖所有鱼的时间，也就是$k+\sum_{i=1}^nt_i$。要能在这个时间内就完成，则除了抓第一条鱼以外抓鱼的时 候锅里都必须在炖鱼（假设锅里的鱼一旦炖好就自动取出来），显然如果 都太小的时候这是不能做到 的，会有一些抓鱼的时间锅里没有在炖鱼，我们称锅里没有炖鱼的抓鱼时间为被浪费的时间，所以我们 的优化目标就是使被浪费的总时间$T$最小，答案即为$k+\sum_{i=1}^nt_i+T$。 对于第$i$条鱼，炖它的时候我们可以不浪费时间抓到$t_i/k$条鱼，或者浪费$k-t_i%k$的时间抓到$t_i/k+1$条鱼。所以如果$\sum_{i=1}^nt_i/k\ge n-1$，则可以不浪费时间完成任务；如果$\sum_{i=1}^nt_i/k<n-1$，则差$m$条鱼就选炖$t_ik$前$m$大的鱼的时候浪费时间多抓一条鱼。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 9;
int T, n;
ll k, la[N], sum[N];
struct Data
{
ll wa, num, tot;
bool operator<(const Data &b) const { return wa != b.wa ? wa > b.wa : num > b.num; }
} a[N];
int main()
{
for (scanf("%d", &T); T--;)
{
scanf("%d%lld", &n, &k);
for (int i = 1; i <= n; i++)
{
ll t;
scanf("%lld", &t);
a[i].num = t / k;
a[i].wa = t % k;
a[i].tot = t;
}
sort(a + 1, a + 1 + n);
la[n + 1] = 0;
sum[n + 1] = 0;
for (int i = n; i >= 1; i--)
{
la[i] = la[i + 1] + a[i].num;
sum[i] = sum[i + 1] + a[i].tot;
}
int ok = 0;
ll last = 0, ans = 1e18;
for (int i = 1; i <= n; i++)
{
if (last <= 0)
last = a[++ok].tot;
if (i != 1)
last -= k;
if (la[ok + 1] + i >= n)
ans = min(ans, k * i + max(last, 0ll) + sum[ok + 1]);
}
printf("%lld\n", ans);
}
}
Kaguya
$dp[i][j][k][l]$表示从$1$号点开始 bfs 到第$i$步, 用了白点$i$个, 黑点$j$个, 且第$i$层个数正好为$l$的期望。 通过枚举新层的节点个数进行转移。 复杂度$O(n^5)$
1
Touma Kazusa’s function
1
sakura
1