A - Range Swap
根据题意，分段输出。
点击查看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 105;
int n, s[N], a, b, c, d;
int main() {
scanf("%d %d %d %d %d", &n, &a, &b, &c, &d);
for(int i = 1; i <= n; i ++) scanf("%d", &s[i]);
for(int i = 1; i <= a - 1; i ++) printf("%d ", s[i]);
for(int i = c; i <= d; i ++) printf("%d ", s[i]);
for(int i = b + 1; i < c; i ++) printf("%d ", s[i]);
for(int i = a; i <= b; i ++) printf("%d ", s[i]);
for(int i = d + 1; i <= n; i ++) printf("%d ", s[i]);
return 0;
}
B - Cat
直接循环修改，然后输出即可。
点击查看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 2005;
int n, len;
char s[N], t[N];
int main() {
scanf("%d %s", &n, s + 1);
t[len = 1] = s[1];
for(int i = 2; i <= n; i ++) {
if(s[i] == 'a' && s[i - 1] == 'n') {
t[++len] = 'y';
t[++len] = 'a';
}
else t[++len] = s[i];
}
printf("%s", t + 1);
return 0;
}
C - Rotate and Palindrome
简单贪心分析可得，两个操作混合使用 不会优于 两个操作分别进行。
因此，可以先枚举使用操作 1 的次数，然后在此基础上双指针计算所需的操作 2 的次数，取最小值输出。
点击查看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int N = 5005;
int n;
ll ans = 1e18, a, b;
char s[N], t[N];
ll solve(int x) {
int len = 0;
ll res = x * a;
for(int i = x + 1; i <= n; i ++) t[++len] = s[i];
for(int i = 1; i <= x; i ++) t[++len] = s[i];
int l = 1, r = n;
while(l < r) {
if(t[l] != t[r]) res += b;
l ++, r --;
}
return res;
}
signed main() {
scanf("%d %lld %lld", &n, &a, &b);
scanf("%s", s + 1);
for(int i = 0; i < n; i ++) {
ans = min(ans, solve(i));
}
printf("%lld", ans);
return 0;
}
D - Money in Hand
背包 DP。
定义 dp[i][j] 为使用前 i 种硬币达到数值 j 的方案是否存在。
每次枚举第 i 种硬币的个数，然后由 dp[i - 1] 转移方程。
点击查看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 55, M = 1e4 + 5;
int n, s, a[N], b[N];
bool dp[N][M];
int main() {
scanf("%d %d", &n, &s);
for(int i = 1; i <= n; i ++) scanf("%d %d", &a[i], &b[i]);
dp[0][0] = 1;
for(int i = 1; i <= n; i ++) {
for(int j = 0; j <= s; j ++) {
dp[i][j] = dp[i - 1][j];
for(int k = 1; k * a[i] <= j && k <= b[i]; k ++) {
dp[i][j] |= dp[i - 1][j - k * a[i]];
}
}
}
if(dp[n][s]) puts("Yes");
else puts("No");
return 0;
}
E - Souvenir
djs 板子题，只需要多加一个 val 数组处理权值。
点击查看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define ll long long
const int N = 305;
int n, m, Q, dis[N][N];
ll val[N][N], a[N];
bool map[N][N], tag[N];
char s[N];
queue<int> q;
void djs(int st) {
while(!q.empty()) q.pop();
dis[st][st] = 0, tag[st] = 1, val[st][st] = a[st], q.push(st);
int now, ver;
while(!q.empty()) {
now = q.front(), q.pop();
for(int i = 1; i <= n; i ++) {
if(!map[now][i]) continue;
if(dis[st][i] > dis[st][now] + 1) {
dis[st][i] = dis[st][now] + 1;
val[st][i] = val[st][now] + a[i];
q.push(i);
}
else if(dis[st][i] == dis[st][now] + 1) {
val[st][i] = max(val[st][i], val[st][now] + a[i]);
}
}
}
}
int main() {
scanf("%d", &n);
memset(dis, 0x3f, sizeof(dis));
for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
for(int i = 1; i <= n; i ++) {
scanf("%s", s + 1);
for(int j = 1; j <= n; j ++) {
map[i][j] = (s[j] == 'Y');
}
}
scanf("%d", &m);
int u, v;
for(int i = 1; i <= m; i ++) {
scanf("%d %d", &u, &v);
if(!tag[u]) djs(u);
if(dis[u][v] > 1e9) puts("Impossible");
else printf("%d %lld\n", dis[u][v], val[u][v]);
}
return 0;
}
F - Guess The Number 2
交互题是真不会。不想补。
（摊牌，摆烂）
G - Unique Walk
有两种情况：
-
S == M，则判断图是否存在欧拉路；
-
S < M，考虑使用缩点，因为不在 S 中的边（u，v）可以经过无数次，所以将其缩成一个点，可以使用并查集维护。缩点后图中只剩下关键边，在新图上判断是否存在欧拉路径即可。
而对于无向连通图，判断欧拉路的条件：
- 图中存在 0 或 2 个度数为奇数的点。
点击查看代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2e5 + 5;
bool tag[N];
int n, m, cnt, k, in[N], fa[N], t[N];
struct node {
int u, v;
}e[N];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void link(int x, int y) {
fa[find(x)] = find(y);
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i ++) fa[i] = i;
for(int i = 1; i <= m; i ++) {
scanf("%d %d", &e[i].u, &e[i].v);
}
scanf("%d", &k);
for(int i = 1; i <= k; i ++) {
scanf("%d", &t[i]);
tag[t[i]] = 1;
}
for(int i = 1; i <= m; i ++) {
if(tag[i]) continue;
link(e[i].u, e[i].v);
}
int u, v;
for(int i = 1; i <= k; i ++) {
u = find(e[t[i]].u), v = find(e[t[i]].v);
in[u] ++, in[v] ++;
}
for(int i = 1; i <= n; i ++) {
cnt += in[i] & 1;
}
if(!cnt || cnt == 2) puts("Yes");
else puts("No");
return 0;
}