sponsored links

牛客寒假算法训练第四场

A题:https://ac.nowcoder.com/acm/contest/330/A
题解:博弈论,此题先手必胜

留坑待补更详细的解释

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100010];
typedef long long ll;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    printf("Applese\n");
    return 0;
}

B题:https://ac.nowcoder.com/acm/contest/330/B

题解:构造题,我觉得对于我的坑点数据是n=1,m>2或者m=1,n>2。没有注意特判

思路和官方题解差不多

牛客寒假算法训练第四场

#include <bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
    scanf("%d %d",&n,&m);
    if(n%2!=0&&m%2!=0){
        printf("-1\n");
    }
    else if((n==1&&m>2)||(m==1&&n>2)){
        printf("-1\n");
    }
    else {
        if(n%2!=0){
            for(int i=0;i<n-1;i++){
                printf("D");
            }
            for(int i=0;i<m-1;i++){
                printf("R");
            }
            for(int i=n-1;i>0;i--){
                printf("U");
            }
            for(int i=m-1-1;i>0;i--){
                printf("L");
                for(int j=0;j<n-2;j++){
                    if(i%2==0){
                        printf("D");
                    }
                    else printf("U");
                }
            }
            printf("L");
            printf("\n");
        }
        else{
            for(int i=0;i<m-1;i++){
                printf("R");
            }
            for(int i=0;i<n-1;i++){
                printf("D");
            }
            for(int i=m-1;i>0;i--){
                printf("L");
            }
            for(int i=n-1-1;i>0;i--){
                printf("U");
                for(int j=0;j<m-1-1;j++){
                    if(i%2==0){
                        printf("R");
                    }
                    else printf("L");
                }
            }
            printf("U");
            printf("\n");
        }
    }
    return 0;
}

C题:https://ac.nowcoder.com/acm/contest/330/C

题解:搜索题,求最短的路径,选择bfs最好。用一个三维数组记录每个点的状态vis[x][y][0/1],代表Applese以火或水属性是否走过点(x,y)。

#include <bits/stdc++.h>
using namespace std;
int n,m;
char maps[110][110];
int vis[110][110][2];
int sx,sy,tx,ty;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct pos
{
    int x,y,step,stute;
};
int bfs(int startx,int starty,int endx,int endy)
{
    queue <pos> q;
    vis[startx][starty][0]=1;
    struct pos t;
    t.x=startx,t.y=starty,t.step=0,t.stute=0;
    q.push(t);
    while(!q.empty()){
        struct pos now,next;
        now=q.front();
        q.pop();
        if(now.x==endx&&now.y==endy){
            return now.step;
        }
        for(int i=0;i<4;i++){
            int x1=now.x+dir[i][0];
            int y11=now.y+dir[i][1];
            int t1=now.step+1;
            int stute1=now.stute;
            if(maps[x1][y11]=='#'||x1>=n||y11>=m||x1<0||y11<0) continue ;
            if(stute1==0&&maps[x1][y11]!='w'&&vis[x1][y11][0]==0){
                vis[x1][y11][0]=1;
                next.x=x1,next.y=y11,next.step=t1,next.stute=stute1;
                q.push(next);
            }
            if(stute1==1&&maps[x1][y11]!='~'&&vis[x1][y11][1]==0){
                vis[x1][y11][1]=1;
                next.x=x1,next.y=y11,next.step=t1,next.stute=stute1;
                q.push(next);
            }
            /*if(maps[x1][y11]=='@'&&vis[x1][y11][stute1]==0){
                next.x=x1,next.y=y11,next.step=t1,next.stute=stute1;
                vis[x1][y11][stute1]=1;
                q.push(next);
            }
            if(maps[x1][y11]=='@'&&vis[x1][y11][stute1^1]==0){
                    next.x=x1,next.y=y11,next.step=t1+1,next.stute=stute1^1;
                    vis[x1][y11][stute1^1]=1;
                    q.push(next);
                }*/ //不能这样写
            if(maps[x1][y11]=='T'){
                return t1;
            }
        }
        if(maps[now.x][now.y]=='@'&&vis[now.x][now.y][now.stute^1]==0){
            next.x=now.x,next.y=now.y,next.step=now.step+1,next.stute=now.stute^1;
            vis[now.x][now.y][now.stute^1]=1;
            q.push(next);
        }
    }
    return -1;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%s",maps[i]);
        for(int j=0;j<m;j++){
            if(maps[i][j]=='S'){
                sx=i,sy=j;
            }
            else if(maps[i][j]=='T'){
                tx=i,ty=j;
            }
        }
    }
    printf("%d\n",bfs(sx,sy,tx,ty));
    return 0;
}

E题:https://ac.nowcoder.com/acm/contest/330/E

题解:因为左右相邻的都不能有相同颜色,明显当每一行的第一个都确定了颜色时,这一行的状态也就确定了,而每一个格子的颜色只有两种选择。所有答案即为牛客寒假算法训练第四场
。因为n的数据大小到了牛客寒假算法训练第四场
,要用欧拉降幂+快速幂。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define N 1000100
#define mod 1e9+7
using namespace std;
char b[N];
char n[N],m[N];
ll p[N];
ll a, c;
ll quick(ll a, ll b){ //快速幂
    ll k = 1;
    while(b){
        if(b%2==1){
            k = k*a;
            k %=c;
        }
        a = a*a%c;
        b /=2;
    }
    return k;
}
void priem(){
    memset(p, 0, sizeof(p));
    ll i, j;
    p[1] = 1;
    for(i=2; i<=sqrt(N); i++){
        for(j=2; j<=N/i; j++)
            p[i*j] = 1;
    }
}
ll ola(ll n){ //欧拉函数
    ll i, j, r, aa;
    r = n;
    aa = n;
    for(i=2; i<=sqrt(n); i++){
        if(!p[i]){
            if(aa%i==0){
                r = r/i*(i-1);
                while(aa%i==0)
                    aa /= i;
            }
        }
    }
    if(aa>1)
        r = r/aa*(aa-1);
    return r;
}
int main(){
        ll d, i, j;
        priem();
        scanf("%s %s",n,m);
        ll l = strlen(n);
        ll B=0;
        c=mod;
        ll oc = ola(c);
        for(i=0; i<l; i++){
            B = B*10+n[i]-'0';
            if(B>oc)
                break;
        }
        if(i==l)
            d = quick(2,B);
        else{
            B=0;
            for(i=0; i<l; i++){
                B = (B*10+n[i]-'0')%oc;
            }
            d = quick(2,B+oc);
        }
        printf("%lld\n",d);

    return 0;
}

还有强大的python解法:

print(pow(2, int(input().split()[0]), 10**9 + 7))

F题:

Applese 有一个QQ群。在这个群中,大家互相请教问题。如 b 向 a 请教过问题,就把 a 叫做是 b 的"老板"。这样一个群中就会有很多老板。
同时规定:如果 a 是 b 的老板,b 是 c 的老板,那么 a 也是 c 的老板。
为了不破坏群里面和谐交流的氛围,Applese 定了一个群规:不允许出现 a 既是 b 的老板, b 又是 a 的老板。
你需要帮助 Applese 判断大家是否遵守了群规。

题解:由题意可知当出现第一个不符合条件的询问出现时,后面所有的都是No。所有可以二分查找到最后一个Yes的位置,通过拓扑排序判断该位置是否符合题意。

#include <bits/stdc++.h>
using namespace std;
int n,m;
struct points
{
    int u,v;
};
struct points G[2000010];
int K=0;
void addedge(int u,int v)
{
    G[++K].u=u;
    G[K].v=v;
}
bool topolo_sort(int m)
{
    vector <int> g[n+10];
    vector<int> indeg(n+10);
    queue <int> q;
    for(int i=1;i<=m;i++){
        g[G[i].u].push_back(G[i].v);
        indeg[G[i].v]++;
    }
    for(int i=1;i<=n;i++){//要把n个点都进行判断后加入,即使他还没有边。
        if(indeg[i]==0){
            q.push(i);
        }
    }
    int cc=0;
    while(!q.empty()){
        int t=q.front();
        q.pop();
        cc++;
        for(int i=0;i<g[t].size();i++){
            indeg[g[t][i]]--;
            if(indeg[g[t][i]]==0){
                q.push(g[t][i]);
            }
        }
    }
    if(cc==n)return true;
    return false;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        addedge(u,v);
    }
    int l=1,r=m;
    int ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(topolo_sort(mid)==false) {
            r=mid-1;
        }
        else{
            l=mid+1;ans=mid;
        }
    }

    for(int i=1;i<=m;i++){
        if(i>ans){
            printf("No\n");
        }
        else {
            printf("Yes\n");
        }
    }
    return 0;
}

G题:

众所周知,Applese 是个很强的选手,它的化学一定很好。
今天他又AK了一套题觉得很无聊,于是想做个毒气炸弹玩。
毒气炸弹需要 k 种不同类型元素构成,Applese一共有 n 瓶含有这些元素的试剂。
已知元素混合遵循 m 条规律,每一条规律都可以用 "x y c" 描述。
表示将第 x 瓶试剂混入第 y 瓶试剂或者把第 y 瓶试剂混入第 x 瓶试剂,需要消耗 c 的脑力。

特别地,除了这 m 条规律外,Applese 可以将任意两瓶相同元素的试剂混合,且不需要消耗脑力。

Applese 想要配出毒气炸弹,就需要使 S 中含有 这 k 种元素。它想知道自己最少花费多少脑力可以把毒气炸弹做出来。

题解:根据题意的m条规律可以构建一个无向图,求该图的一个最小生成树即可,同种元素已经联通。此外,并查集的话要压缩路径。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k;
int a[100010];
const int MAXN=100010;
const int MAXM=100010;
int f[MAXN];
struct Edge{
    int u,v;
    ll w;
}edge[MAXM];
int tol=0;
void addedge(int u,int v,ll w)
{
    edge[tol].u=u;
    edge[tol].v=v;
    edge[tol++].w=w;
}
bool cmp(Edge a,Edge b)
{
    return a.w<b.w;
}
int finds(int a){
    int r=a;
    while(r!=f[r]){
        r=f[r];
    }
    while(a!=f[a]){
        int j=f[a];
        f[a]=r;
        a=j;
    }
    return r;

}
int unions(int x,int y)
{
    int fx=finds(x);int fy=finds(y);
    if(fx==fy){
        return 0;
    }
    else {
        f[fy]=fx;
        return 1;
    }
}
ll ans;
int kruskal(int n)
{
    int res=0;
    sort(edge,edge+tol,cmp);
    for(int i=0;i<tol;i++){
        int u=edge[i].u;
        int v=edge[i].v;
        ll w=edge[i].w;
        if(unions(a[u],a[v])){
            res+=1;
            ans+=w;
        }
        if(res==k-1) break;
    }
    return res;
}
int main ()
{
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<=n;i++){
        f[i]=i;
    }
    int x;int y;ll c;
    for(int i=1;i<=m;i++){
        scanf("%d %d %lld",&x,&y,&c);
        addedge(x,y,c);
    }
    ans=0;
    int t=kruskal(n);
    if(t==k-1){
        printf("%lld\n",ans);
    }
    else {
        printf("-1\n");
    }
    return 0;
}

H题:

Applese 和它的小伙伴参加了一个促销的抽奖活动,活动的规则如下:有一个随机数生成器,能等概率生成 之间的整数,每个参与活动的人都要通过它获取一个随机数。最后得到数字最小的 k 个人可以获得大奖。如果有相同的数,那么后选随机数的人中奖。
Applese 自然是最心急的一个,它会抢在第一个去按随机数。请你帮忙计算一下它能够中奖的概率。

题解:组合数,概率题。枚举小于等于Applese的数的个数,并把每次的概率加上即为答案。牛客寒假算法训练第四场
p为随机的数不大于app的数的概率,q=1-p。

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
typedef long long ll;
typedef long long LL;
LL binarypow(LL a,LL b,LL m) {
    LL ans=1;
    while(b>0){
        if(b&1){
            ans=ans*a%m;
        }
        a=a*a%m;
        b>>=1;
    }
    return ans;
}
ll n;
int k,x;
int main()
{
    cin>>n>>k>>x;
    ll p=1ll*(x+1)*binarypow(100,mod-2,mod)%mod;
    ll q=1ll*(99-x)*binarypow(100,mod-2,mod)%mod;
    ll c=1;ll ans=0;
    for(int i=0;i<k;i++){
        ans+=((c*binarypow(p,i,mod)%mod)*binarypow(q,n-i-1,mod)%mod);
        ans%=mod;
        c=(c*(n-i-1)%mod)*(binarypow(i+1,mod-2,mod)%mod);
        c%=mod;
    }
    cout<<ans%mod<<endl;
    return 0;
}

J题:https://ac.nowcoder.com/acm/contest/330/J

签到题就不说了,用公式就好了

#include <bits/stdc++.h>
using namespace std;
#define eps 1e-6
#define pi 3.1415926
int main()
{
    double ans,f1,f2;
    int a;
    scanf("%lf %lf %d",&f1,&f2,&a);
    ans=f1*f1+f2*f2+2*f1*f2*cos(a*pi/180);
    ans=sqrt(ans);
    printf("%lf\n",ans);
    return 0;
}
Tags: