B - Glass and Mug
难度: ⭐
题目大意
给定两个杯子A, B; 如果A杯子装满水了, 则把A杯子里的水倒掉; 否则如果B杯子空着, 则把B杯子装满水, 否则就把B杯子里的水倒进A杯子里, 直到B杯子空了或者A杯子满了;
问重复上述操作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 = 1e6 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, k, res;
int x, y;
signed main() {
cin >> k >> n >> m;
for(int i = 1; i <= k; i++){
if(x == n) x = 0;
else if(y == 0) y = m;
else {
int a = min(n - x, y);
y -= a;
x += a;
}
}
cout << x << ' ' << y;
return 0;
}
C - T-shirts
难度: ⭐
题目大意
小莫接下来有n天行程, 给定一个字符串s; 如果为0则待在家里, 为1则去吃饭, 为2则去参加派对;
小莫有m件B衣服; 如果要去吃饭, 则要穿A或B衣服都可以; 如果要去参加派对, 则要穿A衣服; 并且每天结束后, 当天穿的衣服都不可以再穿, 直到洗完; 如果待在家里, 则不用穿这两种衣服, 并且可以把之前穿过的衣服都洗完; 问小莫至少需要再买多少件衣服才可以支持这n天的行程;
解题思路
因为两种行程都可以穿A衣服, 所以我们只买A衣服就行; 这样就是一个简单的模拟了;
神秘代码
#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 = 1e6 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, k, res;
signed main() {
cin >> n >> m;
string s;
cin >> s;
int x = m, y = 0;
int a = 0, b = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] == '1') a++;
else if(s[i] == '2') b++;
else {
y = max(y, b + max(0ll, (a - x)));
a = 0, b = 0;
}
}
y = max(y, b + max(0ll, (a - x)));
cout << y;
return 0;
}
D - Swapping Puzzle
难度: ⭐⭐⭐
题目大意
给定两个矩阵A和B; 我们可以对A进行两种操作, 一是交换相邻的两行, 二是交换相邻的两列; 问最少进行多少次操作可以把A转化为B;
解题思路
因为数据范围很小, 并且暴力不是很好写, 那我们可以直接用bfs搜索; 把每个矩阵看作一个状态, 每次交换两行或两列后变为下一个状态; 对此我们可以把二维矩阵压缩为一维, 便于存储和查重; 查重可以用map;
神秘代码
#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 = 1e6 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, k;
vector<int> v1(100), v2(100);
map<vector<int>, int> mp;
int bfs(){
queue<vector<int>> q;
q.push(v1);
mp[v1] = 0;
while(q.size()){
vector<int> t = q.front();
q.pop();
if(t == v2){
return mp[t];
}
for(int i = 1; i < n; i++){
vector<int> v(t);
for(int j = 1; j <= m; j++){
swap(v[(i - 1) * m + j], v[i * m + j]);
}
if(!mp[v]){
q.push(v);
mp[v] = mp[t] + 1;
}
}
for(int i = 1; i < m; i++){
vector<int> v(t);
for(int j = 1; j <= n; j++){
swap(v[i + (j - 1) * m], v[i + 1 + (j - 1) * m]);
}
if(!mp[v]){
q.push(v);
mp[v] = mp[t] + 1;
}
}
}
return -1;
}
signed main() {
cin >> n >> m;
for(int i = 1; i <= n * m; i++){
int x;
cin >> x;
v1[i] = x;
}
for(int i = 1; i <= n * m; i++){
int x;
cin >> x;
v2[i] = x;
}
cout << bfs();
return 0;
}
E - Lucky bag
难度: ⭐⭐⭐⭐
F - Random Update Query
难度: ⭐⭐⭐⭐⭐
- Beginner AtCoder Contest 332beginner atcoder contest 332 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 334 beginner atcoder contest 328 beginner atcoder contest 310 beginner atcoder contest 315