文档章节

2019 HDOJ Multi-University Training Contest Stage 9(杭电多校)

o
 osc_g8254g7s
发布于 2019/08/19 17:49
字数 1133
阅读 11
收藏 0
sol

精选30+云产品,助力企业轻松上云!>>>

有点自闭的一场。

题目链接: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 }
Code via. Sjoshua

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 }
View Code

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 }
View Code

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
HZNU_TI1050 训练实录

菜鸡队训练实录 比赛记录:[名称:奖项 / 排名] 2018: ZJPSC Bronze / 86 CCPC Jilin Bronze / 95 ICPC Shenyang Bronze / 74 ICPC Tsingdao Honorable / 241 CCPC Finals Bronze / 43 201......

osc_pmwdk963
2018/07/30
5
0
训练记录

记录一下打的比赛 2019: ICPC Nanchang Invitational: Bronze/127 SCPSC: Bronze/63 ICPC Nanjing: Honorable/217 ICPC Nanchang: Bronze/179 队伍训练。 2019牛客多校训练: 2019-07-18: 2 ......

osc_cesboqi4
2019/08/21
4
0
HDU 6685 Rikka with Coin (枚举 思维)

2019 杭电多校 9 1006 题目链接:HDU 6685 比赛链接:2019 Multi-University Training Contest 9 Problem Description Rikka hates coins, and she used to never carry any coins with her.......

osc_3rgq3dae
2019/08/20
3
0
HDU 6693 Valentine's Day (概率)

2019 杭电多校 10 1003 题目链接:HDU 6693 比赛链接:2019 Multi-University Training Contest 10 Problem Description Oipotato loves his girlfriend very much. Since Valentine's Day ......

osc_rnrep3wi
2019/08/22
1
0
HDU 6298.Maximum Multiple-数学思维题(脑子是个好东西,可惜我没有) (2018 Multi-University Training Contest 1 1001)

暑假杭电多校第一场,这一场是贪心场,很多贪心的题目,但是自己太菜,姿势挫死了,把自己都写吐了。。。 2018 Multi-University Training Contest 1 HDU6298.Maximum Multiple 题目意思就是...

osc_wk8cl8xe
2018/07/25
2
0

没有更多内容

加载失败,请刷新页面

加载更多

事务特性

ACID ACID : 原子性 - 一致性 - 隔离性 - 持久性 四大特性 原子性: 事务将一组逻辑单元看成 一个操作 , 原子是最小单位不可再分割 一致性: 事务的前后 数据的应该保持一致 隔离性(isolation)...

osc_3grma05a
19分钟前
7
0
微信小程序实现分享到朋友圈

2020年7月8日。微信小程序推出分享朋友圈,所以笔者先来试一下,没想到一下搞成了 。。 按照微信官方文档得第一步,我们需要设置允许发给朋友,在小程序得生命周期里面这样写。 首先,把你的...

osc_a8r2ub9u
21分钟前
7
0
小程序分享到朋友圈 H5打开小程序H5打开APP 「wx-open-launch-weapp」 「wx-open-launch-app」

前言 微信更新了两个功能块 简单使用了下 给大家写篇文章说说 避免走弯路 欧力给! 1.小程序分享到朋友圈 //在页面的js里设置下就ok onShareTimeline(){ return { title: "微视宝...

osc_dwuu5jqk
22分钟前
17
0
解决死锁——哲学家就餐

解决方法有: 1、更改为单个锁 2、将锁排序 产生死锁的原因 产生死锁的原因是一个线程在持有一把锁时又去申请另外一把锁,也就是锁嵌套。而另一把锁被另外一个线程持有。 举个广为人知的例子...

osc_2qah5avr
23分钟前
11
0
面试官:软件测试没搞懂这些,哪里来的自信投简历? 刁钻问得高频的面试题(含答案)

问得高频的问题(含答案) 软件的生命周期(prdctrm) 计划阶段(planning)-〉需求分析(requirement)-〉设计阶段(design)-〉编码(coding)->测试(testing)->运行与维护(running maintrnacne) 测试...

测试人追风
24分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部