ABC068
ABC068
[ABC068B] Break Number
题面翻译
输入一个不大于100的正整数,输出小于等于它且最大的二的幂
题目描述
高橋君は $ 2 $ で割れる数が好きです。
正整数 $ N $ が与えられるので、$ 1 $ 以上 $ N $ 以下の整数のうち、最も $ 2 $ で割れる回数が多いものを求めてください。答えは必ず $ 1 $ つに定まります。
なお、$ 2 $ で割っていき、何回あまりが出ずに割れるかを、$ 2 $ で割れる回数と呼ぶことにします。
例えば
- $ 6 $ ならば、$ 6 $ -> $ 3 \(で、\) 1 $ 回 $ 2 $ で割れます。
- $ 8 $ ならば、$ 8 $ -> $ 4 $ -> $ 2 $ -> $ 1 \(で、\) 3 $ 回 $ 2 $ で割れます。
- $ 3 $ ならば、$ 0 $ 回 $ 2 $ で割れます。
输入格式
入力は以下の形式で標準入力から与えられる。
$ N $
输出格式
問題の答えを出力する。
样例 #1
样例输入 #1
7样例输出 #1
4样例 #2
样例输入 #2
32样例输出 #2
32样例 #3
样例输入 #3
1样例输出 #3
1样例 #4
样例输入 #4
100样例输出 #4
64提示
制約
- $ 1 ≦ N ≦ 100 $
Sample Explanation 1
$ 4 $ は $ 2 $ 回 $ 2 $ で割ることができ、これは $ 1 $, $ 2 $, ..., $ 7 $ の中で最も多いです。
思路
直接暴力计算,并且更新即可。
注意考虑特判。
|
[ABC068C] Cat Snuke and a Voyage
题面翻译
题意
有很多小岛,编号\(1\)到\(n\),某两个岛之间有船可以到达,每次从\(1\)号小岛出发,要到\(n\)号岛屿。规定只能做两次船,问是否能到达目标岛屿。
输入
第一行第一个数字是要到达的岛屿\(n\),第二行一个数字是\(m\),表示有\(m\)个岛之间有船可以连通,接下来\(m\)行每行两个数(岛的编号 ),表示某两个岛连通。
输出
如果能到达,输出
POSSIBLE
,否则输出IMPOSSIBLE
### 题意
有很多小岛,编号$1$到$n$,某两个岛之间有船可以到达,每次从$1$号小岛出发,要到$n$号岛屿。规定只能做两次船,问是否能到达目标岛屿。
### 输入
第一行第一个数字是要到达的岛屿$n$,第二行一个数字是$m$,表示有$m$个岛之间有船可以连通,接下来$m$行每行两个数(岛的编号 ),表示某两个岛连通。
### 输出
如果能到达,输出```POSSIBLE```,否则输出```IMPOSSIBLE```
### 数据范围
$3≤N≤200000$
$1≤M≤200000$
$1≤ai<bi≤N$
$(ai,bi)≠(1,N)$
如果$i≠j$则$(ai,bi)≠(aj,bj).$数据范围
\(3≤N≤200000\)
\(1≤M≤200000\)
\(1≤ai<bi≤N\)
\((ai,bi)≠(1,N)\)
如果\(i≠j\)则\((ai,bi)≠(aj,bj).\)
## 题目描述
[problemUrl]: https://atcoder.jp/contests/abc068/tasks/arc079_a
高橋キングダムには、高橋諸島という、$ N $ 個の島からなる諸島があります。 便宜上、これらの島を島 $ 1 $、島 $ 2 $、 ...、島 $ N $ と呼ぶことにします。
これらの諸島の間では、船の定期便が $ M $ 種類運行されています。 定期便はそれぞれ $ 2 $ つの島の間を行き来しており、$ i $ 種類目の定期便を使うと、 島 $ a_i $ と島 $ b_i $ の間を行き来する事ができます。
すぬけくんは今島 $ 1 $ にいて、島 $ N $ に行きたいと思っています。 しかし、島 $ 1 $ から島 $ N $ への定期便は存在しないことがわかりました。 なので、定期便を $ 2 $ つ使うことで、島 $ N $ に行けるか調べたいと思っています。
これを代わりに調べてあげてください。
## 输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ M $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ : $ a_M $ $ b_M $
## 输出格式
定期便を $ 2 $ つ使いたどり着けるならば `POSSIBLE`、たどり着けないならば `IMPOSSIBLE` と出力する。
## 样例 #1
### 样例输入 #13 2 1 2 2 3
### 样例输出 #1POSSIBLE
## 样例 #2
### 样例输入 #24 3 1 2 2 3 3 4
### 样例输出 #2IMPOSSIBLE
## 样例 #3
### 样例输入 #3100000 1 1 99999
### 样例输出 #3IMPOSSIBLE
## 样例 #4
### 样例输入 #45 5 1 3 4 5 2 3 2 4 1 4
### 样例输出 #4POSSIBLE
## 提示
### 制約
- $ 3\ ≦\ N\ ≦\ 200,000 $
- $ 1\ ≦\ M\ ≦\ 200,000 $
- $ 1\ ≦\ a_i\ <\ b_i\ ≦\ N $
- $ (a_i,\ b_i)\ \neq\ (1,\ N) $
- $ i\ \neq\ j $ ならば $ (a_i,\ b_i)\ \neq\ (a_j,\ b_j) $
### Sample Explanation 2
島 $ 4 $ へ行くには、定期便を $ 3 $ つ使う必要があります。
### Sample Explanation 4
島 $ 1 $、島 $ 4 $、島 $ 5 $ と移動すれば $ 2 $ つの定期便で移動可能です。
思路
注意到是要通过两条船到达,那么可以考虑:统计有那些点是从1到y,有哪些点是从x到n。
如果都满足的话,就可以到达。
|
[ABC068D] Decrease (Contestant ver.)
题面翻译
对于一个长度为N的序列\(a\),我们有这样的操作:
- 从序列\(a\)中选出一个最大值,将其减\(N\),对于剩下的\(N-1\)个元素,将其全部加\(1\)
- 可以证明操作\(K\)次之后,存在序列的最大值将小于或等于N-1。
现在,给定一个正整数\(K\),请构造出一个长度为\(N\)的序列\(a\)
使得满足操作\(K\)次之后满足序列的最大值将小于或等于N-1。题目描述
長さ $ N $ の非負整数列 $ a_i $ に対し、数列の最大値が $ N-1 $ 以下になるまで以下の操作を繰り返し行うことを考えます。
- 数列のうち最も大きい要素を求める、複数ある場合はどれか $ 1 $ つ選ぶ。この要素の値を $ N $ 減らす。これ以外の要素の値を $ 1 $ 増やす。
なお、この操作を行い続けると、いつかは数列の最大値が $ N-1 $ 以下になることが証明できます。
ここで、整数 $ K $ が与えられるので、この操作を行う回数がちょうど $ K $ 回になるような数列 $ a_i $ を $ 1 $ つ求めてください。なお、この問題の入出力の制約下では、かならず $ 1 $ つは条件を満たすような数列が存在することが示せます。
输入格式
入力は以下の形式で標準入力から与えられる。
$ K $
输出格式
以下の形式で数列を出力する。
$ N $ $ a_1 $ $ a_2 $ ... $ a_N $
ここで、$ 2 ≦ N ≦ 50, $ $ 0 ≦ a_i ≦ 10^{16} + 1000 $ でなければならない。
样例 #1
样例输入 #1
0样例输出 #1
4
3 3 3 3样例 #2
样例输入 #2
1样例输出 #2
3
1 0 3样例 #3
样例输入 #3
2样例输出 #3
2
2 2样例 #4
样例输入 #4
3样例输出 #4
7
27 0 0 0 0 0 0样例 #5
样例输入 #5
1234567894848样例输出 #5
10
1000 193 256 777 0 1 1192 1234567891011 48 425提示
制約
- $ 0 ≦ K ≦ 50 10^{16} $
Sample Explanation 3
\[2, 2\] -> \[0, 3\] -> \[1, 1\] と、$ 2 $ 回操作を行います。
思路
直接看这里:[ABC068D] Decrease (Contestant ver.) - 洛谷专栏 (luogu.com.cn)
一道有趣的构造题。
|