天坑待填

洛谷自己出的题目质量非常的不错,而且适合我这种菜鸡选手玩耍。希望经过5场团队合作的比赛,算法能力能够有一些提升吧。

Round1

第一次多人比赛,还蛮有意思的。三个人群电话讨论,体验很不错,感觉比自己一个人做题有趣多了。

整个比赛8道题,乱序。

A À la Volonté du Peuple

T122393

这题是我做的,感觉是这场比赛里自己最有贡献的题了。

题目概述

大概就是一个带重边和自环的无向带权图,点n,边m,1号点有火焰,每秒不停的向没有火焰的地方扩散,两个以及两个以上的火焰的前沿在相遇时会产生一次爆炸,统计在火焰烧便每一条边和每一个点之前会发生的爆炸总数。

1≤n≤3e5

1≤m≤1e6

题解

考虑火焰碰撞的地点:

  1. 在边上碰撞

    在这种情况下,火焰肯定是从两个已经相邻的有火焰的点传入边上的。所以考虑有火焰的点,易得火焰传入的路径是从源点到本点的最短路。

    1. 如果这条边不属于从源点到边两边点的任意一条最短路,那么两边的火焰一定会在这里碰撞。显然,不属于最短路的边一定大于两边最短路之差,这就是判断的依据。
    2. 如果这条边属于两边点的最短路,那么这条边一定会将火焰从边的一端传到另一端。因此不会发生碰撞

    统计这样的边个数即可。

  2. 在点上碰撞

    这种情况下,火焰一定是从不唯一最短路来到这个点上的。所以只需要统计最短路不唯一的点个数即可。

代码

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
#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 300010
#define M 1000010
const int inf = 0x3f3f3f3f;
int dis[N];
int n, m, s;
struct edge
{
int to, cost;
};
vector<edge> G[N];
struct node
{
int len, v;
friend bool operator<(node x, node y)
{
return x.len > y.len;
}
};
void Dijkstra()
{
priority_queue<node> q;
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
node t;
t.len = 0;
t.v = s;
q.push(t);
while (q.size())
{
t = q.top();
q.pop();
if (dis[t.v] < t.len)
continue;
for (int i = 0; i < G[t.v].size(); i++)
{
edge &e = G[t.v][i];
if (dis[e.to] > dis[t.v] + e.cost)
{
dis[e.to] = dis[t.v] + e.cost;
node temp = {dis[e.to], e.to};
q.push(temp);
}
}
}
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++)
{
int a, b, w;
edge t, rt;
scanf("%d %d %d", &a, &b, &w);
t.to = b;
t.cost = w;
rt.to = a;
rt.cost = w;
G[a].push_back(t);
G[b].push_back(rt);
}
s = 1;
Dijkstra();
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < G[i].size(); j++)
{
edge &e = G[i][j];
if ((dis[e.to] - dis[i]) * (dis[e.to] - dis[i]) < e.cost * e.cost)
ans++;
}
}
ans /= 2;
for (int i = 1; i <= n; i++)
{
int flag = 0;
for (int j = 0; j < G[i].size(); j++)
{
edge &e = G[i][j];
if (dis[i] - dis[e.to] == e.cost)
{
flag++;
}
}
if (flag > 1)
ans++;
}
printf("%d", ans);
return 0;
}

B Billionaire

T122394

计算日期的大模拟~~(不是我写的)~~。

标程是zeller公式。

标程代码

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
#include <bits/stdc++.h>
using namespace std;

int getId(int y, int m, int d) {
if (m < 3) {y --; m += 12;}
return 365 * y + y / 4 - y / 100 + y / 400 + (153 * (m - 3) + 2) / 5 + d - 307;
}
vector<int> date(int id) {
int x = id + 1789995, n, i, j, y, m, d;
n = 4 * x / 146097;
x -= (146097 * n + 3) / 4;
i = (4000 * (x + 1)) / 1461001; x -= 1461 * i / 4 - 31;
j = 80 * x / 2447; d = x - 2447 * j / 80; x = j / 11;
m = j + 2 - 12 * x; y = 100 * (n - 49) + i + x;
return vector<int>({y, m, d});
}


void work() {
int M, y, m, d;
scanf("%d%d%d%d", &M, &y, &m, &d);
int id = getId(y, m, d);
int l = 0, r = sqrt(2e9);
while (l < r) {
int mid = (l + r) / 2;
int v = M + (0 + mid) * (mid + 1) / 2;
if (v >= 1000000000) r = mid;
else l = mid + 1;
}
id += l;
auto ret = date(id);
printf("%d %d %d\n", ret[0], ret[1], ret[2]);
}

int main() {
int T;
scanf("%d", &T);
while (T--) work();
}

C Counting K-ary Palindromes

T122395

确认过眼神,是不会做的题。流下了数学不好的眼泪。

题目概述

求k进制下能被p整除的所有的长度为n的回文数字的个数模998244353的值。

1≤n≤1e18

2≤k≤16

2≤p≤1000且p为质数

题解

这题没怎么听懂。

首先考虑p 与k 不互素的情况。这种情况下,整除只与最后一位有关,且有kp− 1 种取法,其余位任取。注意k = p 时答案为[n = 1],可能会导致部分没有特判的程序挂掉。现在考虑(p, k) = 1 的情况。考虑暴力:dpi,j 表示前i 位和后i 位填好了,其余位取0 时mod p = j的方案数。更新一位的复杂度是O(kp) 的,总复杂度是O(nkp) 的。考虑优化,由费马小定理,ki mod p 存在长度为p − 1 循环节,因此ki + kn−i−1 mod p 也有长度为p − 1 的循环节。按p − 1 分块后,每块的贡献是相同的,而块的背包合并可以通过类似多项式乘法的循环卷积来实现,因此就可以快速幂了。
预处理一个块和处理边缘的零散部分的复杂度是O(kp2), 一次块的暴力卷积是O(p2) 的,因此总复杂度为O(kp2 + p2(log n − log p))。
标程使用vector 实现,不开O2 也只跑了一秒,应该是不卡常的。

标程代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define read(a) scanf("%d", &a)
#define x first
#define y second

#define MOD 998244353

LL power(LL x, LL y, LL z) {
LL ret = 1;
for ( x %= z; y; y >>= 1) {
if (y & 1) ret = ret * x % z;
x = x * x % z;
}
return ret;
}

LL n;
int p, K;

void init(vector <int> & a) {
a.clear();
a.resize(p);
a[0] = 1;
}

void upd(vector <int> &a, LL b, int st = 0) {
int x;
if (b == n - b - 1) {
x = int(power(K, b, p)) % p;
} else {
x = int(power(K, b, p) + power(K, n - b - 1, p)) % p;
}
vector <int> c;
c.resize(p);
for (int i = st; i < K; i++) {
for (int j = 0; j < p; j++) {
(c[(j + i * x) % p] += a[j]) %= MOD;
}
}
swap(a, c);
}

void mul(vector <int> &a, vector <int> &b) {
vector <int> c;
c.resize(p);
for (int i = 0; i < p; i++)
for (int j = 0; j < p; j++) {
int x = (i + j) % p;
c[x] = int((c[x] + (LL)a[i] * b[j]) % MOD);
}
swap(a, c);
}

void power(vector <int> &a, long long b) {
vector <int> ret;
init (ret);
for ( ; b; b >>= 1 ) {
if (b & 1) mul(ret, a);
mul(a, a);
}
swap(a, ret);
}

vector <int> ans, tr;

int main() {
scanf("%lld%d%d", &n, &p, &K);
if (n == 1) {
int aa = 0;
for (int i = 0; i < K; i++) {
if (i % p == 0) aa ++;
}
cout << aa << endl;
return 0;
}
LL sz = n / 2 - 1;
if (K % p == 0) {
cout << (K / p - 1) * power(K, sz + (n & 1), MOD) % MOD << endl;
return 0;
}
init(ans);
init(tr);
LL tot = sz / (p - 1);
if (tot) {
for (int i = 2; i <= p; i++) {
upd(tr, i - 1);
}
power(tr, tot);
mul(ans, tr);
}
upd(ans, 0, 1);
for (long long i = 2 + tot * (p - 1); i <= (n + 1) / 2; i++) {
upd(ans, i - 1);
}
printf("%d\n", ans[0]);
}

D Deceiver

T122396

又是数学题,还起源于罪恶的a*b-(a+b)。当场找规律,但是失败了,不会做。

题目描述

T组数据,给定A,B求对于任意非负数x,y使得Ax+By不能组成的第k小的数。

1≤T≤10

1≤A,B≤1e7且A,B互质

1≤K≤1e18

题解

考虑mod B = 0 · · ·B − 1 的最小能被表示的值是多少——大于他们的可以通过+kB 得到。假设这样的最小值分别为m0,m1, · · · ,mB−1,那么小于等于K 的能被表示的非负整数的数量是

考虑如何求mi。由反证法可知0, A, · · · , (B − 1)A 在mod B 意义下必然互不相同,而这些数就枚举了mi。因此,当K < AB 时,上式化为

这是一个非常经典的直线下整点问题,使用类欧几里得算法可以在O(log max(A,B)) 的时间内求解。因此我们得到了计算小于等于K 的能被表示的非负整数的数量的工具,再二分一下就能解决原问题了。时间复杂度O(T log max(A,B) log min(K,AB)),可以通过A,B ≤ 1018, T ≤ 1000 的数据,也即本题原本的数据范围。
考虑到直线下整点是一个掏板子工作,因此放过了暴力。暴力可以这么写:假设A < B,我们尝试计算[kB, (k + 1)B) 这一段里有多少可以被表达出来的,那其实就是{(iA mod B) + kB|iA < (k + 1)B}的集合大小,枚举iA 计算确定答案在哪一段后,再在段内确定就好了——而段内有多少能被表达的已经被枚举了,打好标记for 一下就行了。时间复杂度O(T max(A,B))。

标程代码

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 <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL solve(LL n, LL a, LL b, LL m) {
if (b == 0) return n * (a / m);
if (a >= m) return n * (a / m) + solve(n, a % m, b, m);
if (b >= m) return (n - 1) * n / 2 * (b / m) + solve(n, a, b % m, m);
return solve((a + b * n) / m, (a + b * n) % m, m, b);
}

LL A, B, K;

void work() {
scanf("%lld%lld%lld", &A, &B, &K);
LL l = 1, r = (double)A * B > 3e18 ? 2e18 + 10 : min(LL(2e18) + 10, A * B - 1);
assert(double(A - 1) * (B - 1) / 2 >= K);
while (l < r) {
LL mid = (l + r) / 2;
LL n = mid / A + 1, m = B, a = mid - (n - 1) * A + B, b = A;
LL tot = solve(n, a, b, m) - 1;
LL cnt = mid - tot;
if (cnt >= K) r = mid;
else l = mid + 1;
}
printf("%lld\n", l);
}

int main() {
int T;
scanf("%d", &T);
while (T--) work();
}

E Everybody deserves a long long name

T122397

毒瘤大模拟,考察编辑器的替换功能。

F Final Spark

T122398

这题挺可惜的,差点能A的。

题目概述

T组数据,一个直径为t的小圆的圆心在半径为s的大园内部以最小概率接触到一个以大圆圆心到距离大圆圆心d距离远处一点连线为中轴线、不确定方向、宽度为w、长度无限的矩形的最佳策略进行随机游走,现可以决定矩形的方向,问其接触小圆的最大概率。

1≤T≤1e5

0≤w,t,s≤1000

1≤d≤3000

题解

w + t 相同的数据都没有本质区别,因此可以转化为r′ = 0,w′ = w + t 的题目来做。无论以什么角度射入圆,我们都可以把圆旋转到激光为竖直的情况来开,因此问题就转化为用一个可水平平移的无限长w + t 宽的长方形切一个半径为s 的圆能切下的最大边长。求导可知相切时边长取最大值,因此计算相应弧长即可。

标程代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

long double w, r, d, s;
void work() {
int W, R, D, S;
scanf("%d%d%d%d", &W, &R, &S, &D);
W += R;
if (W >= 2 * S) puts("1.000000000");
else if (W == 0) puts("0.000000000");
else {
w = W, d = D, s = S;
long double a = s - w;
long double deg = acosl(a / s);
printf("%.9lf\n", double(deg / acosl(-1)));
}
}

int main() {
int T;
scanf("%d", &T);
while (T--) work();
}

G Goldbach’s conjecture

T122399

刚刚开始看到1e9的数字挺吓人的,但是看了一眼大家的提交记录发现事情好像就是这么简单,暴力写过了。

面向提交编程

题目概述

大概就是判断一个偶数n是否能被拆成两个素数之和。

4≤n≤1e9

题解

题解就是暴力判断质数。

人傻了,竟然是暴力判断。

在这里证明一下复杂度。

考虑素数分布:O( nlog n)。不太严谨地近似为随机分布,则可以认为枚举成功的概率是O( 1/log2 n) 的。因此就算暴力判断跑得很满,也是O(√nlog2 n) 的。
实测109 以内最小表示最大的偶数是721013438 = 1789 + 721011649。

H Hazardous

T122400

这题当时想到要维护一个可并的数据结构,但是没有想到具体的维护办法,最后也没时间写了。

题目概述

一个n节点的有根树,树上的点被染成不同的颜色,相同的颜色的点集合中每两两点之间的简单距离可以向这两点的所有公共祖先贡献价值,求每个节点的子树中的价值。

1≤n≤1e5

题解

采用支持合并的数据结构,下标维护标号,信息维护深度总和与点数,在每个点合并子树信息并维护答案。合并的两端的某个颜色的信息分别为(dep1, cnt1), (dep2, cnt2),当前点深度为d,则合并时产生贡献dep1× cnt2 + dep2× cnt1 − 2d × cnt1 × cnt2

采用线段树合并等的时间复杂度为O(n log n),采用启发式合并的set(map) 也能够以O(n log2 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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

#define N 201111


struct Node {
LL dep;
int l, r, cnt;
} t[N * 19];

int n, tcnt;
int a[N], rt[N], dep[N];
vector <int> E[N];
LL sc[N], delta;
int curdep;

int Merge(int x, int y, int l, int r) {
if (!y) return x;
if (!x) return y;
if (l == r) {
delta += t[x].dep * t[y].cnt + t[y].dep * t[x].cnt - 2ll * curdep * t[x].cnt * t[y].cnt;
t[x].dep += t[y].dep;
t[x].cnt += t[y].cnt;
}
else {
int mid = (l + r) / 2;
t[x].l = Merge(t[x].l, t[y].l, l, mid);
t[x].r = Merge(t[x].r, t[y].r, mid + 1, r);
}
return x;
}

int init(int p, int l, int r) {
int x = ++tcnt;
if (l < r) {
int mid = (l + r) / 2;
if (p <= mid) t[x].l = init(p, l, mid);
else t[x].r = init(p, mid + 1, r);
}
else t[x].dep = curdep, t[x].cnt = 1;
return x;
}

void dfs(int x, int fa) {
curdep = dep[x];
rt[x] = init(a[x], 1, n);
for (auto v : E[x]) if (v != fa){
dep[v] = dep[x] + 1;
dfs(v, x);
sc[x] += sc[v];
delta = 0;
curdep = dep[x];
rt[x] = Merge(rt[x], rt[v], 1, n);
sc[x] += delta;
}
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
E[u].push_back(v);
E[v].push_back(u);
}
dfs(1, -1);
for (int i = 1; i <= n; i++) printf("%lld ", sc[i]);
}

Round2

这场真的好自闭😢我太难了,完全不会做

A Misaka Network

T123571

题目概述

选择n个点,m条边的DAG中尽量少的节点使得图中所有n个节点都有前驱

1≤n≤1e5

1≤m≤1e6

题解

拓扑排序按顺序贪心去掉相邻的点,选择剩下的点

标程代码

B Mana Eel’s Problem

T123572

题目概述

给定n个整数和x,q次查询从l到r区间内下式的值

其中的

1≤n,q≤3e5

0≤x<998244353

1≤ai≤1e15

LCM(a1,a2,…,an)≤1e15

1≤lrn

题解

暴力算出μ然后线段树

标程代码

C Schedule

T123573

超级恶心的大模拟,map套map套map

考察处理读入字符串😩

D Voluntary Hotel

T123574

题目概述

n个点m条带权为wi的边的无向图,有p个医院,r个医生,每个医都有自己的家,q个宾馆,第i个宾馆可以额外容纳hi个医生,每个医生会选择最短路径从家或者宾馆到医院,家和医院都在某些节点上,现在要给一些医生分配宾馆,让所有医生中走路最多的医生走的路尽可能的少

1≤nm≤1e4

1≤p,q≤100

1≤r≤1e6

1≤wi≤1e9

题解

二分以后网络流判断满流

标程代码

E Anan and Minecraft

T123575

题目概述

有两个n个节点的图,两图总共m条边,现在给两图分别加边,判断每次加边后对于所有的任意一对在第一个图中联通的节点在第二个图中是否全部分别联通

1≤n≤1e5

1≤m≤2e5

题解

双队列

哈希

标程代码

F Rebuild Teldrassil

T123576

题目概述

一颗n节点的树,每个节点有权值,如果树上某两点之间唯一简单路径经过的点的权值的中位数(偶数情况取位于中间较大的一个)大于等于x,我们称这个路径为关键路径,现在可以任意增加一个节点的权值到任意大,如何使得树上的关键路径数量尽量多

1≤n≤3e5

题解

转化为求和统计问题

然后点分治

标程代码

G Mana Eel’s Graph

T123577

题目概述

给定一个n节点m条边的带权ai和带重bi的无向图,定义子图G的权为A(G)=∏u∈Gau,重为B(G)=∏u∈Gbu,现在要选择所有的非空完全子图G‘使得X为A的和,Y为B的和,求X*Ymod998244353的值

1≤n≤40

1≤ai,bi≤1e9

题解

求补图然后算最大独立,然后分别计算权和重

标程代码

H Fetch spring water

T123578

会溢出的乘法,签到题~~(签了好久我好菜)~~

Round3

A Able was I ere I saw Elba

T124758

题目概述

题解

B Bit fixer

T124753

题目概述

题解

C Coprime

T124755

题目概述

n个数字,需要让相邻的数字互质,求最少应该修改的数个数

题解

贪心枚举就可以了

D Dodo bird painting

T124757

题目概述

一个序列的xi处有t堆墨水,每堆墨水向左右扩散,速度为vi,求整个序列被全部覆盖的最早时间

题解

二分答案,然后按左端点排序贪心判断即可

E Eluos blocks

T124756

题目概述

题解

F

题目概述

题解

G

题目概述

题解

H Huaji robot

T124754

题目概述

求边长n正方形做表面内的横纵坐标互质整点中某两个点的可达性

题解

双起点BFS到主对角线即可。

下面证明复杂度:

观察一个对角线下的三角,任意整数n的质因子是logn级别的,也就是说在x=p1,和x=p2的两条横线之间,所以每个连通块最大为(logn*max(p~i~-p~j~))^2^。再加上整个对角线互相联通,双边BFS到这里判断就可以了。

Round4

Round5