程序设计week2

复习

第二周上课首先将第一周赛题的代码进行了评析，我的码力过弱，有几个点是要注意的

• 在读入结束时，有的时候不会给文件的总数，所以要利用EOF来结束循环。
  eg:while(scanf("%d",&a)!=EOF)
  或者是int a; while(cin>>a)
• 全局变量开在main函数里就可以
• 英文a+b此类需要对读入数据进行转换的题目，可以利用常量数组（显然我没有活学活用= =）

char  a[10][10]={"zero","one","two"..."nine"};
int change(string str)
{
   for(int i=0;i<10;i++)
   {
   	if(a[i])==str)
   		return i;
   }
}

作业

1.maze

题目链接https://vjudge.net/contest/359307#problem/A
题目描述：
地图0表示可以走，1表示不可以走，左上角是入口，右下角是出口，输入是一个5 × 5的二维数组，仅由0、1两数字组成，表示法阵地图。输出若干行，表示从左上角到右下角的最短路径依次经过的坐标，格式如样例所示。数据保证有唯一解。
思路：
从左上角开始利用bfs将可以走且未到达过的点放入队列中。由于最后要输出路径，所以每个点记录其父节点。一开始做的时候是从起点往终点走，但是起点的父节点不太好写，当时也没想到用递归QAQ，于是选择从终点向起点走。

#include<string.h>
#include <stdio.h>
#include <queue>
using namespace std;
int visit[6][6];//标记该点是否到达过
struct point
{
    int x,y;
};

point parent[6][6];//标记其父节点，用于递归出全部路径

//利用常量数组来找到其四邻域，代码更为简洁
int dx[]={+1, -1, 0, 0}, 
    dy[]={0, 0, +1, -1};

void bfs(int sx, int sy, int tx, int ty)
{
    queue<point> Q;
    point s;
    s.x=sx;
    s.y=sy;
    parent[s.x][s.y]=s;
    Q.push(s);
    visit[sx][sy]=0;
    while(!Q.empty())
    {
        point a=Q.front();
        Q.pop();
        visit[a.x][a.y]=1;
        //对终点进行特判
        if(a.x==tx&&a.y==ty)
            break;
        //若未达到时将其四邻域放入队列
        for(int i=0;i<4;i++)
        {
        	point b;
            b.x=a.x+dx[i];
            b.y=a.y+dy[i];
            if((b.x>=0&&b.x<=4)&&(b.y>=0&&b.y<=4)&&visit[b.x][b.y]!=-2&&visit[b.x][b.y]==-1)
            {
                Q.push(b);
                parent[b.x][b.y]=a;//记录其父节点
            }
        }
    }
}

int main()
{
	//对数组进行清零
    memset(visit,0,sizeof(visit));
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
        {
            scanf("%d",&visit[i][j]);
            if(visit[i][j]==0) visit[i][j]=-1;
            else visit[i][j]=-2;
        }
    //从终点向前走，便于处理(0,0)的父节点的值。
    bfs(4,4,0,0);
	point a;
	a.x=0;
	a.y=0;
    printf("(0, 0)\n");
    while(a.x!=4||a.y!=4)
        {
            a=parent[a.x][a.y];
            printf("(%d, %d)\n",a.x,a.y);
        }
    return 0;
} 
/*0 1 0 0 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 0
0 1 0 1 0*/

2.Pour Water

链接https://vjudge.net/contest/359307#problem/B
思路：
可以将倒水问题抽离为从一个状态转变为另一个状态，就与迷宫问题有些相似，即为隐式图问题。可以同样利用bfs，只是状态变化从四邻域变为六个：fill A、B, empty A,B，pour A B, pour B A;结构体中利用mark变量来记录最终选择的倒水方式，最后进行递归输出。

#include <stdio.h>
#include <queue>
#include <map>

using namespace std;
struct Status
{
	int a,b;
	int mark;
	bool operator<(const Status &s) const
	{
		return a!=s.a? a<s.a:b<s.b; 
		}	
};

queue<Status> Q;
map<Status,Status> from;

void refresh(Status &s,Status &t)
{
	if(from.find(t)==from.end())
	{
		from[t]=s;
		Q.push(t);
	}
}

void print(Status &p)
{//此处的编码一定要和下面对应好QAQ
//可能还是很啰嗦。。欢迎指正
	if(from.find(p)==from.end()||(p.a==0&&p.b==0))
	{
	if(p.mark==1)
	{
		printf("empty A\n");
		return;
	}
	if (p.mark==2)
	{
		printf("empty B\n");
		return;
	}
	if(p.mark==3)
	{
		printf("fill A\n");
		return;
	}
	if (p.mark==5)
	{
		printf("fill B\n");	
		return;
	}
	if(p.mark==4)
	{
		printf("pour B A\n");
		return;
	}
	if (p.mark==6)
	{
		printf("pour A B\n");		
		return;
	}
	}
	print(from[p]);
	if(p.mark==1)
		printf("empty A\n");
	if (p.mark==2)
		printf("empty B\n");
	if(p.mark==3)
		printf("fill A\n");
	if (p.mark==5)
		printf("fill B\n");	
	if(p.mark==4)
		printf("pour B A\n");
	if (p.mark==6)
		printf("pour A B\n");
}

void bfs(int A,int B,int C)
{
	Status s,t;
	s.a=s.b=s.mark=0;
	Q.push(s);
	
	while(!Q.empty())
	{
		s=Q.front();
		Q.pop();
		if(s.a==C||s.b==C)
		{
			print(s);
			return;
		}
		//倒空a的水 
		if(s.a>0)
		{
			t.a=0;
			t.b=s.b;
			s.mark=1;
			refresh(s,t);
		}
		//empty B
		if(s.b>0)
		{
			t.b=0;
			t.a=s.a;
			s.mark=2;
			refresh(s,t);
		}
		//full A
		if(s.a<A)
		{
			t.a=A;
			t.b=s.b;
			s.mark=3;
			refresh(s,t);
			
			//B2A
			if(s.b!=0)
			{
				if(s.a+s.b<=A)
				{
					t.a=s.a+s.b;
					t.b=0;
					s.mark=4;
					refresh(s,t);
				}
				else 
				{
					t.a=A;
					t.b=s.a+s.b-A;
					s.mark=4;
					refresh(s,t);	
				}
			}
		}
		
		//full B
		if(s.b<B)
		{
			t.a=s.a;
			t.b=B;
			s.mark=5;
			refresh(s,t);
			
			//A2B
			if(s.a!=0)
			{
				if(s.a+s.b<=B)
				{
					t.a=0;
					t.b=s.a+s.b;
					s.mark=6;
					refresh(s,t);
				}
				else 
				{
					t.a=s.a+s.b-B;
					t.b=B;
					s.mark=6;
					refresh(s,t);
				}
			}
		}
	}
}

int main()
{
	int a,b,c;
	while(~scanf("%d%d%d",&a,&b,&c))
	{
		from.clear();
		while(!Q.empty()) Q.pop();
		bfs(a,b,c);
		printf("success\n");
	}
	return 0;
}
/*2 7 5
2 7 4*/

实验

本次的实验是三道模拟题，很能锻炼码力，然鹅orz
有的题目卡在了很小的点上，相信积累成多以后能尽量避免

1.化学

题目描述：
https://vjudge.net/contest/359340#problem/A

思路：
观察与每个碳相连的c的个数，如果有一个c的个数为4则为第五类，若个数为3的c的个数为2个则为第四类，没有个数大于2的c的则为第一类。第二类和第三类长得较为相似，均有一个个数为3的c，所以利用其相连c的相连个数进行判断。如果相连c有两个都相连两个c则为第三类，反之则为第二类。编号任意！
ps：这道题一开始因为没有在循环中初始化好所有的变量调了好久，吃亏吃亏

#include <stdio.h>
#include <string.h>
using namespace std;

int key[10];//记录相连c的个数
int num[10][10];//将所有的碳键记录在二维数组中
int connect[10];//记录与该c相连的c的编号
int two[10];//记录下相连数位2的c的编号

int main()
{
	int T=0;
	scanf("%d",&T);
	while(T--)
	{
		//一定要将变量先全部初始化，每次循环初始一次
		int tmp1=0,tmp2=0;
		int num3=0,num4=0;
		int now=0;
		memset(key,0,sizeof(key));
		memset(num,0,sizeof(num));
		memset(connect,0,sizeof(connect));
		memset(two,0,sizeof(two)); 
		for(int i=0;i<5;i++)
		{
			scanf("%d %d",&tmp1,&tmp2);
			key[tmp1]++;
			key[tmp2]++;
			num[tmp1][tmp2]++;
		}
		
		for(int i=1;i<=6;i++)
		{
			if(key[i]==2)
				two[i]=1;
			if(key[i]==3) 
			{
				num3++;
				connect[i]=i;
			}
			if(key[i]==4) num4++;
		}
		for(int i=1;i<=6;i++)
		{
			if(connect[i]!=0)
			{
				for(int j=1;j<=6;j++)
				{
					if((num[j][i]!=0||num[i][j]!=0)&&two[j]!=0)
					{
						now++;
					}
				}
			}			
		} 
		if(num3==0&&num4==0&&now==0)
		{
			printf("n-hexane\n"); 
			continue;
		}
		if(num3==1&&now==2)
		{
			printf("3-methylpentane\n");
			continue;
		}
		if(num3==2)
		{
			printf("2,3-dimethylbutane\n");
			continue;
		}
		if(num4==1)
		{
			printf("2,2-dimethylbutane\n");
			continue;
		}
		else printf("2-methylpentane\n");
	}
 } 
 /* 2
    1 2
    2 3
    3 4
    4 5
    5 6
    1 4
    2 3
    3 4
    4 5
    5 6*/

2.B - 爆零(×)大力出奇迹(√)

链接https://vjudge.net/contest/359340#problem/B
题目描述：
AC数目和总时长（结构体排序）
思路
对每个人进行遍历，遇到正数且没有括号则AC数+1，加该时间；若有括号，则AC+1，时间加该时间和罚时。若为负数或0则均不变。

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

using namespace std;

struct node
{
	char name[20];
	int ac;
	int time;
	bool operator<(const node &p) const
	{
		if(ac!=p.ac) return ac>p.ac;
		if(time!=p.time) return time<p.time;
		int w=strcmp(name,p.name);
		if(w==-1) return true;
		else return false; 
	}
}person[100000];

int main()
{
	int n,m=0;
	int num=0;
	int a,b=0;
	scanf("%d %d",&n,&m);
	while(scanf("%s",person[num].name)!=EOF)
	{
		person[num].ac=0;
		person[num].time=0;
		for (int i=1;i<=n;i++)
		{
			if(scanf("%d(%d)",&a,&b)==2)
			//网上找到的小技巧，因为scanf返回值是读取元素的个数
			{
				person[num].ac++;
				person[num].time+=(a+b*m);
			}
			else if(a>0)
			{
				person[num].ac++;
				person[num].time+=a;
			}
		}
		num++;
	}
	
	sort(person,person+num);
	for(int i=0;i<num;i++)
		printf("%-10s %2d %4d\n",person[i].name,person[i].ac,person[i].time);
	
	return 0;
 } 

C - 瑞神打牌

链接https://vjudge.net/contest/359340#problem/C
题目描述：
按顺序发牌，对花色和数字进行排序，将每个人的牌进行输出。发牌员先发给自己顺时针的下一个人。（梅花）<（方片）<（黑桃）<（红桃），（输入时，我们用C,D,S,H分别表示梅花，方片，黑桃，红桃，即其单词首字母）。对于牌面的值，我们规定2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < T < J < Q < K < A。
思路：
首先一个点是将数据读入，由于一组数据是由两行给出的，cin处理起来可能会更加方便。在码的时候将字符转换为数字便于排序（一定注意原来的char型数字也要转化为intQAQ调了好久没看出来这个错误），然后是发牌顺序，如果发牌的为N，则将首个元素存在E的数组中，然后依次循环。最后再按格式进行输出。

#include<stdio.h>
#include<iostream>
#include <algorithm>
using namespace std;

struct P
{
	char a;//花色 
	char b;//数字 
	int c;
	int d;
	bool operator<(const P &p) const
	{
		if(c!=p.c) return c<p.c;
		if(d!=p.d) return d<p.d;
		else return false;
	}
 }card[4][13];

//这里可以优化为常量数组
int flo2num(struct P m)
{
	switch (m.a)
	{
		case 'H': 
			return 4;
			break;
		case 'S': 
			return 3;
			break;
		case 'D': 
			return 2;
			break;
		case 'C': 
			return 1;
			break;
	}	
} 

int num2num(struct P m)
{
	switch(m.b)
	{
		case 'T':
			return 10;
			break;
		case 'J':
			return 11;
			break;
		case 'Q':
			return 12;
			break;
		case 'K':
			return 13;
			break;
		case 'A':
			return 14;
			break; 
	}
}

int main()
{
    //freopen("1.txt","r",stdin);
	char F=0;
	int first=0;
	cin>>F;
	while(F!='#')
	{
		if(F=='N') first=3;
		else if(F=='E') first=0;
		else if(F=='S') first=1;
		else first=2;
		
		for(int i=0;i<13;i++)
			for(int j=0;j<4;j++)
			{
				cin>>card[(j+first)%4][i].a>>card[(j+first)%4][i].b;
				card[(j+first)%4][i].c=flo2num(card[(j+first)%4][i]);
				card[(j+first)%4][i].d=num2num(card[(j+first)%4][i]);
			}
				
		for(int i=0;i<4;i++)
			sort(card[i],card[i]+13);
			
		for(int i=0;i<4;i++)
		{
			if(i==0) printf("South ");
			else if (i==1) printf("West ");
			else if (i==2) printf("North ");
			else printf("East ");
			
			printf("player:\n"); 
			
			for(int k=0;k<13;k++)
				printf("+---");
			printf("+\n");
			
			for(int k=0;k<13;k++)
			{
				printf("|%c %c",card[i][k].b,card[i][k].b);
			}
			printf("|\n");
			
			for(int k=0;k<13;k++)
			{
				printf("| %c ",card[i][k].a,card[i][k].a);
			}
			printf("|\n");
			
			for(int k=0;k<13;k++)
			{
				printf("|%c %c",card[i][k].b,card[i][k].b);
			}
			printf("|\n");
			
			for(int k=0;k<13;k++)
				printf("+---");
			printf("+\n");
		}
		cin>>F;
		if(F!='#') printf("\n");
	}
	return 0;
}
/*N
CTCAH8CJD4C6D9SQC7S5HAD2HJH9CKD3H6D6D7H3HQH4C5DKHKS9
SJDTS3S7S4C4CQHTSAH2D8DJSTSKS2H5D5DQDAH7C9S8C8S6C2C3
#*/

本周总结

调代码用了比较多的时间，有的代码是简单有思路，但是写出来的很丑orz。因为没有掌握更多简便的方法对代码进行优化，导致代码过于啰嗦冗长。争取不断改进。课上实验只交上了第一个（还因为初始化耽误了很久）。本周实验遇到了很多小错误，但是看不太出来。。浪费了很多时间，现在要做的就是多多吸取教训多多练习，希望能够进步。