比赛传送门 https://codeforces.com/contest/1271
再次改下写博客的格式, 以锻炼自己码字能力
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.
来源: http://www.bubuko.com/infodetail-3337781.html