牛客周赛 Round 32
小红的 01 背包
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
int a, b, c;
cin >> a >> b >> c;
cout << a / b * c << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红的 dfs
解题思路:
观察可知，一共只有三种情况。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
vector<string> g(4);
for (int i = 1; i <= 3; i++)
{
cin >> g[i];
g[i] = ' ' + g[i];
}
int a = 0;
int b = 0;
int c = 0;
if (g[1][1] != 'd')
{
a++;
}
if (g[1][2] != 'f')
{
a++;
}
if (g[1][3] != 's')
{
a++;
}
if (g[2][1] != 'f')
{
a++;
}
if (g[3][1] != 's')
{
a++;
}
if (g[2][1] != 'd')
{
b++;
}
if (g[2][2] != 'f')
{
b++;
}
if (g[2][3] != 's')
{
b++;
}
if (g[1][2] != 'd')
{
b++;
}
if (g[3][2] != 's')
{
b++;
}
if (g[3][1] != 'd')
{
c++;
}
if (g[3][2] != 'f')
{
c++;
}
if (g[3][3] != 's')
{
c++;
}
if (g[1][3] != 'd')
{
c++;
}
if (g[2][3] != 'f')
{
c++;
}
int ans = min(a, min(b, c));
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红的排列生成
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
int n;
cin >> n;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a.begin() + 1, a.end());
ll ans = 0;
for (int i = 1; i <= n; i++)
{
ans += abs(a[i] - i);
}
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红的二进制树
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const int N = 1e5 + 10;
vector<int> e[N];
int w[N];
int f[N];
void dfs(int u, int fa)
{
f[u] = w[u];
for (auto v : e[u])
{
if (v == fa)
{
continue;
}
dfs(v, u);
f[u] += f[v];
}
}
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
for (int i = 0; i < n; i++)
{
w[i + 1] = s[i] - '0';
}
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
e[a].push_back(b);
}
dfs(1, -1);
for (int i = 1; i <= n; i++)
{
cout << f[i] - w[i] << endl;
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红的回文数
解题思路:
回文数特性：最多只有一个数字出现个数是奇数。
\(0\sim 9共10个数字在每个数位上如果是奇数就是1，否则就是0，压缩组成的10进制数。i\in [0,2^{10}])\)
\(dp[i]:前缀中为i的状态有多少个\)
对于当前状态\(cur\)，如果前缀和状态也为\(cur\)，说明从该前缀到当前为止中，所有数字的个数都是偶数个。
对于当前状态\(cur\)，如果前缀和状态与当前状态只有一个数位不同，说明从该前缀到当前为止中，只有一个数字的个数是奇数个。
上述两种状况能与当前状态构成好整数。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const int N = 1ll << 11;
int dp[N];
void solve()
{
string s;
cin >> s;
int cur = 0;
dp[cur] = 1;
ll ans = 0;
for (int i = 0; i < s.size(); i++)
{
cur ^= 1 << (s[i] - '0');
ans += dp[cur];
for (int j = 0; j < 10; j++)
{
int t = cur;
t ^= 1 << j;
ans += dp[t];
}
dp[cur]++;
}
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红的矩阵修改
解题思路:
状态压缩\(dp\)。
\(dp[i][j]:考虑前i列，第i列为j时的合法方案的最小操作步数\)。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const int N = 1010;
int dp[N][100];
int v[5][N];
bool valid[100];
int n, m;
int b[10];
bool check(int x)
{
for (int i = 1; i <= n; i++, x /= 3)
{
b[i] = x % 3;
}
for (int i = 2; i <= n; i++)
{
if (b[i] == b[i - 1])
{
return false;
}
}
return true;
}
bool check(int a, int b)
{
for (int i = 1; i <= n; i++)
{
if (a % 3 == b % 3)
{
return false;
}
a /= 3;
b /= 3;
}
return true;
}
void solve()
{
memset(dp, 0x3f, sizeof dp);
cin >> n >> m;
int s = 1;
for (int i = 1; i <= n; i++)
{
s *= 3;
}
vector<string> g(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> g[i];
g[i] = ' ' + g[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (g[i][j] == 'r')
{
v[i][j] = 0;
}
else if (g[i][j] == 'e')
{
v[i][j] = 1;
}
else
{
v[i][j] = 2;
}
}
}
ll ans = 1e18;
for (int i = 1; i <= m; i++)
{
if (i == 1)
{
for (int j = 0; j < s; j++)
{
if (check(j))
{
int cnt = 0;
for (int k = 1; k <= n; k++)
{
if (b[k] != v[k][i])
{
cnt++;
}
}
dp[i][j] = min(dp[i][j], cnt);
}
}
}
else
{
for (int j = 0; j < s; j++)
{
if (check(j))
{
int cnt = 0;
for (int k = 1; k <= n; k++)
{
if (b[k] != v[k][i])
{
cnt++;
}
}
for (int k = 0; k < s; k++)
{
if (check(j, k))
{
dp[i][j] = min(dp[i][j], dp[i - 1][k] + cnt);
}
}
}
}
}
}
for (int i = 0; i < s; i++)
{
ans = min(ans, (ll)dp[m][i]);
}
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}