2019内蒙古大学省赛选拔赛题解

发布于 2019-04-09  27 次阅读


有两题没做出来的没写= =

问题 A: Maze Problem

题目

题目描述

Given a maze, find a shortest path from start to goal.

输入

Input consists serveral test cases.

First line of the input contains number of test case T.

For each test case the first line contains two integers N , M ( 1 <= N, M <= 100 ).

Each of the following N lines contain M characters. Each character means a cell of the map.

Here is the definition for chracter.

Constraint:

For a character in the map:
'S' : start cell
'E' : goal cell
'-' : empty cell
'#' : obstacle cell
no two start cell exists.
no two goal cell exists.

输出

For each test case print one line containing shortest path. If there exists no path from start to goal, print -1.

样例输入

1
5 5
S-###
-----
##---
E#---
---##

样例输出

9

提示

four directions

题解

最基础的找最短路径的题目,广搜即可

#include<iostream>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
int n,m,t;
int sx,sy,ex,ey;
char maze[105][105];
int d[105][105];
struct Point{int x,y;};
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        memset(d,-1,sizeof(d));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                cin>>maze[i][j];
                if(maze[i][j]=='S')
                {
                    sx=i;sy=j;
                    maze[i][j]='#';
                }else if(maze[i][j]=='E')
                {
                    ex=i;ey=j;
                    maze[i][j]='-';
                }
                 
            }
        }
        Point s;
        s.x=sx;
        s.y=sy;
        queue<Point> q;
        q.push(s);
        d[sx][sy]=0;
        int dx[]={-1,0,1,0};
        int dy[]={0,1,0,-1};
        while(!q.empty())
        {
            Point p=q.front();
            q.pop();
            for(int i=0;i<4;i++)
            {
                int nx=p.x+dx[i];
                int ny=p.y+dy[i];
                if(nx>=0&&nx<n&&ny>=0&&ny<m&&maze[nx][ny]=='-'&&d[nx][ny]==-1)
                {
                    Point s;
                    s.x=nx;
                    s.y=ny;
                    d[nx][ny]=d[p.x][p.y]+1;
                    q.push(s);
                }
            }
        }
        cout<<d[ex][ey]<<endl;
    }
}

问题 B: 迷瘴

题目

题目描述

小明正在玩游戏,他控制的角色正面临着幽谷的考验——
幽谷周围瘴气弥漫,静的可怕,隐约可见地上堆满了骷髅。由于此处长年不见天日,导致空气中布满了毒素,一旦吸入体内,便会全身溃烂而死。
幸好小明早有防备,提前备好了解药材料(各种浓度的万能药水)。现在只需按照配置成不同比例的浓度。
现已知小明随身携带有n种浓度的万能药水,体积V都相同,浓度则分别为Pi%。并且知道,针对当时幽谷的瘴气情况,只需选择部分或者全部的万能药水,然后配置出浓度不大于 W%的药水即可解毒。
现在的问题是:如何配置此药,能得到最大体积的当前可用的解药呢?
特别说明:由于幽谷内设备的限制,只允许把一种已有的药全部混入另一种之中(即:不能出现对一种药只取它的一部分这样的操作)。

输入

输入数据的第一行是一个整数C,表示测试数据的组数;
每组测试数据包含2行,首先一行给出三个正整数n,V,W(1<=n,V,W<=100);
接着一行是n个整数,表示n种药水的浓度Pi%(1<=Pi<=100)。

输出

对于每组测试数据,请输出一个整数和一个浮点数;
其中整数表示解药的最大体积,浮点数表示解药的浓度(四舍五入保留2位小数);
如果不能配出满足要求的的解药,则请输出0 0.00。

样例输入

2
1 35 68
1 
2 79 25
59 63 

样例输出

35 0.01
0 0.00

题解

贪心,优先选择浓度小的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int c,n,v,w;
int p[105];
int main()
{
    scanf("%d",&c);
    while(c--)
    {
        scanf("%d %d %d",&n,&v,&w);
        for(int i=0;i<n;i++)scanf("%d",&p[i]);
        sort(p,p+n);
        int cnt=0;
        int total=0;
        for(int i=0;i<n;i++)
        {
            total+=p[i];
            if(total>w*(i+1)){
                total-=p[i];
                break;
            }
            cnt++;
        }
        printf("%d %.2f\n",cnt*v,cnt==0?0.0:total*1.0/cnt/100);
    }
}

问题 C: 寻找最小的素数

题目

题目描述

题目很简单,输出比n大的最小的素数

输入

正整数n,n<10^20

输出

比n大的最小素数

样例输入

1

样例输出

2

题解

import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
     
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        BigInteger bigInteger=cin.nextBigInteger();
        System.out.println(bigInteger.nextProbablePrime());
         
    }
}

问题 D: 一笔画问题

题目

题目描述

Tom从小就比较喜欢玩一些小游戏,其中就包括画一笔画,他想请你帮他写一个程序,判断一个图是否能够用一笔画下来。

规定,所有的边都只能画一次,不能重复画。

输入

第一行只有一个正整数N(N<=10)表示测试数据的组数。
每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<=2000),分别表示这个画中有多少个顶点和多少条连线。(点的编号从1到P)
随后的Q行,每行有两个正整数A,B(0<A,B<P),表示编号为A和B的两点之间有连线。

输出

如果存在符合条件的连线,则输出"Yes",
如果不存在符合条件的连线,输出"No"。

样例输入

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

样例输出

No
Yes

题解

首先要判断连通,在连通的基础上再判断是否只有两个或没有奇度点.判断连通可以用并查集或者深搜,此处用的并查集

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,p,q;
int fa[1005],rnk[1005];
int degree[1005];
void init()
{
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;rnk[i]=0;
    }
}
int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
void uni(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(rnk[x]<rnk[y])
    {
        fa[x]=y;
    }else{
        fa[y]=x;
        if(rnk[x]==rnk[y])rnk[x]++;
    }
}
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        int a,b;
        memset(degree,0,sizeof(degree));
        scanf("%d %d",&p,&q);
        init();
        for(int i=0;i<q;i++)
        {
            scanf("%d %d",&a,&b);
            uni(a,b);
            degree[a]++;
            degree[b]++;
        }
        int flag=true;
        int fafa=find(1);
        for(int i=2;i<=p;i++)
        {
            if(fa[i]!=fafa)
            {
                flag=false;
                break;
            }
        }
        int cnt=0;
        for(int i=1;i<=p;i++)
        {
            if(degree[i]&1)cnt++;
        }
        if(flag&&(cnt==0||cnt==2))
        {
            cout<<"Yes\n";
        }else
        {
            cout<<"No\n";
        }
    }
}

问题 E: 最长公共子序列

题目

题目描述

例子:
最长公共子序列(LongestCommon Subsequence, LCS)
输入序列“ABCDGH”和“AEDFHR” 的LCS是“ADH”长度为3。
输入序列“AGGTAB”和“GXTXAYB”的LCS是“GTAB”长度为4。

样例输入

ABCDGH AEDFHR

样例输出

ADH

题解

动规入门题,

a[i-1]!=b[j-1]时,dp[i][j]=max(dp[i-1][j],dp[i][j-1])

a[i-1]==b[j-1]时,dp[i][j=dp[i-1][j-1]+1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int dp[1005][1005];
string ans[1005][1005];
int main()
{
    string a,b;
    cin>>a>>b;
    int len1=a.length(),len2=b.length();
    for(int i=1;i<=len1;i++)
    {
        for(int j=1;j<=len2;j++)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
                ans[i][j]=ans[i-1][j-1]+a[i-1];
                //cout<<"==="<<ans[i][j]<<" "<<ans[i-1][j-1]<<endl;
            }
            else if(dp[i-1][j]>dp[i][j-1])
            {
                dp[i][j]=dp[i-1][j];
                ans[i][j]=ans[i-1][j];
            }else if(dp[i-1][j]<=dp[i][j-1])
            {
                dp[i][j]=dp[i][j-1];
                ans[i][j]=ans[i][j-1];
            }
        }
    }
    cout<<ans[len1][len2];
}

问题 G: 星球大战

题目

题目描述

很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的
机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直
接或间接地连接。 但好景不长,很快帝国又重新造出了他的超级武器。凭借这超级武器的力量,帝国开始有计划
地摧毁反抗军占领的星球。由于星球的不断被摧毁,两个星球之间的通讯通道也开始不可靠起来。现在,反抗军首
领交给你一个任务:给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序,以尽量快的速度求出每
一次打击之后反抗军占据的星球的连通快的个数。(如果两个星球可以通过现存的以太通道直接或间接地连通,则
这两个星球在同一个连通块中)。

输入

输入文件第一行包含两个整数,N (1  < =  N  < =  2M) 和M (1  < =  M  < =  200,000),分别表示星球的
数目和以太隧道的数目。星球用 0 ~ N-1的整数编号。接下来的M行,每行包括两个整数X, Y,其中(0 < = X <> 
Y 表示星球x和星球y之间有“以太”隧道,可以直接通讯。接下来的一行为一个整数k,表示将遭受攻击的星球的
数目。接下来的k行,每行有一个整数,按照顺序列出了帝国军的攻击目标。这k个数互不相同,且都在0到n-1的范
围内。

输出

第一行是开始时星球的连通块个数。接下来的K行,每行一个整数,表示经过该次打击后现存星球
的连通块个数。

样例输入

8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7

样例输出

1
1
1
2
3
3

题解

并查集+离线,先将信息都存下来,然后逆向使用并查集

注意需要首先判断最后有几个连通块,判断连通时注意判断该星球是否被摧毁

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;
int n;
int fa[400005],rnk[400005];
int lt=0;
int m,k,destroyed[400005];
stack<int> target;
vector<int> has_edge[400005];
vector<int> ans;
void init()
{
    for(int i=0;i<n;i++)
    {
        fa[i]=i;rnk[i]=0;
    }
}
int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
void uni(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(rnk[x]<rnk[y])
    {
        fa[x]=y;
    }else{
        fa[y]=x;
        if(rnk[x]==rnk[y])rnk[x]++;
    }
    lt--;
}
void add(int x)
{
    int len=has_edge[x].size();
    for(int i=0;i<len;i++)
    {
        if(!destroyed[has_edge[x][i]]) uni(x,has_edge[x][i]);
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    init();
    int x,y;
    for(int i=0;i<m;i++)
    {
        scanf("%d %d",&x,&y);
        has_edge[x].push_back(y);
        has_edge[y].push_back(x);
    }
    scanf("%d",&k);
    int t;
    for(int i=0;i<k;i++)
    {
        scanf("%d",&t);
        target.push(t);
        destroyed[t]=1;
    }
    for(int i=0;i<n;i++)
    {
        if(!destroyed[i]){
            lt++;
            add(i);
        }
    }
    ans.push_back(lt);
    while(!target.empty())
    {
        int t=target.top();
        target.pop();
        lt++;
        add(t);
        ans.push_back(lt);
    }
    for(int i=ans.size()-1;i>=0;i--)
    {
        cout<<ans[i]<<endl;
    }
}

问题 H: 邮票面值设计

题目

题目描述

给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+K≤40)种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大值MAX,使在1~MAX之间的每一个邮资值都能得到。

例如,N=3,K=2,如果面值分别为1分、4分,则在1分~6分之间的每一个邮资值都能得到(当然还有8分、9分和12分);如果面值分别为1分、3分,则在1分~7分之间的每一个邮资值都能得到。可以验证当N=3,K=2时,7分就是可以得到的连续的邮资最大值,所以MAX=7,面值分别为1分、3分。 

输入

每个测试文件只包含一组测试数据,每组输入两个整数N和K(N+K≤40)。

输出

对于每组输入数据,第一行输出每种邮票的面值,面值之间由一个空格分隔,最后一个面值的后面不要输出空格。第二行输出连续最大能到的面值数,具体格式见样例输出。数据保证答案唯一。

样例输入

3 2

样例输出

1 3
MAX=7

题解

首先k张邮票,第一张面值肯定为1分,后一张面值至少比前一张面值大1,至多为前一张面值的n倍+1,可以根据这个范围进行深搜,然后判断邮票组合的邮资最大值.

判断最大值可以使用动规,dp[i]表示邮资为i分时需要的邮票张数,则dp[i]=min(dp[i],dp[i-value[j]]+1) 0<=j<k且i-value[j]>=0

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
using namespace std;
int value[45],k,n;
int dp[1000000];
int ma;
vector<int> ans;
void solve()
{
    dp[0]=0;
    dp[1]=1;
    for(int i=2;;i++)
    {
        dp[i]=0x3f3f3f;
        for(int j=0;j<k;j++)
        {
            if(i-value[j]>=0)dp[i]=min(dp[i],dp[i-value[j]]+1);
        }
        if(dp[i]>n){
            if(i-1>ma)
            {
                ma=i-1;
                ans.clear();
                for(int i=0;i<k;i++)
                {
                    ans.push_back(value[i]);
                }
            }
            break;
        }
    }
}
void dfs(int cur)
{
    if(cur==k)
    {
        solve();
        return;
    }
    for(int i=value[cur-1]+1;i<=value[cur-1]*n+1;i++)
    {
        value[cur]=i;
        dfs(cur+1);
    }
}
int main()
{
    cin>>n>>k;
    value[0]=1;
    dfs(1);
    for(int i=0;i<ans.size();i++)
    {
        if(i!=0)printf(" ");
        printf("%d",ans[i]);
    }
    printf("\nMAX=%d\n",ma);
}