牛客周赛 Round 55
A
正常枚举。
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
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 1e3 + 100;
ll a[N];
int n, m, k, t;
struct Node
{
ll l, r, id;
} b[N];
struct Edge
{
ll to;
ll w;
};
vector<Edge> edge[N];
void _dijkstra(int s, vector<ll> &dist)
{
vector<bool> vis(n + 1, false);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
dist[s] = 0;
q.push({0, s});
while (!q.empty())
{
ll x = q.top().second;
q.pop();
if (vis[x])
continue;
vis[x] = true;
for (auto &y : edge[x])
{
if (dist[x] + y.w < dist[y.to])
{
dist[y.to] = dist[x] + y.w;
q.push({dist[y.to], y.to});
}
}
}
}
ll ksm(ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b & 1)
{
ans = ans * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return ans % mod;
}
int ans[N];
void Totoro()
{
string s;
cin >> s;
if (s[0] == s[1] && s[1] == s[2])
{
cout << 0 << '\n';
}
else if (s[0] != s[1] && s[1] != s[2] && s[0] != s[2])
{
cout << 2 << '\n';
}
else
{
cout << 1 << '\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Totoro();
return 0;
}
|
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
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
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 1e3 + 100;
ll a[N];
int n, m, k, t;
struct Node
{
ll l, r, id;
} b[N];
struct Edge
{
ll to;
ll w;
};
vector<Edge> edge[N];
void _dijkstra(int s, vector<ll> &dist)
{
vector<bool> vis(n + 1, false);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
dist[s] = 0;
q.push({0, s});
while (!q.empty())
{
ll x = q.top().second;
q.pop();
if (vis[x])
continue;
vis[x] = true;
for (auto &y : edge[x])
{
if (dist[x] + y.w < dist[y.to])
{
dist[y.to] = dist[x] + y.w;
q.push({dist[y.to], y.to});
}
}
}
}
ll ksm(ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b & 1)
{
ans = ans * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return ans % mod;
}
int ans[N];
void Totoro()
{
int n;
cin >> n;
int sum = 1;
int ans = 0;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
x = x % 10;
sum *= x;
if (sum % 10 == 6)
{
ans++;
}
sum %= 10;
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Totoro();
return 0;
}
|
C
正常排序一定最优。
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
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 1e6 + 100;
ll a[N];
ll ksm(ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b & 1)
{
ans = ans * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return ans % mod;
}
int ans[N];
void Totoro()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n - 2; i++)
{
if (a[i] * a[i + 1] == a[i + 1] * a[i + 2])
{
cout << "NO" << '\n';
return;
}
}
cout << "YES" << '\n';
for (int i = 1; i <= n; i++)
{
cout << a[i] << ' ';
}
cout << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Totoro();
return 0;
}
|
D
普通bfs，注意每次反向走到墙的位置即可。
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
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int N = 1e3 + 100;
ll ksm(ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b & 1)
{
ans = ans * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return ans % mod;
}
char a[N][N];
bool vis[N][N];
ll ans = 1e18;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
struct node
{
ll x, y, cnt;
};
int n;
void bfs(int x, int y)
{
queue<node> q;
q.push({x, y, 0});
vis[x][y] = 1;
while (!q.empty())
{
node p = q.front();
q.pop();
if (p.x == n && p.y == n)
{
ans = min(ans, p.cnt);
return;
}
for (int i = 0; i <= 3; i++)
{
int x = p.x + dx[i];
int y = p.y + dy[i];
if (a[x][y] == '1')
{
while (a[x - dx[i]][y - dy[i]] == '0')
{
x -= dx[i];
y -= dy[i];
}
}
if (!vis[x][y])
{
q.push({x, y, p.cnt + 1});
vis[x][y] = 1;
}
}
}
}
void Totoro()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cin >> a[i][j];
}
for (int i = 1; i <= n; i++)
{
a[0][i] = a[n + 1][i] = a[i][0] = a[i][n + 1] = '1';
}
bfs(1, 1);
if (ans == 1e18)
{
cout << -1 << '\n';
}
else
{
cout << ans << '\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Totoro();
return 0;
}
|
E
定义f[i][j]为前i个数字中，序列乘积个位数是j的方案数。
贡献就是再乘于\(2^{n-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
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
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int N = 1e5 + 100;
ll ksm(ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b & 1)
{
ans = ans * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return ans;
}
ll f[N][10];
ll a[N];
void Totoro()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] %= 10;
}
ll ans = 0;
f[0][1] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= 9; j++)
{
f[i][j] = (f[i][j] + f[i - 1][j]) % mod;
f[i][j * a[i] % 10] = (f[i][j * a[i] % 10] + f[i - 1][j]) % mod;
if (j * a[i] % 10 == 6)
{
ans = (ans + f[i - 1][j] * ksm(2, n - i) % mod) % mod;
}
}
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Totoro();
return 0;
}
|
