Date Time

15/10/20 20:36

Author

最近做的TYVJ逗比题系列

最近做了一堆TYVJ的逗【水】比题，在这里整理一下。。。
【虽然似乎好像没意义】

立体图
惊天大模拟，搞一个数组，从正中间开始画。
顺便搞个函数，一次可以画一个方块，从后到前，从下到上画就行了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;  
const int N=105;
int a[N][N],n,m;
char map[4000][4000];
int mxx,mxy,mny,mnx;
void print(int x,int y)
{
	mxx=max(mxx,x);mnx=min(mnx,x-5);
    mxy=max(mxy,y+6);mny=min(mny,y);
	map[x][y]=map[x][y+4]='+';map[x][y+1]=map[x][y+2]=map[x][y+3]='-';
    x--;
    map[x][y]=map[x][y+4]='|';map[x][y+1]=map[x][y+2]=map[x][y+3]=' ';map[x][y+5]='/';
    x--;
    map[x][y]=map[x][y+4]='|';map[x][y+1]=map[x][y+2]=map[x][y+3]=' ';map[x][y+5]=' ';map[x][y+6]='+';
    x--;
    map[x][y]=map[x][y+4]='+';map[x][y+1]=map[x][y+2]=map[x][y+3]='-';map[x][y+5]=' ';map[x][y+6]='|';
    x--;
    map[x][y+1]=map[x][y+5]='/';map[x][y+2]=map[x][y+3]=map[x][y+4]=' ';map[x][y+6]='|';
    x--;
    map[x][y+2]=map[x][y+6]='+';map[x][y+3]=map[x][y+4]=map[x][y+5]='-';
}
int main()
{
 
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
	mxx=mxy=1,mny=mnx=3000;
	for(int i=0;i<=3100;i++)
    for(int j=0;j<=3100;j++)map[i][j]='.';
    int xx=1500,yy=1500;//绘制中心点 
    for(int i=1;i<=n;i++)
    {
        int x=xx,y=yy;
        for(int j=1;j<=m;j++)
        {
            for(int k=1;k<=a[i][j];k++)//从上往下搞一搞 
            print(xx,yy),xx-=3;
            yy+=4,xx=x;//横着搞一搞 
        }
        yy=y-2,xx=x+2;
    }
    for(int i=mnx;i<=mxx;i++){
    for(int j=mny;j<=mxy;j++)
    printf("%c",map[i][j]);puts("");}
}

尼克的任务
我用了spfa无耻的水过了这个题。
对于每个任务[l,l+t-1] 连边l,l+t 边权t
对于某个点没有开始的任务连边i,i+1 边权0
最后求一遍最短路答案=n-最短路

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
const int N=10005,M=N*5;
int list[M],head[N],nxt[M],len[M],n,k,tot;
bool ok[N];
void add(int a,int b,int c)
{
	tot++;
	list[tot]=b,len[tot]=c;
	nxt[tot]=head[a];
	head[a]=tot;
}
bool vis[N];
int dist[N];
void spfa()
{
	memset(dist,0x3f,sizeof dist);
	queue<int>q;dist[1]=0,q.push(1),vis[1]=1;
	while(!q.empty())
	{
		int v=q.front();q.pop();
		vis[v]=0;
		for(int i=head[v];i;i=nxt[i])
		{
			int u=list[i];
			if(dist[u]>dist[v]+len[i])
			{
				dist[u]=dist[v]+len[i];
				if(!vis[u])
				vis[u]=1,q.push(u);
			}
		}
	}
	printf("%d\n",n-dist[n+1]);
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++)
	{
		int l,t;
		scanf("%d%d",&l,&t);
		ok[l]=1;add(l,l+t,t);
	}
	for(int i=1;i<=n;i++)
	if(!ok[i])add(i,i+1,0);
	spfa();
}

表达式计算4
这题不说什么了。。。。先把括号搞一搞
再中缀转一下前缀或后缀最后计算。。。
代码太难看。。。就不贴了。。。。

矩阵取数游戏
显然这题可以发现行和列是不相关的可以直接把每行拎出来做
设f[i][j]代表总共选了i个数左边的选了j个的答案
则
f[i][j]=max(f[i-1][j-1]+a[j]*pow(2,i),f[i-1][j]+a[m-(i-j)+1]*pow(2,i));
然后套上高精度模板。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=100;
int n,m;
struct num
{int a[N],s;}f[N][N],t,a[N],two,zero;
num operator +(num a,num b)
{	
	memset(&t,0,sizeof t);
	t.s=max(a.s,b.s);
	int jin=0;
	for(int i=1;i<=t.s;i++)
	{
		jin+=a.a[i]+b.a[i];
		t.a[i]=jin%10000;
		jin=jin/10000;
	}
	while(jin)t.a[++t.s]=jin%10000,jin/=10000;
	return t;
}
num operator *(num a,num b)
{
	memset(&t,0,sizeof t);
	t.s=a.s+b.s;
	int jin=0;
	for(int i=1;i<=a.s;i++)
	{
		for(int j=1;j<=b.s;j++)
		{
			jin+=a.a[i]*b.a[j]+t.a[i+j-1];
			t.a[i+j-1]=jin%10000;
			jin/=10000;
		}
		for(int j=i+b.s;jin!=0;j++)
		{
			jin+=t.a[j];
			t.a[j]=jin%10000;
			jin/=10000;
		}
	}
	while(t.s>1&&t.a[t.s]==0)t.s--;
	return t;
}
bool operator <(num a,num b)
{
	if(a.s<b.s)return 1;
	if(a.s>b.s)return 0;
	for(int i=a.s;i;i--)
	{
		if(a.a[i]<b.a[i])return 1;
		if(a.a[i]>b.a[i])return 0;
	}
	return 0;
}
num max(num a,num b)
{return a<b?b:a;}
num pow(int p)
{
	num ret=two;
	for(int i=2;i<=p;i++)
	ret=ret+ret;
	return ret;
}
char s[N];
void output(num &a)
{
	printf("%d",a.a[a.s]);
	for(int i=a.s-1;i;i--)printf("%04d",a.a[i]);
	puts("");
}
void read(num &a)
{
	scanf("%s",s);
	int len=strlen(s);
	reverse(s,s+len);
	s[len]=s[len+1]=s[len+2]='0';
	for(int i=0;i<len;i+=4)
	a.a[++a.s]=(s[i+3]-'0')*1000+(s[i+2]-'0')*100+(s[i+1]-'0')*10+s[i]-'0';
}
num dp()
{
	memset(f,0,sizeof f);
	for(int i=1;i<=m;i++)
	for(int j=0;j<=i;j++)
	{
		if(j-1>=0)
		f[i][j]=max(f[i-1][j-1]+a[j]*pow(i),f[i-1][j]+a[m-(i-j)+1]*pow(i));
		else f[i][j]=f[i-1][j]+a[m-(i-j)+1]*pow(i);	
	}
	num ans=zero;
	for(int i=0;i<=m;i++)
	ans=max(ans,f[m][i]);
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	zero.s=1,two.s=1,two.a[1]=2;
	num ans=zero;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		memset(&a[j],0,sizeof a[j]),read(a[j]);
		ans=ans+dp();
	}
	output(ans);
}

过河
一道结论比较神的题。。。
结论：两个石子相差大于100 我们就可以把它们看成100

首先如果S=T 则这是个普及组题直接特判掉
若在S=T-1下结论成立则其他的都成立了
我们考虑极端情况S=9 T=10
在mod 9剩余系下用10可以遍历整个剩余系
不过遍历需要最多走9次所以需要的长度为90
所以90以上的直接看成90就行了
看成100更是对的啦！

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=2000*2000;
int l,s,e,m;
int a[N],t[N];//i位置是否有石子 每个石子的初始位置 
int f[N];
int main()
{
	scanf("%d%d%d%d",&l,&s,&e,&m);
	for(int i=1;i<=m;i++)scanf("%d",&t[i]);
	sort(t+1,t+m+1);
	if(s==e)
	{
		int ans=0;
		for(int i=1;i<=m;i++)
		if(t[i]%s==0)ans++;
		printf("%d\n",ans);
	}
	else
	{
		t[++m]=l;int lst=0;a[0]=1;
		for(int i=1;i<=m;i++)
		{
			if(t[i]-t[i-1]>100)a[lst+100]=1,lst+=100;
			else
			a[lst+(t[i]-t[i-1])]=1,lst+=(t[i]-t[i-1]);
		}
		for(int i=0;i<=lst;i++)f[i]=10000;
		f[0]=1;
		for(int i=0;i<=lst;i++)
		{
			for(int j=s;j<=e;j++)
			f[i+j]=min(f[i+j],f[i]+a[i+j]);
		}
		int ans=0x3f3f3f3f;
		for(int i=lst;i<=lst+e;i++)ans=min(ans,f[i]);
		printf("%d\n",f[lst]-2);
	}
}

Mobile Service
神奇的DP优化感觉好厉害
首先暴力的方程肯定是f[t][i][j][k]啦
t时刻第一个人在i 第二个在j 第三个在k时的答案
超时啦！！！！
考虑优化吧。。。
题意里面说了，有请求人就得过去
所以到i,j,k里面肯定有人在关键点p[t]
t-1时刻肯定也有人在p[t-1]
而且三个人的编号也没有什么太大的意义

然后这么搞
设f[t][i][j]
为t时刻一个人在i 一个人在j 一个人在p[i]时候的答案
然后乱转移：
f[t][j][p[t-1]]=f[t-1][i][j]+d[i][p[t]];
f[t][i][p[t-1]]=f[t-1][i][j]+d[j][p[t]];
f[t][i][j]=f[t-1][i][j]+d[p[t-1]][p[t]];
大概意思就是i去了 j去了或者k去了
神奇啊！！！！

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=1005;
int f[3][205][205];
int p[N],n,l,map[N][N];
void dp()
{
	memset(f,0x3f,sizeof f);
	f[1%2][1][2]=map[3][p[1]];
	f[1%2][1][3]=map[2][p[1]];
	f[1%2][2][3]=map[1][p[1]];
 
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=l;j++)
		for(int k=1;k<=l;k++)
		f[i%2][k][j]=0x3f3f3f3f;
		for(int j=1;j<=l;j++)
		for(int k=1;k<=l;k++)
		{
			f[i%2][k][p[i-1]]=min(f[i%2][k][p[i-1]],f[(i-1)%2][j][k]+map[j][p[i]]);
			f[i%2][j][p[i-1]]=min(f[i%2][j][p[i-1]],f[(i-1)%2][j][k]+map[k][p[i]]);
			f[i%2][j][k]=min(f[i%2][j][k],f[(i-1)%2][j][k]+map[p[i-1]][p[i]]);
		}
	}
	int ans=0x3f3f3f3f;
	for(int i=1;i<=l;i++)
	for(int j=1;j<=l;j++)
	ans=min(ans,f[n%2][i][j]);
	printf("%d\n",ans);
}
int main()
{
	scanf("%d%d",&l,&n);
	for(int i=1;i<=l;i++)
	for(int j=1;j<=l;j++)
	scanf("%d",&map[i][j]);
	for(int i=1;i<=n;i++)scanf("%d",&p[i]);
	dp();
}

新三国争霸
最小生成树+dp
这个一开始难在了dp的阶段划分
如果划分的某个阶段里面有方案更改的话很难做
所以设f[i]表示i时刻的答案它能从f[j]转移过来
[i,j]中间没有改方案
所以f[i]=min(f[j]+kru()*(i-j)*v+k);
kru()为在[i,j]符合条件的最小生成树
然后好像似乎找符合条件的比较麻烦
搞一个g数组维护两个点之间能不能连边
倒着做一做就好了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=20000;
struct edge
{
	int a,b,c;
}s[N];
bool cmp(edge a,edge b)
{return a.c<b.c;}
int f[55],fa[400],n,m,t,v,k;
int find(int x){if(fa[x]!=x)fa[x]=find(fa[x]);return fa[x];}
bool g[400][400],no[400][400][55];
int kru()
{
	for(int i=1;i<=n;i++)fa[i]=i;
	int ans=0,cnt=0;
	for(int i=1;i<=m;i++)
	{
		if(g[s[i].a][s[i].b])continue;
		int a=find(s[i].a);
		int b=find(s[i].b);
		if(a==b)continue;
		fa[a]=b;ans+=s[i].c;cnt++;
	}
	if(cnt<n-1)ans=0x3f3f3f3f;
	return ans;
}
void dp()
{
	sort(s+1,s+m+1,cmp);
	memset(f,0x3f,sizeof f);
	f[0]=0;
	for(int i=1;i<=t;i++)
	{
		memset(g,0,sizeof g);
		for(int j=i-1;j>=0;j--)
		{
			for(int l=1;l<=m;l++)
			g[s[l].a][s[l].b]|=no[s[l].a][s[l].b][j+1];
			f[i]=min(f[i],f[j]+kru()*(i-j)*v+k);
		}
	}
	printf("%d\n",f[t]);
}
int main()
{
	scanf("%d%d%d%d%d",&n,&m,&t,&v,&k);
	for(int i=1;i<=m;i++)
	scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);
	int p;scanf("%d",&p);
	for(int i=1;i<=p;i++)
	{
		int a,b,t1,t2;scanf("%d%d%d%d",&a,&b,&t1,&t2);
		t1=min(t1,t),t2=min(t2,t);
		if(t1>t2)swap(t1,t2);
		for(int j=t1;j<=t2;j++)
		no[a][b][j]=no[b][a][j]=1;
	}
	dp();
}

有理逼近
唬人题，看上去很可怕，实际上很水。。
可以证【感】明【受】找出的两个分数的分母分子相差很【为】小【1】
所以我们找其中一个分数。。然后瞎加加减减一下乱搞。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
double ax,ay,bx,by;
int p,n,f1,f2;
double now,v;
int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);}
void judge(int x,int y)
{
	if(x<=0||x>n)return;
	if(y<=0||y>n)return;
	double now=(x*1.0)/(y*1.0);
	if(now<v)
	{
		if(fabs(now-v)<fabs(v-(ax*1.0)/(ay*1.0))||!f1)
		ax=x,ay=y,f1=1;
	}
	else
	{
		if(fabs(now-v)<fabs(v-(bx*1.0)/(by*1.0))||!f2)
		bx=x,by=y,f2=1;
	}
}
void work()
{
	for(int i=1;i<=n;i++)//分mu 
	{
		double x=i;
		double y=i/v*1.0;
		judge(x,y);
		judge(x-1,y);
		judge(x+1,y);
		judge(x-1,y+1);
		judge(x+1,y-1);
		judge(x,y+1);
		judge(x,y-1);
		judge(x-1,y-1);
		judge(x+1,y+1);
	}
	int g=gcd(ax,ay);
	ax/=g,ay/=g;
	g=gcd(bx,by),bx/=g,by/=g;
	cout<<ax<<"/"<<ay<<" "<<bx<<"/"<<by<<endl;
}
int main()
{
	scanf("%d%d",&p,&n);
	v=sqrt(p);
	work();
}

bomb
一道很容易错的题，会误认为是Dilworth定理。。其实并不是Dilworth定理
Dilworth定理必须用于偏序集偏序集必须要具备三个性质
自反的、反对称的和可传递的
然而这个玩意并不满足自反因为是严格单调自身不可比
所以只能用二分图匹配求第二问。。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int N=3000,M=300000;
int n,f[N];
int fa[N],vis[N];
struct pos
{
	int x,y,z;
}a[N];
int list[M],head[N],nxt[M],tot;
void add(int a,int b)
{
	tot++;
	list[tot]=b;
	nxt[tot]=head[a];
	head[a]=tot;
}
bool dfs(int v)
{
	for(int i=head[v];i;i=nxt[i])
	{
		int u=list[i];
		if(!vis[u])
		{
			vis[u]=1;
			if(fa[u]==0||dfs(fa[u]))
			{fa[u]=v;return 1;}
		}
	}
	return 0;
}
bool cmp(pos a,pos b)
{
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
bool judge(int i,int j)
{return a[i].y>a[j].y&&a[i].z>a[j].z;}
void dp()
{
	int ans=0;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		f[i]=1;
		for(int j=1;j<i;j++)
		if(judge(i,j))f[i]=max(f[i],f[j]+1);
		ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
}
void build()
{
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(i!=j)
	{
		if(a[i].x>a[j].x&&a[i].y>a[j].y&&a[i].z>a[j].z)//能达到 
		add(i,j);
	}
}
void work()
{
	int ans=0;
	for(int i=1;i<=n;i++)
	{
 
 
		memset(vis,0,sizeof vis);
		ans+=dfs(i);
	}
	printf("%d\n",n-ans);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
	dp();
	build();
	work();
}

等差数列
发现好像直接dp会超时。。。然而发现每个数都特别小
就用数字大小直接来作为状态了
设f[i][j]为前i个数，公差为j时的答案。
转移就是的时候注意公差为0的特殊考虑一下。。
要不然会多算

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
using namespace std;
const int N=1005,d=1005,mod=9901;
int f[N][N*3],a[N],n;
void dp()
{
	int ans=0;
	for(int i=1;i<=n;i++)f[i][0]=1;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<i;j++)
		{
			int k=a[i]-a[j]+d;
			f[i][k]=(f[i][k]+f[j][k]+(k!=0))%mod;
		}
	}
	for(int i=1;i<=n;i++)
	for(int j=0;j<=2*d;j++)
	ans=(ans+f[i][j])%mod;
	printf("%d\n",ans);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	dp();
}

MM不哭
似乎有好多种做法：
做法1：f[i][j][0/1]表示左边搞了i个，右边搞了j个在i/j时的答案
做法2：f[i][j][0/1]表示只搞[i,j],在i/j时的答案
我用的做法2
其实这个做法2是个区间dp 只不过O(1)转移

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2005;
long long f[N][N][2],sum[N];//1左边 2右边 
int n,c;
struct pos
{
	int a,b,c;
}s[N];
bool cmp(pos a,pos b)
{return a.a<b.a;}
long long d(int l,int r)
{return abs(s[l].a-s[r].a);}
long long w(int l,int r)
{
	if(l>r)swap(l,r);
	return sum[n]-sum[r]+sum[l-1];
}
void dp()
{
	for(int len=1;len<n;len++)
	for(int l=1;l<=n-len;l++)
	{
		int r=l+len;
		f[l][r][0]=
		min(f[l+1][r][0]+d(l,l+1)*w(l+1,r),
		f[l][r-1][1]+d(r-1,r)*w(l,r-1)+d(r,l)*w(r,l));
 
		f[l][r][1]=
		min(f[l][r-1][1]+d(r-1,r)*w(l,r-1),
		f[l+1][r][0]+d(l,l+1)*w(l+1,r)+d(l,r)*w(l,r));
	}
	printf("%I64d\n",min(f[1][n][1],f[1][n][0]));
}
int main()
{
	scanf("%d%d",&n,&c);
	for(int i=1;i<=n;i++)scanf("%d%d",&s[i].a,&s[i].b),s[i].c=i;
	sort(s+1,s+n+1,cmp);
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+s[i].b;
	memset(f,0x7f,sizeof f);
	for(int i=1;i<=n;i++)
	if(s[i].c==c){f[i][i][1]=f[i][i][0]=0;break;}
	dp();
}

最优贸易
这是普及组的题？？？？？
先在图上dfs一遍标记出来哪些点能从1走到
然后把这些点扔进队列跑spfa
spfa松弛的时候改成dist[u]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N=100005,M=500005*3;
int list[M],head[N],next[M],w[N],tot,n,m;
void add(int a,int b)
{
	tot++;
	list[tot]=b;
	next[tot]=head[a];
	head[a]=tot;
}
int list2[M],head2[N],next2[M],w2[N],tot2;
void add2(int a,int b)
{
	tot2++;
	list2[tot2]=b;
	next2[tot2]=head2[a];
	head2[a]=tot2;
}
int vis[N],p[N],cnt,dist[N];
void dfs(int v)
{
	vis[v]=1;
	p[++cnt]=v;
	for(int i=head[v];i;i=next[i])
	if(!vis[list[i]])dfs(list[i]);
}
void dfs2(int v)
{
	vis[v]=1;
	p[++cnt]=v;
	for(int i=head2[v];i;i=next2[i])
	if(!vis[list2[i]])dfs2(list2[i]);
}
void spfa()
{
	memset(dist,0x3f,sizeof dist);
	memset(vis,0,sizeof vis);
	queue<int>q;
	for(int i=1;i<=cnt;i++)
	dist[p[i]]=0,q.push(p[i]),vis[p[i]]=1;
	while(!q.empty())
	{
		int v=q.front();q.pop();vis[v]=0;
		for(int i=head[v];i;i=next[i])
		{
			int u=list[i];
			if(dist[u]<dist[v]+w[u]-w[v])
			{
				dist[u]=dist[v]+w[u]-w[v];
				if(!vis[u])
				q.push(u),vis[u]=1;
			}			
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;scanf("%d%d%d",&a,&b,&c);
		add(a,b);if(c==2)add(b,a);
		add2(b,a);if(c==2)add2(a,b);
	}
	dfs(1);
	spfa();
	memset(vis,0,sizeof vis);cnt=0;
	dfs2(n);
	int ans=0;
	for(int i=1;i<=cnt;i++)
	ans=max(ans,dist[p[i]]);
	printf("%d\n",ans);
}

Icebound

icebound-area

Date Time

Author

Category

Tags

最近做的TYVJ逗比题系列

取消回复