AcWing第73场周赛

1：数对

题目链接：

这道题目就是求一下两个数字之间的差值如果小于给定的k，就加一次，但是这里可能会出现i，j相同，但是顺序相反，这也算一种情况，那么我们就可以直接暴力枚举，这里有个问题是，如果i，j相反了之后，数字相同还算一种情况吗？

答案是的，我们发现第二个样例出现了i=1,j=5是为（55,55）,i=5,j=1时为（55，55），答案算作一种情况；

那么代码如下：

#include<iostream>

using namespace std;

int arr[10010];
int n,m;

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>arr[i];
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j&&abs(arr[i]-arr[j])<=m)//直接暴力循环判断即可 
			ans++;
		}
	} 
	cout<<ans<<endl; 
}

2：矩阵

原题链接：

这道题目给我们的是二维矩阵，又让我们求出二维矩阵旋转之后有多少种不同的情况，如果直接找所有相同矩阵的某一种情况太困难了，所以这里我们可以直接把答案存起来，就算它会旋转，最多也只有6*5*4*3/4种，所以我们直接存下一个矩阵之后，把这个矩阵的所有反转情况存下来，只要接下来的判断出现就说明他一定与上面的某个矩阵一模一样；

我们只需要找到那些不一样的即可，至于存储可以使用char二维数组，也可以直接用string存储；

代码如下：

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

map<string,int> mp;
string a,b;
int ans=0;

int main()
{
	int n;
	cin>>n;
	n--;
	cin>>a>>b;
	reverse(b.begin(),b.end());//因为我们是旋转，所以这里要用符合旋转的情况记录
	a+=b;//把b接在a后面，方便接下来遍历 
	a+=a;//复制一次就可以避免循环时指针前移的情况 
	for(int i=0;i<=3;i++)
	{
		string p;
		for(int j=0;j<=3;j++)//两层循环找到所有相同情况 
			p+=a[i+j];
		mp[p]++;//把每种情况都加入 
	}
	ans++;
	//这里是为了卡掉第一个没有**的数据 
	while(n--)
	{
		string o;
		cin>>o;//卡掉** 
		cin>>a>>b;
		reverse(b.begin(),b.end());
    	a+=b;
    	a+=a;
    	int flag=0;
    	for(int i=0;i<=3;i++)
    	{
	    	string p;
	    	for(int j=0;j<=3;j++)
		    	p+=a[i+j];
		    if(!mp[p])
		    {
		    	flag=1;
		    	mp[p]++;//这里可以直接退出，不退出也可以过 
			}
    	}
    	if(flag) ans++;//如果出现p不存在于已经出现的数据，那说明是一个新的数据，加入答案，上面已经把数据加入 
	}
	cout<<ans<<endl;//直接输出 
}

3：最短路径

题目链接：

这道题目如果大家看过我之前的关于天梯赛L2的一道题目的话就会发现这道题目并不难，其实就是遍历一遍树，找到距离根节点最远的那个点的距离，然后用总长度减去最远距离即可；

大家可以去看一下：

第三道题目：龙龙送外卖，那道题目应该是比这道题目要难得，在那到题目里使用了并查集来找最长边，这里使用dfs循环，其实复杂度一样，但是那种方法明显更简单；

答案如下：

#include<iostream>
#include<cstring>
using namespace std;

const int N=100010;
typedef long long LL;
int h[N],e[N*2],ne[N*2],idx,w[N*2];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;//建边，顺便记得存储权值 
}

int find(int u,int fa)
{
	int res=0;
	for(int i=h[u];i!=-1;i=ne[i])//遍历节点的所有边，记得如果是父节点就要跳出去 
	{
		int j=e[i];
		if(j==fa) continue;
		res=max(res,find(j,u)+w[i]);//find找的是以前一个为起始点，他的父节点是后一个点的所有子树 
		                            //中最大距离是多少与res比较即可 
	}
	return res;
}

int main()
{
	int n;
	cin>>n;
	n--;
	memset(h,-1,sizeof(h));
	LL sum=0;
	while(n--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);//记住建双向边 
	    sum+=2*c;//答案是遍历一遍所有节点，所以路径会有一个来回 
	}
	cout<<sum-find(1,-1);//直接减去最大的路径即可 
	
}