B - MissingNo.
难度: ⭐
题目大意
给定n个数, 这n个数中最小值到最大值之间缺一个数, 输出这个数;
解题思路
数据不大, 暴力即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 1e4 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int f[N];
signed main(){
cin >> n;
for (int i = 1; i <= n; i++) cin >> f[i];
sort(f + 1, f + 1 + n);
for (int i = 2; i <= n; i++) {
if (f[i] != f[i - 1] + 1) {
cout << f[i - 1] + 1;
break;
}
}
return 0;
}
C - Remembering the Days
难度: ⭐⭐
题目大意
给定n个点m条边, 每条边都有一个权值; 从任意一个点出发, 在不重复经过同一个点的情况下所能经过的边权和最大为多少;
解题思路
数据不大, 暴搜即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 1e3 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int g[N][N];
bool st[N];
void dfs(int u, int sum) {
idx = max(idx, sum);
for (int i = 1; i <= n; i++) {
if (g[u][i]&&!st[i]) {
st[u] = true;
dfs(i, sum + g[u][i]);
st[u] = false;
}
}
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = c;
}
for (int i = 1; i <= n; i++) {
dfs(i,0);
}
cout << idx;
return 0;
}
D - President
难度: ⭐⭐⭐
题目大意
小莫和安姐在竞选市长, 每个地区有(xi + yi)个人, 其中xi人支持小莫, yi人支持安姐, 支持人数较多的人会获得zi分, 最后分数最大的人竞选成功; 请问最少有多少人从支持安姐转向小莫可以让小莫赢得竞选;
解题思路
这道题的本质其实一个01背包dp, 对于支持安姐的地区最少有yi - xi + 1个人转向支持小莫就可以让该地方支持小莫; 设小莫需要dis=(z1 - z2 + 1) / 2价值就可以超过安姐; 把每个地区看作物品, zi是价值, yi - xi + 1是重量; 求最少需要多少重量可以得到dis价值;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 1e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int ta = 0, ao = 0;
int dp[N];
struct stu {
int x, y;
}cre[N];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int a, b, c;
cin >> a >> b >> c;
if (a > b) ta += c;
else {
ao += c;
int x = (b - a + 1) / 2;
cre[++idx] = { x,c };
}
}
int d = ao - ta;
if (d < 0) {
cout << 0;
return 0;
}
d = (ao - ta + 1) / 2;
for (int i = 1; i <= d; i++) dp[i] = 1e15;
dp[0] = 0;
for (int i = 1; i <= idx; i++) {
for (int j = d; j >= 0;j--) {
dp[j] = min(dp[j], dp[max(0ll,j- cre[i].y)] + cre[i].x);
}
}
cout << dp[d];
return 0;
}
E - Avoid Eye Contact
难度: ⭐⭐⭐
题目大意
给定一个字符矩阵, '#'表示障碍, '>', 'v', '<', '^'表示此处有监控, 并且字符的指向就是监控的方向, 该监控的范围是该方向的一条直线, 知道遇到障碍或者其他监控; 'S'为起点, 'G'是终点, 要求小莫从起点走到终点, 并且期间不被监控拍到所需要的最少步数, 保证起点和终点不在监控范围内;
解题思路
没什么好方法, 就是一个大模拟, 对于每个监控我们直接遍历它的监控范围并做标记, 最后bfs一下就行, 没啥好说的;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 3e3 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
PII st, ed;
struct stu {
int x, y, d;
};
char g[N][N];
bool s[N][N];
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
int bfs() {
queue<stu> q;
q.push({ st.first,st.second,0 });
while (q.size()) {
auto t = q.front();
q.pop();
if (g[t.x][t.y] == 'G') {
return t.d;
}
int a = t.x, b = t.y, d = t.d;
for (int i = 0; i < 4; i++) {
int x = a + dx[i], y = b + dy[i];
if (x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] != '#' && !s[x][y]) {
s[x][y] = true;
q.push({ x,y,d + 1 });
}
}
}
return -1;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
if (g[i][j] == 'S') {
st.first = i, st.second = j;
}
else if (g[i][j] == 'G') {
ed.first = i, ed.second = j;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[i][j] == '<') {
s[i][j] = true;
for (int k = j - 1; k >= 1; k--) {
if (g[i][k] != '.') {
break;
}
s[i][k] = true;
}
}
else if (g[i][j] == '>') {
s[i][j] = true;
for (int k = j + 1; k <= m; k++) {
if (g[i][k] != '.') {
break;
}
s[i][k] = true;
}
}
}
}
for (int j = 1; j <= m; j++) {
for (int i = 1; i <= n; i++) {
if (g[i][j] == '^') {
s[i][j] = true;
for (int k = i - 1; k >= 1; k--) {
if (g[k][j] != '.') {
break;
}
s[k][j] = true;
}
}
else if (g[i][j] == 'v') {
s[i][j] = true;
for (int k = i + 1; k <= n; k++) {
if (g[k][j] != '.') {
break;
}
s[k][j] = true;
}
}
}
}
cout << bfs();
return 0;
}