首页 > 其他分享 >Test 2022.10.12

Test 2022.10.12

时间:2022-10-12 19:58:01浏览次数:52  
标签:12 int add maxn Test include 2022.10 dp dis

今天是关机专场

关于我好不容易写的题解因为关机而无了这件事

T1 理想的正方形

本来写了挺多的,现在不想多说了,简单来说就是维护一个二维的单调队列

一维单调队列

就是对每一行维护从\(i\)开始长度为\(n\)的区间中的最大最小值

二维单调队列

对我们一维单调队列维护出来所有处于同一列的值,纵向维护最大最小值,就可以得到一个矩形内的最大最小值了

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+100;
int maxh[maxn][maxn],minh[maxn][maxn];
int Maxh[maxn][maxn],Minh[maxn][maxn];
int v[maxn][maxn];
int a,b,n,qmax[maxn],qmin[maxn];
int H,T,h,t;
int main()
{
	scanf("%d%d%d",&a,&b,&n);
	for(register int i=1;i<=a;++i)
		for(register int j=1;j<=b;++j)
			scanf("%d",&v[i][j]);
	
	for(register int i=1;i<=a;++i)
	{
		H=T=h=t=qmax[1]=qmin[1]=1;
		for(register int j=2;j<=b;++j)
		{
			while(H<=T&&v[i][j]>=v[i][qmax[T]])T--;	
			while(h<=t&&v[i][j]<=v[i][qmin[t]])t--;
			qmax[++T]=qmin[++t]=j;
			while(j-qmax[H]>=n)H++;
			while(j-qmin[h]>=n)h++;
			if(j>=n)
				maxh[i][j-n+1]=v[i][qmax[H]],
				minh[i][j-n+1]=v[i][qmin[h]];
		}	
	}
	for(register int j=1;j<=b-n+1;++j)
	{
		H=T=h=t=qmax[1]=qmin[1]=1;
		for(register int i=2;i<=a;++i)
		{
			while(H<=T&&maxh[i][j]>=maxh[qmax[T]][j])T--;	
			while(h<=t&&minh[i][j]<=minh[qmin[t]][j])t--;
			qmax[++T]=qmin[++t]=i;
			while(i-qmax[H]>=n)H++;
			while(i-qmin[h]>=n)h++;
			if(i>=n)
				Maxh[i-n+1][j]=maxh[qmax[H]][j],
				Minh[i-n+1][j]=minh[qmin[h]][j];
		}
	}
	int ans=2005120700;
	for(register int i=1;i+n-1<=a;++i)
		for(register int j=1;j+n-1<=b;++j)
			ans=min(ans,Maxh[i][j]-Minh[i][j]);
	cout<<ans;
	return 0;
}

T2 凸多边形的划分

不想多说了,我写的是网络流,对每一个点,他可以和所有不和他相邻的边匹配,然后简简单单建模一下,直接跑\(MCMF\)就行了,但是有问题:会考虑到同一个三角形,即使在图上是完全不同的两组匹配,可能是我太菜了,反正按照我现在的网络流水平,我是无法处理这种情况的。

正解 区间\(dp\)

对于每两个点(记为\(l,r\))的连线,我们考虑从\(l\)到\(r\)的子多边形,把它划分成若干个三角形的最小化费,首先值得肯定的是,我们需要把动态规划的问题转化成每一个之前阶段的子问题,也就是说,这个子多边形还要划分成不同的子多边形,那么就是妥妥的区间动态规划问题问题了。

最外层枚举两个端点之间的距离\(len\),然后是左端点\(l\)和中间点\(k\),对于我们枚举的每个\(k\):\(l,r,k\)的连线都会构成一个三角形,产生新的花费,同时把多边形割成两个子多边形加上中间的三角形,最后按着定义来就是区间\(dp\)的板子了

转移方程是这样的

\[dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+val[l]\times val[r]\times val[k]) \]

小小注意

这个数据范围当然\(long long\)也是无法存下来的,最方便的就是用\(int128\)了

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define int __int128
using namespace std;
const int maxn=105,INF=1e30;
int dp[maxn][maxn],a[maxn];
using namespace std;
inline int re() 
{
	int x=0,f=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
	return x*=f;
}
inline void wr(int n)
{
	if(n==0) return;
	if(n<0)putchar('-'),n=-n;
    wr(n/10);
    putchar(n%10+'0');
}
inline int min(int x,int y){return x>y?y:x;}
signed main() 
{
    int n;
	n=re();
    for(register int i=1;i<=n;++i)a[i]=re();
    for(register int len=3;len<=n;++len)
	{
        for(register int l=1;l+len-1<=n;++l) 
		{
            int r=l+len-1;
            dp[l][r]=INF;
            for(register int k=l+1;k<=r-1;++k) 
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[k]*a[r]);
        }
    }
    wr(dp[1][n]);
    return 0;
}

T3 电路维修

可以\(0-1bfs\)但是我不会也可以最短路,既然是最小步数,那么理所应当的想到要么就是\(IDA*\),要么就是最短路了。

建图

对于给出的\('/'\),我们把当前格子拆成四个点,把左下角和右上角建一条边权为\(0\)的双向边,表示不用改动就可以从这两个点互相到达;把左上角和右下角建一条边权为\(1\)的双向边,表示需要改变一次才能使他们互相到达

对于给出的' \ ',我们做相反的操作就行了,应该很好理解

建图的正确性

不用赘述了吧

小小的注意事项

首先稠密图肯定不能用\(spfa\)了,然而这道题普通的\(dijkstra\)的效率是\(O((nm)^2)\)的,所以还需要堆优化,复杂度就可以降到\(O(nm\log nm)\)了

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
const int maxm=1e6;
const int maxn=3e5;
struct Edge{int u,v,w,nex;}E[maxm];
int T,n,m,s,t,tote,head[maxm];
void add(int u,int v,int w){E[++tote].u=u,E[tote].v=v,E[tote].w=w,E[tote].nex=head[u],head[u]=tote;}
int dis[maxm],vis[maxm];
char map[550][550];
template<typename T>inline void in(T &x){
	x=0;int f=0;char c=getchar();
	for(;!isdigit(c);c=getchar())f|=(c=='-');
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x=f?-x:x;
}
template<typename T>inline void out(T x){
	if(x<0)x=~x+1,putchar('-');
	if(x>9)out(x/10);
	putchar(x%10^48);
}
void ADD(int x,int y)
{
	if(map[x][y]=='/')
	{
		add((m+1)*x+y,(m+1)*(x-1)+y+1,0);
		add((m+1)*(x-1)+1+y,(m+1)*x+y,0);
		add((m+1)*(x-1)+y,(m+1)*x+y+1,1);
		add((m+1)*x+y+1,(m+1)*(x-1)+y,1);
	} 
	else 
	{
		add((m+1)*x+y,(m+1)*(x-1)+y+1,1);
		add((m+1)*(x-1)+1+y,(m+1)*x+y,1);
		add((m+1)*(x-1)+y,(m+1)*x+y+1,0);
		add((m+1)*x+y+1,(m+1)*(x-1)+y,0);
	}
}
void reset()
{
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	memset(head,0,sizeof head);
	tote=0;
}
priority_queue < pair<int,int> >q;
signed main()
{
	scanf("%lld",&T);
	while(T--)
	{
		reset();
		in(n),in(m);	
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=m;++j)
				map[i][j]=getchar(),ADD(i,j);
			getchar();
		}
		s=1,t=(n+1)*(m+1);
		dis[s]=0;
		q.push(make_pair(0,1));
		while(!q.empty())
		{
			int x=q.top().second;q.pop();
			if(vis[x])continue;
			vis[x]=1;
			for(int i=head[x];i;i=E[i].nex)
			{
				int v=E[i].v,w=E[i].w;
				if(dis[v]>dis[x]+w)
				{
					dis[v]=dis[x]+w;
					q.push(make_pair(-dis[v],v));
				}
			}
		}
		if(!vis[t])printf("NO SOLUTION\n");
		else out(dis[t]),putchar('\n');
	}

	return 0;
}

T4 换教室

一眼\(dp\)

分析

首先题目中给出的点数是小于\(200\)的,所以可以直接用\(Floyd\)预处理出每个点之间的最小距离,然后注意题目中是会给出重边的,甚至会存在自环,所以我们需要特判一下,并且每次输入的边应该和当前的边取最小值才行,然后注意每个点到自己的距离一定是\(0\),因为当前这节课和上一节课上课的教室可能是同一间,所以当前点到当前点的最小距离应该是\(0\)

设计\(dp\)方程

很容易看出来这道题的阶段是前\(i\)间教室,然后状态就是用了\(j\)次换教室的机会,但是这个时候,我们仍然无法涉及到换课与否,所以应该另外引入一维状态\(k:0/1\)表示当前状态是否选择了换课

然后\(dp\)定义出来了转移按照定义就应该很好写了

第一种情况:当前选择不换课\(dp[i][j][0]\)

那么就需要从第\(i-1\)个阶段转移过来,此阶段可能申请换课,也可能不会,于是我们把每种可能乘以他的期望

写出来就是$$ dp[i][j][0]=min(dp[i-1][j][0]+dis[c[i-1]][c[i]],dp[i-1][j][1]+dis[c[i-1]][c[i]]\times (1-k[i-1])+dis[d[i-1]][c[i]]\times k[i-1]) $$

第二种情况:当前选择换课\(dp[i][j][1]\)

同样需要从第\(i-1\)个阶段转移过来,可能换课,也可能不会

写出来是

\[ dp[i][j][1]=min(dp[i-1][j-1][0] +dis[c[i-1]][c[i]]*(1-k[i]) +dis[c[i-1]][d[i]]*k[i], dp[i-1][j-1][1] +dis[c[i-1]][c[i]]*(1-k[i])*(1-k[i-1]) +dis[d[i-1]][c[i]]*(1-k[i])*k[i-1] +dis[c[i-1]][d[i]]*k[i]*(1-k[i-1]) +dis[d[i-1]][d[i]]*k[i]*k[i-1]) \]

初始化

注意\(dp[1][0][0]=dp[1][1][1]=1\)

答案

\(ans=\min{\min_{i=0}^{M}{dp[N][i][1],dp[N][i][0]}}\)

Code

#include<bits/stdc++.h>
#define re register 
using namespace std;
const int maxn=2e3+100;
const double INF=1e18;
int N,M;int n,m,u,v,w;
int c[maxn],d[maxn];int dis[maxn][maxn];
double k[maxn],dp[maxn][maxn][2];
void floyd()
{
	for(re int k=1;k<=n;++k)
		for(re int i=1;i<=n;++i)
			for(re int j=1;j<=n;++j)
				dis[j][i]=dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	for(re int i=1;i<=n;++i)dis[i][i]=0;			
}
void prework()
{
	scanf("%d%d%d%d",&N,&M,&n,&m);
	memset(dis,63,sizeof dis);
	for(re int i=0;i<=N;++i)for(re int j=0;j<=M;++j)dp[i][j][0]=dp[i][j][1]=INF;
	for(re int i=1;i<=N;++i)scanf("%d",&c[i]);
	for(re int i=1;i<=N;++i)scanf("%d",&d[i]);
	for(re int i=1;i<=N;++i)scanf("%lf",&k[i]);
	for(re int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&u,&v,&w);
		dis[u][v]=dis[v][u]=min(dis[u][v],w);
	}
	floyd();
	dp[1][0][0]=dp[1][1][1]=0;
}
int main()
{
	freopen("classroom.in","r",stdin);
	freopen("classroom.out","w",stdout);
	prework();
	for(re int i=2;i<=N;++i)
	{
		dp[i][0][0]=dp[i-1][0][0]+dis[c[i-1]][c[i]];
		for(re int j=1;j<=min(i,M);++j)
		{
			double tmp1=INF,tmp2;
			tmp1=min(dp[i-1][j][0]
							+dis[c[i-1]][c[i]],
							
							dp[i-1][j][1]
							+dis[c[i-1]][c[i]]*(1-k[i-1])
							+dis[d[i-1]][c[i]]*k[i-1]);
			tmp2=min(dp[i-1][j-1][0]
							+dis[c[i-1]][c[i]]*(1-k[i])
							+dis[c[i-1]][d[i]]*k[i],
			
							dp[i-1][j-1][1]
							+dis[c[i-1]][c[i]]*(1-k[i])*(1-k[i-1])
							+dis[d[i-1]][c[i]]*(1-k[i])*k[i-1]
							+dis[c[i-1]][d[i]]*k[i]*(1-k[i-1])
							+dis[d[i-1]][d[i]]*k[i]*k[i-1]);
			dp[i][j][0]=min(dp[i][j][0],tmp1);
			dp[i][j][1]=min(dp[i][j][1],tmp2);
		}
	}
	double ans=INF;
	for(re int i=0;i<=M;++i)ans=min(ans,min(dp[N][i][1],dp[N][i][0]));
	printf("%.2lf",ans);
	return 0;
}

标签:12,int,add,maxn,Test,include,2022.10,dp,dis
From: https://www.cnblogs.com/Hanggoash/p/16785744.html

相关文章

  • 10.12 搜索枚举模拟赛总结
    远古遗迹t2196行调了2h+,T3来不及写期望得分:100+100+0+100=300实际得分:0+100+0+0=100多测分类讨论,T1其中一种情况输出不换行。T4其中一种情况让输出tf我输出01......
  • Single Transaction Analysis (ST12) getting started
     heSingleTransactionAnalysiswasdeveloped topromotetheusageofABAPtraceinsideSAPSupport.ItintegratestheABAP-(SE30)andthePerformance(ST05)......
  • 10.12
    今日内容1.多层语法糖2.有参装饰器3.装饰器模板4.装饰器修复技术5.递归函数1.多层语法糖defoutter(func1):print('加载了outter1')defwraapper1(*args,......
  • 2022-10-12 vue+uniapp+echarts 使用记录
    第一步:安装echartsnpmiecharts第二步:在main.js引入echartsimportechartsfrom'echarts'Vue.prototype.$echarts=echarts第三步:在项目中使用<template>......
  • 2022-10-12 vue+uniapp+echarts 报错日志
    这里是vue+uniapp+echarts报错日志报错一:.initisundefined初始化图表失败,请检查你的echarts是否安装成功成功==》请检查你当前安装的版本是否过高,是==》降低版本(比......
  • 123
    下发文件最长反链首先,如果l和r的数字位数相同,那么肯定是r-l+1.为了能够增加更多的数,一定是选择最大的那些数.证明:一个n+1位数中出现n连续数字的种类数......
  • python进阶之路12之有参装饰器、多层语法糖、递归函数简介
    多层语法糖defoutter1(func1):print('加载了outter1')defwrapper1(*args,**kwargs):print('执行了wrapper1')res1=func1(*args,**kwa......
  • JavaWeb学习日记 2022.10.10
    DDL操作表/查询表&创建表usetables;查询当前数据库下所有表名称showtables;查询表结构desc+表名称;创建表的基本语法createtable+表名(     字段......
  • }大括号位置不对引起的TS1128: Declaration or statement expected. 报错
     今天在查TS代码中,发现一个private函数总是报错,TS1128:Declarationorstatementexpected. 查了许久,还以为是vscode中ts插件的问题,折腾了一通,还是报错,静下心......
  • 12.NIO-AIO文件异步
    1.5.6、文件异步AIO@Slf4jpublicclassAIOTest{publicstaticvoidmain(String[]args){try{AsynchronousFileChannelchannel=Async......