ABC065

[ABC065A] Expired?

题面翻译

高桥君在保质期前 \(a\) 天买了食物，\(b\) 天后吃了，但是高桥君吃了过期 \(x\) 天的食物不会胃痛，如果过了 \(x\) 天吃，他就会胃痛。

给定 \(x,a,b\)，如果食物没有过期，输出 delicious。

如果食物过期了但吃了不会胃痛，输出 safe。

如果吃了会胃痛，输出 dangerous。

题目描述

高橋君は胃が強いので、賞味期限を $ X $ 日まで過ぎた食品を食べてもお腹を壊しません。 賞味期限を $ X+1 $ 日以上過ぎた食品を食べると、お腹を壊します。

また、賞味期限を過ぎずに食べると、おいしく感じます。そうでない場合、おいしく感じません。

高橋君は、賞味期限の $ A $ 日前に食品を買ってきて、買ってから $ B $ 日後に食べました。

高橋君が食品をおいしく感じた場合 delicious を、おいしくは感じなかったがお腹は壊さなかった場合 safe を、お腹を壊した場合 dangerous を出力するプログラムを作成してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ X $ $ A $ $ B $

输出格式

高橋君が食品をおいしく感じた場合 delicious を、おいしくは感じなかったがお腹は壊さなかった場合 safe を、お腹を壊した場合 dangerous を出力せよ。

样例 #1

样例输入 #1

4 3 6

样例输出 #1

safe

样例 #2

样例输入 #2

6 5 1

样例输出 #2

delicious

样例 #3

样例输入 #3

3 7 12

样例输出 #3

dangerous

提示

制約

• $ 1 ≦ X,A,B ≦ 10^9 $

Sample Explanation 1

賞味期限を $ 3 $ 日過ぎて食べるので、おいしくは感じませんが、お腹も壊しません。

Sample Explanation 2

賞味期限を過ぎていないので、おいしく感じます。

Sample Explanation 3

賞味期限を $ 5 $ 日過ぎて食べるので、お腹を壊します。

思路

这题完全败在了理解上qwq。

#include <bits/stdc++.h>
using namespace std;

int x, a, b;

int main() {
    scanf("%d%d%d", &x, &a, &b);
    if (a >= b) {
        puts("delicious");
    }
    else if ((b - a) <= x) {
        puts("safe");
    }
    else {
        puts("dangerous");
    }
    return 0;
}

[ABC065B] Trained?

题面翻译

有一堆按钮，按钮的编号是从 \(1\) 到 \(n\) 。第 \(i\) 个按钮对应第 \(i\) 个灯。

你按下第 \(i\) 个按钮时，如果你按下的按钮对应的灯是关闭的,那么灯 \(a_i\) 会开启，灯 \(i\) 会关闭； 如果按钮对应的灯是开启的,那么按下它就什么都不会发生。

最初，灯 \(1\) 是关闭的，其他的灯都开着。 高桥君希望最后灯 \(2\) 是关闭的。

输出他最少按下按钮的次数，如果不能则输出 \(-1\) 。

题目描述

筋力をつけたい高橋君は、AtCoder 社のトレーニング設備で、トレーニングをすることにしました。

AtCoder 社のトレーニング設備には $ N $ 個のボタンがついており、ちょうど $ 1 $ 個のボタンが光っています。 ボタンには、$ 1 $ から $ N $ までの番号がついています。 ボタン $ i $ が光っているときにそのボタンを押すと、ボタン $ i $ の明かりが消え、その後ボタン $ a_i $ が光ります。$ i=a_i $ であることもあります。 光っていないボタンを押しても、何も起こりません。

最初、ボタン $ 1 $ が光っています。高橋君は、ボタン $ 2 $ が光っている状態で、トレーニングをやめたいと思っています。

そのようなことは可能かどうか判定し、もし可能なら最低で何回ボタンを押す必要があるかを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ a_1 $ $ a_2 $ : $ a_N $

输出格式

ボタン $ 2 $ を光らせることが不可能な場合、$ -1 $ を出力せよ。 そうでない場合、ボタン $ 2 $ を光らせるために必要なボタンを押す回数の最小値を出力せよ。

样例 #1

样例输入 #1

3
3
1
2

样例输出 #1

2

样例 #2

样例输入 #2

4
3
4
1
2

样例输出 #2

-1

样例 #3

样例输入 #3

5
3
3
4
2
4

样例输出 #3

3

提示

制約

• $ 2 ≦ N ≦ 10^5 $
• $ 1 ≦ a_i ≦ N $

Sample Explanation 1

ボタン $ 1,3 $ の順に押せばよいです。

Sample Explanation 2

ボタン $ 1 $ を押すとボタン $ 3 $ 、ボタン $ 3 $ を押すとボタン $ 1 $ が光るので、ボタン $ 2 $ が光ることはありません。

思路

算是一个简单的链表？直接模拟即可

#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;
int a[MAXN];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int i=1;
    int cnt=0;
    while(n--){
        //如果到达2点，直接输出操作次数
        if(i==2){
            cout<<cnt;
            return 0;
        }
        i=a[i];
        cnt++;
    }
    cout<<-1;
    return 0;
}

[ABC065C] Reconciled?

题面翻译

题目描述

すぬけ君养了 $ N $ 只狗和 \(M\) 只猴。すぬけ君想把这 \(N+M\) 只动物排成一列。

すぬけ君希望狗与狗不能互相挨着，猴与猴不能互相挨着。

这样的排列方式有多少种？请输出答案对 \(10^9+7\) 取模的结果。不过，狗与狗间，猴与猴间相互区别。

数据范围

• $1 N,M ^5 $

输入

输入按以下标准：

N M

输出

输出方案数对 \(10^9+7\) 取模的结果

样例1解释

将每只狗分别记为A,B，将每只猴分别记为C,D，则共有ACBD,ADBC,BCAD,BDAC,CADB,CBDA,DACB,DBCA \(8\) 种排列方法。

感谢@ミク 提供的翻译

题目描述

すぬけ君は、犬を $ N $ 匹と猿を $ M $ 匹飼っています。すぬけ君は、この $ N+M $ 匹を一列に並べようと思っています。

文字通り犬猿の仲の犬たちと猿たちを仲直りさせたいすぬけ君は、犬同士、または猿同士が隣り合うところができないように並べようと思っています。

このような並べ方は何通りあるでしょうか。犬と猿は $ 10^9+7 $ 以上の数を理解できないので、並べ方の個数を $ 10^9+7 $ で割ったあまりを求めてください。 ただし、犬同士、また猿同士は互いに区別します。また、左右が反転しただけの列も異なる列とみなします。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ M $

输出格式

並べ方の個数を $ 10^9+7 $ で割ったあまりを出力せよ。

样例 #1

样例输入 #1

2 2

样例输出 #1

8

样例 #2

样例输入 #2

3 2

样例输出 #2

12

样例 #3

样例输入 #3

1 8

样例输出 #3

0

样例 #4

样例输入 #4

100000 100000

样例输出 #4

530123477

提示

制約

• $ 1 ≦ N,M ≦ 10^5 $

Sample Explanation 1

犬をそれぞれ A,B とし、猿をそれぞれ C,D とすると、ACBD,ADBC,BCAD,BDAC,CADB,CBDA,DACB,DBCA の $ 8 $ 通りの並べ方があります。

思路

数学题。

如果猴子和狗的数目之差大于1，肯定不行，直接输出0即可。

如果小于或者等于1，需要分类讨论。

如果相等，那么狗和猴子的顺序可以颠倒，需要乘以2，不等则不行。

那么问题就变成了简单的排列组合问题，注意猴子和狗子是有区分的，那么答案就是狗子数目的阶乘和猴子数目阶乘的乘积。

#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;
ll fac[MAXN];
//预处理出阶乘
void init(){
    fac[1]=1;
    for(int i=2;i<=1e5;i++){
        fac[i]=(fac[i-1]*i)%mod;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int n,m;cin>>n>>m;
    //之差大于1，直接输出0
    if(abs(n-m)>1)cout<<"0";
    else{
        ll ans=0;
        //如果相等，则可以交换位置，注意*2
        if(n==m){
            ans=(fac[n]*fac[m]%mod)*2%mod;
        }
        //不等则不行
        else{
            ans=(fac[n]*fac[m]%mod);
        }
        cout<<ans;
    }
    return 0;
}

[ABC065D] Built?

题面翻译

题目描述

平面上有 \(N\) 个城市。第 \(i\) 个城市的坐标为 \((x_i,y_i)\) 。同一个坐标上可能有多个城市。在坐标为 \((a,b)\) 的城市和坐标为 \((c,d)\) 的城市间建造一条道路需要 \(min(|a-c|,|b-d|)\) 円。只能在城市与城市间建造道路。 要使任意两个城市之间有直接或间接道路相连，最少需要多少円？

数据范围

• \(2 \leq N \leq 10^5\)
• \(0 \leq x_i,y_i \leq 10^9\)
• 输入全为整数

输入

输入按以下形式： \[ N \] \[ x_1 \space y_1 \] \[ x_2 \space y_2 \] \[ : \] \[ x_N \space y_N \]

输出

请输出使任意两城市间有直接或间接道路连接所需最少钱数。

样例1解释

在城市 \(1\) 与城市 \(2\) 间建造一条道路，在城市 \(2\) 与城市 \(3\) 间建造一条道路，花费 \(2+1=3\) 円。

感谢@ミク 提供的翻译

题目描述

平面上に、$ N $ 個の街があります。$ i $ 個目の街は、座標 $ (x_i,y_i) $ にあります。同じ座標に、複数の街があるかもしれません。

座標 $ (a,b) $ にある街と座標 $ (c,d) $ にある街の間に道を造るのには、$ min(|a-c|,|b-d|) $ 円かかります。街と街の間以外に、道を造ることはできません。

任意の $ 2 $ つの街の間を、道を何本か通って行き来できるようにするためは、最低で何円必要でしょうか。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ : $ x_N $ $ y_N $

输出格式

任意の $ 2 $ つの街の間を道を何本か通って行き来できるようにするためにかかるお金の最小値を出力せよ。

样例 #1

样例输入 #1

3
1 5
3 9
7 8

样例输出 #1

3

样例 #2

样例输入 #2

6
8 3
4 9
12 19
18 1
13 5
7 6

样例输出 #2

8

提示

制約

• $ 2 ≦ N ≦ 10^5 $
• $ 0 ≦ x_i,y_i ≦ 10^9 $
• 入力は全て整数である

Sample Explanation 1

街 $ 1 $ と $ 2 $ 、街 $ 2 $ と $ 3 $ の間に道を造ると、かかるお金は $ 2+1=3 $ 円になります。

思路

比较容易地发现可以使用最小生成树。

但是如果直接建图的话，肯定会TLE。

不妨采取以下思路：题目要求的是\(min(x_i-x_j,y_i-y_j)\)。那么我们可以先对所有点的\(x\)坐标进行排序，得到的相邻两个差是最小的，所以我们只需要建\(n-1\)条边，每条边的权值为\(x_i-x_{i-1}\)。

同理，\(y\)也是进行一样的处理。

最后再在其中选择最小值即可。

#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;
ll n;
ll fa[MAXN];
struct node{
    ll id;
    ll x,y;
}a[MAXN];

struct Edge{
    ll from,to,val;
}b[MAXN];

bool cmp1(node x,node y){
    return x.x<y.x;
}

bool cmp2(node x,node y){
    return x.y<y.y;
}

bool cmp3(Edge x,Edge y){
    return x.val<y.val;
}

ll find(ll x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
        a[i].id=i;
    }
    //注意初始化
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    
    //根据x坐标进行建边
    sort(a+1,a+1+n,cmp1);
    ll cnt=0;
    for(int i=2;i<=n;i++){
        b[++cnt].from=a[i-1].id;
        b[cnt].to=a[i].id;
        b[cnt].val=a[i].x-a[i-1].x;
    }

    //根据y坐标进行建边
    sort(a+1,a+1+n,cmp2);
    for(int i=2;i<=n;i++){
        b[++cnt].from=a[i-1].id;
        b[cnt].to=a[i].id;
        b[cnt].val=a[i].y-a[i-1].y;
    }
    sort(b+1,b+1+cnt,cmp3);

    ll ans=0;
    //联通操作
    for(ll i=1;i<=cnt;i++){
        ll from=find(b[i].from);
        ll to=find(b[i].to);
        if(from!=to){
            fa[from]=to;
            n--;
            ans+=b[i].val;
            if(n==1)break;
        }
    }
    cout<<ans;
    return 0;
}