P4774【屠龙勇士】题解请翻到Day6T2

中山纪中游记

Day -inf

听说有个夏令营，在暑假培训两周，报了
后来另外一个夏令营的两周也调过来了，花一个月(悲)

Day 0

早上摸了会儿鱼，准备了一下比赛，就跑来了，环境还不错，就是WC不能冲水(当晚wcr排遗重创众人)
发现跟xjq和wyc一个宿舍，针不戳(然而发现两位dalao似乎都对我的比赛题目idea没什么兴趣)
有什么难的，也就是一个拉格朗日插值+三模NTT/MTT+数字表格+杜教筛

那没事了，我出我的，你写你的（
电脑疯狂蓝屏，无奈之下换了一台，稍有缓解
晚上：毒瘤XC说网络流是PJ算法
幸好我淦了点分治初步，多项式初步，杜教筛初步和莫反初步，上得了台面
注册进去就淦了道点分治原题
每日一笑：

Day 1

比赛7:50到11:50，然而10:50才能提交(还是OI赛制，吐了)

T1

是道签到题(那还40)，我还以为是被卡常了，结果发现2.5e7的数字我才开3e7空间(后来开成6e7拿了90pts，最后发现hash插入没判重……)

code(加了大量优化导致可读性极差):

#include<cstdio>
#include<cstring>
using namespace std;
int a[66659993];
inline bool ch(int x)
{
	for(register int i=(1ll*x*x+x+66659993)%66659993;(*(a+i));i=((i==66659992)?0:(i+1)))if((*(a+i))==x)return 1;
	return 0;
}
inline void ins(int x){register int i=(1ll*x*x+x+66659993)%66659993;while((*(a+i))&&(*(a+i))!=x)i=((i==66659992)?0:(i+1));(*(a+i))=x;}
int b[5010],n,ans;
int main()
{
	scanf("%d",&n);
	for(register int i=1;i<=n;++i)
	{
		scanf("%d",&(*(b+i)));
		for(register int j=i-1;j;--j)if(ch((*(b+i))-(*(b+j)))){++ans;break;}
		for(register int j=i;j;--j)ins((*(b+i))+(*(b+j)));
	}
	printf("%d",ans);
	return 0;
}

T2

考场上弱智了打了20pts的暴力跑路，赛后听DP恍然大悟

code:

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
using namespace std;
int n,b1,b2,x[1010],y[1010];
inline double dis(int xx,int yy){return sqrt(1.0*(x[xx]-x[yy])*(x[xx]-x[yy])+(y[xx]-y[yy])*(y[xx]-y[yy]));}
double dp[1010][1010],ans=1e9;
int main()
{
	scanf("%d%d%d",&n,&b1,&b2),++b1,++b2;
	for(register int i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);
	for(register int i=1;i<=n;++i)for(register int j=1;j<=n;++j)dp[i][j]=1e9;
	dp[1][1]=0;
	for(register int i=1,k;i<n;++i)for(register int j=1;j<n;++j)
	{
		k=max(i,j)+1;
		if(k==n)
		{
			if(k!=b1)dp[k][j]=min(dp[k][j],dp[i][j]+dis(i,k)+dis(j,k));
			if(k!=b2)dp[i][k]=min(dp[i][k],dp[i][j]+dis(i,k)+dis(j,k));
		}
		else
		{
			if(k!=b1)dp[k][j]=min(dp[k][j],dp[i][j]+dis(i,k));
			if(k!=b2)dp[i][k]=min(dp[i][k],dp[i][j]+dis(j,k));
		}
	}
	for(register int i=1;i<n;++i)ans=min(ans,min(dp[i][n],dp[n][i]));
	cout<<fixed<<setprecision(2)<<ans;
	return 0;
}

T3

绝对的神仙题，就想到一个区间合并，打了个10pts暴力就跑路了(结果还爆0了)
赛后听讲评一脸蒙，只听到“双指针”，“合并区间”，“DP”……
orz wcr错解DP90pts

code:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
char S[15],T[15];
int k,n,m,l,r,ans,dp[15][15];
inline bool N()
{
	register int ch=0;
	for(register int i=r-1;i>=l;--i)if(S[i]<S[i+1]){ch=i;break;}
	if(!ch)return 0;
	for(register int i=r;i>ch;--i)if(S[i]>S[ch]){swap(S[ch],S[i]),sort(S+ch+1,S+r+1);break;}
	return 1;
}
inline void LCS(){for(register int i=1;i<=n;++i)for(register int j=1;j<=m;++j)dp[i][j]=(S[i]==T[j])?(max(max(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]+1)):(max(dp[i-1][j],dp[i][j-1]));}
inline void dfs()
{
	sort(S+l,S+r+1);
	do{LCS(),ans=max(ans,dp[n][m]);}while(N());
}
int main()
{
	cin>>T+1>>S+1,n=strlen(S+1),m=strlen(T+1);
	scanf("%d",&k);
	if(n>10||m>10||k>1){printf("I love data structures and polynomial forever!!!");return 0;}
	if(!k)LCS(),printf("%d",dp[n][m]);
	else scanf("%d%d",&l,&r),++l,++r,dfs(),printf("%d",ans);
	return 0;
}

T4

神仙题，考场上打了一个玄学分层贪心，手造样例鲨掉了，就换了个图上DP，直接40pts->5pts。
orz cxy，考场上直接AC
讲评时讲了一堆东西，大概有：
0，两点通过有向边半连通表示可以比较
1，偏序集：就是一个有向图传递闭包之后的东西啦
2，反链：一个偏序集的反图上的链
3，独立集：一个图内的一个点集，满足互不连通(在偏序集的定义等价于反链)
4，本题求最长反链长度，搞出偏序集后直接匈牙利即可

code:

#include<cstring>
#include<cstdio>
using namespace std;
int n,m,x,y,ans,vis[210],match[210];
bool a[210][210];
inline bool dfs(int x,int id)
{
	if(vis[x]==id)return 0;
	vis[x]=id;
	for(register int i=1;i<=n;++i)if(a[x][i])if((!match[i])||dfs(match[i],id)){match[i]=x;return 1;}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&m);
	while(m--)scanf("%d%d",&x,&y),a[x][y]=1;
	for(register int k=1;k<=n;++k)for(register int i=1;i<=n;++i)for(register int j=1;j<=n;++j)a[i][j]|=a[i][k]&a[k][j];
	for(register int i=1;i<=n;++i)if(dfs(i,i))++ans;
	printf("%d",n-ans);
	return 0;
}

每日一笑：
讲T4时讲题人一直在强调用网络流，结果匈牙利 O ( n 3 ) O(n^3) O(n3)轻松39ms
下午调题，晚上划水准备比赛
总结：少暴力，多DP

Day 2

每日一笑：

起床，刷牙，吃饭，写题

T1

很鬼畜的一道题，赛时打了个求重心的代码改了改，然后就卡壳了，然后就没有然后了
15pts，唯一一道没改的题

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,x,st[200010],top,siz[200010],to[400010],nxt[400010],head[200010],tot,mx,mn=1e9,ans[200010],q;
inline bool cmp(int x,int y){return x>y;}
inline void add(int x,int y){to[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
inline void Getsiz(int x,int f)
{
	siz[x]=1;
	for(register int i=head[x];i;i=nxt[i])if(to[i]!=f)Getsiz(to[i],x),siz[x]+=siz[to[i]];
}
inline void getroot(int x,int f)
{
	for(register int i=head[x];i;i=nxt[i])if(to[i]!=f)getroot(to[i],x);
	top=mx=0;
	for(register int i=head[x];i;i=nxt[i])
	{
		if(to[i]==f)st[++top]=n-siz[x];
		else st[++top]=siz[to[i]];
	}
	sort(st+1,st+top+1,cmp);
	for(register int i=1;i<=top;++i)mx=max(mx,i+st[i]);
	if(mx<mn)mn=mx,ans[q=1]=x;
	else if(mx==mn)ans[++q]=x;
}
int main()
{
	scanf("%d",&n);
	for(register int i=2;i<=n;++i)scanf("%d",&x),add(x,i),add(i,x);
	Getsiz(1,0),getroot(1,0),sort(ans+1,ans+q+1);
	printf("%d\n",mn);
	for(register int i=1;i<=q;++i)printf("%d ",ans[i]);
	return 0;
}

T2

题意不清，我写了个树剖+ST表，光荣爆0
讲评时才知道是一个类似二维顺序对之类的问题
倍增DP

code:

#include<cstdio>
#include<cstring>
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline bool idigit(char x){return (x<'0'|x>'9')?0:1;}
inline int read()
{
	register int num=0,f=1;
	char c=0;
	while(!idigit(c=getchar())){if(c=='-')f=-1;}
	while(idigit(c))num=(num<<1)+(num<<3)+(c&15),c=getchar();
	return num*f;
}
inline void write(int x)
{
	register int F[20],cnt=0,tmp=x>0?x:-x;
	if(x<0)putchar('-');
	while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}
	while(cnt>0)putchar(F[--cnt]);
	if(x==0)putchar('0');
	putchar('\n');
}
int n,m,ans,la,x,y,Log[200010],mx[200010][20],mn[200010][20],fa[200010][20],f[200010][20],w[200010];
int main()
{
	n=read(),Log[0]=-1;
	for(register int i=1;i<=n;++i)mx[i][0]=mn[i][0]=read(),Log[i]=Log[i>>1]+1;
	for(register int i=2;i<=n;++i)fa[read()][0]=read();
	for(register int j=1;j<=Log[n];++j)for(register int i=1;i<=n;++i)fa[i][j]=fa[fa[i][j-1]][j-1],mn[i][j]=min(mn[i][j-1],mn[fa[i][j-1]][j-1]),mx[i][j]=max(mx[i][j-1],mx[fa[i][j-1]][j-1]),f[i][j]=max(mx[fa[i][j-1]][j-1]-mn[i][j-1],max(f[i][j-1],f[fa[i][j-1]][j-1]));
	m=read();
	while(m--)
	{
		x=read(),y=read(),la=1e9,ans=0;
		for(register int i=0;y;++i,y>>=1)if(y&1)ans=max(ans,max(f[x][i],mx[x][i]-la)),la=min(la,mn[x][i]),x=fa[x][i];
		write(ans);
	}
	return 0;
}

T3

毒瘤费用流建模，考试时想出了一个费用流，结果建模挂了，补了一发反悔贪心，光荣爆0

code:

#include<deque>
#include<cstdio>
#include<cstring>
using namespace std;
inline int min(int x,int y){return x<y?x:y;}
inline bool idigit(char x){return (x<'0'|x>'9')?0:1;}
inline int read()
{
	register int num=0;
	register char c;
	while(!idigit(c=getchar()));
	while(idigit(c))num=(num<<1)+(num<<3)+(c&15),c=getchar();
	return num;
}
int n,m,s,t,x,head[2010],d[2010],ans[2010],tot=1,flo,nxt[6010],to[6010],w[6010],f[6010],ans1,ans2,q,r;
bool vis[2010];
void add(int x,int y,int z,int zz){w[++tot]=z,f[tot]=zz,to[tot]=y,nxt[tot]=head[x],head[x]=tot;}
deque <int> b;
inline bool bfs()
{
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	while(b.size())b.pop_front();
	d[s]=0,b.push_back(s);
	while(!b.empty())
	{
		r=b.front(),b.pop_front(),vis[r]=0;
		for(register int i=head[r];i;i=nxt[i])if(w[i]&&d[r]+f[i]<d[to[i]])
		{
			d[to[i]]=d[r]+f[i];
			if(!vis[to[i]]){vis[to[i]]=1;if(b.size()&&d[to[i]]<d[b.front()])b.push_front(to[i]);else b.push_back(to[i]);}
		}
	}
	return d[t]<0;
}
inline int dinic(int x,int flow)
{
	vis[x]=1;
	if(x==t||!flow)return flow;
	register int rest=0,k;
	for(register int i=head[x];i;i=nxt[i])
	{
		if((!vis[to[i]])&&w[i]&&d[to[i]]==d[x]+f[i])
		{
			k=dinic(to[i],min(w[i],flow-rest)),w[i]-=k,w[i^1]+=k,rest+=k;
			if(rest==flow)return flow;
		}
	}
	return rest;
}
int main()
{
	n=read(),m=read(),s=n+m+2*n*m+1,t=n+m+2*n*m+2;
	for(register int i=1;i<=n;++i)add(s,2*n*m+i,2,0),add(2*n*m+i,s,0,0);
	for(register int i=1;i<=m;++i)add(2*n*m+n+i,t,2,0),add(t,2*n*m+n+i,0,0);
	for(register int i=1;i<=n;++i)for(register int j=1;j<=m;++j)x=read(),add(2*n*m+i,(i-1)*m+j,1,0),add((i-1)*m+j,2*n*m+i,0,0),add((i-1)*m+j,(n+i-1)*m+j,1,-x),add((n+i-1)*m+j,(i-1)*m+j,0,x),add((n+i-1)*m+j,2*n*m+n+j,1,0),add(2*n*m+n+j,(n+i-1)*m+j,0,0);
	while(bfs())memset(vis,0,sizeof(vis)),flo=dinic(s,1e9),ans1+=flo,ans2+=flo*d[t];
	printf("%d",-ans2);
	return 0;
}

T4

毒瘤数据结构，但良心到暴力有50pts
刚开始以为正解是线段树+值域分块，结果就是线段树
那你值域怎么才1000……
学完指令集回来就爆踩std
一颗线段树维护5个tag……

code:

#include<cstdio>
#include<cstring>
using namespace std;
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
int n,m,I,s,t,op,v,a[800010],add[800010],mx[800010],f[800010],ans,id,val;
bool ch[800010];
inline void build(int l,int r,int k)
{
	a[k]=I,mx[k]=-1e9,f[k]=l;
	if(l==r)return;
	register int mid=l+r>>1;
	build(l,mid,k<<1);
	build(mid+1,r,k<<1|1);
}
inline void pushdown(int k){if(add[k])a[k<<1]+=add[k],a[k<<1|1]+=add[k],add[k<<1]+=add[k],add[k<<1|1]+=add[k],mx[k<<1]+=add[k],mx[k<<1|1]+=add[k],add[k]=0;if(mx[k]!=-1e9)a[k<<1]=max(a[k<<1],mx[k]),a[k<<1|1]=max(a[k<<1|1],mx[k]),mx[k<<1]=max(mx[k<<1],mx[k]),mx[k<<1|1]=max(mx[k<<1|1],mx[k]),mx[k]=-1e9;}
inline void pushup(int k){ch[k]=ch[k<<1]|ch[k<<1|1];if(f[k<<1]==-1)a[k]=a[k<<1|1],f[k]=f[k<<1|1];else if(f[k<<1|1]==-1)a[k]=a[k<<1],f[k]=f[k<<1];else if(a[k<<1]>a[k<<1|1])a[k]=a[k<<1|1],f[k]=f[k<<1|1];else a[k]=a[k<<1],f[k]=f[k<<1];}
inline void Add(int L,int R,int l,int r,int k,int q)
{
	if(L<=l&&r<=R){add[k]+=q,a[k]+=q,mx[k]+=q;return;}
	pushdown(k);
	register int mid=l+r>>1;
	if(L<=mid)Add(L,R,l,mid,k<<1,q);
	if(R>mid)Add(L,R,mid+1,r,k<<1|1,q);
	pushup(k);
}
inline void Max(int L,int R,int l,int r,int k,int q)
{
	if(L<=l&&r<=R){a[k]=max(a[k],q),mx[k]=max(mx[k],q);return;}
	pushdown(k);
	register int mid=l+r>>1;
	if(L<=mid)Max(L,R,l,mid,k<<1,q);
	if(R>mid)Max(L,R,mid+1,r,k<<1|1,q);
	pushup(k);
}
inline int querymn(int L,int R,int l,int r,int k)
{
	if(L<=l&&r<=R){if(a[k]<val)val=a[k],id=f[k];return a[k];}
	pushdown(k);
	register int mid=l+r>>1,ans=1e9;
	if(L<=mid)ans=min(ans,querymn(L,R,l,mid,k<<1));
	if(R>mid)ans=min(ans,querymn(L,R,mid+1,r,k<<1|1));
	pushup(k);
	return ans;
}
inline bool check(int L,int R,int l,int r,int k)
{
	if(L<=l&&r<=R)return ch[k];
	register int mid=l+r>>1;
	register bool Ch=0;
	if(L<=mid)Ch|=check(L,R,l,mid,k<<1);
	if(R>mid)Ch|=check(L,R,mid+1,r,k<<1|1);
	return Ch;
}
inline void upd(int l,int r,int k)
{
	if(l==r){ch[k]=1,f[k]=-1,a[k]=1e9;return;}
	pushdown(k);
	register int mid=l+r>>1;
	(id<=mid)?(upd(l,mid,k<<1)):(upd(mid+1,r,k<<1|1));
	pushup(k);
}
int main()
{
	scanf("%d%d%d",&n,&m,&I),build(1,n,1);
	while(m--)
	{
		scanf("%d%d%d%d",&op,&s,&t,&v);
		if(op==1){if(check(s,t,1,n,1))continue;++ans,Add(s,t,1,n,1,-v),val=1e9;while(querymn(s,t,1,n,1)<=0)upd(1,n,1),val=1e9;}
		else if(op==2)Add(s,t,1,n,1,v);
		else Max(s,t,1,n,1,v);
	}
	printf("%d",ans);
	return 0;
}

总结：写做法前看看是否现实
中午12:10排队到12:30……
不能再颓了，晚上一定要卷掉多项式开根！
没卷掉，倒是给myd讲了T4，给ljh和kj讲了网络流与费用流
番外话：orz kj，政治填涂答题卡错误少12分屈居年级第三/kk

Day3

每日一笑：

可能是卷多项式卷多了，现在看这个GMT第一反应是FMT/jk
上午打比赛，成功用暴力+骗分登顶B组，拿下rank1
什么？qbf？他是A组的！

T1

考试时没想到LCA，暴力碾了过去，40pts
LCA的做法真妙

code:

#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
inline bool idigit(char x){return (x<'0'|x>'9')?0:1;}
inline int read()
{
	register int num=0;
	register char c;
	while(!idigit(c=getchar()));
	while(idigit(c))num=(num<<1)+(num<<3)+(c&15),c=getchar();
	return num;
}
inline void write(int x)
{
	register int F[20],cnt=0;
	if(!x)putchar('0');
	while(x)F[cnt++]=x%10,x/=10;
	while(cnt)putchar(F[--cnt]|48);
	putchar('\n');
}
int n,m,s,t,c[200010],dep[200010],lca[200010][19],x,y,k,mx=1;
inline int LCA(int x,int y)
{
	if(dep[x]<dep[y])x^=y^=x^=y;
	int len=dep[x]-dep[y],k,w;
	while(len)
	{
		k=len&-len;
		len^=k;
		w=0,k>>=1;
		while(k)k>>=1,++w;
		x=lca[x][w];
	}
	if(x==y)return x;
	for(register int i=log2(dep[x]);i>=0;--i)if(lca[x][i]!=lca[y][i]&&lca[x][i]&&lca[y][i])x=lca[x][i],y=lca[y][i];
	return lca[x][0];
}
inline int dis(int x,int y){return dep[x]+dep[y]-(dep[LCA(x,y)]<<1);}
int main()
{
	m=read(),n=(m<<1)+4,dep[1]=lca[2][0]=lca[3][0]=lca[4][0]=1,dep[2]=dep[3]=dep[4]=s=2,t=3;
	for(register int i=1;i<=m;++i)c[i]=read(),dep[(i<<1)+3]=dep[(i<<1)+4]=dep[c[i]]+1,lca[(i<<1)+3][0]=lca[(i<<1)+4][0]=c[i];
	for(register int i=1,k=log2(n);i<=k;++i)for(register int j=1;j<=n;++j)lca[j][i]=lca[lca[j][i-1]][i-1];
	for(register int i=1;i<=m;++i)
	{
		if(dis(s,(i<<1)+3)>dis(s,t))t=(i<<1)+3;
		if(dis((i<<1)+3,t)>dis(s,t))s=(i<<1)+3;
		if(dis(s,(i<<1)+4)>dis(s,t))t=(i<<1)+4;
		if(dis((i<<1)+4,t)>dis(s,t))s=(i<<1)+4;
		write(dis(s,t));
	}
	return 0;
}

T2

暴力出奇迹，良心出题人给暴力95分
不改了
据说暴力可以过？

code:

#include<cstdio>
#include<cstring>
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
const int mod=1000000007;
int n,x,dp[10010][2],l,r,ans=1;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int main()
{
	scanf("%d%d",&n,&x),dp[0][0]=1;
	if(x>0){putchar('0');return 0;}
	for(register int i=2;i<=n;++i)
	{
		scanf("%d",&x);
		if(x>=i||x>n-i){putchar('0');return 0;}
		if(i)
		{
			if(!l)dp[1][1]=dp[0][0],dp[0][1]=dp[0][0];
			for(register int j=max(1,l);j<=min(r,min(i,n-i+1));++j)dp[j-1][1]=add(dp[j-1][1],dp[j][0]),dp[j][1]=add(dp[j][1],dp[j][0]),dp[j+1][1]=add(dp[j+1][1],dp[j][0]);
			l=max(l-1,0),r=min(r+1,min(i,n-i+1));
			for(register int j=l;j<=r;++j)dp[j][0]=dp[j][1],dp[j][1]=0;
		}
		if(x!=-1){if(!(ans=1ll*ans*dp[x][0]%mod)){putchar('0');return 0;}dp[x][0]=1,l=x,r=x;}
	}
	printf("%d",1ll*ans*dp[0][0]%mod);
	return 0;
}

T3

二分答案+DP，被我二分答案+乱搞贪心A掉了

code:

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,l=1,r=20001,mid,c;
pair<int,int>a[110],k;
inline bool cmp(pair<int,int>x,pair<int,int>y){return 1.0*x.first/x.second<1.0*y.first/y.second;}
inline bool cmp1(pair<int,int>x,pair<int,int>y){return 1.0*(max(x.first,x.second)+1001)/(min(x.first,x.second)+1000)<1.0*(max(y.first,y.second)+1000)/(min(y.first,y.second)+1000);}
inline bool check(int x)
{
	k.first=k.second=m;
	for(register int i=n;i;--i)
	{
		if(k.first<=0){if(k.second<=0)break;k.second-=x/a[i].second;}
		else if(k.second<=0)k.first-=x/a[i].first;
		else if(cmp(a[i],k))c=min(k.first,x/a[i].first),k.first-=c,k.second-=(x-c*a[i].first)/a[i].second;
		else c=min(k.second,x/a[i].second),k.second-=c,k.first-=(x-c*a[i].second)/a[i].first;
	}
	return k.first<=0&&k.second<=0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;++i)scanf("%d%d",&a[i].first,&a[i].second);
	sort(a+1,a+n+1,cmp1);
	while(l<r)
	{
		mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	printf("%d",check(mid)?mid:mid+1);
	return 0;
}

T4

毒瘤最大流，咕中
又没卷掉多项式开根/fad

Day 4

第一次赛后AK(第一个AK)虐全场，纪念一下：

然而赛时全暴力，一个下午就写完正解了

T1

毒瘤期望DP
据说珂以 O ( n ) − T ( 1 ) O(n)-T(1) O(n)−T(1)？

code:

#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
long double O[210],G[210],F[210],ans;
int main()
{
	scanf("%d%d",&n,&m),G[1]=F[1]=1;
	for(register int i=2;i<=n;++i)F[i]=F[i-1]/m;
	for(register int i=2;i<=n;++i)for(register int j=1;j<=i;++j)
	{
		O[i]+=j*F[j]*O[i-j]*(1-2.0/m)+j*F[j]*G[i-j]*(1-1.0/m);
		G[i]+=j*F[j]*O[i-j]/m;
	}
	for(register int i=1;i<n;++i)ans+=i*i*O[n-i+1]*F[i];
	printf("%.10Lf",ans+F[n]*n);
	return 0;
}

T2

毒瘤题目，通过将极限转为高斯消元来做

code:

#include<cstdio>
#include<algorithm>
using namespace std;
inline long double ab(long double x){return x<0?-x:x;}
long double a[210][210],b[210][210],q,z;
int n,c[210],x,y,m;
int main()
{
	scanf("%d",&n);
	for(register int i=1;i<=n;++i)scanf("%d",&c[i]),b[i][i]=1;
	scanf("%d",&m);
	while(m--)scanf("%d%d%Lf",&x,&y,&z),b[x][x]-=z,b[x][y]+=z;
	for(register int i=1;i<=n;++i){for(register int j=1;j<=n;++j)if(i!=j)a[i][j]=-b[j][i]/b[j][j];a[i][i]=1/b[i][i],a[i][n+1]=-c[i];}
	for(register int i=1,k=1;i<=n;k=++i)
	{
		for(register int j=i+1;j<=n;++j)if(ab(a[j][i])>ab(a[k][i]))k=j;
		for(register int j=1;j<=n+1;++j)swap(a[i][j],a[k][j]);
		for(register int j=1;j<=n;++j)if(i!=j){q=a[j][i]/a[i][i];for(register int l=i+1;l<=n+1;++l)a[j][l]-=a[i][l]*q;}
	}
	for(register int i=1;i<=n;++i)printf("%.6Lf\n",-a[i][n+1]/a[i][i]);
	return 0;
}

T3

终极卡常数学神题，倍增优化暴力毫无作用/fad

code:

#include<cstdio>
#include<cstring>
using namespace std;
long long n,x,y,now,ans,d[210],p[200010],cnt,k;
int T,tot;
bool vis[1000010];
inline void exgcd(long long a,long long b)
{
	if(!b)x=1,y=0;
	else
	{
		exgcd(b,a%b);
		register long long tmp=x;x=y,y=tmp-a/b*y;
	}
}
inline void dfs(int x)
{
	if(x>tot)
	{
		exgcd(now,n/now);
		y=-y%now,(y<=0)?(y+=now):0;
		if(ans>n/now*y)ans=n/now*y;
		return;
	}
	dfs(x+1),now*=d[x],dfs(x+1),now/=d[x];
}
int main()
{
	for(register int i=2;i<=1000000;++i)
	{
		if(!vis[i])p[++cnt]=i;
		for(register int j=1;j<=cnt&&i*p[j]<=1000000;++j){vis[i*p[j]]=1;if(!(i%p[j]))break;}
	}
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld",&n),n<<=1,tot=0,now=1,k=n,ans=1e18;
		for(register long long i=1;p[i]*p[i]<=k&&i<=cnt;++i)if(!(k%p[i]))
		{
			d[++tot]=p[i],k/=p[i];
			while(!(k%p[i]))d[tot]*=p[i],k/=p[i];
		}
		if(k!=1)d[++tot]=k;
		dfs(1);
		printf("%lld\n",ans);
	}
	return 0;
}

T4

神级暴力优化，无限orz
O ( n 2 ) − > O ( n ) O(n^2)->O(n) O(n2)−>O(n)(实现懒得用基排所以是 O ( n log ⁡ n ) O(n\log n) O(nlogn))

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,ans,c,st[600010],top;
struct hash_table
{
	int head[65536],to[150010],nxt[150010],tot;
	inline void add(int x,int y){to[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
	inline void ins(unsigned long long x,int limit,int id){add((x>>(limit<<4))&65535,id);}
	inline void query(unsigned long long x,int limit){for(register int i=head[(x>>(limit<<4))&65535];i;i=nxt[i])st[++top]=to[i];}
}fi,se,th,fo;
unsigned long long a[150010],x;
int main()
{
	scanf("%d",&n);
	for(register int i=1;i<=n;++i)
	{
		scanf("%llu",&a[i]),ans=top=0;
		fi.query(a[i],0);
		se.query(a[i],1);
		th.query(a[i],2);
		fo.query(a[i],3);
		sort(st+1,st+top+1);
		top=unique(st+1,st+top+1)-st-1;
		for(register int j=1;j<=top;++j)
		{
			x=a[i]^a[st[j]],c=0;
			while(x)c+=(x&1),x>>=1;
			ans+=(c==3);
		}
		printf("%d\n",ans);
		fi.ins(a[i],0,i);
		se.ins(a[i],1,i);
		th.ins(a[i],2,i);
		fo.ins(a[i],3,i);
	}
	return 0;
}

珂以卷一晚上多项式了
艹 了 ， 又 没 卷 掉 多 项 式 开 根 ， 重 构 了 重 构 了 \color{white}艹了，又没卷掉多项式开根，重构了重构了 艹了，又没卷掉多项式开根，重构了重构了
然 而 并 没 有 什 么 用 \color{white}然而并没有什么用 然而并没有什么用

Day 5

每日一笑：
关于一些矛盾：


淀粉质永远的神

T1

蒻智博弈论，想到结论直接A

code:

#include<cstdio>
#include<cstring>
using namespace std;
inline bool idigit(register char x){return x>='0'&&x<='9';}
inline int fread()
{
	register int num=0;
	register char c;
	while(!idigit(c=getchar()));
	while(idigit(c))num=(num<<3)+(num<<1)+(c&15),c=getchar();
	return num;
}
int T,K,n;
bool ans;
int main()
{
	T=fread();
	while(T--)
	{
		K=fread(),ans=0;
		while(K--){n=fread()*fread(),ans^=fread();while(--n)fread();}
		printf(ans?"lyp win\n":"ld win\n");
	}
	return 0;
}

T2

神仙DP，暴力30pts滚粗

code:

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
using namespace std;
int n,m,head[60],to[310],nxt[310],w[310],tot,dp[60][1010][21],x,y,z;
double ans=1e9;
inline void add(int x,int y,int z){to[++tot]=y,w[tot]=z,nxt[tot]=head[x],head[x]=tot;}
int main()
{
	scanf("%d%d",&n,&m),memset(dp,0x3f,sizeof(dp));
	dp[1][0][0]=0;
	while(m--)scanf("%d%d%d",&x,&y,&z),add(y,x,z);
	for(register int j=1;j<20;++j)for(register int i=1;i<=n;++i)for(register int l=head[i];l;l=nxt[l])for(register int k=w[l];k<=1000;++k)dp[i][k][j]=min(dp[i][k][j],dp[to[l]][k-w[l]][j-1]+w[l]*w[l]);
	for(register int j=1;j<=20;++j)for(register int i=0;i<=1000;++i)ans=min(ans,(dp[n][i][j]-(1.0*i*i)/j)/j);
	cout<<fixed<<setprecision(4)<<ans;
	return 0;
}

T3

神仙DP，暴力爆炸0pts
赛场最高20就离谱

code:

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
int T,n,x,y,ans,O[2010][2010],G[2010][2010],F[2010][2010],S[27],s[27][2010],A[2010][26],B[2010][26],ans1[2010],ans2[2010],c[2010];
char a[2010],b[2010];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		cin>>a+1>>b+1,x=y=1,ans=0,n=strlen(a+1),memset(S,0,sizeof(S)),memset(s,0,sizeof(s)),memset(c,0,sizeof(c)),memset(O,0x3f,sizeof(O)),memset(G,0,sizeof(G)),memset(F,0,sizeof(F)),memset(A,0,sizeof(A)),memset(B,0,sizeof(B));
		for(register int i=1;i<=n+1;++i)O[n+1][i]=n+1-i;
		for(register int i=n;i;--i){for(register int j=0;j<=25;++j)A[i][j]=A[i+1][j],B[i][j]=B[i+1][j];++A[i][a[i]-'a'],++B[i][b[i]-'a'];}
		for(register int i=n;i;--i)
		{
			for(register int j=n;j;--j){if(O[i+1][j]<1e9&&O[i][j]>O[i+1][j]&&A[i+1][a[i]-'a']<B[j][a[i]-'a'])O[i][j]=O[i+1][j],G[i][j]=i+1,F[i][j]=j;if(O[i+1][j+1]<1e9&&O[i][j]>O[i+1][j+1]&&a[i]==b[j])O[i][j]=O[i+1][j+1],G[i][j]=i+1,F[i][j]=j+1;}
			for(register int j=n;j;--j)if(O[i][j+1]<1e9&&O[i][j]>O[i][j+1]+1)O[i][j]=O[i][j+1]+1,G[i][j]=i,F[i][j]=j+1;
		}
		while(x!=n+1){while(G[x][y]==x)y=F[x][y];if(F[x++][y]!=y)++c[y++];}
		--x;
		for(register int i=1;i<=n;++i)if(c[i]!=1)s[b[i]-'a'][++S[b[i]-'a']]=i;
		for(register int i=n;i&&x;--i)if(c[i]==1){while(a[x]!=b[i])ans1[++ans]=s[a[x]-'a'][S[a[x]-'a']--],ans2[ans]=i+1,--x;--x;}
		for(register int i=x;i;--i)ans1[++ans]=s[a[i]-'a'][S[a[i]-'a']--],ans2[ans]=1;
		for(register int i=1;i<ans;++i)for(register int j=i+1;j<=ans;++j)ans1[j]+=(ans1[i]>=ans1[j]&&ans1[j]>=ans2[i]),ans2[j]+=(ans1[i]>ans2[j]&&ans2[j]>ans2[i]);
		printf("%d\n",ans);
		for(register int i=1;i<=ans;++i)printf("%d %d\n",ans1[i],ans2[i]);
	}
	return 0;
}

T4

神仙数据结构优化，考场上根本想不到，但60pts暴力还算不错
orz gjy，bitset优化60pts暴力当场AC

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,xlsh[4010],ylsh[4010],X,Y,x1[2010],x2[2010],y1[2010],y2[2010],ans,s;
bool exist[2010];
int main()
{
	scanf("%d",&n);
	for(register int i=1;i<=n;++i)
	{
		scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]),exist[i]=(x1[i]==x2[i]),xlsh[++X]=x1[i],xlsh[++X]=x2[i],ylsh[++Y]=y1[i],ylsh[++Y]=y2[i];
		if(x1[i]>x2[i]||y1[i]>y2[i])x1[i]^=x2[i]^=x1[i]^=x2[i],y1[i]^=y2[i]^=y1[i]^=y2[i];
	}
	sort(xlsh+1,xlsh+X+1),sort(ylsh+1,ylsh+Y+1),X=unique(xlsh+1,xlsh+X+1)-xlsh-1,Y=unique(ylsh+1,ylsh+Y+1)-ylsh-1;
	for(register int i=1;i<=n;++i)x1[i]=lower_bound(xlsh+1,xlsh+X+1,x1[i])-xlsh,y1[i]=lower_bound(ylsh+1,ylsh+Y+1,y1[i])-ylsh,x2[i]=lower_bound(xlsh+1,xlsh+X+1,x2[i])-xlsh,y2[i]=lower_bound(ylsh+1,ylsh+Y+1,y2[i])-ylsh;
	for(register int i=1;i<=n;++i)for(register int j=1;j<=n;++j)if(exist[i]&&exist[j]&&x1[i]<x1[j]){s=0;for(register int k=1;k<=n;++k)s+=(x2[k]>=x1[j]&&x1[k]<=x1[i]&&y1[k]<=y2[i]&&y1[k]<=y2[j]&&y1[k]>=y1[i]&&y1[k]>=y1[j]&&!exist[k]);ans+=(s*(s-1));}
	printf("%d",ans>>1);
	return 0;
}

Day6

每日一笑：
当代初一蒟蒻日常：

一天卷掉两个多项式板子的后果

T1

线性DP，考试乱写爆0

code:

#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
int a[200010],OGF[200010],EGF[200010],ans=1e18,n;
signed main()
{
	scanf("%lld",&n);
	for(register int i=1;i<=n;++i)scanf("%lld",&a[i]);
	for(register int i=1;i<=n;++i)OGF[i]=(a[i]>a[i-1])?OGF[i-1]:(OGF[i-1]+a[i-1]-a[i]+1);
	for(register int i=n;i;--i)EGF[i]=(a[i]>a[i+1])?EGF[i+1]:(EGF[i+1]+a[i+1]-a[i]+1),ans=min(ans,max(OGF[i],EGF[i]));
	printf("%lld",ans);
	return 0;
}

不用在意变量名，最近在学生成函数，被虐疯了

T2

吐槽一下：“比提高组弱一点”的比赛为什么会搬NOI2018屠龙勇士原题啊
cxydalao还直接A掉了，orz
发现剑跟龙是固定对应的，multiset维护一下，然后直接ExCRT碾过去即可
注意逆元要用exgcd求
番外：
我曾经在多测特判中直接break
我曾经用过upper_bound(multiset.begin(),multiset.end(),a[i])，T飞

code:

#include<set>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
inline bool idigit(char x){return (x<'0'|x>'9')?0:1;}
inline int read()
{
	int num=0,f=1;
	char c=0;
	while(!idigit(c=getchar())){if(c=='-')f=-1;}
	while(idigit(c))num=(num<<1)+(num<<3)+(c&15),c=getchar();
	return num*f;
}
multiset<int>WBLT;
multiset<int>::iterator it;
int T,n,m,ans,OGF,g,a[100010],b[100010],c[100010],p[100010],k[100010],x,y;
bool ok;
inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
inline int exgcd(int a,int b){if(!b){x=1,y=0;return a;}else{register int res=exgcd(b,a%b),i=x;x=y,y=i-a/b*y;return res;}}
inline int mul(int x,int y,int z){register int res=0;y%=z,y=(y>0)?y:y+z;while(y){if(y&1)res=(res+x)%z;y>>=1,x=(x+x)%z;}return res;}
inline int inv(int xx,int yy){exgcd(xx%yy,yy);return (x<0)?(x+yy):x;}
signed main()
{
	T=read();
	while(T--)
	{
		n=read(),m=read(),WBLT.clear(),ok=0;
		for(register int i=1;i<=n;++i)a[i]=read();
		for(register int i=1;i<=n;++i)p[i]=read();
		for(register int i=1;i<=n;++i)b[i]=read();
		while(m--)WBLT.insert(read());
		for(register int i=1;i<=n;++i)
		{
			it=((*WBLT.begin())>a[i])?WBLT.begin():(--WBLT.upper_bound(a[i]));
			WBLT.erase(it),k[i]=*it;
			WBLT.insert(b[i]);
		}
		for(register int i=1;i<=n&&!ok;++i)ok=(p[i]!=a[i]);
		if(!ok){ans=1;for(register int i=1;i<=n;++i)x=p[i]/gcd(p[i],k[i]),ans=ans/gcd(ans,x)*x;printf("%lld\n",ans);continue;}
		for(register int i=1;i<=n&&ok;++i)ok=(p[i]==1);
		if(ok){ans=0;for(register int i=1;i<=n;++i)ans=max(ans,(a[i]+k[i]-1)/k[i]);printf("%lld\n",ans);continue;}
		for(register int i=1;i<=n&&!ok;++i)(k[i]%=p[i])?0:((a[i]==p[i])?(k[i]=p[i]=1,a[i]=0):(printf("-1\n"),ok=1));
		if(ok)continue;
		for(register int i=1;i<=n;++i){g=gcd(k[i],p[i]);if(a[i]%g){printf("-1\n"),ok=1;break;}exgcd(k[i],p[i]),p[i]/=g,a[i]=mul((x%p[i]+p[i])%p[i],a[i]/g,p[i]);}
		if(ok)continue;
		for(register int i=1;i<n;++i){g=gcd(p[i],p[i+1]);if((a[i+1]-a[i])%g){printf("-1\n"),ok=1;break;}OGF=p[i]/g*p[i+1],ans=(mul(mul(inv(p[i]/g,p[i+1]/g),(a[i+1]-a[i])/g,p[i+1]/g),p[i],OGF)+a[i])%OGF,p[i+1]=OGF,a[i+1]=ans;}
		if(!ok)printf("%lld\n",a[n]);
	}
	return 0;
}

T3

神仙状压DP，暴力50pts滚粗

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a[20],b[20],p[20],q,s,ans1,ans2;
long double ans;
bool vis[20];
inline void dfs(int x,int la,int sum)
{
	if(x==n)
	{
		if(s-(sum<<1)>ans1)ans1=s-(sum<<1),ans2=1;
		else if(s-(sum<<1)==ans1)++ans2;
		return;
	}
	for(register int i=1;i<=n;++i)if(!vis[i])vis[i]=1,dfs(x+1,a[i],sum+min(a[i],la)),vis[i]=0;
}
int main()
{
	scanf("%d",&n);
	if(n<=10)
	{
		s=n;
		for(register int i=1;i<=n;++i)scanf("%d",&a[i]),s+=a[i];
		s<<=1,dfs(0,0,0);
		printf("%d %d",ans1,ans2);
		return 0;
	}
	for(register int i=1;i<=n;++i)scanf("%d",&a[i]),p[i]=a[i];
	sort(p+1,p+n+1);
	for(register int l1=0,r1=n+1,l2=0,r2=n+1;l2+1<=r2-1;)
	{
		b[++l2]=p[--r1];
		if(l2+1>r2-1)break;
		b[--r2]=p[--r1];
		if(l2+1>r2-1)break;
		b[++l2]=p[++l1];
		if(l2+1>r2-1)break;
		b[--r2]=p[++l1];
	}
	for(register int i=1;i<=n;++i)ans=ans+(b[i]+1-min(b[i],b[i+1])<<1);
	printf("%.0Lf ",ans),ans=1,memset(b,0,sizeof(b)),q=unique(p+1,p+n+1)-p-1;
	for(register int i=1;i<=n;++i)a[i]=lower_bound(p+1,p+q+1,a[i])-p,++b[a[i]];
	for(register int i=n>>1;i;--i)ans*=i;
	for(register int i=n-(n>>1);i;--i)ans*=i;
	if(!(n&1))ans*=2;
	for(register int i=1;i<=q;++i)if(b[i]!=1)ans*=(1+0.1*(n-b[i]));
	printf("%.0Lf",ans);
	return 0;
}

T4

正解是树形DP/费用流+AC自动机，考试时直接放弃
集体爆0就离谱

总结

毒瘤比赛，24题675分