再次改下写博客的格式，以锻炼自己码字能力
A. Suits
题意：有四种材料，第一套西装需要 \(a\)、\(d\) 各一件，卖 \(e\) 块；第二套西装需要 \(b\)、\(c\)、\(d\) 各一件，卖 \(f\) 块。问，怎么做套装卖的前最多。
题解：【贪心】---- 先选比较贵的那一套，因为 \(d\) 套都要用上则以它为基准，再用剩余材料加第二套的总价钱
// https://codeforces.com/contest/1271/problem/A
#include<iostream>
#include<cstdio>
using namespace std;
int a, b, c, d, e, f;
int main()
{
int ans = 0;
cin >> a >> b >> c >> d >> e >> f;
int mmoney = max(e, f); // 比较二者谁更贵
if(mmoney == f){
int l = min(d, min(b, c));
ans += l * f;
d -= l;
int r = min(a, d);
ans += r * e;
}
else {
int r = min(a, d);
ans += r * e;
d -= r;
int l = min(d, min(b, c));
ans += l * f;
}
printf("%d\n", ans);
return 0;
}
B. Blocks
题意：翻转地砖使其最后的砖块颜色都一样，每翻转一块都要带动它相邻的右边一块（自左向右），输出最少翻转数以及每次翻转的位置
题解：【搜索】【翻转】数据很小，可以分别讨论每次翻成白或者翻成黑两种情况，以得到最后较小的情况（注意有翻不到的情况）
// https://codeforces.com/contest/1271/problem/B
#include<iostream>
#include<cstdio>
using namespace std;
int n;
char ch[202];
int num[202];
// 分别存储黑白两种答案
int black[1002];
int white[1002];
int main()
{
scanf("%d", &n);
scanf("%s", ch);
for(int i = 0; i < n; i++){
if(ch[i] == 'B') num[i] = 1;
else num[i] = 0;
}
// 先判断全黑的
int b = 0, w = 0;
bool can = false; // 判断能否满足要求
for(int i = 0; i < n - 1; i++){
if(num[i] != 1) { // 如果该块不是黑色则翻 将会带动下一块的颜色变化
num[i] = 1 - num[i];
num[i + 1] = 1 - num[i + 1];
black[b++] = i + 1;
}
}
if(num[n - 1] == 1) can = true;
else b = 0x3f3f3f3f;
// 重新初始化 num[] 判断全白的
for(int i = 0; i < n; i++){
if(ch[i] == 'B') num[i] = 1;
else num[i] = 0;
}
for(int i = 0; i < n - 1; i++){
if(num[i] != 0){
num[i] = 1 - num[i];
num[i + 1] = 1 - num[i + 1];
white[w++] = i + 1;
}
}
if(num[n - 1] == 0) can = true;
else w = 0x3f3f3f3f;
if(!can) printf("-1\n");
else if(w > b){
printf("%d\n", b);
for(int i = 0; i < b; i++){
printf("%d%c", black[i], i == b - 1 ? '\n' : ' ');
}
}
else {
printf("%d\n", w);
for(int i = 0; i < w; i++){
printf("%d%c", white[i], i == w - 1 ? '\n' : ' ');
}
}
return 0;
}
C. Shawarma Tent
题意：有一群学生从学校回家，他们都会走曼哈顿距离的最近距离，然后让你建一个商店在他们的路上，使他们经过商店的人数最多
题解：【贪心】涉及到曼哈顿距离，所以学生们只能按坐标轴上的线走而不能走斜线，同时商店的位置除了学校可以任意取，就可以定位在学校的上下左右四个方向取其中的一个点即可。对应四个方向，可以把学生的点分为四个象限，然后求这四个象限里哪个象限的点最多即可。
// https://codeforces.com/contest/1271/problem/C
#include<iostream>
#include<cstdio>
using namespace std;
int n, W, H, w, h;
int dw[] = { 0, 1, 0, -1 }, dh[] = { 1, 0, -1, 0 };
int d[4];
int main()
{
scanf("%d %d %d", &n, &W, &H);
while(n--){
scanf("%d %d", &w, &h);
if(w != W) d[w > W ? 1 : 3]++;
if(h != H) d[h > H ? 0 : 2]++;
}
int m = 0, t;
for(int i = 0; i < 4; i++){
// printf("i:%d d:%d\n", i, d[i]);
if(d[i] > m){
m = d[i]; t = i;
}
}
printf("%d\n", m);
printf("%d %d\n", W + dw[t], H + dh[t]);
return 0;
}
补题没有rating。