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 $ の中で最も多いです。

思路

直接暴力计算，并且更新即可。

注意考虑特判。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=3e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
double r[10];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    int k=0;
    int tot=0;
    int ans=0;
    if(n==1||n==2){
        cout<<1;
        return 0;
    }
    for(int i=1;i<=n;i++){
        k=i;
        int cnt=0;
        while(1){
            if(k%2==0){
                k/=2;
                cnt++;
            }
            else break;
        }
        if(cnt>tot){
            ans=i;
            tot=cnt;
        }
    }
    cout<<ans;
    return 0;
}

[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

### 样例输入 #1

3 2 1 2 2 3

### 样例输出 #1

POSSIBLE

## 样例 #2

### 样例输入 #2

4 3 1 2 2 3 3 4

### 样例输出 #2

IMPOSSIBLE

## 样例 #3

### 样例输入 #3

100000 1 1 99999

### 样例输出 #3

IMPOSSIBLE

## 样例 #4

### 样例输入 #4

5 5 1 3 4 5 2 3 2 4 1 4

### 样例输出 #4

POSSIBLE

## 提示

### 制約

- $ 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。

如果都满足的话，就可以到达。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
int a[MAXN],b[MAXN];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(x==1)a[y]=1;
        if(y==n)b[x]=1;
    }
    //枚举所有的点，看看能否从1到i，又从i到n
    for(int i=1;i<=m;i++){
        if(a[i]&&b[i]){
            cout<<"POSSIBLE";
            return 0;
        }
    }
    cout<<"IMPOSSIBLE";
    return 0;
}

[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)

一道有趣的构造题。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll k;cin>>k;
    cout<<50<<"\n";
    for(int i=0;i<50;i++){
        cout<<i+(k+i)/50<<" ";
    }
    return 0;
}