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

上午

打比赛，基本疯了，myd暴力AT1，wj二分+贪心（错解）AT3，我T2式子推了2h，然后打错±号并同时%少了，成功爆到57.5
wjRank2 235，mydRank10 165
俺枯矣

中午

和myd，wj各下一盘棋，果断输掉（我就应该下国际象棋，正经人谁下中国象棋啊
话说军棋，五子棋和围棋好像都没有马，国际象棋最多20只马？？？
输到怀疑人生，然后看了20mins道德经和《庄子》，心态突然协调
气不喘了，腿不酸了，一口气能爬8层楼
但是道德经里好多生僻字啊，还是《庄子》好，文言文和白话文一样好看

下午

讲的都是毒瘤题，T4的数据八成是出题人用阴寿出的，不然怎么是阴间题？
最大流+黑白染色+语文七级考试=玩毛线
不过有一说一，我这些题改的贼快，已经改完了
晚饭的时候邀请绑架初一党去闲逛刷街，结果……
wj：你不会再迷路吧？
我：所以才叫你们啊
wj：你迟早把我们带迷路……
emmmmm……
不过我没迷路嘿嘿嘿
目前刷街进度：20%->60%

晚上

写题解和游记，预估写完了还能A几道题

T1

这边发现这个范围在开快读等卡常方法下是可以在O(nm)内AC的
个人数据自测可A，如若不行，和本人无任何关系
保证在GMOJ可过
所以放暴力啦
其实就是对新增节点暴力跳啊
code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int n=4,m,a[333000],c[333000],b[333000],wj[333000],fa[333000],ans=3;
inline int read()
{
    int ret,c,f=1;
    while (((c=getchar())> '9'||c< '0')&&c!='-');
    if (c=='-') f=-1,ret=0;
    else ret=c-'0';
    while ((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*f;
}
int max(int x,int y)
{
	return x>y?x:y;
}
int main()
{
	m=read();
	a[1]=b[1]=c[1]=1;
	fa[2]=fa[3]=fa[4]=1;
	wj[2]=1,wj[3]=2,wj[4]=3;
	while (m--)
	{
		int x=read();
		fa[n+1]=fa[n+2]=x;
		a[x]=b[x]=1;
		wj[n+1]=1,wj[n+2]=2;
		while (fa[x]!=1)
		{
			if (wj[x]==1) a[fa[x]]=max(a[fa[x]],max(a[x],b[x])+1);
			if (wj[x]==2) b[fa[x]]=max(b[fa[x]],max(a[x],b[x])+1);
			x=fa[x];
			ans=max(ans,b[x]+a[x]);
		}
		if (wj[x]==1) a[fa[x]]=max(a[fa[x]],max(a[x],b[x])+1);
		if (wj[x]==2) b[fa[x]]=max(b[fa[x]],max(a[x],b[x])+1);
		if (wj[x]==3) c[fa[x]]=max(c[fa[x]],max(a[x],b[x])+1);
		x=1;
		ans=max(max(ans,b[x]+c[x]),max(a[x]+b[x],a[x]+c[x]));
		printf("%d\n",ans);
		n+=2;
	}
	return 0;
}

T2

感谢whx老师提前教了这题半个结论
问题可划分成多个子问题，即第i个已知点（高$h_i$，位置为$w_i$）到第i+1个已知点的方案数，最后乘起来即可
抽象子问题得：从($i,h_i$)点开始，不击穿x轴，到达($i+1,h_{i+1}$)的方案数
(x,y)可到(x+1,y+1),(x+1,y),(x+1,y-1)
dp+卡常可AC
但这里讲数学方法，时间复杂度最坏是O（n*玄学）……
但非常非常快！！！
单个子问题公式为(设$|h_i?h_{i+1}|=m,w_{i+1}?w_i=n$)：
$$\sum _{k=0}^{n?m}((n?k+m)\mathrm{m}\mathrm{o}\mathrm{d}2+1)\mathrm{m}\mathrm{o}\mathrm{d}2?C(n,k)?(C(n?k,\frac{n?k+m}{2})?C(n?k,\frac{n?k+h_i+h_{i+1}+2}{2}))$$
是不是又长又臭？？
解释一下，n是总步数，m是需要上升多少，k是在枚举(x+1,y)走的步数，C(n,k)即n步选k步的方案数。
显然若$(n?k+m)\mathrm{m}\mathrm{o}\mathrm{d}2=1$是走不到的，而走得到的要考虑合不合法。
合法总数=全部的-不合法的
我们可以发现，在剩下的n-k步中，一定有(n-k-m)/2步向下走，所以我们在剩下n-k步中选这么多步向下即全部的方案数
接下来我们转化一下条件：
不击穿x轴意味着不触碰y=-1的直线
那么对于每一个不合法的走法，我们把第一次触碰y=-1的直线后的点以后的走法统统翻下来（建议看图理解），容易证明所有不合法的走法翻折后一定汇于一点（留作习题，可感性理解），且其与不合法方案是双射关系，即一一对应的关系，不重复不遗漏。
所以不合法方案数=到这个新点的方案数，即$C(n?k,\frac{n?k+h_i+h_{i+1}+2}{2})$
code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
long long n,myd=1000000007,fst[40002],e[40002],o[40002],lst=1;
long long ins[40002];
long long ksm(long long x,int y)
{
	long long ans=1;
	while (y)
	{
		if (y&1) ans=ans*x%myd;
		x=x*x%myd;
		y>>=1;
	}
	return ans;
}
long long inv(long long x)
{
	return ksm(x,1000000005);
}
long long Del(long long x,long long y)
{
	return x<y?(x-y+myd)%myd:x-y;
}
long long C(long long x,long long y)
{
	if (y>x) return 0;
	return fst[x]%myd*ins[y]%myd*ins[x-y]%myd;
}
int main()
{
	freopen("brick.in","r",stdin);
	freopen("brick.out","w",stdout);
	scanf("%lld",&n);
	lst=1;
	fst[0]=1;
	ins[0]=inv(1)%myd;
	for (long long i=1;i<=2*n;i++)
	{
		fst[i]=fst[i-1]*i%myd;
		ins[i]=inv(fst[i])%myd;
	}
	for (long long i=1;i<=n;i++)
	{
		scanf("%lld",&e[i]);
	}
	if (e[1]>0||e[n]>0)
	{
		cout<<0;
		fclose(stdin);
		fclose(stdout);
		return 0;
	}
	e[1]=e[n]=0;
	o[1]=1;
	for (int i=2;i<=n;i++)
	{
		if (e[i]<0) continue;
		int wj=abs(e[i]-e[lst]);
		for (int j=0;j<=i-lst-wj;j++)
		{
			int kyx=(i-j-lst);
			if ((kyx+wj)%2==0)
			{
				o[i]+=Del(C(kyx,(kyx+wj)>>1),C(kyx,(kyx+e[i]+e[lst]+2)>>1))*C(i-lst,j)%myd;
				o[i]%=myd;
			}
		}
		o[i]=o[i]*o[lst]%myd;
		lst=i;
	}
	cout<<o[n];
	fclose(stdin);
	fclose(stdout);
	return 0;
}
//这题还挺短的，同时我出过一个弱化版

T3

二分答案+dp
dp的是前i个人在做j个1号子任务时还可做几个2号任务
方程见代码得了
code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int x[101][101],n,m,a[101][2];
int max(int x,int y)
{
	return x>y?x:y;
}
bool check(int mid)
{
	memset(x,-0x3f,sizeof(x));
	x[0][0]=0;
	for (int k=1;k<=n;k++)
	{
		for (int j=0;j<=m;j++)
		{
			for (int i=0;i<=j&&mid>=i*a[k][0];i++)
			{
				x[k][j]=max(x[k-1][j-i]+(mid-i*a[k][0])/a[k][1],x[k][j]);
			}
		}
	}
	return x[n][m]>=m;
}
int main()
{
	freopen("company.in","r",stdin);
	freopen("company.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d%d",&a[i][0],&a[i][1]);
	int l=0,ans,r=100000,mid;
	while (l<=r)
	{
		mid=l+r>>1;
		if (check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T4

首先语文七级考试得可以黑白染色，会得到二分图
接下来就是一个最小割
由著名最小割最大瘤定理，得阴间网络流求最大流
为了保证点数最大，需要这样建边（我们预设二分图左边为$D_1$集合，右边$D_2$集合，INF>inf，inf>所有点权，而且2个都是大很多）：
S连所有$D_1$的点,T连所有$D_2$的点，边权为inf+该点点权
所有原图边设成$D_1$->$D_2$的形式，并连边，边权INF
然后残量网络求方案
code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
#include<deque>
using namespace std;
long long n,m,s,t,tot=2,tot2=2,head[4101],head2[4101],dep[4101],l,r,u[4101],r2,wj[4101];
long long w,ans,x[90001],y[90001];
bool vis[4101],myd[4101];
long long mn(long long x,long long y)
{
	return (x>y?y:x);
}
struct f{
	long long to,net;
	long long w;
} a[100011],a2[100011];
void add(long long x,long long y,long long w)
{
	a[tot].to=y,a[tot].w=w,a[tot].net=head[x],head[x]=tot++;
	return;
}
void add2(long long x,long long y)
{
	a2[tot2].to=y,a2[tot2].net=head2[x],head2[x]=tot2++;
	return;
}
bool bfs()
{
	memset(dep,0,sizeof(dep));
	l=0,r=0;
	u[r++]=s;
	dep[s]=1;
	while (l<r)
	{
		r2=r;
		for (long long i=l;i<r;i++)
		{
			for (long long j=head[u[i]];j;j=a[j].net)
			{
				if (a[j].w!=0&&dep[a[j].to]==0)
				{
					u[r2++]=a[j].to;
					dep[a[j].to]=dep[u[i]]+1;
				}
			}
		}
		l=r,r=r2;
	}
	return dep[t];
}
long long dfs(long long d,long long in)
{
	if (d==t)
	{
		return in;
	}
	long long out=0;
	long long uw=dep[d]+1;
	for (long long j=head[d];j&&in;j=a[j].net)
	{
		if (a[j].w==0||dep[a[j].to]!=uw) continue;
		long long s=dfs(a[j].to,mn(in,a[j].w));
		out+=s,in-=s;
		a[j].w-=s,a[j^1].w+=s;
	}
	if (out==0)
	{
		dep[d]=0;
	}
	return out;
}
void dft(int x,int fa,int wjj)
{
	if (vis[x]) return;
	vis[x]=1;
	if (wjj==1)
	{
		add(s,x,wj[x]+1e9),add(x,s,0);
	}
	else
	{
		myd[x]=1;
		add(x,t,wj[x]+1e9),add(t,x,0);
	}
	for (int i=head2[x];i;i=a2[i].net)
	{
		if (a2[i].to!=fa) dft(a2[i].to,x,wjj^1);
	}
	return;
}
void gjy(int x)
{
	vis[x]=1;
	for (int i=head[x];i;i=a[i].net)
	{
		if (!vis[a[i].to]&&a[i].w>0) gjy(a[i].to);
	}
	return;
}
int main()
{
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	scanf("%d%d",&n,&m);
	t=n+1,s=t+1;
	for (int i=1;i<=n;i++) scanf("%d",&wj[i]);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		add2(x[i],y[i]),add2(y[i],x[i]);
	}
	for (int i=1;i<=n;i++) dft(i,0,1);
	for (int i=1;i<=m;i++)
	{
		if (myd[x[i]]) swap(x[i],y[i]);
		add(x[i],y[i],1e15),add(y[i],x[i],0);
	}
	memset(vis,0,sizeof(vis));
	while (bfs())
	{
		ans+=dfs(s,1e20);
	}
	gjy(s);
	int we=0,we2=0;
	for (int i=1;i<=n;i++) if (myd[i]^vis[i]) we++,we2+=wj[i];
	cout<<we<<' '<<we2<<endl;
	for (int i=1;i<=n;i++) printf("%d",myd[i]^vis[i]);
	fclose(stdin);
	fclose(stdout);
    return 0;
}