有点自闭的一场。
题目链接：http://acm.hdu.edu.cn/contests/contest_show.php?cid=856
B：
本质就是数射线交点。
1 /* Codeforces Contest 2019_mutc_09 2 * Problem B 3 * Au: SJoshua 4 */ 5 #include <unordered_map> 6 #include <cctype> 7 #include <cstdio> 8 #include <vector> 9 #include <string> 10 #include <iostream> 11 #include <algorithm> 12 13 using namespace std; 14 15 class binTree { 16 public: 17 binTree(vector <int> &a) { 18 bit.resize(a.size() + 1); 19 for (int i = 1; i <= a.size(); i++) { 20 bit[i] = a[i - 1]; 21 for (int j = i - 2; j >= i - lowbit(i); j--) { 22 bit[i] += a[j]; 23 } 24 } 25 } 26 void edit(int index, int delta) { 27 for (int i = index; i < bit.size(); i += lowbit(i)) { 28 bit[i] += delta; 29 } 30 } 31 int query(int index) { 32 int ret = 0; 33 for (int i = index; i > 0; i -= lowbit(i)) { 34 ret += bit[i]; 35 } 36 return ret; 37 } 38 private: 39 int lowbit(int num) { 40 return num & (-num); 41 } 42 vector <int> bit; 43 }; 44 45 struct event { 46 int type, line, col; // 1: in / 2: query(up) / 3: query(down) / 4: out 47 }; 48 49 int read(void) { 50 char ch; 51 do { 52 ch = getchar(); 53 } while (!isdigit(ch)); 54 int ret = 0; 55 while (isdigit(ch)) { 56 ret *= 10; 57 ret += ch - '0'; 58 ch = getchar(); 59 } 60 return ret; 61 } 62 63 int main(void) { 64 int T; 65 T = read(); 66 while (T--) { 67 int n, m, k; 68 m = read(); 69 n = read(); 70 k = read(); 71 vector <event> events; 72 vector <int> ints(2 * k); 73 for (int i = 0; i < k; i++) { 74 int x, y; 75 char d; 76 y = read(); 77 x = read(); 78 scanf(" %c", &d); 79 ints[i] = x; 80 ints[i + k] = y; 81 switch (d) { 82 case 'L': 83 events.push_back({1, x, 0}); 84 events.push_back({4, x, y}); 85 break; 86 case 'R': 87 events.push_back({1, x, y}); 88 events.push_back({4, x, m}); 89 break; 90 case 'U': 91 events.push_back({2, x, y}); 92 break; 93 case 'D': 94 events.push_back({3, x, y}); 95 break; 96 } 97 } 98 ints.push_back(0); 99 ints.push_back(m); 100 ints.push_back(n); 101 unordered_map <int, int> mp; 102 sort(ints.begin(), ints.end()); 103 ints.resize(unique(ints.begin(), ints.end()) - ints.begin()); 104 for (int i = 0; i < ints.size(); i++) { 105 mp[ints[i]] = i + 1; 106 } 107 for (auto &e: events) { 108 e.line = mp[e.line]; 109 e.col = mp[e.col]; 110 } 111 sort(events.begin(), events.end(), [](event &a, event &b) -> bool { 112 return a.col == b.col ? a.type < b.type : a.col < b.col; 113 }); 114 long long int ans = 1; 115 vector <int> arr(ints.size() + 1); 116 auto bt = binTree(arr); 117 for (auto e: events) { 118 switch (e.type) { 119 case 1: 120 bt.edit(e.line, 1); 121 break; 122 case 2: 123 ans += bt.query(mp[n]) - bt.query(e.line - 1); 124 break; 125 case 3: 126 ans += bt.query(e.line); 127 break; 128 case 4: 129 bt.edit(e.line, -1); 130 break; 131 } 132 } 133 cout << ans << endl; 134 } 135 return 0; 136 }
E：
考虑y开头的坑。
1 /* Codeforces Contest 2019_mutc_09 2 * Problem E 3 * Au: SJoshua 4 */ 5 #include <cstdio> 6 #include <vector> 7 #include <string> 8 #include <iostream> 9 10 using namespace std; 11 12 int main(void) { 13 int T; 14 cin >> T; 15 while (T--) { 16 string str; 17 cin >> str; 18 int i = 0; 19 for (auto ch: str) { 20 if (ch == 'y') { 21 i++; 22 } else { 23 break; 24 } 25 } 26 if (i < str.length() && str[i] == 'z') { 27 str[i] = 'b'; 28 } 29 cout << str << endl; 30 } 31 return 0; 32 }
F：
直接暴力枚。
1 /* Codeforces Contest 2019_mutc_09 2 * Problem F 3 * Au: SJoshua 4 */ 5 #include <cstdio> 6 #include <vector> 7 #include <string> 8 #include <iostream> 9 10 using namespace std; 11 12 bool sol[10][5][2][21]; 13 14 void search(void) { 15 vector <int> c1; 16 for (int p10 = 0; p10 <= 9; p10++) { 17 auto c2 = c1; 18 for (int p20 = 0; p20 <= 4; p20++) { 19 auto c3 = c2; 20 for (int p50 = 0; p50 <= 1; p50++) { 21 for (unsigned int i = 0; i < 1 << c3.size(); i++) { 22 int sum = 0; 23 for (int j = 0; j < c3.size(); j++) { 24 sum += c3[j] * ((i >> j) & 1); 25 } 26 if (sum <= 20) { 27 sol[p10][p20][p50][sum] = true; 28 } 29 } 30 c3.push_back(5); 31 } 32 c2.push_back(2); 33 } 34 c1.push_back(1); 35 } 36 } 37 38 int solve(int n) { 39 int dollar = 0; 40 vector <bool> rec(10), ext(10), top(10); // rec: 100以下 ext: 100以上 41 int maxn = 0; 42 vector <int> raw(n); 43 bool fake = false; 44 for (int i = 0; i < n; i++) { 45 cin >> raw[i]; 46 int bit = raw[i] / 100; 47 if (bit > maxn) { 48 maxn = bit; 49 for (int i = 0; i < 10; i++) { 50 top[i] = false; 51 } 52 } 53 if (bit == maxn) { 54 top[raw[i] % 100 / 10] = true; 55 } 56 dollar = max(dollar, bit); 57 if (raw[i] >= 100) { 58 ext[raw[i] % 100 / 10] = true; 59 } else { 60 rec[raw[i] % 100 / 10] = true; 61 } 62 if (raw[i] % 10) { 63 fake = true; 64 } 65 } 66 if (fake) { 67 return -1; 68 } 69 int ans = 99999999; 70 int a, b, c, d; 71 for (int i = 0; i <= 9; i++) { 72 for (int j = 0; j <= 4; j++) { 73 for (int k = 0; k <= 1; k++) { 74 bool flag = true, flag2 = true; 75 for (int p = 0; p <= 9; p++) { 76 if (rec[p]) { 77 // 7 20 40 50 60 70 90 110 78 // 100+的是否都能直接拿出来？ 79 if (!sol[i][j][k][p]) { 80 flag = false; 81 break; 82 } 83 } 84 if (ext[p]) { 85 if (!(sol[i][j][k][p] || sol[i][j][k][p + 10])) { 86 flag = false; 87 break; 88 } 89 } 90 if (top[p]) { 91 if (!sol[i][j][k][p + 10]) { 92 flag2 = false; 93 } 94 } 95 } 96 if (flag) { 97 int cur = i + j + k + dollar; 98 if (dollar && flag2) { 99 cur--; 100 } 101 if (cur < ans) { 102 ans = cur; 103 a = i, b = j, c = k; 104 d = dollar; 105 if (dollar && flag2) { 106 d--; 107 } 108 } 109 } 110 } 111 } 112 } 113 // cout << a << b << c << d << endl; 114 return ans; 115 } 116 117 int main(void) { 118 int T; 119 cin >> T; 120 search(); 121 while (T--) { 122 int n; 123 cin >> n; 124 cout << solve(n) << endl; 125 } 126 return 0; 127 }