河南理工大学算法协会暑期集训积分赛（五） Day33

Steve的水池

Description:
Steve 拥有深棕色头发，晒黑的褐色皮肤，紫色的眼睛，身穿青蓝色的衬衫，一条紫蓝色牛仔裤以及灰黑色的鞋子。他还拥有2px至4px大小的胳膊。Steve 似乎拥有轻微的浅棕色胡子茬，或者拥有一张嘴，这取决于你怎样看他。

Steve 需要种庄稼，圈养动物来获得食物来源，为了抵抗怪物，他需要挖矿获得铁锭，金锭，甚至钻石来制作更高级的武器装备，通常，他还需要对武器装备附魔，来提升效果，为此，他不得不需要经常下矿。

在经历了枯燥又乏味的矿工生活后，Steve 打算建造一个水池来放松放松，他打算把水池建造成一个高度为1，长宽分别为N,M的水池，为此，他需要向水池中倒水，但Steve 只有一个水桶，他不想要浪费更多的铁锭来制作更多的水桶，为此，他需要尽可能少的往水池里倒水以尽快建造好水池，但是Steve 的世界有一个很奇怪的特性，每向一个区域倒水的时候，在这个区域会形成一个水源，当一个区域四个方向中至少有两个方向紧挨着这个区域的地方都为水源的话，这个区域也将会形成水源，Steve 想要知道最少他需要倒多少次水才能使水池每处都形成水源。

输入格式
输入第1行为一个整数T。（1 ≤ T ≤ 1000）
第2行到第T+1行每行为两个整数N,M代表水池的长宽。（1 ≤ N,M ≤ 1e9）

输出格式
输出为T行，每行输出一个整数，代表Steve 最少需要的倒水次数。

样例
input
1
1 1
output
1
input
2
1 3
3 3
output
2
3

Problem solving:
这道题我是找规律做的。但是标程竟然是(m+n)/2向上取整。
我找规律过程艰辛就不细说了。
另外今天学到了ceil返回的是一个double类型！！！

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int t;
    ll n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld %lld",&m,&n);
        ll k=max(m,n)-min(m,n);
        ll ans=min(m,n);
        if(k%2==1)
        {
            ans+=(k)/2+1;
        }
        else
        {
            ans+=(k)/2;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

标程

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int t;
    cin>>t;
    ll n,m;
    while(t--)
    {
        cin>>n>>m;
        cout<<(ll)ceil((m+n)*0.5)<<endl;
    }
    return 0;
}

掷骰子

Description:
骰子，中国传统民间娱乐用来投掷的博具，早在战国时期就已经被发明。

现在给你 n 个骰子，求 n 个骰子掷出点数之和为 a 的概率是多少。

输入格式
第一行输入一个整数 T，表示有 T 组测试数据（1≤T≤10）
每组测试数据输入两个整数n,a，表示共有n个骰子，骰子点数总和为a(1≤n≤1000,n≤a≤6∗n)

输出格式
如题。答案对 1e9+7 取余。

样例
input
2
1 2
2 2
output
166666668
27777778

Problem solving:
这道题就是给你骰子的个数，然后给你一个点数，问你那个点数出现的概率。因为涉及到精度所以要用逆元处理。
这道题是个dp。看了学长的标程才做(cv)出来了。

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
const int mod = 1e9+7;
typedef long long ll;
ll dp[maxn][maxn*6];
ll poww(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1)    ans=(ans*x)%mod;
        x=(x*x)%mod;
        y/=2;
    }
    return ans;
}
int main()
{
    int t,n,a;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d %d",&n,&a);
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=6*n;j++)
            {
                for(int k=j-6;k<j;k++)
                {
                    if(k<0)    continue;
                    dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
                }
            }
        }
        printf("%d\n",dp[n][a]*poww(poww(6,n),mod-2)%mod);
    }
}

标程

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
const ll mod=1000000007;
const int maxn=1000+10;
ll dp[maxn][maxn*6];
ll quickpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void solve(){
    int t;
    int n,a;
    scanf("%d",&t);
    while(t--){
        memset(dp,0,sizeof(dp));
        scanf("%d %d",&n,&a);
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=i;j<=6*n;j++){
                for(int k=j-6;k<j;k++){
                    if(k<0) continue;
                    dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
                }
            }
        }
        printf("%lld\n",dp[n][a]*quickpow(quickpow(6,n),mod-2)%mod);
    }
}
int main()
{
    solve();
    return 0;
}

Subsequence

Description:
Steve 和 Alex 喜欢研究字符串，今天他们学到了一个新名词—“Subsequence“。对于字符串 s 和 t 来说，t 被称为 s 的”Subsequence“当且仅当 s 删除若干字母后能得到 t （也可以不删)。

例如：”ab”,”ac”,”bc”都是”abc”的”Subsequence“，而”ba”和”ca”则不是。

现在 Steve 和 Alex 手中各自有一个只由小写字母组成的字符串 s 和 t ，请判断 t 是否是 s 的”Subsequence“。

输入格式
第一行输入一个T,代表数据组数。
接下来输入T组，每组包含两行，第一行输入s，第二行输入t。
(1≤T≤1000,1≤|t|≤|s|≤10000)

输出格式
输出T行，如果t是s的”Subsequence“，输入”YES”,否则输出”NO”。

样例
input
3
abc
ac
abc
ba
abc
a
output
YES
NO
YES

Problem solving:
这道题就是签到题。直接从一开始就暴力查找即可。
个人认为有一点小小的贪心的思想。

Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        string x,y;
        cin>>x>>y;
        int l=x.size(),pos=0;
        for(int i=0;i<l;i++)
        {
            if(x[i]==y[pos])
            {
                pos++;
            }
        }
        if(pos==y.size())
        {
            puts("YES");
        }
        else    puts("NO");
    }
}

标程

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define debug(x) cerr << #x << ' ' << (x) << endl;
using namespace std;

typedef long long ll;
const int MAXN = 1e6 + 7;

int main() {
    int T;
    cin >> T;
    while(T--){
        string s, t;
        cin >> s >> t;
        int n = s.size(), m = t.size();
        int i, j;
        i = j = 0;
        while(i < n && j < m){
            if(s[i] == t[j])    j++;
            i++;            
        }
        if(j == m)  cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

Steve的游戏名

Description:
定义一个字符串s是一步字符串，当 s 满足以下两个条件：
s 中仅包含小写字母。
对于任意的1≤i<|s|满足，s[i]+1=s[i+1]，也就是说，s[i]在英文字母表中的位置的下一位是s[i+1]，特别的，我们认为z的下一位是a，其中|s|表示s的长度。
举个例子：abc、zab 都是一步字符串，而 acd、zbc不是。
Steve 特别喜欢长长的名字，因此他在 Minecraft 中的名字特别特别的长。
Alex 对 Steve 的名字特别感兴趣，她想知道 Steve 的名字中有多少个子串是一步字符串。
形式化来说，对于一个字符串 s，问有多少对 满足 1≤i≤j≤n，且 s[i]...s[j] 是一步字符串。
保证 Steve 在 Minecraft 中的名字仅包含小写英文字母。

输入格式
输入包含多组测试数据。
第一行一个数字 T ，表示测试数据个数。
接下来每两行表示一个测试数据。
第一行一个数字 n 。
第二行一个长度为 n 的字符串 s。
数据范围：1≤T≤100,1≤n≤2e5

输出格式
一个数字表示答案。

样例
input
2
3
abc
3
zab
output
6
6
提示
abc中的一步字符串有a、b、c、ab、bc、abc。
zab中的一步字符串有z、a、b、za、ab、zab。

Problem solving:
这道题也挺简单的，一步字符串就是相邻的字符后面的比前面的a思科(ASCLL)码大1。z看作是a的下一位。
假设我们现在找到了一个长度为n的一步字符串，那么他的所有子串也都是一步字符串，字串个数为(n+1)*n/2。
所以我们只需要暴力查找到每一个最长的一步字符串然后加起来即可。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n,m;
    string s;
    scanf("%lld",&n);
    while(n--)
    {
        scanf("%lld",&m);
        cin>>s;
        ll mid=1,ans=0;
        for(ll i=0;i<m-1;i++)
        {
            if((s[i]-'a'+1)%26==(s[i+1]-'a')%26)
            {
                mid++;
            }
            else
            {
                ans+=(1+mid)*mid/2-mid;
                mid=1;
            }
        }
        if(mid)    ans+=(1+mid)*mid/2-mid;
        ans+=m;
        printf("%lld\n",ans);
    }
}

标程

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
#define debug(x) cerr << #x << ' ' << (x) << endl;
using namespace std;

typedef long long ll;
const int MAXN = 2e5 + 7;

int cnt[MAXN];
int main() {
    int T;
    cin >> T;
    while(T--){
        int n;
        string s;
        cin >> n >> s;
        cnt[n] = n;
        per(i, n-2, 0){
            if(((s[i] - 'a' + 1) % 26 + 'a') == s[i+1]){
                cnt[i+1] = cnt[i+2];
            } else cnt[i+1] = i+1;
        }
        ll res = 0;
        rep(i, 1, n){
            res += 1LL * (cnt[i] - i + 1);
        }
        cout << res << endl;
    }
    return 0;
}

数字串

Description:
给你一个长度为 n 的数字串，找出其中位数不超过15位的不包含前导0和后导0的数 x ,使得 x+f(x) 是一个回文数,其中 f(x) 表示将 x 反转过来的数。

输入格式
多组输入，处理到文件结束,样例保证不超过1000组。
每组第一行一个整数 n ，表示数字串的长度(1≤n≤1000)，
接下来一行输入一个长度为 n 的数字串。

输出格式
第一行一个数 m 表示数字串中符合条件的数的个数(数可以重复)。
第二行从小到大输出 m 个数，每个数字之间以空格隔开。

样例
input
3
123
output
6
1 2 3 12 23 123
提示
1+1=2,
2+2=4,
3+3=6,
12+21=33,
23+32=55,
123+321=444

Problem solving:
神签到题，直接暴力模拟每个串就行。
这里卡到我的地方时不知道怎么遍历字符串的每个子串了。这个确实是我憨批了。
用字符串输入，然后遍历每个子串。转换成整型之后进行判断。
每一步都直接判断就行了。
因为输出时候有要求，所以我们把满足条件的都存进一个数组sort一下输出即可。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4+10;
ll a[maxn];
ll solve(ll x)
{
    ll res=0;
    while(x)
    {
        res=res*10+x%10;
        x/=10;
    }
    return res;
}
int main()
{
    int n;
    string s;
    while(cin>>n)
    {
        cin>>s;
        int pos=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='0')    continue;
            ll mid=0;
            for(int j=0;j<15&&i+j<n;j++)
            {
                mid=mid*10+s[i+j]-'0';
                if(s[i+j]=='0')    continue;
                if(mid+solve(mid)==solve(mid+solve(mid)))
                {
                    a[pos++]=mid;
                }
            }
        }
        sort(a,a+pos);
        cout<<pos<<endl;
        for(int i=0;i<pos;i++)
            cout<<a[i]<<" ";
        puts("");
    }
    return 0;
}

标程

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4+10;
ll a[maxn];
ll solve(ll x)
{
    ll res=0;
    while(x)
    {
        res=res*10+x%10;
        x/=10;
    }
    return res;
}
int main()
{
    int n;
    string s;
    while(cin>>n)
    {
        cin>>s;
        int pos=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='0')    continue;
            ll mid=0;
            for(int j=0;j<15&&i+j<n;j++)
            {
                if(s[i+j]=='0')    continue;
                mid=mid*10+s[i+j]-'0';
                if(mid+solve(mid)==solve(mid+solve(mid)))
                {
                    a[pos++]=mid;
                }
            }
        }
        sort(a,a+pos);
        cout<<pos<<endl;
        for(int i=0;i<pos;i++)
            cout<<a[i]<<" ";
        puts("");
    }
    return 0;
}

Alex的午饭

Description:
Steve 和Alex每天都在为午饭吃什么而发愁，因为吃的东西实在是太多了，而且很多都特别好吃。为了解决吃什么的问题，Alex决定每次吃饭前发布一个问卷调查，让他的好朋友选出他们今天最想吃的食物，然后Alex会根据问卷的结果来确定吃什么

每个问卷只收集一种食物，每个食物都由一个数字num来表示。Alex会选出问卷中出现次数超过问卷总数一半的数字来决定今天的午饭

输入格式
单组输入，每组两行

第一行有一个整数N (1≤N≤2e7)

第二行有N个整数num (num≤1e18)，代表每个问卷中的数字

输出格式
输出一个整数，即出现次数超过N2的数

样例
input
4
1 1 1 2
output
1
input
5
2 2 3 3 3
output
3
提示
保证每组数据一定存在符合条件的数
请注意题目上的内存限制

Problem solving:
这道题我是用map卡过得，但好像正解是一个xxx判断法，

标程

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll a,t;
    cin>>t;
    ll res=0;ll ans;
    for(ll i=0;i<t;i++)
    {
        cin>>a;
        if(!res)
            ans=a;
        if(a==ans)
            res++;
        if(a!=ans)
            res--;
    }
    cout<<ans<<endl;
    return 0;
}

The war land

Description:
Steve 和 Alex 开始玩一款叫做战争大陆的游戏，整个地图由 n 个岛屿和 n−1 条桥梁组成，第 i 个岛屿的战略能力为 wi ，整个地图是联通的。游戏开始 Steve 和 Alex 需要断掉一座桥梁，这样整个地图就被划分为了两个联通的区域 A 和 B 并且 A 和 B 之间无法到达。
为了使游戏尽可能公平，现在他们想让 A 和 B 的战略能力之和的差值的绝对值最小。

输入格式
第一行输入T代表数据组数。
接下来T组，对于每一组：
第一行输入n，接下来n−1行，每行输入两个数字u,v代表u和v之间的岛屿有一座桥梁，最后一行输入n个数，第i个数代表第i个岛屿的战略值wi。
(1≤T≤10,1≤n≤100000,1≤wi≤1e9,1≤u,v≤n)

输出格式
输出T组，对于每组输入，输出最小的差值的绝对值。

样例
input
2
4
1 2
2 3
2 4
2 5 7 3
2
1 2
1 2
output
3
1

Problem solving:
这道题我一开始以为要用类似于背包的处理方式，但是发现不可以。因为你不知道你分开的两堆能不能正好是割一下就能分开的。
还是安生的看学长的图论的方法做吧。
大致的意思就是一次dfs处理出来每个点往下的点的个数。根节点这个可以自己随便选，不影响结果的。假如我们以dis[i]代表i节点下面的所有节点的权值的总和，一次dfs处理完之后。在遍历每个节点，求出从这个点将原图分隔成两部分之后的权值的差值，每次取一次min，最后输出即可。
假设根节点我们找的是1，遍历的每个点用i表示
那么1下面的所有的节点的权值的和就是dis[1]，i下面的就是dis[i]，分开之后的差值就是dis[1]-dis[i]-dis[i]，但是有可能是负的，所以我们还要取一次绝对值

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
typedef long long ll;
ll dis[maxn],w[maxn];
vector<int> ma[maxn];
void dfs(int u,int par)
{
    dis[u]=w[u];
    for(int v=0;v<ma[u].size();v++)
    {
//        cout<<ma[u][v]<<endl;
        if(ma[u][v]==par)    continue;
        dfs(ma[u][v],u);
        dis[u]+=dis[ma[u][v]];
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(dis,0,sizeof(dis));
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)    ma[i].clear();
        int u,v;
        for(int i=1;i<=n-1;i++)
        {
            cin>>u>>v;
            ma[u].push_back(v);
            ma[v].push_back(u);
        }
        for(int i=1;i<=n;i++)    cin>>w[i];
        dfs(1,0);
        long long ans=0x3f3f3f3f3f3f3f3f;
        for(int i=2;i<=n;i++)
        {
            ans=min(ans,abs(dis[1]-2*dis[i]));

        }
        cout<<ans<<endl;
    }
    return 0;
}

标程

#include<bits/stdc++.h>

using namespace std;
const int N = 200001;
long long siz[N],w[N];
vector<int> G[N];
void dfs(int u,int par){
    siz[u]=w[u];
    for(int v:G[u]){
        cout<<v<<endl;
        if(v==par) continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
}
int main(){
    int T;cin>>T;
    while(T--){
        memset(siz,0,sizeof(siz));
        int n;cin>>n;
        for(int i=1;i<=n;i++) G[i].clear();
        int u,v;
        for(int i=1;i<=n-1;i++){
            cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        for(int i=1;i<=n;i++) cin>>w[i];
        dfs(1,0);
        long long ans=999999999999999999;
        for(int i=2;i<=n;i++){
            ans=min(ans,abs(siz[1]-2*siz[i]));
        }
        cout<<ans<<endl;
    }
    return 0;
}

Number throry

Description:
steve 学完了快速幂，现在会他快速的计算：(i^j)%d , Alex 作为一个数学大师，给了 steve 一个问题：已知
i∈[1,n],j∈[1,m] ，计算满足 (i^j)%d=0 的 (i,j) 的对数。

输入格式
T组输入，对于每一组输入三个数n,m,d。
(1≤T≤1000,1≤n,m,d≤1e9)。

输出格式
对于每组输入，输出答案，每个答案占一行。

样例
input
4
3 10 7
3 5 3
10 30 6
100 100 8
output
0
5
30
4937

Problem solving:
这道题很有意思，用到了质因子分解。就是首先我们要知道2的30次方已经是大于1e9得了。
我们对d进行质因子分解。就像这样
d=p1^x1*p2^x2*...*pn^xn
我们要找的i是要满足(i^j)%d等于0的，所以假如说
g=p1^(x1/j)*p2^(x2/j)*...*pn^(xn/j)为i的因子的话，那么i的j次方一定是可以整除d的。
所以这种情况下的满足条件的i跟j的对数就是n/g.
这里还有一个需要我们注意的地方就是指数的地方是需要向上取整的，这是为什么呢？我们举个例子就可以看出来了。

假如现在
d=p1^5*p2^5
j=2
如果我们直接除，不向上取整的话
g=p1^2*p2^2
此时g的j次方就是=p1^4*p2^4
他并不一定%d之后为0
但是我们向上取整的话如果多了是没有影响的，因为在计算多余部分之前已经为0了，你再怎么乘也一直都是0

我们已经说过，但是我们已经说过2的30次方已经是大于1e9得了。所以你可以知道，在m>=30之后的情况每个j算出来的g都是一样的，所以这一部分我们只计算一次就够了，再乘以这个区间的大小m-29就是剩余这一部分所有的满足条件的对数。

因为计算的过程中我们是要计算除法的，所以要求一次逆元。

可以看一下代码注释理解理解

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p[50];
ll poww(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1)    ans*=x;
        x*=x;
        y/=2;
    }
    return ans;
}   //快速幂，为了求逆元
int main()
{
    ll t;ll n,m,d;
    scanf("%d",&t);
    while(t--)
    {
        map<ll,ll> ma;
        scanf("%lld %lld %lld",&n,&m,&d);
        ll pos=1;
        for(ll i=2;i*i<=d;i++)
        {
            if(d%i==0)    ma[i]=0,p[pos++]=i;
            while(d%i==0)
            {
                ma[i]++;
                d/=i;
            }
        }
        ll ans=0;
        if(d>1)    p[pos++]=d,ma[d]=1;   //质因子分解，并且记录一下每个质因子的幂，这里我是用map存的，当然你也可以用别的

//        for(map<ll,ll>::iterator it=ma.begin();it!=ma.end();it++)
//            cout<<it->first<<" "<<it->second<<endl;

        for(ll i=1;i<=min(m,(ll)30);i++)//这个i代表的其实就是刚才解题思路里面的j，这个min处理的这一下很巧妙。
        {
            ll g=1;
            for(ll j=1;j<pos;j++)
            {
                g*=poww(p[j],ceil(ma[p[j]]*1.0/i));
            }
            if(i==30)    ans+=(m-29)*(n/g);
            else    ans+=n/g;//分两种情况
        }
        cout<<ans<<endl;
    }
    return 0;
}

标程

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=(ans*a);
        a=(a*a);
        b>>=1;
    }
    return ans;
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        ll n,m,d;
        scanf("%lld %lld %lld",&n,&m,&d);
        vector<pair<ll,ll> > prs;
        for(ll i=2;i*i<=d;i++){
            if(d%i==0){
                long long cnt=0;
                while(d%i==0){
                    d/=i;cnt++;
                }
                prs.push_back({i,cnt});
            }
        }
        ll res=0;
        if(d!=1) prs.push_back({d,1});
        for(auto v:prs)
            cout<<v.first<<" "<<v.second<<endl;
        for(ll j=1;j<=min(m,1LL*30);j++){
            ll g=1;
            for(auto v:prs){
                g*=qpow(v.first,(v.second+j-1)/j);
            }
            if(j==30) res+=(m-29)*(n/g);
            else res+=n/g;
        }
        printf("%lld\n",res);
    }
    return 0;
}

Steve的难题

Description:
Steve参加了2019年的暑期集训，在集训最后一场积分赛时，Steve英勇AC，提交了几十发全A了。Steve顿时惊叹，这不都是水题吗，于是接下来碰到的问题却难倒了他。求1/(n!)模p意义下的值。

输入格式
多组输入，处理到文件结束。
每行输入两个数n,p,(1≤n≤1e5,n<p≤1e9).
数据保证 p 是个质数。

输出格式
如题

样例
input
3 5
3 7
3 11
output
1
6
2

Problem solving:
这道题就直接暴力的写，求出n的阶乘中的每一个数的逆元乘起来即可。

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
vector<int> vec[maxn];
int step[maxn];
bool vis[maxn];
int n,m;
void bfs(int x)
{
    queue<int> que;
    que.push(x);
    vis[x]=1;step[x]=0;
    while(!que.empty())
    {
        x=que.front();
        que.pop();
        for(int i=0;i<vec[x].size();i++)
        {
            int y=vec[x][i];
            for(int j=0;j<vec[y].size();j++)
            {
                int z=vec[y][j];
                if(vis[z])    continue;
                vis[z]=1;
                step[z]=step[x]+1;
                que.push(z);
                if(z==n)    return ;
            }
         }
    }
}
int main()
{
    cin>>n>>m;
    int u,v;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    bfs(1);
    if(step[n]==0)    puts("-1");
    else    cout<<step[n]<<endl;
    return 0;
}

标程

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=1000000+10;
const int INF=0x3f3f3f3f;
ll niyuan(ll a,ll b,ll p){
    ll res=1;
    if(b<=0) return res;
    while(b){
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
void solve(){
    ll n,p;
    while(~scanf("%lld %lld",&n,&p)){
        ll res=1;
        for(ll i=1;i<=n;i++){
            res=res*niyuan(i,p-2,p)%p;
        }
        printf("%lld\n",res);
    }
}
int main()
{
    solve();
    return 0;
}

Steve's Shortest Path

Description:
Alex 和 Steve 来到了一个神奇的国度，这个国家有 n 个城市和 m 条道路。这 m 条道路都是双向的，而且这个国家的客车有个特点，每辆客车除出发城市和到达城市外有且仅可经过一个城市。

假设u城市到v有一条道路并且 v 到 p 有一条道路,那么客车从 u 出发不能到达 v 但是能到达 p，Steve 和 Alex 在编号为 1 的城市,他们想知道能不能到达编号为 n 的城市，如果能，最少需要坐几次客车？

输入格式
单组输入。
第一行输入 n 和 m 代表城市的个数和路径的条数。
接下来 m 行每行输入两个数 u 和 v 代表 u 到 v 之间有条路。(2≤n,m≤1e6,1≤u,v≤n)。

输出格式
如果 Steve 和 Alex 能够到达终点，输出最少需要坐几次车才能到达，否则输出−1。

样例
input
2 1
1 2
output
-1
input
3 2
1 2
2 3
output
1

Problem solving:
这道题比赛的时候没看懂，现在发现还是很简单的。
题意就是给你一个图，有一个起点，每次只能走两步，问你能否到达终点。！！语文老师的锅！！
直接bfs就行了，每次走两步并且累计上步数，如果最后终点的步数还是你初始化的值，说明无法到达，输出-1即可。繁殖直接输出到达终点的步数。

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
vector<int> vec[maxn];
int step[maxn];
bool vis[maxn];
int n,m;
void bfs(int x)
{
    queue<int> que;
    que.push(x);
    vis[x]=1;step[x]=0;
    while(!que.empty())
    {
        x=que.front();
        que.pop();
        for(int i=0;i<vec[x].size();i++)
        {
            int y=vec[x][i];
            for(int j=0;j<vec[y].size();j++)
            {
                int z=vec[y][j];
                if(vis[z])    continue;
                vis[z]=1;
                step[z]=step[x]+1;
                que.push(z);
                if(z==n)    return ;
            }
         }
    }
}
int main()
{
    cin>>n>>m;
    int u,v;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    bfs(1);
    if(step[n]==0)    puts("-1");
    else    cout<<step[n]<<endl;
    return 0;
}

标程

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
vector<int>vec[maxn];
int step[maxn];
bool vis[maxn];
int n,m;
void bfs(int x){
    queue<int>que;
    que.push(x);
    vis[x]=1;
    step[x]=0;
    while(!que.empty()){
        x=que.front();
        que.pop();
        for(int i=0;i<vec[x].size();i++){
            int y=vec[x][i];
            for(int j=0;j<vec[y].size();j++){
                int z=vec[y][j];
                if(vis[z]) continue;
                vis[z]=1;
                step[z]=step[x]+1;
                que.push(z);
                if(z==n) return ;
            }
        }
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    int u,v;
    for(int i=0;i<m;i++){
        scanf("%d %d",&u,&v);
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    bfs(1);
    if(step[n]==0) printf("-1\n");
    else printf("%d\n",step[n]);
    return 0;
}