大一大二省赛热身赛（2019.5.9训练）

本次训练共8题，本文附AC代码和题目链接（本篇文章题目按从难到易排序）

D题 nefu 1840 隧道

#include <bits/stdc++.h>
using namespace std;
char a[60][60];
int n,r1,c1,r2,c2,ans,cnt1,cnt2,cost,newx,newy,vis[60][60];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct node
{
    int x,y;
}p1[60],p2[60];
void dfs1(int x,int y)//从起点开始搜索，用p1记录能走到的位置
{
    vis[x][y]=1;
    p1[++cnt1].x=x;
    p1[cnt1].y=y;
    if(x==r2&&y==c2)return;
    for(int i=0;i<4;i++)
    {
        newx=x+dir[i][0];
        newy=y+dir[i][1];
        if(newx>=1&&newx<=n&&newy>=1&&newy<=n&&vis[newx][newy]==0&&a[newx][newy]=='0')
            dfs1(newx,newy);
    }
}
void dfs2(int x,int y)//从终点开始搜索，用p2记录能走到的位置
{
    vis[x][y]=1;
    p2[++cnt2].x=x;
    p2[cnt2].y=y;
    for(int i=0;i<4;i++)
    {
        newx=x+dir[i][0];
        newy=y+dir[i][1];
        if(newx>=1&&newx<=n&&newy>=1&&newy<=n&&vis[newx][newy]==0&&a[newx][newy]=='0')
            dfs2(newx,newy);
    }
}
int main()
{
    cin>>n>>r1>>c1>>r2>>c2;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    dfs1(r1,c1);//从起点搜索
    if(vis[r2][c2]==1){printf("0\n");return 0;}//如果从起点开始搜索能到终点，则不必建隧道，花费为0
    dfs2(r2,c2);//从终点搜索
    ans=0x3f3f3f3f;
    for(int i=1;i<=cnt1;i++)
        for(int j=1;j<=cnt2;j++)//遍历从起点开始能走到的全部位置和从终点开始能走到的全部位置，找最小花费
        {
            cost=(p1[i].x-p2[j].x)*(p1[i].x-p2[j].x)+(p1[i].y-p2[j].y)*(p1[i].y-p2[j].y);
            ans=min(ans,cost);
        }
    printf("%d\n",ans);
    return 0;
}

F题 nefu 1842 恐龙的故事

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+1000;//这里的N要开大一点，比1e6大1000才行，开1e6+10会错！
int t,m,cnt,cnt1,prime[N],pre[N];
bool flag[N];
void get_prime()
{
    memset(flag,1,sizeof(flag));
    flag[1]=0;
    for(int i=2;i<=N;i++)
    {
        if(flag[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]*i<=N;j++)
        {
            flag[prime[j]*i]=0;
            if(i%prime[j]==0)break;
        }
    }
    for(int i=1;i<=N;i++)
    {
        if(flag[i]&&flag[prime[i]])
            pre[++cnt1]=prime[i];
    }
}
int main()
{
    get_prime();
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>m;
        for(int i=1;i<=cnt1;i++)
        {
            if(pre[i]>=m)
            {printf("%d\n",pre[i]);break;}
        }
    }
    return 0;
}

B题 nefu 1838 闹钟

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,x,mn,ans,a[300010],b[300010];
ll gcd(ll a,ll b)
{return b?gcd(b,a%b):a;}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>a[1];
    for(ll i=2;i<=n;i++)
    {
        cin>>a[i];
        b[i-1]=a[i]-a[i-1];
    }
    for(ll i=2;i<=n-1;i++)
        b[i]=gcd(b[i],b[i-1]);
    mn=b[n-1];//mn代表最大公约数
    for(ll i=1;i<=m;i++)
    {
        cin>>x;
        if(mn%x==0){ans=i;printf("YES\n");break;}
    }
    ans==0?printf("NO\n"):printf("%lld\n",ans);
    return 0;
}

C题 nefu 1839 减法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,sum,l,a[1000010];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(ll i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    l=unique(a+1,a+n+1)-(a+1);
    for(ll i=1;i<=k;i++)
    {
        a[i]=a[i]-sum;
        sum=sum+a[i];
        if(i>l)printf("0\n");
        else printf("%lld\n",a[i]);
    }
    return 0;
}

E题 nefu 1841 尖括号

#include <bits/stdc++.h>
using namespace std;
char a[150];
int t,n,x1,x2,ans;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        x1=x2=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]=='>')break;
            else x1++;
        }
        for(int i=n;i>=1;i--)
        {
            if(a[i]=='<')break;
            else x2++;
        }
        ans=min(x1,x2);
        printf("%d\n",ans);
    }
    return 0;
}

A题 nefu 1837 哪些数不在

#include <bits/stdc++.h>
using namespace std;
int n,m,l,r,cnt,vis[150],ans[150];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>l>>r;
        for(int j=l;j<=r;j++)
            vis[j]=1;
    }
    for(int i=1;i<=m;i++)
    {
        if(vis[i]==0)
        ans[++cnt]=i;
    }
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++)
    i==cnt?printf("%d\n",ans[i]):printf("%d ",ans[i]);
    return 0;
}

H题 nefu 1844 巧克力

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,a,b,c,s,ans,k1,k2;
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>s>>a>>b>>c;
        k1=s/c;//k1表示最多可购买的数量
        k2=k1/a;//k2表示最多可买多少个a个
        ans=k1+k2*b;
        printf("%lld\n",ans);
    }
    return 0;
}