首页 > 代码库 > Codeforces Round#413 Problem A - C
Codeforces Round#413 Problem A - C
[写在前面感(乱)叹(七)人(八)生(糟)的话]
本想借此机会一口气玩到蓝名，结果，A题写炸(少判了一种情况)，C题写炸(辜负了我5分钟狂敲出来的线段树)，结果又掉Rating...内心好绝望。。。
Problem#A Carrot Cakes
vjudge链接[here]
（偷个懒,cf链接就不给了）
题目大意是说，烤面包，给出一段时间内可以考的面包数，建第二个炉子的时间，需要达到的面包数，问建炉子是否合理。
玄学 & 智商题，可能是因为我智商不够，所以在我决定休息的时候被hank掉了。。。
输NO的情况大概是当炉子建好后，考完第一波的时间，任务已经或刚好完成。
Code
1 /** 2 * Codeforces 3 * Problem#799A 4 * Accepted 5 * Time:15ms 6 * Memory:8k 7 */ 8 #include<iostream> 9 #include<fstream> 10 #include<sstream>11 #include<algorithm>12 #include<cstdio>13 #include<cstring>14 #include<cstdlib>15 #include<cctype>16 #include<cmath>17 #include<ctime>18 #include<map>19 #include<stack>20 #include<set>21 #include<queue>22 #include<vector>23 using namespace std;24 typedef bool boolean;25 #define inf 0xfffffff26 #define smin(a, b) (a) = min((a), (b))27 #define smax(a, b) (a) = max((a), (b))28 template<typename T>29 inline boolean readInteger(T& u) {30 char x;31 int aFlag = 1;32 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1);33 if(x == -1) {34 ungetc(x, stdin);35 return false;36 }37 if(x == ‘-‘) {38 aFlag = -1;39 x = getchar();40 }41 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘);42 u *= aFlag;43 ungetc(x, stdin);44 return true;45 }46 47 int n, t, k, d;48 49 inline void work() {50 readInteger(n);51 readInteger(t);52 readInteger(k);53 readInteger(d);54 int turns = d / t + 1;55 if(turns * k > n)56 puts("NO");57 else if(turns * k == n && (d == t || turns * t <= d + t))58 puts("NO");59 else60 puts("YES");61 }62 63 int main() {64 work();65 return 0;66 }
Problem#B T-shirt buying
vjudge链接[here]
题目大意是说，每件衣服有两面，每面有个颜色，有些人要来买，他只买存在一面有他喜欢的颜色且价格最低的一个，输出每个人付的钱，没有买到输出-1。
用个set，依题意乱搞就好了。(每场比赛貌似都是b题稳AC)
Code
1 /** 2 * Codeforces 3 * Problem#799B 4 * Accepted 5 * Time:296ms 6 * Memory:14964k 7 */ 8 #include<iostream> 9 #include<fstream> 10 #include<sstream> 11 #include<algorithm> 12 #include<cstdio> 13 #include<cstring> 14 #include<cstdlib> 15 #include<cctype> 16 #include<cmath> 17 #include<ctime> 18 #include<map> 19 #include<stack> 20 #include<set> 21 #include<queue> 22 #include<vector> 23 using namespace std; 24 typedef bool boolean; 25 #define inf 0xfffffff 26 #define smin(a, b) (a) = min((a), (b)) 27 #define smax(a, b) (a) = max((a), (b)) 28 template<typename T> 29 inline boolean readInteger(T& u) { 30 char x; 31 int aFlag = 1; 32 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 33 if(x == -1) { 34 ungetc(x, stdin); 35 return false; 36 } 37 if(x == ‘-‘) { 38 aFlag = -1; 39 x = getchar(); 40 } 41 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 42 u *= aFlag; 43 ungetc(x, stdin); 44 return true; 45 } 46 47 typedef class Tshirt { 48 public: 49 int p; 50 int id; 51 52 Tshirt() { } 53 Tshirt(int p, int id):p(p), id(id) { } 54 55 boolean operator < (Tshirt b) const { 56 if(p != b.p) return p < b.p; 57 return id < b.id; 58 } 59 }Tshirt; 60 61 int n, m; 62 int* prices; 63 int *color1, *color2; 64 65 multiset<Tshirt> ps[3]; 66 67 inline void init() { 68 readInteger(n); 69 prices = new int[(const int)(n + 1)]; 70 color1 = new int[(const int)(n + 1)]; 71 color2 = new int[(const int)(n + 1)]; 72 for(int i = 1; i <= n; i++) 73 readInteger(prices[i]); 74 for(int i = 1; i <= n; i++) { 75 readInteger(color1[i]); 76 ps[color1[i] - 1].insert(Tshirt(prices[i], i)); 77 } 78 for(int i = 1; i <= n; i++) { 79 readInteger(color2[i]); 80 if(color1[i] != color2[i]) 81 ps[color2[i] - 1].insert(Tshirt(prices[i], i)); 82 } 83 } 84 85 inline void solve() { 86 int c; 87 readInteger(m); 88 while(m--) { 89 readInteger(c); 90 c--; 91 if(ps[c].size() == 0) { 92 printf("-1 "); 93 } else { 94 multiset<Tshirt>::iterator t = ps[c].begin(); 95 printf("%d ", t->p); 96 if(color1[t->id] != c + 1) { 97 ps[color1[t->id] - 1].erase(ps[color1[t->id] - 1].find(Tshirt(t->p, t->id))); 98 } else if (color2[t->id] != c + 1) { 99 ps[color2[t->id] - 1].erase(ps[color2[t->id] - 1].find(*t));100 }101 ps[c].erase(t);102 }103 }104 }105 106 int main() {107 init();108 solve();109 return 0;110 }
Problem#C Fountains
vjudge链接[here]
C题思路不是很难，很好想，结果写炸了。。。
第一种情况，买两个不同购买方式的物品，贪心就好了。
第二种情况，买两个购买方式相同的物品，先按价格从小到大拍一道序，然后记录一个能延伸到的一个最远的物品r,每次i++时要用while循环去更新r，接着剩下的事交给线段树查最大值就好了。两种购买方式的物品都做一下就好了。
当然，写炸的缘故
1.自己坑自己。。sort的cmpare函数改了后没有改for循环的顺序(第一种情况比较懒，开始就写了就不想改了)
2.少特判当某种购买方式的物品不存在的情况，然后建树就挂了，MLE。
Code
1 /** 2 * Codeforces 3 * Problem#799C 4 * Accepted 5 * Time:62ms 6 * Memory:6300k 7 */ 8 #include<iostream> 9 #include<fstream> 10 #include<sstream> 11 #include<algorithm> 12 #include<cstdio> 13 #include<cstring> 14 #include<cstdlib> 15 #include<cctype> 16 #include<cmath> 17 #include<ctime> 18 #include<map> 19 #include<stack> 20 #include<set> 21 #include<queue> 22 #include<vector> 23 using namespace std; 24 typedef bool boolean; 25 #define inf 0xfffffff 26 #define smin(a, b) (a) = min((a), (b)) 27 #define smax(a, b) (a) = max((a), (b)) 28 template<typename T> 29 inline boolean readInteger(T& u) { 30 char x; 31 int aFlag = 1; 32 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 33 if(x == -1) { 34 ungetc(x, stdin); 35 return false; 36 } 37 if(x == ‘-‘) { 38 aFlag = -1; 39 x = getchar(); 40 } 41 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 42 u *= aFlag; 43 ungetc(x, stdin); 44 return true; 45 } 46 47 typedef class MyPair { 48 public: 49 int c; 50 int p; 51 52 MyPair(int c = 0, int p = 0):c(c), p(p) { } 53 }MyPair; 54 55 typedef class SegTreeNode { 56 public: 57 int val; 58 SegTreeNode* l, *r; 59 60 SegTreeNode():val(0), l(NULL), r(NULL) { } 61 62 inline void pushUp() { 63 val = max(l->val, r->val); 64 } 65 }SegTreeNode; 66 67 typedef class SegTree { 68 public: 69 SegTreeNode* root; 70 71 SegTree() { } 72 SegTree(int n, MyPair*& lis) { 73 build(root, 1, n, lis); 74 } 75 76 void build(SegTreeNode*& node, int l, int r, MyPair*& lis) { 77 node = new SegTreeNode(); 78 if(l == r) { 79 node->val = lis[l].c; 80 return; 81 } 82 int mid = (l + r) >> 1; 83 build(node->l, l, mid, lis); 84 build(node->r, mid + 1, r, lis); 85 node->pushUp(); 86 } 87 88 int query(SegTreeNode*& node, int l, int r, int ql, int qr) { 89 if(ql > qr) return 0; 90 if(l == ql && r == qr) { 91 return node->val; 92 } 93 int mid = (l + r) >> 1; 94 if(qr <= mid) return query(node->l, l, mid, ql, qr); 95 if(ql > mid) return query(node->r, mid + 1, r, ql, qr); 96 int a = query(node->l, l, mid, ql, mid); 97 int b = query(node->r, mid + 1, r, mid + 1, qr); 98 return max(a, b); 99 }100 101 void clear(SegTreeNode*& node) {102 if(node->l) clear(node->l);103 if(node->r) clear(node->r);104 delete node;105 }106 }SegTree;107 108 int n;109 int C, D;110 MyPair *cs, *ds;111 int cnc = 0, cnd = 0;112 int bc = -1, bd = -1;113 SegTree stc, stdd;114 115 inline void init() {116 readInteger(n);117 readInteger(C);118 readInteger(D);119 cs = new MyPair[(const int)(n + 1)];120 ds = new MyPair[(const int)(n + 1)];121 int a, b;122 char x;123 for(int i = 1; i <= n; i++) {124 readInteger(a);125 readInteger(b);126 getchar(); x = getchar();127 if(x == ‘C‘ && b <= C)128 cs[++cnc] = MyPair(a, b);129 else if(x == ‘D‘ && b <= D)130 ds[++cnd] = MyPair(a, b);131 }132 }133 134 boolean cmp1(const MyPair& a, const MyPair& b) {135 if(a.c != b.c) return a.c > b.c;136 return a.p < b.p;137 }138 139 boolean cmp2(const MyPair& a, const MyPair& b) {140 if(a.p != b.p) return a.p < b.p;141 return a.c > b.c;142 }143 144 int res = 0;145 146 inline void solve() {147 if(cnc > 0)148 sort(cs + 1, cs + cnc + 1, cmp1);149 if(cnd > 0)150 sort(ds + 1, ds + cnd + 1, cmp1);151 for(int i = 1; i <= cnc; i++)152 if(cs[i].p <= C) {153 bc = cs[i].c;154 break;155 }156 for(int i = 1; i <= cnd; i++)157 if(ds[i].p <= D) {158 bd = ds[i].c;159 break;160 }161 if(bc != -1 && bd != -1)162 res = bc + bd;163 164 if(cnc > 0)165 sort(cs + 1, cs + cnc + 1, cmp2);166 if(cnd > 0)167 sort(ds + 1, ds + cnd + 1, cmp2);168 int r = cnc;169 if(cnc) {170 stc = SegTree(cnc, cs);171 for(int i = 1; i <= r; i++) {172 int a0 = 0, a1 = 0;173 while(cs[i].p + cs[r].p > C) r--;174 if(i > r) break;175 if(i > 1)176 a0 = stc.query(stc.root, 1, cnc, 1, i - 1);177 if(i < cnc)178 a1 = stc.query(stc.root, 1, cnc, i + 1, r);179 if(a0 == 0 && a1 == 0) continue;180 smax(res, max(a0, a1) + cs[i].c);181 }182 }183 184 r = cnd;185 if(cnd) {186 stdd = SegTree(cnd, ds);187 for(int i = 1; i <= r; i++) {188 int a0 = 0, a1 = 0;189 while(ds[i].p + ds[r].p > D) r--;190 if(i > r) break;191 if(i > 1)192 a0 = stdd.query(stdd.root, 1, cnd, 1, i - 1);193 if(i < cnd)194 a1 = stdd.query(stdd.root, 1, cnd, i + 1, r);195 if(a0 == 0 && a1 == 0) continue;196 smax(res, max(a0, a1) + ds[i].c);197 }198 }199 printf("%d", res);200 }201 202 int main() {203 init();204 solve();205 return 0;206 }
Codeforces Round#413 Problem A - C
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。