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

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

A-I love cube

题目大意

给你一个边长为n-1的立方体，问这个立方体中，三个点都在整数点上的等边三角形有多少。

解题思路

观察得，答案为$8\times\sum \limits_{i = 1}^{n-1} i^3$。

对于$1^3+2^3+3^3+\dots+n^3$，公式为${(\frac{n\times(n+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
ll mod = 1e9 + 7;
ll qpow(ll a, ll b, ll mod) {
    ll ans = 1;
    while (b) {
        if (b & 1)    ans = (ans * a) % mod;
        a = (a * a) % mod, b >>= 1;
    }
    return ans % mod;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll t = qpow(2, mod - 2, mod);
    int T; cin >> T;
    while (T--) {
        ll n; cin >> n;
        n--;
        n %= mod;
        ll ans = n % mod;
        ans = (ans * (n+1) % mod) % mod;
        ans = (ans * t % mod) % mod;
        ans = qpow(ans, 2, mod);
        ans = (ans * 8) % mod;
        cout << ans << endl;
    }
    return 0;
}

C-I love playing games

题目大意

给你一张无向图了，有两个人分别位于x点和y点，每一轮都可以前往相邻的点，两人不能同时位于一个点，问谁先到达终点。

解题思路

先对图进行bfs，求出终点到其他点的最短路。

如果$dis[x]!=dis[y]$，那谁路径短取胜。

如果$dis[x]==dis[y]$，那先手必不可能败，可能平局。

如果路径没有交点，那必定是平局。

如果路径存在交点，那需要考虑对于每个交点能取得情况，需要用dfs来遍历。

完整代码

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
struct node{
	int a, b, c;
};
const int INF = 1e9;
int n, m, x, y, z;
int dis[1010], dp[1010][1010][2];
vector<int> Map[1010], pre[1010];
vector<node> v;

void bfs() {
	queue<int> q;
	rep(i, 1, n)	dis[i] = INF;
	q.push(z), dis[z] = 0;
	while (!q.empty()) {
		int t = q.front(); q.pop();
		for (auto x : Map[t]) {
			if (dis[x] == INF) {
				dis[x] = dis[t] + 1;
				q.push(x);
			}
		}
	}
}

int dfs(int x, int y, int k) {
	if (!k && (x == z || y == z)) {
		if (x == y)	return 2;
		else if (x == z) return 1;
		return 3;
	}
	if (dp[x][y][k])	return dp[x][y][k];
	if (!k) {//先手
		int ans = 2;
		for (auto t : pre[x]) {
			if ((t != y || t == z) && dfs(t, y, k ^ 1) == 1) {//如果能取胜，则选择取胜
				ans = 1;
				break;
			}
		} 
		dp[x][y][k] = ans;
	}
	else {//后手
		int ans = 1;
		for (auto t : pre[y]) {
			if ((t != x || t == z) && dfs(x, t, k ^ 1) == 2) {//如果能平局，则选择平局
				ans = 2;
				break;
			}
		}
		dp[x][y][k] = ans;
	}
	v.push_back({ x,y,k });
	return dp[x][y][k];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		cin >> n >> m >> x >> y >> z;
		rep(i, 1, n)
			Map[i].clear();
		rep(i, 1, m) {
			int u, v; cin >> u >> v;
			Map[u].push_back(v);
			Map[v].push_back(u);
		}
		bfs();
		if (dis[x] != dis[y]) {
			if (dis[x] > dis[y]) cout << 3 << endl;
			else cout << 1 << endl;
			continue;
		}
		if (dis[x] == INF) {
			cout << 2 << endl;
			continue;
		}
		rep(i, 1, n) {
			for (auto x : Map[i]) {
				if (dis[i] == dis[x] + 1) {
					pre[i].push_back(x);
				}
			}
		}
		cout << dfs(x, y, 0) << endl;
		rep(i, 1, n) 
			pre[i].clear();
		for (auto x : v)
			dp[x.a][x.b][x.c] = 0;
		v.clear();
	}
	return 0;
}

D-I love counting

题目大意

莫队加分块

解题思路

完整代码

E-I love string

题目大意

给你一串字符串，问你每次可以按照字符串顺序，将字符串中的字母放到另外一个空字符串的首位或者末尾，问有多少种方式能够使空字符串的字典序最小。

解题思路

签到题，按照思路模拟即可。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int mod = 1000000007;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        string s; cin >> s;
        ll ans = 1;
        char f = s[0], l = s[0];
        rep(i, 1, n) {
            if (f == l) {
                if (f == s[i])    ans = (ans * 2) % mod;
                else if (f > s[i])    f = s[i];
                else l = s[i];
            }
            else if (f >= s[i])    f = s[i];
            else l = s[i];
        }
        cout << ans << endl;
    }
    return 0;
}

H-I love exam

题目大意

给你n个科目，每个科目初始是0分，每个科目都有若干个复习资料，问在t天内，在挂p科以下能得到的最高分。

解题思路

对于每个科目，我们可以用$f[i][j]$来表示对于第i门科目来说，花费j天能得到的最多分数。、

这样就转换成了对于每一个科目进行01背包。

之后可以用$dp[i][j][k]$来表示对于前i门科目，花费j天，挂k科能得到的最多分数。

然后在dp一遍即可。

对于某一门不及格的情况下，当$k!=0$时，$dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-g][k-1]+f[i][g])$。

当这门科目可以及格的时候，$dp[i][j][k] = max(dp[i][j][k],dp[i-1][k-g][k]+f[i][g])$。

完整代码

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
map<string, int> M;
vector<pair<int, int>> v[100];
int f[100][550];
int dp[100][550][5];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		memset(f, -0x3f, sizeof(f));
		memset(dp, -0x3f, sizeof(dp));
		M.clear();
		rep(i, 1, n) {
			string s; cin >> s;
			M[s] = i;
			v[i].clear();
		}
		int m; cin >> m;
		rep(i, 1, m) {
			string s; int x, y;
			cin >> s >> x >> y;
			v[M[s]].push_back({ x,y });
		}
		int t, p; cin >> t >> p;
		rep(i, 1, n) {
			f[i][0] = 0;
			for (auto x : v[i]) {
				for (int j = t; j >= x.second; j--) {
					f[i][j] = min(100, max(f[i][j], f[i][j - x.second] + x.first));
				}
			}
		}
		dp[0][0][0] = 0;
		rep(i, 1, n) {
			rep(j, 0, t) {
				rep(k, 0, p) {
					rep(g, 0, j) {
						if (f[i][g] < 60 && k)
							dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - g][k - 1] + f[i][g]);
						if (f[i][g] >= 60)
							dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - g][k] + f[i][g]);
					}
				}
			}
		}
		int ans = -1;
		rep(i, 0, p)	ans = max(ans, dp[n][t][i]);
		cout << ans << endl;
	}
	return 0;
}

K-I love max and multiply

题目大意

给你两个长度为n的序列A和B，定义一个序列C，满足$C_k=max\lbrace A_iB_j\rbrace，(i\text{&}j\geq k)$，求序列C的和。

解题思路

C序列不好求，我们可以先转为D序列，$D_k=max \lbrace A_iB_j\rbrace,(i\text{&}j=k)$，然后对D序列从小到大遍历。

但是$i\text{&}j=k$也不好求，我们可以转为求包含k的情况。

我们发现，当需要满足$i\text{&}j=i$的时候，j只需要把i二进制中的0变成1即可。

可能会存在某些需要变多个1的情况，但是可以发现，这个变多个1的情况，在之前已经是出现过了的。

所以我们只需要对i枚举每一位，只用考虑变一个1的情况，记录所有情况的最大值和最小值（因为存在负数），这样就能保证从大到小枚举，一定能够枚举到大于等于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
const ll N = 1e6 + 5, INF = 1e18, mod = 998244353;
ll A[N], a[N], B[N], b[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		rep(i, 0, n - 1) {
			cin >> A[i]; a[i] = A[i];
		}
		rep(i, 0, n - 1) {
			cin >> B[i]; b[i] = B[i]                   ;
		}
		ll m = 1;
		while (m < n)	m <<= 1;
		rep(i, n, m) {
			A[i] = B[i] = -INF;
			a[i] = b[i] =  INF;
		}
		per(i, n - 1, 0) {
			for(int j = 1;j < m;j <<= 1){
				if (!(j & i)) {
					A[i] = max(A[i], A[i ^ j]);
					a[i] = min(a[i], a[i ^ j]);
					B[i] = max(B[i], B[i ^ j]);
					b[i] = min(b[i], b[i ^ j]);
				}
			}
		}
		ll ans = 0, f = -INF;
		per(i, n - 1, 0) {
			ll t = -INF;
			t = max(t, A[i] * B[i]);
			t = max(t, A[i] * b[i]);
			t = max(t, a[i] * B[i]);
			t = max(t, a[i] * b[i]);
			t = max(t, f);
			f = t;
			ans = (ans + t % mod + mod) % mod;
		}
		cout << (ans + mod) % mod << endl;
	}
	return 0;

}

L-I love 114514

题目大意

弱智题

解题思路

用find来找string中是否存在114514子串，不存在则返回-1。

完整代码

1
2
3
4
5
6
7
8
9
10
11
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		string s; cin >> s;
		if (s.find("114514") == -1)    cout << "Abuchulaile" << endl;
		else cout << "AAAAAA" << endl;
	}
	return 0;
}
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

扫一扫，分享到微信

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

请我喝杯咖啡吧~

支付宝
微信