五月赛题解

Dimly_dust · 2020-04-18 17:24:33 · 个人记录

T1 Crossing River

就是一道贪心题，在前面基础上加了个小数罢了。

#include<bits/stdc++.h>
using namespace std;
int a[101][101],endx,endy,lujing=0,minlu=1e10,n;
int dx[4]= {0,-1,0,1};
int dy[4]= {1,0,-1,0};
void dfs(int x,int y,int lu)
{
    if(x==endx&&y==endy)
    {
        lujing++;
        if(lu<minlu)minlu=lu;
        return;
    }
    for(int i=0; i<4; i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx>=1&&yy<=n&&yy>=1&&xx<=n&&a[xx][yy]==0)
        {
            a[xx][yy]=1;
            lu++;
            dfs(xx,yy,lu);
            a[xx][yy]=0;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);

    cin>>n;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            cin>>a[i][j];
            if(a[i][j]==3)
            {
                endx=i;
                endy=j;
                a[i][j]=0;
            }
        }
    }
    dfs(1,1,0);
    if(lujing==0)
    {
        cout<<"No,way!"<<endl;
        return 0;
    }
    cout<<lujing<<endl;
    cout<<minlu-1<<endl;
    return 0;
}

T2 简单迷宫

又是一道简单的水题，DFS

#include<bits/stdc++.h>
using namespace std;
int a[101][101],endx,endy,lujing=0,minlu=1e10,n;
int dx[4]= {0,-1,0,1};
int dy[4]= {1,0,-1,0};
void dfs(int x,int y,int lu)
{
    if(x==endx&&y==endy)
    {
        lujing++;
        if(lu<minlu)minlu=lu;
        return;
    }
    for(int i=0; i<4; i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx>=1&&yy<=n&&yy>=1&&xx<=n&&a[xx][yy]==0)
        {
            a[xx][yy]=1;
            lu++;
            dfs(xx,yy,lu);
            a[xx][yy]=0;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);

    cin>>n;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            cin>>a[i][j];
            if(a[i][j]==3)
            {
                endx=i;
                endy=j;
                a[i][j]=0;
            }
        }
    }
    dfs(1,1,0);
    if(lujing==0)
    {
        cout<<"No,way!"<<endl;
        return 0;
    }
    cout<<lujing<<endl;
    cout<<minlu-1<<endl;
    return 0;
}

T3 乌拉尔银狼

本题是一道简单哒快速幂qwq

就是要小心数据范围qwq

所以开ULL就可以了qwq

琪露诺：我是幻想乡最强哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈啊哈哈哈哈哈哈哈哈哈哈哈

所以就很简单啦qwq

#include<bits/stdc++.h>
using namespace std;
unsigned long long b,p,ans;
int k;
int f(int p)
{
    if(p==0) return 1;
    else
    {
        int tmp=f(p/2)%k;
        tmp=(tmp*tmp)%k;
        if(p%2==1) tmp=(tmp*b)%k;
        return tmp;
    }
}
int main()
{

    //cin>>b>>p>>k;
        cin>>b;
        cin>>p;
        cin>>k;
        b%=k;
        ans=1;
        if(p!=0) cout<<f(p);
        else  cout<<0;
        return 0;
}

以及原题解：This

T4 毒瘤蒟蒻树

此题由 【战略游戏】转变而来。

算法：树状DP

双倍经验： P2016 战略游戏

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
vector<int>G[1505];
int n,m,f[1505][5];
void dfs(int x,int fa)
{
    f[x][0]=1;
    for(int i=0;i<G[x].size();i++)
    {
        if(G[x][i]==fa)
            continue;
        dfs(G[x][i],x);
        f[x][0]+=min(f[G[x][i]][0],f[G[x][i]][1]);
        f[x][1]+=f[G[x][i]][0];
    }
}
int main()
{
    scanf("%d",&n);
    int a,b,c;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&b);
        for(int j=1;j<=b;j++)
        {
            scanf("%d",&c);
            G[a].push_back(c);
            G[c].push_back(a);
        }
    }
    dfs(0,-1);
    printf("%d",min(f[0][0],f[0][1]));
}