牛客小白月赛75
A.上班
题意：
分析：
签到题
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x, y, z;
cin >> x >> y >> z;
cout << x + min(y, z);
return 0;
}
B.崇拜
题意：
分析：
按知识点难度从大到小排序，然后计算按这个顺序讲解的最大崇拜值。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N];
bool cmp(int A, int B)
{
return A > B;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, x, y;
cin >> n >> x >> y;
for (int i = 0; i < n; i ++)
cin >> a[i];
sort(a, a + n, cmp);
int res = 0, Max = -0x3f3f3f3f;
for (int i = 0; i < n; i ++)
{
if (a[i] > y)
res += 3;
else if (a[i] < x)
res --;
Max = max(Max, res);
}
cout << max(0, Max);
return 0;
}
C.方豆子
题意：
分析：
递归模拟一下就行了。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 3 * 1024 + 5;
char a[N][N];
char good[7][7] = {"******", "******", "******", "***...", "***...", "***..."};
char bad[7][7] = {"......", "......", "......", "...***", "...***", "...***"};
void setGood(int x, int y)
{
for (int i = 0; i < 6; i ++)
for (int j = 0; j < 6; j ++)
a[x + i][y + j] = good[i][j];
}
void setBad(int x, int y)
{
for (int i = 0; i < 6; i ++)
for (int j = 0; j < 6; j ++)
a[x + i][y + j] = bad[i][j];
}
void create(int x, int y, bool flag, int n)
{
if (n == 1)
{
if (flag)
setGood(x, y);
else
setBad(x, y);
return;
}
int m = 3 * (1 << n);
create(x, y, !flag, n - 1);
create(x, y + m / 2, !flag, n - 1);
create(x + m / 2, y, !flag, n - 1);
create(x + m / 2, y + m / 2, flag, n - 1);
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
create(0, 0, 1, n);
int m = 3 * (1 << n);
for (int i = 0; i < m; i ++)
{
for (int j = 0; j < m; j ++)
{
cout << a[i][j];
}
cout << endl;
}
return 0;
}
D.矩阵
题意：
分析：
由于只有相邻的元素互异才能移动，如果元素相同则修改，因此最终的路径一定是010101010……或者1010101010……交替。观察前面两种路径，我们可以发现，（x, y）处的元素与起点的元素满足一定条件：当哈夫曼距离为奇数时，（x，y）的元素与起点不同，当哈夫曼距离为偶数时，(x，y)的元素与起点相同。因此我们在搜索最短花费时，可以根据当前位置与起点的哈夫曼距离以及当前元素与起点元素是否相同来却确定节点之间的边权值，最后跑一边dijkstra即可。
代码:
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 1010;
typedef pair<int, int> PII;
typedef pair<int, PII> PIPII;
char g[N][N];
int d[N][N], dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
bool st[N][N];
int n, m;
void dijkstra()
{
memset(d, 0x3f, sizeof d);
priority_queue<PIPII, vector<PIPII>, greater<PIPII>> heap;
d[0][0] = 0;
heap.push({0, {0, 0}});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int dist = t.x;
PII ver = t.y;
int x1 = ver.x, y1 = ver.y;
if (st[x1][y1])
continue;
st[x1][y1] = true;
for (int i = 0; i < 4; i ++)
{
int x2 = x1 + dx[i], y2 = y1 + dy[i];
if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m)
continue;
int w;
if ((x2 + y2) & 1)
{
if (g[x2][y2] == g[0][0])
w = 2;
else
w = 1;
}
else
{
if (g[x2][y2] == g[0][0])
w = 1;
else
w = 2;
}
if (d[x2][y2] > dist + w)
{
d[x2][y2] = dist + w;
heap.push({d[x2][y2], {x2, y2}});
}
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i ++)
cin >> g[i];
dijkstra();
cout << d[n - 1][m - 1];
return 0;
}
E.数数
题意：
分析：
动态规划。
状态定义：f[i][j]表示放置了i个数，且前i个数的和为i * j的方案数。
状态转移：f[i + 1][k] += f[i][j]，对于任意j使得1 ≤ (i + 1) × k - i × j ≤ m。
答案：\(\sum_{i=1}^m\)f[n][i]
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, mod = 1e9 + 7;
typedef long long LL;
LL f[N][N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i ++)
f[1][i] = 1;
for (int i = 1; i < n; i ++)
{
for (int j = 1; j <= m; j ++)
{
for (int k = (i * j) / (i + 1) + 1; k <= m; k ++)
{
if ((i + 1) * k - i * j > m)
break;
f[i + 1][k] = (f[i + 1][k] + f[i][j]) % mod;
}
}
}
LL ans = 0;
for (int i = 1; i <= m; i ++)
ans = (ans + f[n][i]) % mod;
cout << ans;
return 0;
}