210，竟然和$wyc$wyc巨佬一样高$Rank1$Rank1，有点高兴。。。

惊现套题普一分数线250，我怕是个弱智

T1 逛公园

大意

给定一个有向图，求把它变成一个无环图的最小修改边数。

---

思路

比较容易想到$dfs$dfs，然后需要加上一些剪枝或是随机性枚举即可
详细过程:

我们设置这道题的一个特征就是任意两点间都有一条边，而且是有向的，对于这样的有向完全图不存在环当且仅当所有顶点的出度从小到大排列依次为0, 1, 2, … , $n-1$n−1，下面我们给出证明：
如果一个有向图的所有点出度都至少为1，那么这个图一定有环，因为在找到环之前$DFS$DFS总可以找到新的节点。如果有向图无环，必然存在一个点没有出度。由于任两点之间都有有向边，那么其它所有点都要连一条边指向它，这样其它所有点的出度都至少为1了。删掉这个出度为0的点后剩下的图仍然无环，不断对剩下的图继续上面的过程就得到了我们的结论。
这样，这道题的搜索就比较明显了，由于一个拓扑完全图的拓扑序是唯一存在的，我们可以直接枚举拓扑序，效率为 $O(N!)$O(N!) ，期望得分$30$30。
于是，我们不得不去寻求一个高效的剪枝。我们首先通过$DFS$DFS依次确定出度为0, 1, 2, … , $n-1$n−1的点，并且在每次确定一个点后，更新一下当前已经改变的边数，并且通过对剩下的点的出度与目标出度之间作比较，可以得出接下来最少需要改变的边的数量，这里由于数据比较小，可以用计数排序去处理，之后从小到大分别与，0、1、2等等取差的绝对值，最后除以2，记为$Min$Min，如果当前已经改变的边数+$Min$Min大于等于已有的最优值，就没有必要再搜下去了。这样基本上可以通过全部点，期望得分$100$100，但可能有一个点比较危险，接近时限边缘。
下面在给出另一种有效的随机算法。
由于一个拓扑完全图的拓扑序是唯一存在的，所以我们可以多次生成一个随机的拓扑序，然后经过有限次的调整改变其拓扑序，使其到达当前的最优值或者比较优的值。
现在介绍一种简单的调整方法。
我们先生成一个拓扑序：$A_0$A0​ ,$A_1$A1​,$A_2$A2​ ,…,$A_{N-1}$AN−1​ 分别代表出度为0,1,2,…,$N-1$N−1 的点。
然后我们可以选出$A_i$Ai​和 $A_{i+1}$Ai+1​ ( 0 <= i <= $N-2$N−2) 先把$A_i$Ai​ 和 $A_{i+1}$Ai+1​位子交换，再将$A_{i+1}$Ai+1​ 向后移动到能使改变的边的总数量最少的位置，同时将$A_i$Ai​向前移动到边的总数量最少的位置，检查结果是否更优，如果更优就更新一下当前的最优值，并改变点的顺序。如此直到不再有更新为止。经试验是要随机次数达到7次就能够过全部数据。

代码略

---

T2 三个袋子

大意

求$n$n个不同球，放进三个相同的袋子，且袋子可以空，求方案数，答案对$k$k取模

---

思路

设$f_i$fi​表示$i$i个球的方案数，得到方程$f_i=f_{i-1}\times 3+1$fi​=fi−1​×3+1，因为$n\geq 1e9$n≥1e9，要用矩阵乘法加速

---

代码

#include<cstdio>
#include<cstring>
using namespace std;int n,mod;
struct node{int a[2][2];}x,ans;
inline node mul(node a,node b)
{
	node c;
	memset(&c,0,sizeof(c));
	for(register int k=0;k<2;k++)
	for(register int i=0;i<2;i++)
	for(register int j=0;j<2;j++)
	c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod+mod)%mod;//矩阵乘法
	return c;
}
inline void ksm(register int y)
{
	ans.a[0][0]=1;ans.a[0][1]=-1;
	x.a[0][0]=3;x.a[0][1]=0;
	x.a[1][0]=1;x.a[1][1]=1;
	for(;y;x=mul(x,x),y>>=1)if(y&1)ans=mul(ans,x);//快速幂
	return;
}
signed main()
{
	scanf("%d%d",&n,&mod);
	ksm(n-1);
	printf("%d",ans.a[0][0]);
}

---

T3 智捅马蜂窝

大意

给定一些点和一些计算公式，求$1$1点到$n$n点的最短路

---

思路

$floyd$floyd

---

代码

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;int n,w,x[101],y[101];
double d[101][101];
double power(double x){return x*x;}
signed main()
{
	scanf("%d%d",&n,&w);
	for(register int i=1;i<n;i++)
	for(register int j=i+1;j<=n;j++)
	d[i][j]=d[j][i]=2147483647;
	for(register int i=1,fa;i<=n;i++)
	{
		d[i][i]=0;
		scanf("%d%d%d",x+i,y+i,&fa);
		d[i][fa]=d[fa][i]=min(d[fa][i],(double)sqrt(power(x[fa]-x[i])+power(y[fa]-y[i]))/1.0/w);
	}
	for(register int i=1;i<=n;i++)
	for(register int j=1;j<=n;j++)
	{
		if(x[i]==x[j]&&y[i]<y[j])
		d[j][i]=min(d[j][i],sqrt((y[j]-y[i])/5.0));
	}
	for(register int k=1;k<=n;k++)
	 for(register int i=1;i<=n;i++)
	  for(register int j=1;j<=n;j++)
	if(i!=j&&i!=k&&k!=j)
	d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	printf("%0.2lf",d[1][n]);
}

---

T4 过河

大意

水里有一些石头，手里也有一些石头，一步能跨$S\sim E$S∼E的距离，求最小步数

---

思路

首先，我们从范围最小的n下手。从一个起点跳到终点所要的最少步数时的石子数（暂且认为就是 步数-1 ，不考虑中间踩到任何已有的石子），以及最少石子数（每个石子正好垫一脚），这两种情况所用的石头数最多相差$n$n，且已经是极端情况了，即不可能相差$n+1$n+1或更大的值，这样$DP$DP的状态数就可以减少到略大于$n^2$n2。（最小步数同理最大相差$n$n）接下来就只用考察状态转移了，当从一个点到其后面的另一个点，如果能走到，那么只要考虑中间步数最少的情况，即中间用的石子数最少的情况，每个状态转移就是（$t-s$t−s）次。能不能走到可以用很多方法去判断，如 （距离 $div\ s$div s）$t\geq$t≥距离 或 （距离 $div\ t + 1$div t+1）$s\leq$s≤距离。这样，无论数据出到多么bt都能以$O(n^3)$O(n3)的效率出解了。

实现的时候要注意把$0$0点和终点后$s-1$s−1个点也放进去，最后看终点后$s-1$s−1个点石子用的最多的情况，输出最小值；如果走不到的话，只用整张表扫一次，把剩下的石头都以t的距离计进去，输出最大值。

下面简单讲述搜索的方法。

搜索实际上也是以原有的石子作状态，只是预处理比较复杂。

首先，我们要判断平平能否跳到对岸。我们可以用$O(2n)$O(2n)的复杂度统计出平平从起点跳到每个石子最少需要消耗的石子数，再算一下剩下的石子能否使他跳到对岸就好了，同时也可算出他最远能到达的距离。

接下来就是处理最少步数的问题了，我们先统计出从一个石子跳到另一个石子所需要的石子数（暂且认为就是 步数-1 ，不考虑中间踩到任何已有的石子）。

然后从起点开始做$DF$DFS，再加上几个比较弱的剪枝就可以了。

剪枝1：当前以走过的步数＋从这个石子跳到对岸所需要的最少步数（不考虑石子是否够用)$\geq$≥当前已有的最优步数 ，这种情况可以剪掉。

剪枝2：假设走到某个石子是所用的步数为$step$step ， 所剩的石子数为 $sum$sum ；如果在这之前出现过某个状态，其所用的步数$\leq step$≤step ，而且所剩的石子数$\geq sum$≥sum 。这种情况也可以剪掉。

加上这两个剪枝，基本上就能过全部点了，但总耗时略高于$Dp$Dp，不过相差不大。

---

代码略