A - Grandma Laura and Apples
难度: ⭐⭐(⭐)
题目大意
小莫在市集卖苹果, 苹果的价格是p (p一定是偶数); 现在有n个顾客前来买苹果, 并且每次会买当前苹果数量的一半, 如果当前苹果数量是奇数, 那么小莫会再赠送顾客半个苹果; 给出的n组输入, 如果是"half", 则说明小莫没有赠送苹果; 如果是"halfplus", 说明小莫赠送了该顾客半个苹果; 请问小莫卖完所有苹果后的收益是多少;
解题思路
由题意得, 小莫手上的苹果会一直保持整数; 我们要从后往前推算总苹果数是多少; 最后苹果数量为cnt = 0, 如果是"halfplus", 则说明顾客购买之前苹果数量是奇数, 也就是cnt * 2 + 1; 如果是"half", 则是偶数, 也就是cnt * 2, 那么根据数量很容易得知顾客付了多少钱; 可以用dfs实现从后往前推算;
神秘代码
#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, inf = 1e18;
typedef pair<int, int> PII;
int n, m, cnt = 0, res = 0;
string s;
int p[N];
void dfs(int u){
if(u < 1) return;
string s;
cin >> s;
dfs(u - 1);
if(s == "half"){
cnt *= 2;
res += cnt / 2 * m;
}
else if(s == "halfplus"){
cnt = cnt * 2 + 1;
res += cnt / 2 * m + m / 2;
}
}
signed main(){
cin >> n >> m;
dfs(n);
cout << res;
return 0;
}
B - Alice, Bob, Two Teams
难度: ⭐⭐
题目大意
现在有n个物品, 每个物品都有各自的价值Ai, 然后给出一个长度为n字符串, 将这些物品划分给小莫和安姐, 如果第i个字符是'A', 说明第i个物品属于安姐, 如果是'B', 则属于小莫; 现在小莫有一次操作机会, 她可以选择该字符串的一段前缀或者后缀, 然后把一段的字符翻转('A'变成'B','B'变成'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, inf = 1e18;
typedef pair<int, int> PII;
int n, m, res;
string s;
int p[N];
signed main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> p[i];
cin >> s;
for(int i = 0; i < s.size(); i++){
if(s[i] == 'B') res += p[i + 1];
}
int maxn = res, cnt = res;
for(int i = 0; i < s.size(); i++){
if(s[i] == 'A') cnt += p[i + 1];
else cnt -= p[i + 1];
maxn = max(cnt, maxn);
}
cnt = res;
for(int i = s.size(); i >= 0; i--){
if(s[i] == 'A') cnt += p[i + 1];
else cnt -= p[i + 1];
maxn = max(cnt, maxn);
}
cout << maxn;
return 0;
}
C - Takahashi Gets Lost
难度: ⭐⭐⭐
题目大意
给定一个矩阵, 该矩阵由陆地和海洋组成, 小莫位于某个陆地上, 并且进行了n次移动; 给定这n次移动每次的方向; 请问有多少个可以满足条件的陆地;
解题思路
用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 = 1e6 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, k, res;
string s;
char g[510][510];
struct node{
int x, y, id;
};
queue<node> q;
void bfs(){
while(q.size()){
auto t = q.front();
q.pop();
int x = t.x, y = t.y;
if(t.id == s.size()){
res++;
continue;
}
if(s[t.id] == 'L'){
if(y - 1 >= 1 && g[x][y - 1] == '.'){
q.push({x, y - 1, t.id + 1});
}
}
else if(s[t.id] == 'R'){
if(y + 1 <= m && g[x][y + 1] == '.'){
q.push({x, y + 1, t.id + 1});
}
}
else if(s[t.id] == 'U'){
if(x - 1 >= 1 && g[x - 1][y] == '.'){
q.push({x - 1, y, t.id + 1});
}
}
else if(s[t.id] == 'D'){
if(x + 1 <= n && g[x + 1][y] == '.'){
q.push({x + 1, y, t.id + 1});
}
}
}
}
signed main(){
cin >> n >> m >> k;
cin >> s;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> g[i][j];
if(g[i][j] == '.'){
q.push({i, j, 0});
}
}
}
bfs();
cout << res;
return 0;
}
D - Epic Transformation
难度: ⭐⭐⭐
题目大意
现有一个长度为n的数组, 我们可以从中挑选出两个不同的数, 然后把他们从数组中删去; 该操作可以做无限次; 请问操作完后该数组的长度最短是多少;
解题思路
我们可以把这个题抽象成要把数组中满足条件的数两两匹配; 并且要优先和当前出现次数最多的数匹配; 我们可以把该数组规整一下; 比如原数组为1 2 1 3 1 2, 规整后为1 1 1 2 2 3; 按出现次数从大到小排列; 然后我们要从中切一刀, 将左边和右边的数组上下堆叠起来, 这样就实现了优先和出现次数最多的两两匹配, 并且还能保证两个数字之间不同; 但是要注意, 这一刀不能从出现次数最多的数字块中切, 因为那样会导致匹配时会有两个相同的数字;
其实再往后推我们会发现一个公式, 如果出现次数最多的数字的数量x大于等于n / 2, 那么直接让其他数字都和他匹配即可, 也就是2 * x - n; 相反如果小于n / 2, 那么按照上面的切法, 如果n是偶数, 那么一定可以让左边和右边的长度相等, 也就是0; 如果是奇数, 那就会多出一个, 也就是1;
注意: 至于怎么让map按第二关键字排序, 我们可以把map里的数据都挪到vector里面, 然后对vector进行自定义排序即可;
神秘代码
#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, inf = 1e18;
typedef pair<int, int> PII;
int n, m, k;
string s;
int p[N], f[N];
vector<PII> v;
map<int, int> mp;
bool cmp(PII a, PII b){
return a.second > b.second;
}
signed main(){
IOS;
int t;
cin >> t;
while(t--){
cin >> n;
int res = n;
mp.clear();
v.clear();
for(int i = 1; i <= n; i++){
cin >> p[i];
mp[p[i]]++;
}
for(auto t : mp){
v.push_back(t);
}
int idx = 0;
sort(v.begin(), v.end(), cmp);
for(auto t : v){
for(int i = 1; i <= t.second; i++){
f[++idx] = t.first;
}
}
for(int i = 2; i <= n; i++){
if(f[i] == f[1]) continue;
res = min(res, abs(n - 2 * (i - 1)));
}
cout << res << endl;
}
return 0;
}