Loading... ![toc] # Atcoder Beginner Contest 185 题解报告 [比赛地址](https://atcoder.jp/contests/abc185/tasks) + `总评:` ```text 重新开始简单的做一些思维训练了...(可能实际都算不上思维训练). 总的来说A,B,C,D没有难度 E题没写出来,想法是LIS,但是我并不会写LIS F题树状数组/线段树模板题 ``` ## A: `ABC Preparation` + `题面:` 我们在准备Atcoder Beginner Contest的比赛,举行一场比赛需要有四种类型题目,分别为100分题,200分题,300分题,400分题.四种题目的数量分别是$A_1,A_2,A_3,A_4$.请问最多可以举行多少场比赛? + `数据范围:` >+ $1\le A_i \le 100(1\le i \le 4) $ >+ $A_i \in \Z^+$ + `思路:` 答案显然是: $$ Answer = min(A_i) $$ + `参考代码:` ```cpp int main() { int a,mi = 1e9; for(int i = 0;i < 4;i++){ cin >> a; mi = min(a,mi); } cout << mi << endl; return 0; } ``` + `插曲:` 写题的时候,是和`Tomoyo`讨论关于做`VR`课设的事情,他看到我在写A,写的时候可能有点分心,我就顺口说了一句没想到,还真的给我`WA`了 原因是:`cout << mi << endl;`写成了`cout << a << endl;` 这就是立flag的下场么 ## B: `Smartphone Addiction` + `题面:` 你的手机有$N$`mAh`的电量,在`n + 0.5`$(n\in \N)$的时刻,你的手机将会下降`1 mAh`电量 现在你手机满电在`0 时刻`从家里出发,并造访$M$个咖啡馆,最后在$T$时刻回家. 我们呆在第$i$个咖啡馆的时间从$A_i$到$B_i$,在咖啡馆的的时间里面,我们会对手机充电,此时在`n + 0.5`$(n\in \N)$的时刻,你的手机将会上升`1 mAh`电量. 如果你的手机充满了电,那么电量不再上升. `问:回家途中手机有无关机(电量为0)` + `数据范围:` >+ $1 \le N \le 10^9$ >+ $1 \le M \le 1000$ >+ $1 \le T \le 10^9$ >+ $0 < A_1 < B_1 < A_2 < ... < A_M < B_M < T$ >+ 所有数据均为整数 + `思路:` 没有思路,就模拟啦,这个代码可能写丑了点 + `参考代码:` ```cpp int a,b; int main() { int n,m,t,lst = 0,beg; cin >> n >> m >> t; beg = n; for(int i = 0;i < m;i++){ cin >> a >> b; n -= a-lst; if(n <= 0){ puts("No"); return 0; } n += b-a; n = min(beg,n); lst = b; } n -= t - lst; if(n <= 0) { puts("No"); return 0; } puts("Yes"); return 0; } ``` ## C: `Duodecim Ferra` + `题面:` 有一个长度为$L$的铁棒,选择$11$个位置进行切割,切割后的$12$块长度必须为整数,问有多少种切割方式,保证答案不超过$2^{63}$ + `数据范围:` > $12 \le L \le 200,L \in \Z$ + `思路:` 简单排列组合题,答案即$\binom{L-1}{11}$,`C++`写起来可能麻烦些,直接上`Python`. + `参考代码:` ```python import math n = int(input())-1 print(math.factorial(n)//(math.factorial(11)*math.factorial(n-11))) ``` + `插曲:` `RE`了一发,`Python`太久没写,输入写成了`n = input()`,第三行直接成字符串与整数进行操作发生错误. ## D: `Stamp` + `题面:` 现在有$N$块从左到右的方块,从左边开始的第$i$块方块的编号是$i$.其中$M$块方块,编号为$A_1,A_2,...,A_M$的颜色是<font color = blue>蓝色的</font>; 其余的方块的颜色是白色的,现在你要创造一个宽度为$k$的印章,每次能覆盖连续的$k$个方块,并将它们涂成<font color = red>红色</font>.最后我们要将所有的白色方块全部涂成<font color = "red">红色</font>,且不能影响<font color = blue>蓝色</font>方块. `问:`在最优的选择$k$长度印章的情况下,最少要涂多少次. + `数据范围:` >+ $1 \le N \le 10^9$ >+ $0 \le M \le 2\times 10^5$ >+ $1 \le A_i \le N$ >+ 保证$A_i$各不相同,所有数据都是整数 + `思路:` 显然先以蓝色方块为分割点,获得所有连续的白色方块长度,假设为$n$段:$d_1,d_2,...,d_n$,一开始没仔细看样例,以为白色的砖只能涂一次.所以想到的答案是$$\frac {N-M} {gcd(d_i)_{i=1}^n}$$写完代码浪费了很多时间 看了样例发现涂成了红色的方块还可以涂,答案变成了 $$ \sum_{i=1}^n \lceil \frac {d_i} {min(d_i)} \rceil $$ + `参考代码:` ```cpp int num[201000]; vector<int> nums; int main() { int n,m; scanf("%d%d",&n,&m); for(int i = 0;i < m;i++){ scanf("%d",&num[i]); } sort(num,num+m); num[m] = n+1; int lst = 0,now; int mi = n; for(int i = 0;i <= m;i++){ now = num[i] - lst - 1; if(now){ mi = min(mi,now); nums.push_back(now); } lst = num[i]; } int ans = 0; for(int i = 0;i < nums.size();i++){ ans += (nums[i]+mi-1)/mi; } printf("%d\n",ans); return 0; } ``` ## F: `Range Xor Query` + `题面:` 我们有一个长度为$N$的数组$A$. 进行$Q$次操作,第$i$次操作输入三个数:$T_i,X_i,Y_i$ + 如果$T_i = 1$,将$A_{X_i}$替换为$A_{X_i}\oplus Y_i$ + 如果$T_i = 2$,打印$A_{X_i}\oplus A_{X_{i+1}}\oplus \dots \oplus A_{Y_i}$ + `数据范围:` >+ $1\le N \le 300000$ >+ $1\le Q \le 300000$ >+ $0\le A_i < 2^{30}$ >+ $T_i \in \{1,2\}$ >+ 如果$T_i = 1$,$1\le X_i \le N$且$0\le Y_i < 2^{30}$ >+ 如果$T_i = 2$,$1\le X_i \le Y_i \le N$ >+ 保证输入数据均为整数 + `思路:` 标准的树状数组/线段树模板题,只需要单点更新和区间查询即可 + `参考代码:` ```cpp inline int lowbit(int n) { return n&(-n); } int tree[maxn]; void add(int x,ll y) { while(x<=maxn){ tree[x]^=y; x+=lowbit(x); } } int getsum(int x) { ll ans=0; while(x){ ans^=tree[x]; x-=lowbit(x); } return ans; } int main() { int n,m,tmp; scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++){ scanf("%d",&tmp); add(i,tmp); } for(int i = 0;i < m;i++){ int op,x,y; scanf("%d",&op); if(op==1){ scanf("%d%d",&x,&y); add(x,y); } else{ scanf("%d%d",&x,&y); printf("%d\n",getsum(y)^getsum(x-1)); } } return 0; } ``` Last modification：December 14, 2020 © Allow specification reprint Support Appreciate the author Like 如果觉得我的文章对你有用，请随意赞赏