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

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:

请我喝杯咖啡吧~

支付宝
微信