本次新生赛部分题解

A poj1129

这题的愿意是考察四色原理(不是太难,主要是了解),但是模拟+暴力枚举也是可以过的,有几个WA点,注意看注释

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main()
{
    int n,i,j,k;
    while(cin>>n && n)
    {
        bool map[50][50];
        memset(map,false,sizeof(map));
        char ch[1000];
        getchar();
        for(i=1;i<=n;i++)
        {
            gets(ch);
            for(j=2;j<strlen(ch);j++)
                map[i][ch[j]-'A'+1]=true;
        }
        int visit[27];
        int color[27];
        memset(visit,0,sizeof(visit));
        memset(color,0,sizeof(color));
        int maxlen=0;
        for(i=1;i<=n;i++)
        {
            memset(visit,0,sizeof(visit));
            for(j=1;j<=n;j++)
                if(map[i][j])
                    if(color[j])
                        visit[color[j]]=1;
            for(j=1;j<=26;j++)
            if(!visit[j])
            {
                color[i]=j;
                if(j>maxlen)
                maxlen=j;
                break;
            }
            if(j==4)break;//这里用到四色原理剪枝
        }
        if(maxlen==1)
            printf("1 channel needed.\n");//注意单复数和结尾的点
        else
            printf("%d channels needed.\n",maxlen);
    }
    return 0;
}

B 最小运输代价

floyd路径记录,按字典序记录,比裸floyd要难一点,WA点很多

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int map[505][505];//数据范围没给,就写了一般最大的情况
int path[505][505];
int cost[505];
int main()
{
    while(cin>>n && n)//多组数据
    {
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&map[i][j]);
            if(map[i][j]==-1)
            map[i][j]=0xfffffff;
            path[i][j]=j;
        }
        for(int i=1;i<=n;i++)
        scanf("%d",&cost[i]);
        for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
                if(map[i][k]+map[k][j]+cost[k]<map[i][j])
                {
                    map[i][j]=map[i][k]+map[k][j]+cost[k];
                    path[i][j]=path[i][k];
                }
                else
                if(map[i][k]+map[k][j]+cost[k]==map[i][j])
                {
                    if(path[i][j]>path[i][k])
                        path[i][j]=path[i][k];
                }
        }
        int a,b;
        while(~scanf("%d%d",&a,&b))
        {
            if(a==-1 && b==-1)
            break;
            printf("From %d to %d :\n",a,b);
            printf("Path: %d",a);
            int temp=a;
            while(temp!=b)
            {
                printf("-->%d",path[temp][b]);
                temp=path[temp][b];
            }
            printf("\n");
            printf("Total cost : %d\n\n",map[a][b]);//回城符
        }
    }
    return 0;
}

D 南邮oj1076机器狗组装

贪心每次选最小的两个合并,但是如果每次结束都排序会超时,可以想到最小堆维护的代价为logn,于是就可以在nlogn的时间里解决,stl为我们提供了现成的堆数据结构——优先队列

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct cmp
{
    bool operator()(int a,int b)
    {
        return a>b;
    }
};
int main()
{
    priority_queue<int,vector<int>,cmp> q;
    int n,sum=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int temp;
        scanf("%d",&temp);
        q.push(temp);
    }
    for(int i=1;i<n;i++)
    {
        int temp1=q.top();
        q.pop();
        int temp2=q.top();
        q.pop();
        q.push(temp1+temp2);
        sum+=(temp1+temp2);
        //cout<<sum<<endl;
    }
    cout<<sum<<endl;
    return 0;
}

E HDU1253

胜利大逃亡,比较裸的BFS,不会的同学可以借这道题学习一下,但是注意如果写的不是太好,提交选G++会超时

我也是超了好几次,改用c++就过了

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
int map[50][50][50];
bool vis[50][50][50];
int a,b,c,t;
typedef struct s
{
	int x;
	int y;
	int z;
	int step;
}qu;
int go(int x,int y,int z)  
{  
    if(0<=x&&x<a&&0<=y&&y<b&&0<=z&&z<c&&map[x][y][z]==0)  
    return 1;  
    return 0;  
}  
int dir[6][3]={{1,0,0},{-1,0,0},{0,0,1},{0,0,-1},{0,1,0},{0,-1,0}};
int main()
{
	int ti;
	scanf("%d",&ti);
	while(ti--)
	{
		int flag=0;
		scanf("%d%d%d%d",&a,&b,&c,&t);
		int i,j,k;
		memset(vis,false,sizeof(vis));
		for(i=0;i<a;i++)
		for(j=0;j<b;j++)
		for(k=0;k<c;k++)
		scanf("%d",&map[i][j][k]);
		qu temp1,temp2;
		queue<qu> q;
		temp1.x=0;
		temp1.y=0;
		temp1.z=0;
		temp1.step=0;
		vis[temp1.x][temp1.y][temp1.z]=true;
		q.push(temp1);
		while(!q.empty())
		{
			temp1=q.front();
			if(temp1.step>t)
			{
				break;
			}
			q.pop();
			if(temp1.x==a-1 && temp1.y== b-1 && temp1.z==c-1)
			{
				cout<<temp1.step<<endl;
				flag=1;
				break;
			}
			else
			{
				for(i=0;i<6;i++)
				{
					temp2.x=temp1.x+dir[i][0];
					temp2.y=temp1.y+dir[i][1];
					temp2.z=temp1.z+dir[i][2];
					temp2.step=temp1.step+1;
					if(go(temp2.x,temp2.y,temp2.z) && !vis[temp2.x][temp2.y][temp2.z])
					{
						vis[temp2.x][temp2.y][temp2.z]=true;
						q.push(temp2);
					}
				}
			}
		}
		if(!flag)
			cout<<"-1"<<endl;
	}
	return 0;
}

f超级楼梯

递推dp[i]=dp[i-1]+dp[i-2]

I福州大学月赛题 文件系统

小模拟,考察代码基本功和细心程度,注意细节不会有太大问题

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef struct user
{
    char name[12];
    int groupnum;
    char group[105][12];
}user;
typedef struct file
{
    char name[12];
    char quan[5];
    char owner[12];
    char group[12];
}file;
int main()
{
    int t;
   // freopen("in.txt","r",stdin);
    cin>>t;
    while(t--)
    {
		user u[105];
		file f[105];
		int map[105][105];
        int n,m;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%s%d",&u[i].name,&u[i].groupnum);
            for(int j=0;j<u[i].groupnum;j++)
            scanf("%s",&u[i].group[j]);
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%s%s%s%s",f[i].name,f[i].quan,f[i].owner,f[i].group);
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(strcmp(u[i].name,f[j].owner)==0)
                map[i][j]=(f[j].quan[0]-'0');
                else
                {
					bool flag=false;
                    for(int k=0;k<u[i].groupnum;k++)
                    {
                        if(strcmp(u[i].group[k],f[j].group)==0)
                        {
                            map[i][j]=f[j].quan[1]-'0';
							flag=true;
                            break;
                        }
                    }
                    if(!flag)
                    map[i][j]=f[j].quan[2]-'0';
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m-1;j++)
            printf("%d ",map[i][j]);
            printf("%d\n",map[i][m-1]);
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之树的子结构(九度OJ1520)

题目描述: 输入两颗二叉树A,B,判断B是不是A的子结构。 输入: 输入可能包含多个测试样例,输入以EOF结束。 对于每个测试案例,输入的第一行一个整数n,m(...

204100
来自专栏技术博文

php pathinfo()的用法

pathinfo — 返回文件路径的信息  mixed pathinfo ( string $path [, int $options = PATHINFO_D...

41770
来自专栏小樱的经验随笔

hihoCoder #1082 : 然而沼跃鱼早就看穿了一切(字符串处理)

#1082 : 然而沼跃鱼早就看穿了一切 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 ? fjxmlhx每天都在被沼跃鱼刷屏,因...

29550
来自专栏安恒网络空间安全讲武堂

hacklu CTF 2018 Baby PHP

过file_get_contents()用到了php伪协议。https://www.lorexxar.cn/2016/09/14/php-wei/。只要通过ph...

27320
来自专栏生信技能树

R for Data Science(十二)

一直觉得编程能力好的人都会写函数,我对R语言写函数能力比较差,就学了这一章节,拆分如何写函数以及为什么写函数 例如我们看一下这个代码

14320
来自专栏灯塔大数据

每周学点大数据 | No.28 表排序

No.28期 表排序 Mr. 王:前面我们讨论了一些基础磁盘算法,现在我们来讨论一些关于磁盘中图算法的问题。 通过对基础磁盘算法的学习,我们可以很容易地想到...

34370
来自专栏深度学习那些事儿

探讨pytorch中nn.Module与nn.autograd.Function的backward()函数

本文讲解基于pytorch0.4.0版本,如不清楚版本信息请看这里。backward()在pytorch中是一个经常出现的函数,我们一般会在更新loss的时候使...

2K50
来自专栏深度学习之tensorflow实战篇

把一个矩阵行优先展成一个向量,numpy.ravel() vs numpy.flatten()区别

首先声明两者所要实现的功能是一致的(将多维数组降位一维),两者的区别在于返回拷贝(copy)还是返回视图(view),numpy.flatten()返回一份拷贝...

35660
来自专栏深度学习那些事儿

探讨pytorch中nn.Module与nn.autograd.Function的backward()函数

本文讲解基于pytorch0.4.0版本,如不清楚版本信息请看这里。backward()在pytorch中是一个经常出现的函数,我们一般会在更新loss的时候使...

30040
来自专栏Android相关

散列表(Hash Table)

散列表是一种以平均O(1)时间插入、删除和查找的数据结构,可是类似于findMax,findMin等操作则需要以O(N)的时间才能完成

18730

扫码关注云+社区

领取腾讯云代金券