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

比赛
字数统计: 2.2k   |   阅读时长≈ 11 分钟

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:

请我喝杯咖啡吧~

支付宝
微信