[数据结构与算法] 纪中游记Day1&题解

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 纪中游记Day1&题解 -> 正文阅读

[数据结构与算法]纪中游记Day1&题解

前言

1day前到的纪中，宿舍很艰苦，中午迷惑行为：穿长袖
下午迷惑行为：在纪中迷路
题目很好，孩子很喜欢，下次还会再来

上午

上午和stoorz，myd一起吃饭，myd在哭穷，这边表示他在骗鬼
剩下时间在打模拟赛，我Rank9，非常菜，才115，（wj65，myd更低），Velix巨佬AC2题成功Rank2
话说AJ叫我们订正2题来着？~~Velix AK IOI~~
这边在下午已经订完
个人认为rp=300

中午

有匿名同志在打棋，这边不举报了，***：我2个马都没了
聪爷在吐槽wj的比赛，XJQ表示他想重开，WJ说一定要来
我来了个迷惑行为穿了长袖，成为下午讲题中唯一一个长袖校服
个人认为rp=100

下午

下午叫人讲题，我荣幸地讲T4 90分假算法，收获一机房的懵逼脸……
台下同学：没听懂，能不能讲慢一点？？
个人表示很GG ~~谁还记得模拟赛算法啊~~
吃完晚饭myd继续哭穷，他只剩26（感谢myd本人的更正）29元，我们表示：干脆分了
吃完晚饭我和wj回机房改题，现已改完
期间wj电脑蓝屏一次
改完我下楼逛了一圈，然后……

纪中迷路记

迷迷糊糊逛到操场，然后打球的人在说：最后一球，马上迟到了，然后纪中的铃声就响了，我吓个半死，绕半个纪中跑一圈，跑到游泳池才找到路

感觉rp=-100

晚上

晚上闲着没事写游记和题解
wj再次变身蓝精灵
下面是1则评论：
wj：快点写游记啊，我们等着看搞笑小说

T1

Description

小A一直认为，如果在一个由N个整数组成的数列An中，存在 $A_m + A_n + A_p = A_i（1 <= m, n, p < i）$ （m, n, p可以相同）的话， $A_i$ 就是一个“好元素”。现在，小A有一个数列，他想知道这个数列中有多少个“好元素”，请你帮帮他。

Input

第一行只有一个正整数N，意义如上。

第二行包含N个整数，表示数列An。

Output

输出一个整数，表示这个数列中“好元素”的个数。

Sample Input

输入1：

2
1 3

输入2：

6
1 2 3 5 7 10

输入3：

3

-1 2 0

Sample Output

输出1：

输出2：

输出3：

思路

~~SBhash，毁我青春，耗我钱财，废我人生~~
本题O(n^4)爆零选手报到
正解：
移项得： $A_m+A_n=A_i-A_p$
把左式hash，右式暴力，n方可解
code:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int hash[30000005],n,a[5001],ans;
void h(int x)
{
	int u=x%30000001+30000001;
	u%=30000001;
	while (hash[u]!=x&&hash[u]!=0) u=(u+1)%30000005;
	hash[u]=x;
	return;
}
bool h2(int x)
{
	int u=x%30000001+30000001;
	u%=30000001;
	while (hash[u]!=x&&hash[u]!=0) u=(u+1)%30000005;
	return hash[u]!=0;
}
int main()
{
	freopen("good.in","r",stdin);
	freopen("good.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	bool o=0;
	for (int i=1;i<=n;i++)
	{
		if (a[i]==0&&o)
		{
			ans++;
			continue;
		}
		if (a[i]==0) o=1;
		for (int j=1;j<i;j++)
		{
			if (h2(a[i]-a[j]))
			{
				ans++;
				break;
			}
		}
		for (int j=1;j<=i;j++)
		{
			h(a[i]+a[j]);
		}
	}
	printf("%d",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T2

Description

平面内给出 n 个点，记横坐标最小的点为 A，最大的点为 B，现在Zxd想要知道在每个点经过一次（A 点两次）的情况下从 A 走到 B，再回到 A 的最短路径。但他是个强迫症患者，他有许多奇奇怪怪的要求与限制条件：

从 A 走到 B 时，只能由横坐标小的点走到大的点。
由 B 回到 A 时，只能由横坐标大的点走到小的点。
有两个特殊点 b1 和 b2， b1 在 0 到 n-1 的路上，b2 在 n-1 到 0 的路上。

请你帮他解决这个问题助他治疗吧！

Input

第一行三个整数 n,b1,b2,( 0 < b1，b2 < n-1 且 b1 <> b2)。n 表示点数，从 0 到 n-1 编号，b1 和 b2 为两个特殊点的编号。

以下 n 行，每行两个整数 x、y 表示该点的坐标(0 <= x，y <= 2000)，从 0 号点顺序

给出。Doctor Gao为了方便他的治疗，保证所有点横坐标不同，并且已经将给出的点按 x 增序排好了。

Output

仅一行，输出最短路径长度（精确到小数点后面 2 位）

Sample Input

Sample Output

18.18

思路

dfs10分万岁！！
珂爱的myd同志使用dfs成功20
~~wcr：玩nm！~~
来回=2遍从左到右
dis(x,y)为x号点，y号点的直线距离
显然dp，设 $f_{i,j}$ 为第一遍从左到右现已数到第i个，第二遍从左到右现已数到第j个的最优解
$f_{i,j}+dis(i,k)=>f_{k,j}$
$f_{i,j}+dis(j,k)=>f_{i,k}$
注意我们第一遍和第二遍的两头都是1，n，所以我们需要多算一次n-1到n
code:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int x[1001],y[1001];
double p(int xx,int yy)
{
	return sqrt((x[xx]-x[yy])*(x[xx]-x[yy])+(y[xx]-y[yy])*(y[xx]-y[yy]));
}
int n,b1,b2;
double ans[1001][1001];
int main()
{
	freopen("path.in","r",stdin);
	freopen("path.out","w",stdout);
	scanf("%d%d%d",&n,&b1,&b2);
	for (int i=0;i<n;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
	}
	x[n]=x[n-1],y[n]=y[n-1];
	memset(ans,0x7f7f7f7f,sizeof(ans));
	ans[0][0]=0;
	for (int i=0;i<=n;i++)
	{
		for (int j=0;j<=n;j++)
		{
			int k=max(i,j)+1;
			if (k==b1) ans[k][j]=min(ans[i][j]+p(i,k),ans[k][j]);
			else if (k==b2) ans[i][k]=min(ans[i][j]+p(j,k),ans[i][k]);
			else
			{
				ans[k][j]=min(ans[i][j]+p(i,k),ans[k][j]);
				ans[i][k]=min(ans[i][j]+p(j,k),ans[i][k]);
			}
		}
	}
	printf("%.2lf",min(ans[n][n-1],ans[n-1][n]));
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T3

在这里插入图片描述

思路

全场最难题，这里有一只90分的错解蒟蒻
~~用乱搞向数据哀悼~~
个人正解：
先把输入进行操作：

并块
把每个点所在块的左右都记下来(设为 $l_i,r_i$ )
可设不可更换点为[i，i]

设 $s_{i,j}$ 为S从i开始，T从j开始的块内最大匹配数
只考虑每个块的最左点（ $l_i$ ），并通过指针一块一块地处理出 $s_{l_i,j}$ ,利用一些先后顺序（我们计算j+1时，清空前j个的影响即可），这里是O(nm)的，代码截取：

for (int i=0;i<y.size();i++)
	{
		if (a[i].l==i)//当某个点为最左点时
		{
			memset(o,0,sizeof(o));//清空桶
			int j=i;
			while (a[j].l==i)
			{
				o[y[j]-'a']++;
				j++;
			}//把最左块记入桶
			for (j=0;j<x.size();j++)
			{
				if (o[x[j]-'a']) o[x[j]-'a']--;
				else break;
			}//考虑最左块可以到那里
			s[i][0]=j;//存下
			for (int kk=1;kk<x.size();kk++)
			{
				//判断是否仍可继续匹配
				if (j>=kk) o[x[kk-1]-'a']++;//若可以，则清空之前无效操作
				else j=kk;//否则需重置终点
				for (;j<x.size()&&o[x[j]-'a'];j++)
				{
					o[x[j]-'a']--;
				}//考虑最左块可以到那里
				s[i][kk]=j-kk;//存下
			}
		}
	}

接下来设 $us_{i,j}$ 为S从i开始，T从j开始的最大匹配数，为了不影响其他值，我们需要倒序枚举i
us的方程：
$us_{i,j}= \begin{cases} s_{l_i,j}, s_{l_i,j}+i-1<=r_i\\ s_{l_i,j},s_{l_i,j}+i=m \\ us_{r_i+1,j-i+1+r_i}+r_i-i+1, else \end{cases}$
接下来我们逐条解释：
第一条：对于 $us_{i,j}$ ，它在S串中从0到其末尾的长度应该是 $us_{i,j}+i-1$ ，若这末尾没有超出i所在的块( $r_i$ )，就相当于把需要的字符补到对应位置，若这个块首满足 $s_{l_i,j}+i-1<=r_i$ ，显然整个 $s_{l_i,j}$ 都满足上面的限制（即下限），同时显然 $us_{i,j}$ 不可能比 $s_{l_i,j}$ 大， $s_{l_i,j}$ 即上限，题目求最大匹配，所以我们取上限。

第二条同理，不可能超出T的限制，所以取 $s_{l_i,j}$

第三条是在us内部的递推，其实前两条可以理解为边界，而这里才是真正的方程。
考虑S串里的匹配，一个子串可以跨过多个块，但设该子串的头为i，显然在头所在的块里的部分可以表示为 $r_i+1$ ，我们把子串的头砍到 $r_i+1$ ，发现倒序时 $us_{r_i+1,j-i+1+r_i}$ 已计算完成，所以可以用 $us_{r_i+1,j-i+1+r_i}+r_i-i+1$ 表示。
code：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
string x,y;
int k,ans,ss;
struct f{
	int l,r;
} a[100005],b[100005];
bool cmp(f a,f b)
{
	if (a.l==b.l) return a.r<b.r;
	return a.l<b.l;
}
int l,kk,o[26];
int s[4001][4001],us[4001][4001];
int main()
{
	freopen("lcs.in","r",stdin);
	freopen("lcs.out","w",stdout);
	cin>>x>>y>>k;
	for (int i=1;i<=k;i++) scanf("%d%d",&a[i].l,&a[i].r);
	for (int i=0;i<x.size();i++)
	{
		a[++k].l=i,a[k].r=i;
	}
	sort(a+1,a+k+1,cmp);
	b[l].l=a[1].l,b[l].r=a[1].r;
	for (int i=2;i<=k;i++)
	{
		if (a[i-1].l==a[i].l&&a[i].r==a[i-1].r) continue;
		if (b[l].r>=a[i].l) b[l].r=max(b[l].r,a[i].r);
		else l++,b[l].l=a[i].l,b[l].r=a[i].r;
	}
	sort(b,b+l,cmp);
	for (int i=0,j=0;i<y.size();i++)
	{
		if (b[j].r<i) j++;
		a[i].l=b[j].l,a[i].r=b[j].r;
	}
	for (int i=0;i<y.size();i++)
	{
		if (a[i].l==i)
		{
			memset(o,0,sizeof(o));
			int j=i;
			while (a[j].l==i)
			{
				o[y[j]-'a']++;
				j++;
			}
			for (j=0;j<x.size();j++)
			{
				if (o[x[j]-'a']) o[x[j]-'a']--;
				else break;
			}
			s[i][0]=j;
			for (int kk=1;kk<x.size();kk++)
			{
				if (j>=kk) o[x[kk-1]-'a']++;
				else j=kk;
				for (;j<x.size()&&o[x[j]-'a'];j++)
				{
					o[x[j]-'a']--;
				}
				s[i][kk]=j-kk;
			}
		}
	}
	for (int i=y.size()-1;i>=0;i--) for (int j=0;j<x.size();j++)
	{
		if (s[a[i].l][j]+i-1<a[i].r) us[i][j]=s[a[i].l][j];
		else if (s[a[i].l][j]+i==x.size()) us[i][j]=s[a[i].l][j];
		else us[i][j]=us[a[i].r+1][j-i+1+a[i].r]+a[i].r-i+1;
		ans=max(us[i][j],ans);
	}
	cout<<ans;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T4

Description

vani和cl2在一片树林里捉迷藏……

这片树林里有N座房子，M条有向道路，组成了一张有向无环图。

树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。如果从房子A沿着路走下去能够到达B，那么在A和B里的人是能够相互望见的。

现在cl2要在这N座房子里选择K座作为藏身点，同时vani也专挑cl2作为藏身点的房子进去寻找，为了避免被vani看见，cl2要求这K个藏身点的任意两个之间都没有路径相连。

为了让vani更难找到自己，cl2想知道最多能选出多少个藏身点？

Input

第一行两个整数N，M。

接下来M行每行两个整数x、y，表示一条从x到y的有向道路。

Output

一个整数K，表示最多能选取的藏身点个数。

Sample Input

Sample Output

思路

dfs纯暴力5分，wj树形dp5分，myd树形dp直接爆蛋
~~这告诉我们，暴力出奇迹~~
正解：
先来一个floyd计算连通性，接下来就是喜闻乐见的求反链了（匈牙利算法实现）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,a[201][201],ans,o[201],x,y;
int head[201],to[40001],net[40001],tot=1;
bool vis[4001];
int match[4001];
bool dfs(int x)
{
	for (int i=head[x];i;i=net[i])
	{
		if (vis[to[i]]) continue;
		vis[to[i]]=1;
		if (match[to[i]]==0)
		{
			match[to[i]]=x;
			return 1;
		}
		else
		{
			if (dfs(match[to[i]]))
			{
				match[to[i]]=x;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&m);
	ans=n;
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		a[x][y]=1;
	}
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) for (int k=1;k<=n;k++)
	{
		a[j][k]|=a[j][i]&a[i][k];
	}
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++)
	{
		if (a[i][j])
		{
			to[tot]=j,net[tot]=head[i],head[i]=tot++;
		}
	}
	for (int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		ans-=dfs(i);
	}
	cout<<ans;
	return 0;
}