本次新生赛部分题解
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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014-06-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读