A
贪心即可，如果晚上做梦了并且白天没做梦，那就提前让白天做梦，如果白天晚上都做梦了，全加入答案。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, P = 131, mod = 998244353, INF = 1e18;
void solve()
{
int n;
cin >> n;
string s, t;
cin >> s >> t;
int ans = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'Y' && t[i] == 'Y') ans += 3;
else if (s[i] == 'Y' || t[i] == 'Y') ans += 2;
}
cout << ans << endl;
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
// int t;
// cin >> t;
// while (t--)
solve();
return 0 ^ 0;
}
B
对数字x每位排序，然后贪心地构造，注意不能包含前导0，那么第一位除了0之外排最小的数，第二位开始依次插入最小的即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, P = 131, mod = 1e9 + 7, INF = 1e18;
void solve()
{
string s;
cin >> s;
sort(s.begin(), s.end());
int cnt = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '0') cnt++;
else {
cout << s[i];
for (int j = 1; j <= cnt; j++) cout << 0;
cnt = 0;
}
}
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
// int t;
// cin >> t;
// while (t--)
solve();
return 0 ^ 0;
}
C
考了一个小小的思维题，观察到条件每次操作只会新产生偶数个0或1，所以对于所有字符串长度为奇数的，必定可以通过有限次操作变为全部相同的字符（奇数 = 奇数 + 偶数）。
对于所有字符串长度为偶数的，我们可以记录一个cnt0代表字符0的个数， cnt1代表字符为1的个数，由于每次操作只会新产生偶数个0或1，所以只有当cnt0 % 2 == 0 && cnt1 % 2== 0 才能满足条件，否则都是不满足的
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 5, P = 131, mod = 1e9 + 7, INF = 1e18;
void solve()
{
string s;
cin >> s;
int n = s.size();
if (n & 1) {
cout << "Yes" << endl;
return;
}
int cnt0 = 0, cnt1 = 0;
for (int i = 0 ; i < n; i++) {
if (s[i] == '1') cnt1++;
else cnt0++;
}
if (cnt0 % 2 == 0 && cnt1 % 2 == 0) {
cout << "Yes" << endl;
}
else cout << "No" << endl;
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--)
solve();
return 0 ^ 0;
}
D
最短路板子题，不会写的肯定是对于这个算法理解的还不熟练，希望可以通过这个题加深一下理解。
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define endl '\n'
using namespace std;
const int N = 2e5 + 5, P = 131, mod = 1e9 + 7, INF = 1e18;
int dis[2005][2005]; // dis[i][j] 代表到达i,j这个位置最少需要花费的单位时间
struct shen{
int x, y, t;
};
bool operator<(shen l, shen r)//重载小根堆，每次让小根堆返回到当前位置最少需要花费的单位时间
{
return l.t > r.t;
}
vector<pii> dd{{1, 0}, {0, 1}, {0, -1}}; // 下左右三个方向
void solve()
{
int n, m;
cin >> n >> m;
vector<vector<int>> a(n + 1, vector<int> (m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
memset(dis, 0x3f3f3f, sizeof dis); // 初始赋为无穷大
dis[1][1] = 0; // 起点当然为0
priority_queue<shen> q;
q.push({1, 1, 0}); // 下面就是开始跑dijkstra
while (q.size()) {
auto [x, y, t] = q.top();
q.pop();
for (auto [dx, dy] : dd) { // 枚举三个方向
int xx = dx + x, yy = dy + y;
if (xx < 1 || xx > n || yy < 1 || yy > m) continue; // 超过边界直接continue掉
int cnt = 1;
if (a[x][y] != a[xx][yy]) { // 如果不等于代表需要换装备，花费2单位时间
cnt = 2;
}
if (t + cnt < dis[xx][yy]) {
dis[xx][yy] = t + cnt; // 更新dis数组
q.push({xx, yy, t + cnt});
}
}
}
cout << dis[n][m] << endl;
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
// int t;
// cin >> t;
// while (t--)
solve();
return 0 ^ 0;
}
E
考了一个数学小知识，一个数是4的倍数，那么最后两位一定会是4的倍数，同理一个数最后两位是4的倍数，那么这个数也一定是4的倍数，因此我们直接暴力枚举每一个相邻的位置即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 510, P = 131, mod = 998244353, INF = 1e10;
bool check(char a, char b) // 用来判断是否是4的倍数
{
int t = (a - '0') * 10 + (b - '0');
if (t % 4 == 0) return 1;
else return 0;
}
void solve()
{
string s;
cin >> s;
int len = s.size();
if (check(s[len - 2], s[len - 1])) {
cout << 0 << endl;
return;
}
if (check(s[len - 1], s[0])) {
cout << 1 << endl;
return;
}
for (int i = 0; i <= len - 2; i++) {
if (check(s[i], s[i + 1])) {
cout << i + 2 << endl;
return;
}
}
cout << -1 << endl;
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
// int t;
// cin >> t;
// while (t--)
solve();
return 0 ^ 0;
}
F
暴力枚举每个位置为分界点的时候，设这个位置为i，则i（包括i）前面的全为大写字母，后面的全为小写字母，然后取最小值即可。那么我们如何维护i前面需要多少次操作才能将i前面全改为大写字母？直接暴力枚举的话时间复杂度是O(n2）的，不能够接受，我们可以维护一个前缀和sum1，sum1[i] 代表前i个字符中大写字母有多少个，同样，我们也维护一个sum2, sum2[i] 代表前i个字符中小写字母有多少个，这样我们就可以快速的知道前i个有多少个小写字母了，即sum2[i]个，i后面有sum1[n] - sum1[i]个大写字母。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 5, P = 131, mod = 1e9 + 7, INF = 1e18;
void solve()
{
string s;
cin >> s;
int n = s.size();
s = " " + s;
vector<int> sum1(n + 1), sum2(n + 1);
for (int i = 1; i <= n; i++) { // 预处理两个前缀和
if (s[i] >= 'A' && s[i] <= 'Z') sum1[i] = sum1[i - 1] + 1;
else sum1[i] = sum1[i - 1];
if (s[i] >= 'a' && s[i] <= 'z') sum2[i] = sum2[i - 1] + 1;
else sum2[i] = sum2[i - 1];
}
int ans = INF;
for (int i = 1; i < n; i++) {
int ans1 = sum2[i], ans2 = sum1[n] - sum1[i];
ans = min(ans, ans1 + ans2);
}
cout << ans << endl;
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
// int t;
// cin >> t;
// while (t--)
solve();
return 0 ^ 0;
} G
算是比较板子的题了，观察到操作次数k越大，数组的最大值就会越小，答案非常明显具有单调性，所以我们直接二分答案即可。假设当前最大值为mid，我们check一下mid是否合法，如果合法就取更小，否则取更大即可。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 5, P = 131, mod = 1e9 + 7, INF = 1e18;
void solve()
{
int n, k, x;
cin >> n >> k >> x;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
auto check = [&] (int mid) -> int{ // 计算最大值为mid所需要操作的最小次数
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (a[i] > mid) {
int sum = a[i] - mid;
cnt += (sum + x - 1) / x;
}
}
if (cnt <= k) return 1; //如果所需的次数少于k，那么最大值mid是可以取到的
return 0;
};
int l = a[1] - k * x - 1, r = a[n] + 1;
while (l + 1 < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid;
}
cout << r << endl;
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
// int t;
// cin >> t;
// while (t--)
solve();
return 0 ^ 0;
}
H
非常经典的树形dp了，设状态dp[i][0/1]， dp[i][0]表示以i为根的子树且i不染色的总方案数，dp[i][1]，表示以i为根的子树且i染色的总方案数，我们取1为整颗树的根节点，那么答案就是dp[1][0] + dp[1][1]了。
状态设置完之后我们就考虑改如何转移，dp[i][0]只能由dp[v][1]转移过来（v是i的子节点），dp[i][1]可以由dp[v][1],dp[v][0]转移过来，所以转移方程就很明显了 dp[i][0] = (dp[i][0] * dp[v][1]) % mod，dp[i][1] = (dp[i][1] * ((dp[v][0] + dp[v][1]) % mod)) % mod。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 5, P = 131, mod = 1e9 + 7, INF = 1e18;
int n;
int dp[N][2];
vector<int> g[N];
void dfs(int x, int fa)
{
for (auto v : g[x]) {
if (v == fa) continue;
dfs(v, x);
dp[x][0] = (dp[x][0] * dp[v][1]) % mod;
dp[x][1] = (dp[x][1] * ((dp[v][0] + dp[v][1]) % mod)) % mod;
}
}
void solve()
{
cin >> n;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= 1; j++) {
dp[i][j] = 1;
}
}
dfs(1, 0);
cout << (dp[1][0] + dp[1][1]) % mod << endl;
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
// int t;
// cin >> t;
// while (t--)
solve();
return 0 ^ 0;
}
Comments NOTHING