今天是Day3 虽然讲的知识点不难 但是考的不太好啊只有150，QAQ 说好的搜索成了暴力专题 出题人我问你矩阵乘法和搜索有关系嘛QAQ

Day3所讲知识点深度优先搜索、广度优先搜索、记忆化搜索、迭代加深搜索

D3T1 矩阵乘法

题目大意：

给定三个n*n的矩阵A,B,C，判断C是否等于A×B。(多组数据)

数据范围：

对于20%的数据，n=1，对于60%的数据，n<=100，对于100%的数据，1<=n<=1000
矩阵A和矩阵B中的元素为小于1000的非负整数。矩阵C中的元素在int范围内
考试的时候也没想出正解 就交了暴力 还附上了读入优化期望多拿点分 但最后还是60分嘛没有差距
先附上60分暴力代码

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int t,n;
int a[1100][1100];
int b[1100][1100];
int c[1100][1100];
int read()
{
	int sum=0;
	char c;
	c=getchar();
	while(c==' '||c=='\n')
		c=getchar();
	while(c<='9'&&c>='0')
		sum=sum*10+(c-'0'),c=getchar();
	return sum;
}
void small_numberread()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&b[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&c[i][j]);
}
void big_numberread()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			a[i][j]=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			b[i][j]=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			c[i][j]=read();
}
int check()
{
	for(int i=n;i>=1;i--)
		for(int j=1;j<=n;j++)
		{
			int sum=0;
			for(int k=n;k>=1;k--)
				sum=sum+a[i][k]*b[k][j];
			if(sum!=c[i][j]) return 0;
		}
	return 1;
}
int main()
{
	scanf("%d",&t);
	while(t)
	{
		--t;
		memset(a,0,sizeof a);
		memset(b,0,sizeof b);
		memset(c,0,sizeof c);
		scanf("%d",&n);
		if(n<=100)small_numberread();
		else big_numberread();	
		if(check())printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

附上出题人正解：

矩阵乘法不满足交换律，即A×B不一定等于B×A。但矩阵乘法满足结合律。

• 本题要求判断给定的矩阵是否满足
• A × B=C。
• 如果上式成立，在等号两边都左乘一个向量a，等号必然成立，即
• a× (A×B)=a×C

根据结合律，即(a×A)×B=a×C

• 因此，如果A × B=C，则(a×A)×B=a×C必然成立，反之则未必成立（必要条件）
• 本题就是利用必要条件进行判断：随机一个n维向量a，检查是否有(a×A)×B=a×C。如果等号不成立，则原式必然不成立。

因为是向量与方阵相乘，每次判断的复杂度为O(n^2)。只要多判断几次，即可“几乎”判断出原式的正确性！

#include<cstdio>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 1010
#define MAXM 100010
#define INF 1000000000
int a[MAXN][MAXN],b[MAXN][MAXN],c[MAXN][MAXN],r[MAXN];
int ans1[MAXN],ans2[MAXN],ans3[MAXN];
int n;
void mul(int a[MAXN],int b[MAXN][MAXN],int s[MAXN])
{
	int tmp[1001];
	for(int j=1;j<=n;j++)
    {
    	tmp[j]=0;
    	for(int k=1;k<=n;k++)
    	   tmp[j]+=a[k]*b[k][j];
    }
    for(int i=1;i<=n;i++)s[i]=tmp[i];
}
bool jud()
{
	for(int i=1;i<=n;i++)
	    if(ans1[i]!=ans2[i])return 0;
	return 1;
}
int tmp;
int main()
{
	
	scanf("%d",&tmp);
	for(int i=1;i<=1000;i++)r[i]=rand();
	while(tmp--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		    for(int j=1;j<=n;j++)
		        scanf("%d",&a[i][j]);
		for(int i=1;i<=n;i++)
		    for(int j=1;j<=n;j++)
		        scanf("%d",&b[i][j]);
		for(int i=1;i<=n;i++)
		    for(int j=1;j<=n;j++)
		        scanf("%d",&c[i][j]);
		mul(r,a,ans1);
		mul(ans1,b,ans1);
		mul(r,c,ans2);
		if(jud())printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

D3T2 交朋友

题目描述：

有n个OIers要交朋友 (n&1) 其中：第i个人和第j个人成为朋友要花费t[i][j]的时间，并且每个人只有唯一的朋友，问要让所有人都拥有朋友最少要花费多长时间？
数据范围：对于40%的数据，N<=6，对于100%的数据，N<=16

思路：

因为数据量只有16，所以我们就选择DFS
面对第i个人，他只可能有两种情况
1：他没有朋友 2：他与之前的人成为了朋友
面对情况1 我们就可以从他之后的人开始 寻找还没有朋友的人
面对情况2 我们直接跳过他 进入下一层DFS

考试其实想到了正解 但是少了一个else (或return)!!! 没有else的话从情况2的DFS出来后又进入到了选人阶段 就算不超时间 答案也是错的嘛QAQ

100 分->40分 QAQ

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,ans=0x7f7f7f7f;
bool use[50];
int a[50][50];
void dfs(int deep,int sum)
{
	if(deep>n)
	{
		ans=min(ans,sum);
		return ;
	}
	if(use[deep]) dfs(deep+1,sum);
	else
	{
		for(int i=deep+1;i<=n;i++)
			if(!use[i])
			{
				use[i]=true;
				dfs(deep+1,sum+a[deep][i]);
				use[i]=false;
			}
		return ;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	dfs(1,0);
	printf("%d",ans);
	return 0;
}

D3T3 物以类聚

题目大意：

有n个糖果，标号为1...n，每个糖果都有一个种类，m次询问
标号L到标号R之间共有种类为k的糖有多少块。

数据范围：

对于 50%的数据， n，m<=2000
对于 100%的数据, n，m<=100000，k在int范围内

思路：

正解是反离散种类 二分查找