PTA数据结构11——15_某天,诺诺有许多活动需要参加。但由于活动太多,诺诺无法参加全部活动。请帮诺诺安

7-11 最少失约

某天，诺诺有许多活动需要参加。但由于活动太多，诺诺无法参加全部活动。请帮诺诺安排，以便尽可能多地参加活动，减少失约的次数。假设：在某一活动结束的瞬间就可以立即参加另一个活动。

输入格式:

首先输入一个整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据首先输入一个正整数n，代表当天需要参加的活动总数，接着输入n行，每行包含两个整数i和j（0≤i<j<24），分别代表一个活动的起止时间。

输出格式:

对于每组测试，在一行上输出最少的失约总数。

输入样例:

1
5
1 4
3 5
3 8
5 9
12 14

输出样例:

2

#include<stdio.h>
//结构体
struct ss{ 
    int a;
    int b;
}p[];
//结构体
//冒泡排序 
void bubble(struct ss arr[], int len)
{
 
	for (int i = 0; i < len - 1; i++)//9趟
	{
		int flag = 0;
		for (int j = 0; j < len - 1 - i; j++)//比较9次
		{
			if (arr[j].b>arr[j + 1].b)
			{
				flag = 1;
                  
				int temp = arr[j].a;
				arr[j].a = arr[j + 1].a;
				arr[j + 1].a = temp;
                
                temp = arr[j].b;
				arr[j].b = arr[j + 1].b;
				arr[j + 1].b = temp;
			}
		}
		if (!flag)
			break;
	}
}
//冒泡排序
 
int main()
{
    int T, n;
    scanf("%d",&T);//输入测试组数
    
    for(int w = 0; w < T; w ++)
    {
        scanf("%d",&n);//输入n组测试数据
        for(int j = 0; j < n; j ++){
            scanf("%d %d",&(p[j].a), &(p[j].b) );//活动起止时间
        }
        bubble(p,n);//引用冒泡排序
        
        int j = 0;
        int count = 1;//因为第一个默认是直接参加
        for(int i = 1; i < n; i ++){
            if(p[i].a >= p[j].b){
                j = i;
                count ++;
            }
        }
 
        printf("%d\n",n-count);
    }
}

7-12 n皇后问题

要求在n*n格的棋盘上放置彼此不会相互攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

输入格式:

测试数据有多组，处理到文件尾。对于每组测试，输入棋盘的大小n（1<n<12）。

输出格式:

对于每组测试，输出满足要求的方案个数。

输入样例:

4

输出样例:

2

#include<stdio.h>
#include<string.h>
#define N 30
int col[N],dg[N],udg[N];
int n,ans;
 
void dfs(int u)
{
	int i=0;
	if(u==n)
	{
		ans++;
		return ;
	}
	
	for(i=0;i<n;i++)
	{
		if(!col[i]&&!dg[i+u]&&!udg[i-u+n])
		{
			col[i]=dg[i+u]=udg[i-u+n]=1;
			dfs(u+1);
			col[i]=dg[i+u]=udg[i-u+n]=0;
		}
	}
}
 
void print()
{
	int i=0;
	for(i=0;i<n;i++)
		printf("%d %d %d\n",col[i],dg[i],udg[i]);
	printf("\n");
}
 
int main()
{
	int i=0;
	while(~scanf("%d",&n))
	{
//		print();
		ans=0;
		dfs(0);
		printf("%d\n",ans);
//		print();
	}
	return 0;
}

7-13 最佳组队问题

双人混合ACM程序设计竞赛即将开始，因为是双人混合赛，故每支队伍必须由1男1女组成。现在需要对n名男队员和n名女队员进行配对。由于不同队员之间的配合优势不一样，因此，如何组队成了大问题。
给定n×n优势矩阵P，其中P[i][j]表示男队员i和女队员j进行组队的竞赛优势(0<P[i][j]<10000)。设计一个算法，计算男女队员最佳配对法，使组合出的n支队伍的竞赛优势总和达到最大。

输入格式:

测试数据有多组，处理到文件尾。每组测试数据首先输入1个正整数n（1≤n≤9），接下来输入n行，每行n个数，分别代表优势矩阵P的各个元素。

输出格式:

对于每组测试，在一行上输出n支队伍的竞赛优势总和的最大值。

输入样例:

3
10 2 3
2 3 4
3 4 5

输出样例:

18

#include<stdio.h>
#include<string.h>
#define N 10
int p[N][N];
int n,ans,res;
int flag[N];
int a[N];
 
void dfs(int u)
{
	int i=0;
	if(u==n+1)
	{
		res=0;
		for(i=1;i<=n;i++)
			res+=a[i];
		if(ans<res)
			ans=res;
		return ;
	}
	for(i=1;i<=n;i++)
	{
		if(!flag[i])
		{
			flag[i]=1;
			a[u]=p[u][i];
			dfs(u+1);
			flag[i]=0;
		}
	}
}
 
int main()
{
	int i=0,j=0;
	while(~scanf("%d",&n))
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				scanf("%d",&p[i][j]);
		ans=0;
		dfs(1);
		printf("%d\n",ans);
	}
	return 0;
}

7-14 猜对了一半(*)

赛场内 n (0<n≤10) 名短跑运动员正在参加百米短跑比赛。赛场外有 m (0<m≤100) 名热心观众，他们每人都对比赛结果作出了 2 个预测。比赛结束后，运动员的名次各不相同，但令人惊奇的是每位观众都猜对了一半。请问这些运动员取得的实际名次是多少？

例如场内有 4 名运动员参加比赛，场外 3 名观众的预测分别为：

• 1 号运动员名次为 1，2 号运动员名次为 3
• 3 号运动员名次为 1，4 号运动员名次为 4
• 4 号运动员名次为 2，1 号运动员名次为 3

由每人猜对一半推理可知：

• 1 号运动员名次为 4
• 2 号运动员名次为 3
• 3 号运动员名次为 1
• 4 号运动员名次为 2

请编写程序，根据观众的预测来推算运动员的实际名次。

输入格式

两个正整数 n 和 m (运动员人数、观众人数)
随后有 m 行数据，每行包含 4 个整数，为 m 位观众的预测
每行包含的 4 个整数 x1​、r1​ 和 x2​、r2​ 表示该观众的两个预测：
x1​ 号运动员名次为 r1​，x2​ 号运动员名次为 r2​

说明：

• n 名运行员的编号为从 1 到 n 的正整数，无重号和跳号。
• n 名运动员的名次为从 1 到 n 的正整数，无并列的情况。

输出格式

若问题无解，则输出 None。
若问题有解，则输出多行数据，每一行表示一个答案，按字典序输出。
每一行包含 n 个整数，分别是 1 ~ n 号运动员取得的实际名次。

注：整数间用空格间隔，行末没有空格。

说明：

输入样例1

4 3
1 1 2 3
3 1 4 4
4 2 1 3

输出样例1

4 3 1 2

输入样例2

4 3
3 4 2 1
4 3 3 2
1 4 2 3

输出样例2

None

输入样例3

4 3
2 4 4 1
4 2 2 3
3 4 1 1

输出样例3

1 4 3 2
2 3 4 1

#include<stdio.h>
/*n运动员人数，m观众人数，c所求运动员名次的方案数，
falg[]标记观众预测为真的名次，a[][]保存观众的预测*/
int n, m, c, flag[11], a[105][6];
//mc运动员名次，k观众猜测此运动员假名次个数，jiamc[]保存观众猜测此运动员名次为假的名次 
struct{
	int mc, k, jiamc[105];
}ydy[11]; 
//per[]为每个方案运动员的名次，sum保存每个方案运动员名次的十进制整数 
struct{
	int per[11];
	long long sum;
} ans[1000], t;
int pj(int n, int mc){//判断n号运动员，mc是否为假 
	int i;
	for(i = 0; i < ydy[n].k; i++){
		if(ydy[n].jiamc[i] == mc){
			return 0;//mc为假，返回0 
		}
	}
	return 1;//mc为真，返回1 
}
int shu(int cur){//回溯法把剩余没有名次的运动员根据约束条件补齐 
	if(cur > n){
	    int i;
	    for(i = 1; i <= n; i++){
	        ans[c].per[i] = ydy[i].mc;
		}
		c++;
	}
	else{
		int i;
		if(ydy[cur].mc == 0){//运动员cur没有名次 
			for(i = 1; i <= n; i++){//运动员名次 
				if(flag[i] == 0 && pj(cur, i)){//名次i未被标记且第cur个运动员的名次i不在假名次中 
					ydy[cur].mc = i;
					flag[i] = 1;
					shu(cur + 1);
					ydy[cur].mc = 0;
					flag[i] = 0;
				}
			}
		}
		else{//运动员cur有名次 
			shu(cur + 1);
		}
	}
}
int search(int cur){
	if(cur < m){
	    int i;
		for(i = 0; i < 2; i++){/*i == 0时，假设观众cur第一个预测为真，则其第二个预测为假，
		i == 1时，假设观众cur第二个预测为真，则其第一个预测为假 */
			if(ydy[a[cur][2 * i + 1]].mc == a[cur][2 * i + 2]){/*观众cur预测同一个运动员的名次
			与之前观众预测相同*/ 
			    if(pj(a[cur][3 - 2 * i], a[cur][4 - 2 * i])){//观众cur预测的假名次，还未保存在在该运动员的jiamc[]中 
			    	ydy[a[cur][3 - 2 * i]].jiamc[ydy[a[cur][3 - 2 * i]].k] = a[cur][4 - 2 * i];//保存相应运动员名次为假的名次 
			    	ydy[a[cur][3 - 2 * i]].k++;//假名次个数增加 
			    	search(cur + 1);
			    	ydy[a[cur][3 - 2 * i]].jiamc[ydy[a[cur][3 - 2 * i]].k] = 0;
			    	ydy[a[cur][3 - 2 * i]].k--;
				} 
			   	else{//观众cur预测的假名次，已经保存在该运动员的jiamc[]中
			    	search(cur + 1);
				}
			}
			else{//观众cur预测不是同一个运动员 
			    //名次未被标记且运动员名次不相同且运动员的jiamc[]等于1，即运动员名次为真，或者第一层 
				if((flag[a[cur][2 * i + 2]] == 0 && ydy[a[cur][2 * i + 1]].mc == 0 && pj(a[cur][2 * i + 1], a[cur][2 * i + 2])) || cur == 0){
					ydy[a[cur][2 * i + 1]].mc = a[cur][2 * i + 2];//保存相应运动员的名次 
					flag[a[cur][2 * i + 2]] = 1;//标记名次 
					ydy[a[cur][3 - 2 * i]].jiamc[ydy[a[cur][3 - 2 * i]].k] = a[cur][4 - 2 * i];//保存相应运动员名次为假的名次
					ydy[a[cur][3 - 2 * i]].k++;//假名次个数增加 
					search(cur + 1);
					ydy[a[cur][2 * i + 1]].mc = 0;	
					flag[a[cur][2 * i + 2]] = 0;
					ydy[a[cur][3 - 2 * i]].jiamc[ydy[a[cur][3 - 2 * i]].k] = 0;
					ydy[a[cur][3 - 2 * i]].k--;				   	
				}
			}
		}
	}
	else if(cur == m){//cur等于观众人数，进入shu（）补齐其余运动员的名次 
		shu(1);
	}
}
int main()
{
	int i, j, k;
	scanf("%d", &n);
	scanf("%d", &m);
	for(i = 0; i < m; i++){
		scanf("%d %d %d %d", &a[i][1], &a[i][2], &a[i][3], &a[i][4]);
	}
	search(0);
	if(c == 0){//方案数为0 
		printf("None\n");
		return 0;
	}
	for(i = 0; i < c; i++){//把每一行运动员名次转换成十进制整数 
		for(j = 1; j <= n; j++){
			ans[i].sum = ans[i].sum * 10 + ans[i].per[j];
		}
	}
	
	for(i = 0; i < c - 1; i++){//通过上面得到的整数从小到大排序，即可得到字典序 
		k = i;
		for(j = k + 1; j < c; j++){
			if(ans[j].sum < ans[k].sum){
				k = j;
			}
		}
		t = ans[k];
		ans[k] = ans[i];
		ans[i] = t;
	}
	for(i = 0; i < c; i++){//输出答案 
		for(j = 1; j <= n; j++){
			if(j == 1){
				printf("%d", ans[i].per[j]);
			}
			else{
				printf(" %d", ans[i].per[j]);
			}
		}
		printf("\n");
	}
	return 0;
}

7-15 单链表基本操作

请编写程序实现单链表插入、删除结点等基本算法。给定一个单链表和一系列插入、删除结点的操作序列，输出实施上述操作后的链表。单链表数据域值为整数。

输入格式:

输入第1行为1个正整数n，表示当前单链表长度；第2行为n个空格间隔的整数，为该链表n个元素的数据域值。第3行为1个正整数m，表示对该链表施加的操作数量；接下来m行，每行表示一个操作，为2个或3个整数，格式为0 k d或1 k。0 k d表示在链表第k个结点后插入一个数据域值为d的结点，若k=0则表示表头插入。1 k表示删除链表中第k个结点，此时k不能为0。注：操作序列中若含有不合法的操作（如在长度为5的链表中删除第8个结点、删除第0个结点等），则忽略该操作。n和m不超过100000。

输出格式:

输出为一行整数，表示实施上述m个操作后的链表，每个整数后一个空格。输入数据保证结果链表不空。

输入样例:

5
1 2 3 4 5
5
0 2 8
0 9 6
0 0 7
1 0 
1 6

输出样例:

7 1 2 8 3 5 

#include<stdio.h>
typedef struct Node
{
    int data;
    struct Node*next;
}node;
node* head=NULL;
node* rear;  //设置全局变量,便于实现尾插法
void insertend(node* temp)  //链表尾插法
{
    if(head==NULL)
    {
        head=temp;
        rear=temp;
        rear->next=NULL;
    }
    else
    {
        rear->next=temp;
        rear=temp;
        rear->next=NULL;
    }
}
void insert(node*temp,int k,int d)  //表头插入,第k个结点后插入一个数据域值为d的结点
{
    if(k==0)
    {
        temp->data=d;
        temp->next=head;
        head=temp;
    }
    else
    {
        node* p0=head;
        while(k-1>0)
        {
            p0=p0->next;
            k--;
        }
        temp->next=p0->next;
        p0->next=temp;
        temp->data=d;
    }
}
void delete(int k)  //删除链表中第k个结点
{
    node* p=head;
    int nm=1;
    while(p!=NULL&&nm<k-1)
    {
        p=p->next;
        nm++;
    }
    node*q=p;p=p->next;  //p指向第k个结点,q是p的前驱结点
    if(p->next!=NULL)
    {
        q->next=p->next;
        free(p);
    }
    else
    {
        q->next=NULL;
        free(p);
    }
}
int main()
{
    int n,i;
    int num;
    node*p;
    int m;
    scanf("%d",&n);//输入第1行为1个正整数n，表示当前单链表长度
    for(i=0;i<n;i++)  //创建链表
    {
        node*n=(node*)malloc(sizeof(struct Node));
        insertend(n);
    }
    p=head;   //遍历链表输入data域值
    while(p!=NULL)
    {
        scanf("%d",&num);
        p->data=num;
        p=p->next;
    }
    scanf("%d",&m);//第3行为1个正整数m，表示对该链表施加的操作数量
    int n1,n2,n3;
    for(i=0;i<m;i++)
    {
    	scanf("%d",&n1);
    	if(n1==0)
		{
			scanf("%d",&n2);
            scanf("%d",&n3);
			if(n2>=0&&n2<=n)
            {
			    node*temp=(node*)malloc(sizeof(struct Node));
			    insert(temp,n2,n3);
			    n++;
            }
		}
		if(n1==1)
		{
			scanf("%d",&n2);
			if(n2>0&&n2<=n)
			{
				delete(n2);
				n--;
			}
		}
	}
	p=head;
	while(p!=NULL)
    {
	    printf("%d ",p->data);
	    p=p->next;
    }
    return 0;
}