B.Obsession with Robots
先假设除了机器人走的路其他的地方都是障碍,然后记录下来可以走的地方用BFS遍历一遍,判断一个机器人有没有bug
#include <bits/stdc++.h>
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
typedef pair<int, int> PII;
const int N = 300;
int mp[N][N];
bool st[N][N];
int dis[N][N];
struct point {
int x;
int y;
};
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int main () {
for (int i = 0; i <= 250; i++) {
for (int j = 0; j <= 250; j++) {
mp[i][j] = 1; //1表示不能走
}
}
string s;
cin >> s;
int x = 105, y = 105;
mp[x][y] = 0;//0表示可以走
int end_x;
int end_y;//记录终点
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] == 'L') {
x--;
} else if (s[i] == 'U') {
y++;
} else if (s[i] == 'R') {
x++;
} else if (s[i] == 'D') {
y--;
}
mp[x][y] = 0;//机器人走过的地方可以走
end_x = x;
end_y = y;//最后走到的地方就是终点
}
queue <point> q;
q.push({105, 105});//起点入队
st[105][105] = true;
while (!q.empty()) {//开始BFS
int front_x = q.front().x;
int front_y = q.front().y;
for (int i = 0; i < 4; i++) {
int a = front_x + dx[i];
int b = front_y + dy[i];
if (mp[a][b] == 0 && st[a][b] == false) {//如果可以走并且没有被搜索过
st[a][b] = true; //标记为已经搜索过
dis[a][b] = dis[front_x][front_y] + 1; //记录走的步数
struct point temp;
temp.x = a;
temp.y = b;
q.push(temp);
}
}
q.pop();
}
if (dis[end_x][end_y] < (int)s.size()) {//最后比较BFS的路径距离和机器人的路径距离
cout << "BUG" << '\n';
} else {
cout << "OK" << '\n';
}
return 0;
}
B. Subsequence Hate
这个题只能是下面的这几种情况才能满足需求
000000000000
111111111111
000001111111
111111100000
所以我们要把字符串变成上面的这种情况
#include <bits/stdc++.h>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
typedef pair<int, int> PII;
const int N = 1005;
int s1[N];//s1代表字符串1数量的前缀和
int s0[N];//s0代表字符串0数量的前缀和
void solve() {
string x;
cin >> x;
string s = "s";
s += x;
for (int i = 1; i < (int)s.size(); i++) {//得到前缀和
if (s[i] == '1') {
s1[i] = s1[i - 1] + 1;
s0[i] = s0[i - 1] + 0;
}
if (s[i] == '0') {
s1[i] = s1[i - 1] + 0;
s0[i] = s0[i - 1] + 1;
}
}
int ans = 0x3f3f3f3f;
int n = s.size() - 1;
for (int i = 1; i < (int)s.size(); i++) {
int a = s0[i] - s0[0]; //将0变成1
a += s1[n] - s1[i]; //将1变成0;
//都变成1111000
int b = s1[i] - s1[0];
b += s0[n] - s0[i];
//都变成00000111
ans = min(ans, min(a, b));//每次取操作次数最小的那个
}
cout << ans << '\n';//打印结果
}
signed main () {
std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
int t;
cin >> t;
while (t) {
solve();
t--;
}
return 0;
}
C.A Cookie for You
客人1是那个曲奇多吃哪一个所以可以将这些曲奇全部吃完.
而客人2是那个曲奇少吃哪一个所以我们先将饼干分配给客人2
#include <bits/stdc++.h>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
typedef pair<int, int> PII;
const int N = 100008;
void solve() {
//应该优先服务第二种客人因为第一种客人会选择多的吃也就是说
//除了饼干没有的情况,第一种客人都不会发怒
//而第二种客人选择饼干较少的吃就很难搞,我们模拟一下过程
int a, b, n, m;
cin >> a >> b >> n >> m;
if (a <= b) { //香草小于等于巧克力
if (m <= a) {//给二号客人吃香草的
a -= m;//还剩下a香草
} else {
no;//不够吃打印no
return;
}
if (a + b >= n) {//只要剩下的饼干数量大于客人1的数量就可以
yes;//一号客人可以满足
} else {
no;
}
} else { //香草大于巧克力
if (m <= b) { //二号客人吃巧克力
b -= m;
} else {
no;//不够吃打印no
return;
}
if (a + b >= n) {//只要剩下的饼干数量大于客人1的数量就可以
yes;
} else {
no;
}
}
}
signed main () {
std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
int t;
cin >> t;
while (t) {
solve();
t--;
}
return 0;
}
A. Winner
官方题解:
问题很简单，写代码就可以了。在第一遍中计算游戏结束时每个玩家的得分总和。令 M 为这些总和中的最大值。在第二遍检查每一轮。如果当前玩家X的分数不少于M，并且他的最终分数等于M，那么他就是胜利者。下面的测试说明玩家可能会获得超过 M 分，然后失去一些，最后获胜。
#include <bits/stdc++.h>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
typedef pair<int, int> PII;
const int N = 100008;
signed main () {
int n;
cin >> n;
vector<pair<string, int>> a;
map<string, int>mp;
map<string, int>mp2;
int m = -999999999999999;
string s;
int x;
for (int i = 1; i <= n; i++) {
cin >> s >> x;
a.push_back({s, x});//记录数据
mp[s] += x;//记录s当前的分数
}
for (auto q : mp) {//遍历mp取出最大值
m = max(q.second, m);
}
string ans;//记录答案
for (int i = 0; i < (int)a.size(); i++) {
mp2[a[i].first] += a[i].second;//开始逐个记录答案
if (mp[a[i].first] == m && mp2[a[i].first] >= m) {
//如果当前的这个mp2的值大于等于m,并且最后的结果值等于m
ans = a[i].first;//这个就是答案
break;
}
}
cout << ans << '\n';
return 0;
}