2021“MINIEYE杯”中国大学生算法设计超级联赛(1)

A-Mod, Or and Everything

题目大意

给你一个n,需要你求$(n mod 1) or (n mod 2) or … or (n mod (n - 1)) or (n mod n).$

解题思路

一眼规律题,打表找规律即可。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
ll n; cin >> n;
if (n <= 2) cout << 0 << endl;
else if (n <= 4) cout << 1 << endl;
else {
n -= 4;
ll t = 4;
while (n > t) {
n -= t;
t *= 2;
}
cout << t - 1 << endl;
}
}
return 0;
}

E-Minimum spanning tree

题目大意

给你n-1个点,标号从2到n,每两个点之间的边权为$lcm(a,b)$,求最小生成树的最小边权和。

解题思路

对于质数,则连接到2,贡献为i*2,对于合数,则连接到因数,贡献为i。

预处理素数筛打表。

完整代码

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
const int N = 1e7 + 5;
ll ans[N], prime[N];
int cnt = 0, vis[N];

void init(int maxn) {
rep(i, 2, maxn) {
if (!vis[i]) {
for (ll j = 2; j * i <= maxn; j++) {
vis[i * j] = 1;
}
if(i!=2) ans[i] = ans[i - 1] + 2 * i;
}
else ans[i] = ans[i - 1] + i;
}
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
init(N - 5);
int t; cin >> t;
while (t--) {
int n; cin >> n;
cout << ans[n] << endl;
}
return 0;
}

F-Xor sum

题目大意

给你一个长度为n的序列,需要你找到长度最小且左端点最小的区间,异或和不小于k。

解题思路

用01Trie树来处理。

先对序列求前缀异或,然后按顺序插入Trie树中。

在插入的时候,维护一下经过每个节点的的最大的位置。

在查询的时候,按每一位来判断,如果x这一位为0,k也为0,那么我取1一定比他大,可以更新一次答案,如果存在0的边,可以继续循环,如果x这一位为0,k为1,那么我只能在这一位寻找1的边,如果不存在就直接返回,1的情况类似,注意最后更新一下最终节点的答案。

数组要开大一点,但不能太大,注意初始化不能无脑memset。

完整代码

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
const int N = 1e5 + 5;
int trie[N * 31][2], cnt;
int num[N], sum[N], pos[N * 31], k;

void insert(int x, int p) {
int now = 0;
per(i, 30, 0) {
int t = x >> i & 1;
if (!trie[now][t]) trie[now][t] = ++cnt;
now = trie[now][t];
pos[now] = max(pos[now], p);
}
}

void query(int x, int& l) {
int now = 0;
per(i, 30, 0) {
int tx = x >> i & 1;
int tk = k >> i & 1;
if (!tx) {
if (!tk) {
l = max(l, pos[trie[now][1]]);
if (!trie[now][0]) return;
now = trie[now][0];
}
else {
if (!trie[now][1]) return;
now = trie[now][1];
}
}
else {
if (!tk) {
l = max(l, pos[trie[now][0]]);
if (!trie[now][1]) return;
now = trie[now][1];
}
else {
if (!trie[now][0]) return;
now = trie[now][0];
}
}
}
l = max(l, pos[now]);
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
cnt = 0;
int n; cin >> n >> k;
insert(0, 0);
rep(i, 1, n) {
cin >> num[i];
sum[i] = sum[i - 1] ^ num[i];
}
int l = 1e9, r = 1e9, len = 1e9;
for (int i = 1; i <= n; i++) {
if (sum[i] >= k) {
len = i;
l = 1, r = i;
break;
}
}
rep(i, 1, n) {
int p = 0;
query(sum[i], p);
insert(sum[i], i);
if (p) {
int tmp = i - p;
if (tmp < len) {
l = p + 1, r = i;
len = tmp;
}
else if (tmp == len && p + 1 < l) {
l = p + 1, r = i;
}
}
}
if (len == 1e9) cout << -1 << endl;
else cout << l << " " << r << endl;
rep(i, 0, cnt - 1) trie[i][0] = trie[i][1] = pos[i] = 0;
}
return 0;
}

G-Pass!

题目大意

有 n 个球员在足球场上传球。一开始只有第一个球员有球。之后每过一秒,有球的球员都会将球传给其他球员。

设$f(t)$为在 t 秒后,有多少种传球方式,球会回到第一个球员手中。

需要你找到最小的非负整数 t,使得 $f(t)$模 998244353 的答案为 x。

解题思路

首先根据题目描述可以得到$f(i)=(n-2)\times f(i-1)+(n-1)\times f(i-2)$。

然后通过特征方程求解得到$f(t)=\frac{(n-1)^t+(n-1)\times (-1)^t}{n}=x(mod 998244353)$。

变形得到$(n-1)^t+(n-1)\times(-1)^t = n\times x$,即需要求最小的这个t,设t为$i\times m-j $,其中m为$ceil(\sqrt{998244353})$。

最终得到式子$((n-1)^m)^i=(n\times x-(n-1)\times (-1)^j)\times (n-1)^j$,因为存在$(-1)^j$,所以需要分奇偶来用BSGS。

注意一下特判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
25
26
27
28
29
30
31
32
33
34
const ll mod = 998244353, m = 31596;
unordered_map<ll, ll> M;

int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
ll n, x; cin >> n >> x;
if (x == 1) {
cout << 0 << endl;
continue;
}
ll p = n - 1;
ll a = 1, b = n * x;
for (ll i = 0, t = 1; i < m; i++, t = t * p % mod) {
a = a * p % mod;
ll tmp;
if (i & 1) tmp = (b + p) % mod * t;
else tmp = (b - p) % mod * t;
M[tmp%mod] = i;
}
ll ans = -1;
for (ll i = 1, t = a; i <= m; i++, t = t * a % mod) {
if (M.count(t)) {
ans = i * m - M[t];
break;
}
}
cout << ans << endl;
M.clear();
}
return 0;
}

H-Maximal submatrix

题目大意

给你一个$n\times m$的矩阵,问这个矩阵中,满足每一列都从上到下非递减的最大子矩阵的面积是多少。

解题思路

先把矩阵每一点按照是否大于等于上一列的点分为0和1,如果满足大于等于上一列的点设为1,把这个矩阵转换为01矩阵。

然后用悬线法求出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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int v[2020][2020], u[2020][2020];
int h[2020], l[2020], r[2020];

int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
int n, m; cin >> n >> m;
rep(i, 1, n) {
rep(j, 1, m) {
cin >> v[i][j];
if (v[i][j] >= v[i - 1][j]) u[i][j] = 1;
else u[i][j] = 0;
}
}
rep(i, 1, m) h[i] = 0;
int ans = 0;
rep(i, 1, n) {
rep(j, 1, m) {
if (u[i][j]) h[j]++;
else h[j] = 1;
l[j] = r[j] = j;
}
rep(j, 2, m) {
while (l[j] > 1 && h[l[j] - 1] >= h[j])
l[j] = l[l[j] - 1];
}
per(j, m - 1, 1) {
while (r[j] < m && h[r[j] + 1] >= h[j])
r[j] = r[r[j] + 1];
}
rep(j, 1, m) ans = max(ans, (r[j] - l[j] + 1) * h[j]);
}
cout << ans << endl;
}
return 0;
}

I-KD-Graph

题目大意

给你一个n个点m条边的图,你需要把这些点恰好分为k组,分组时需要满足每一组中任意两点之间的路径满足最大值小于等于d,某一组之外的点与这一组的点任意路径最大值大于d,求d的最小值。

解题思路

类似kruskal算法的思路。

把每条边按照边权从小到大排序。

如果两点属于同一个集合,则不需要操作。

如果这两点不是同一个一个集合,则需要合并。

如果需要合并的时候,恰好分了k+1组,这时可以暂时认为d为这条边的边长,继续枚举,如果之后出现了两点不在同一个集合且边长为d,则答案无解。因为如果你选了这条边,组数就会小于k,如果你不选,则不满足题目要求。

特判一下k等于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
const int N = 5e5 + 5, maxn = 1e5 + 5;
struct side {
int u, v, dis;
bool operator <(const side& t) const {
return dis < t.dis;
}
}s[N];
int fa[maxn];

int find(int son) {
int root = son;
while (fa[root] != root) root = fa[root];
while (son != root) {
int t = fa[son];
fa[son] = root;
son = t;
}
return root;
}

void join(int son1,int son2) {
int rt1 = find(son1), rt2 = find(son2);
if (rt1 != rt2) fa[rt2] = rt1;
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
int n, m, k; cin >> n >> m >> k;
rep(i, 1, m) cin >> s[i].u >> s[i].v >> s[i].dis;
sort(s + 1, s + 1 + m);
rep(i, 1, n) fa[i] = i;
int ans = -1, group = n;
if (n == k) {
cout << 0 << endl;
continue;
}
rep(i, 1, m) {
int u = s[i].u, v = s[i].v, dis = s[i].dis;
int rt1 = find(u), rt2 = find(v);
if (rt1 != rt2) {
if (group == k + 1) ans = dis;
else if (group == k) {
if(dis==ans) ans = -1;
break;
}
group--;
join(rt1, rt2);
}
}
cout << ans << endl;
}
return 0;
}

J-zoto

题目大意

解题思路

莫队加分块,有点难,之后再补

完整代码

  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!

扫一扫,分享到微信

微信分享二维码
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信