NEU winter_training 2

之前教练让我写这个的题解
顺便复制过来水一发博客

7-1 到底有多二

题解

数字位数很长,于是把数字以字符串的形式读进来,数2的个数,再额外特判是否负数和偶数。

代码

#include<iostream>
#include<cstdio>
#include<ctype.h>
using namespace std;
string s;
double ans;
int main(){
    cin>>s;
    int len=s.size();
    for(int i=0;i<len;++i){
        if(isdigit(s[i]) && s[i]=='2')ans+=1;
    }
    if(s[0]=='-')ans=ans*1.5/(len-1);
    else ans/=len;
    if(s[len-1]%2==0)ans*=2;
    printf("%.2f%%",ans*100);
    return 0;
}

7-2 大笨钟

题解

读懂题然后根据题意分类讨论即可。

12:00及之前都是不敲钟的,非整点的时候会比整点多敲一下钟。

代码

#include<iostream>
#include<cstdio>
using namespace std;

int h,m;
int main(){
    scanf("%d:%d",&h,&m);
    if(h<12 || h==12 && m==0)printf("Only %02d:%02d.  Too early to Dang.",h,m);
    else {
        if(m)for(int i=13;i<=h+1;++i)printf("Dang");
        else for(int i=13;i<=h;++i)printf("Dang");
    }
    return 0;
}

7-3 谁先倒

题解

依旧是根据题意模拟,记录两个人喝酒的杯数,其中一个超过上限时结束循环。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
int a,b,A,B,n;
using namespace std;
int main(){
    scanf("%d%d%d",&A,&B,&n);
    for(int i=1;i<=n;++i){
        int x,y,z,w;
        scanf("%d%d%d%d",&x,&y,&z,&w);
        if(x+z==y && x+z!=w)++a;
        if(x+z!=y && x+z==w)++b;
        if(a>A){printf("A\n%d",b);break;}
        if(b>B){printf("B\n%d",a);break;}
    }
    return 0;
} 

7-4 帅到没朋友

题解

比起前边的题,是个稍微大了一点的模拟……

存储每个朋友圈去重后的人数(siz),以及每个人属于哪几个朋友圈(bel)

然后对于每个查询的人(注意去重),检查这个人所在的朋友圈及人数来确定他是否太帅

代码

#include<cstdio>
#include<algorithm>
using namespace std;

const int N=101;
const int ID=100000;
int n,m,a[1001];
int cnt[ID],bel[ID][N],siz[N];
bool ask[10001],handsome;
int ans[ID],cntans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int k;scanf("%d",&k);
        for(int j=1;j<=k;++j)
        scanf("%d",&a[j]);
        sort(a+1,a+k+1);
        unique(a+1,a+k+1);//去重 
        for(int j=1;j<=k;++j){
            bel[ a[j] ][ ++cnt[a[j]] ]=i;//a[j]属于朋友圈i,cnt记录这个人属于几个朋友圈
            ++siz[i];//该朋友圈的人数
        }
    }
    scanf("%d",&m);
    for(int i=1;i<=m;++i){
        int pos;scanf("%d",&pos);
        if(ask[pos]==1)continue;//查询多次只输出一次
        ask[pos]=1;
        bool ishandsome=1;//这个人是否有朋友
        for(int i=1;i<=cnt[pos];++i){
            if(siz[ bel[pos][i] ]>1)ishandsome=0;
        }
        if(ishandsome){
            ans[++cntans]=pos;
            handsome=1;//是否有人太帅
        }
    }
    if(!handsome)printf("No one is handsome");
    else{
        for(int i=1;i<=cntans;++i){
            printf("%05d",ans[i]);
            if(i<cntans)printf(" ");
        }
    }   
    return 0;
}

7-5 重要的话说三遍

题解

\I‘m gonna WIN!/ \I‘m gonna WIN!/ \I‘m gonna WIN!/

……这个我实在不知道该写点什么好qwq。

代码

#include<cstdio>

int main(){
    printf("I'm gonna WIN!\n");
    printf("I'm gonna WIN!\n");
    printf("I'm gonna WIN!");
    return 0;
}

7-6 奇偶分家

题解

%2为0则为偶数,为1则为奇数。

代码

#include<stdio.h>

int n,odd,eve;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int x;scanf("%d",&x);
        if(x%2)++odd;
        else ++eve; 
    }
    printf("%d %d",odd,eve);
    return 0;
}

7-7 输出GPLT

题解

用四个变量分别计G、P、L、T的个数,再按规定顺序循环输出即可。

代码

#include<stdio.h>
#include<string.h>

char s[10009]; 
int g,p,l,t;
int main(){
    scanf("%s",s);
    g=p=l=t=0;
    int len=strlen(s);
    for(int i=0;i<len;++i){
        if(s[i]>='a' && s[i]<='z')s[i]-='a'-'A';
        if(s[i]=='G')++g;
        if(s[i]=='P')++p;
        if(s[i]=='L')++l;
        if(s[i]=='T')++t;
    }
    while(g+p+l+t){
        if(g){--g;printf("G");}
        if(p){--p;printf("P");}
        if(l){--l;printf("L");}
        if(t){--t;printf("T");}
    }
    printf("\n");
    return 0;
}

7-8 后天

题解

七天一循环可以通过%7来实现

不过条件是星期要用0~6来表示

可以通过-1再+1达到这个效果

代码

#include<stdio.h>

int main(){
    int d;scanf("%d",&d);
    d=((d+2)-1)%7+1;
    printf("%d\n",d);
    return 0;
}

7-9 抢红包

题解

又是一道模拟

对于每个红包,抢的人加钱数,发的人减钱数

排序按照三个条件依次排

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
const int N=10001;
using namespace std;
struct node{
    int id,money,cnt;
    bool operator < (const node& b) const {
        if(money!=b.money)return money>b.money;//钱数优先
        else if(cnt!=b.cnt)return cnt>b.cnt;//红包数第二
        else return id<b.id;//还相等的看id
        
    } 
}per[N];
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;++i){
        per[i].id=i;
        int k;scanf("%d",&k);
        for(int j=1;j<=k;++j){
            int p,m;scanf("%d%d",&p,&m);
            ++per[p].cnt;
            per[p].money+=m;//抢红包的
            per[i].money-=m;//发红包的
        }
    }
    sort(per+1,per+n+1);
    for(int i=1;i<=n;++i){
        printf("%d %.2lf",per[i].id,(double)per[i].money/100);
        if(i<n)printf("\n");
    }
    return 0;
}

7-10 排座位

题解

用了两个邻接矩阵存储宾客之间的关系

一个类似floyd的三重循环扩散朋友关系(若ik是朋友,kj是朋友,那么ij也是朋友)

代码

#include<iostream>
#include<cstdio>
#include<ctype.h>
using namespace std;
bool suki[101][101],kirai[101][101];
int n,m,K;
int main(){
    scanf("%d%d%d",&n,&m,&K);
    for(int i=1;i<=m;++i){
        int a,b,f;scanf("%d%d%d",&a,&b,&f);
        if(f==1)suki[a][b]=suki[b][a]=1;//朋友关系
        else kirai[a][b]=kirai[b][a]=1;//敌人关系
    }
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    for(int k=1;k<=n;++k)
        suki[i][j]|=suki[i][k]&suki[k][j];//扩散朋友关系
    for(int i=1;i<=K;++i){
        int a,b;scanf("%d%d",&a,&b);
        if( suki[a][b] && !kirai[a][b])printf("No problem");
        if(!suki[a][b] && !kirai[a][b])printf("OK");
        if( suki[a][b] &&  kirai[a][b])printf("OK but...");
        if(!suki[a][b] &&  kirai[a][b])printf("No way");
        if(i<K)printf("\n");
    }
    return 0;
}

7-11 玩转二叉树

题解

根据前序遍历和中序遍历求树的结构的部分和第一场中的7-10 树的遍历 相似,区别在于后序遍历根在最后,前序遍历根在最前
按层序输出部分依旧采用BFS
将树镜面翻转的部分,可以存树的时候反着存,也可以输出的时候反着输出

代码

#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
const int N=301;
int n,pre[N],in[N];//前序遍历和中序遍历
int root,ls[N],rs[N];
int work(int lp,int rp,int li,int ri){//前序遍历和中序遍历的边界
    if(li==ri)return in[ri];
    int rt=pre[lp];//这棵子树的根
    int k=li;while(in[k]!=rt)++k;//找到它在中序遍历中的位置
    int lenl=k-li;
    if(li<k)ls[rt]=work(lp+1,lp+lenl,li,k-1);
    if(k<ri)rs[rt]=work(lp+1+lenl,rp,k+1,ri);
    return rt;
}
queue<int>q;
void print(){//BFS输出层序遍历
    while(!q.empty()){
        int x=q.front();q.pop();
        printf("%d",x);
        if(rs[x])q.push(rs[x]);//先输出右子树
        if(ls[x])q.push(ls[x]);//再输出左子树
        if(!q.empty())printf(" ");
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&in[i]);//中序遍历
    for(int i=1;i<=n;++i)scanf("%d",&pre[i]);//前序遍历
    root=work(1,n,1,n);
    q.push(root);
    print();
    return 0;
}

7-12 关于堆的判断

题解

一道堆的模板题。

依次把每个数插到末尾,逐层向上调整维护之类的堆的基本操作就不再赘述了

用了一个map(M)记录每个数在堆里的位置

以及这个题的读入比较麻烦需要注意

代码

#include<iostream> 
#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<map>
using namespace std;
const int N=1009;
int x,y,n,m,h[N],heap_size;
string s;
map<int,int>M;//每个数在堆里的位置
void insert(int k,int val){//堆的插入操作
    while(k>1 && h[k/2]>h[k]){
        swap(M[h[k]],M[h[k/2]]);
        swap(h[k],h[k/2]);
        k/=2;
    }
}
int poi;
inline int qread(){//从命题里读取数字
    int an=0,f=1;
    while(s[poi]<'0'||s[poi]>'9'){if(s[poi]=='-')f=-1;++poi;}
    while(s[poi]<='9'&&s[poi]>='0'){an=an*10+(s[poi]^48);++poi;}
    return an*f;
}
int judge(){//判断命题类型
    int len=s.size();
    for(int i=0;i<len;++i){
        if(s[i]=='b')return 2;
        if(s[i]=='p')return 3;
        if(s[i]=='c')return 4;
    }
    return 1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&h[i]);
        M[h[i]]=++heap_size;
        insert(i,h[i]);
    }
    getchar();
    for(int i=1;i<=m;++i){
        getline(cin,s);
        int flag=judge();
        poi=0;x=qread();if(flag>1)y=qread();
        x=M[x],y=M[y];
        switch(flag){
            case 1://为根
                if(x==1)printf("T");
                else printf("F");
                break;
            case 2://为兄弟节点
                if(x/2==y/2)printf("T");//父节点相同
                else printf("F");
                break;
            case 3:
                if(y/2==x)printf("T");
                else printf("F");
                break;
            case 4:
                if(x/2==y)printf("T");
                else printf("F");
                break;
        }
        if(i<m)printf("\n");
    }
    return 0;
}

7-13 天梯地图

题解

一道最短路题。

每条边有两个权值,按两个权值分别跑最短路,spfa或者dijkstra都可以(dijkstra更长)

注意同时间到达取最短,同距离取节点最少,两个条件不一样

fa数组用来存储路径中每个点的上一个结点,跑完最短路后从终点反向搜一遍得出路径

特判两条路径相等的情况

以及因为这道题的点标号是0~n-1,在输入输出的部分做了点手脚让它变成1~n

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=509;
int n,m,s,t;
int p[N],cnt;
struct edge{int to,nex,dis,tim;}e[N*N<<1];
void add(int u,int v,int dis,int tim){
    e[++cnt]=(edge){v,p[u],dis,tim};
    p[u]=cnt; 
}
int dis[N],tim[N],fa1[N],fa2[N];
int ans1[N],cnt1,ans2[N],cnt2;
bool in[N];
queue<int>q; 
inline int spfa1(int s)//最快
{
    memset(dis,0x3f,sizeof(dis));//距离
    memset(tim,0x3f,sizeof(tim));//时间
    memset(in,0,sizeof(in));
    q.push(s);tim[s]=dis[s]=0;in[s]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();in[x]=0;
        for(int i=p[x];i;i=e[i].nex)
        {
            int v=e[i].to;
            if(tim[v]==tim[x]+e[i].tim && dis[v]>dis[x]+e[i].dis){//相同时间取最短
                dis[v]=dis[x]+e[i].dis;
                fa1[v]=x;
                if(!in[v]){in[v]=1;q.push(v);}
            }
            if(tim[v]>tim[x]+e[i].tim)
            {
                tim[v]=tim[x]+e[i].tim;
                dis[v]=dis[x]+e[i].dis;
                fa1[v]=x;
                if(!in[v]){in[v]=1;q.push(v);}
            }
        }
    }
    return tim[t];
}
inline int spfa2(int s)//最短
{
    memset(dis,0x3f,sizeof(dis));//距离
    memset(tim,0x3f,sizeof(tim));//节点数(废数组利用系列)
    memset(in,0,sizeof(in));
    q.push(s);tim[s]=dis[s]=0;in[s]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();in[x]=0;
        for(int i=p[x];i;i=e[i].nex)
        {
            int v=e[i].to;
            if(dis[v]==dis[x]+e[i].dis && tim[v]>tim[x]+1){//相同距离取节点最少
                tim[v]=tim[x]+1;
                fa2[v]=x;
                if(!in[v]){in[v]=1;q.push(v);}
            }
            if(dis[v]>dis[x]+e[i].dis)
            {
                tim[v]=tim[x]+1;
                dis[v]=dis[x]+e[i].dis;
                fa2[v]=x;
                if(!in[v]){in[v]=1;q.push(v);}
            }
        }
    }
    return dis[t];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v,type,val1,val2;
        scanf("%d%d%d%d%d",&u,&v,&type,&val1,&val2);
        add(u+1,v+1,val1,val2);if(!type)add(v+1,u+1,val1,val2);
    }
    scanf("%d%d",&s,&t);++s,++t;
    ans1[0]=spfa1(s);//最少的时间
    for(int x=t;x;x=fa1[x])ans1[++cnt1]=x-1;
    ans2[0]=spfa2(s);//最短的距离
    for(int x=t;x;x=fa2[x])ans2[++cnt2]=x-1;
    bool eq=1;//两路径是否相同
    if(cnt1!=cnt2)eq=0;
    for(int i=1;eq && i<=cnt1;++i)if(ans1[i]!=ans2[i])eq=0;
    if(eq){
        printf("Time = %d; Distance = %d: ",ans1[0],ans2[0]);
        for(int i=cnt1;i;--i){printf("%d",ans1[i]);if(i>1)printf(" => ");}
    }
    else{
        printf("Time = %d: ",ans1[0]);
        for(int i=cnt1;i;--i){printf("%d",ans1[i]);if(i>1)printf(" => ");}
        printf("\n");
        printf("Distance = %d: ",ans2[0]);
        for(int i=cnt2;i;--i){printf("%d",ans2[i]);if(i>1)printf(" => ");}
    }
    return 0;
} 

7-14 喊山

题解

BFS。

因为每两个山头距离为1,于是对于每个查询的山头,从该山头出发向四周BFS即可。

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=100001;
struct edge{int to,nex;}e[N<<2];
int p[N],cnt;
void add(int u,int v){
    e[++cnt]=(edge){v,p[u]};
    p[u]=cnt;
}
struct node{
    int id,dis;
};
int n,m,k,ans,maxdis;
queue<node>q;
int dis[N];
void bfs(int s){
    memset(dis,0,sizeof(dis));
    while(!q.empty())q.pop();
    ans=0;maxdis=1;dis[s]=1;
    q.push((node){s,1});
    while(!q.empty()){
        node cur=q.front();q.pop();
        int u=cur.id;
        if(dis[u]==maxdis)ans=min(ans,u);//距离相同取编号最小
        if(dis[u]>maxdis)maxdis=dis[u],ans=u;
        for(int i=p[u];i;i=e[i].nex){
            int v=e[i].to;if(dis[v])continue;
            dis[v]=dis[u]+1;
            q.push((node){v,dis[v]});
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;++i){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    for(int i=1;i<=k;++i){
        int s;scanf("%d",&s);
        bfs(s);
        printf("%d",ans);
        if(i<k)printf("\n");
    }
    return 0;
} 

?

?

?

NEU winter_training 2

上一篇:WPF之UniformGrid使用小记


下一篇:C# RichTextBox实现背景透明