[数据结构与算法]纪中游记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：

1

输出2：

4

输出3：

1

思路

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 的最短路径。但他是个强迫症患者，他有许多奇奇怪怪的要求与限制条件：

1. 从 A 走到 B 时，只能由横坐标小的点走到大的点。

2. 由 B 回到 A 时，只能由横坐标大的点走到小的点。

3. 有两个特殊点 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

5 1 3

1 3

3 4

4 1

7 5

8 3

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分的错解蒟蒻
用乱搞向数据哀悼
个人正解：
先把输入进行操作：

1. 并块
2. 把每个点所在块的左右都记下来(设为$l_i,r_i$)
3. 可设不可更换点为[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;//存下
			}
		}
	}

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

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

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

4 4

1 2

3 2

3 4

4 2

Sample Output

2

思路

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;
}