首页 > 其他分享 >《LGJOJ 8.22》 测试总结

《LGJOJ 8.22》 测试总结

时间：2023-08-27 11:56:04浏览次数：39  
标签：node 10 vcc 8.22 int tot MAXN 测试 LGJOJ

\(T1\) 青蛙

送分题，不说了。

也是唯一会做的题。

点击查看代码 
#include<bits/stdc++.h>
typedef long long LL;

using namespace std;
const int MAXN=210;
int n,m,k,x,y,z;
int f[MAXN][MAXN][MAXN];
int dx[10+10]={0,0,1,-1,0};
int dy[10+10]={1,-1,0,0,0};
int dz[10+10]={0,0,0,0,1};
char ch[MAXN][MAXN][MAXN];
struct ddl {
	int z,x,y;
};
void bfs() {
	memset(f,127,sizeof(f));
	queue<ddl> q;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			f[1][i][j]=0;
			if(ch[1][i][j]!='*') q.push((ddl){1,i,j});
		}
	}
	while(!q.empty()) {
		ddl ls=q.front();
		q.pop();
		if(ls.x==x&&ls.y==y&&ls.z==z) {
			printf("%d\n",f[ls.z][ls.x][ls.y]*2);
			exit(0);
		}
		for(int i=0;i<5;++i) {
			int xx=ls.x+dx[i];
			int yy=ls.y+dy[i];
			int zz=ls.z+dz[i];
			if(f[zz][xx][yy]<1e9||ch[zz][xx][yy]=='*'||xx<1||xx>n||yy<1||yy>m||zz>k) continue;
			q.push((ddl){zz,xx,yy});
			f[zz][xx][yy]=f[ls.z][ls.x][ls.y]+1;
		}
	}
}
int main () {
	scanf("%d%d%d%d%d%d",&n,&m,&k,&x,&y,&z); z=k-z+1;
	for(int i=k;i>=1;--i) {
		for(int j=1;j<=n;++j) {
			for(int q=1;q<=m;++q) {
				cin>>ch[i][j][q];
			}
		}
	}
	bfs();
	return 0;
}

\(T2\) 数学题

正解貌似是矩阵转置求逆什么的，反正我不会。

不过这题看到区间询问，而且对于询问是可以 \(dp\) 的，而且是静态的，一般可以考虑动态 \(dp\) ，或者猫树分治，不过这题显然猫树分治。

不过貌似可以卡过去，反正我卡不过去，人傻常数大。

时间复杂度 \(nlognm^2\)

点击查看代码 
#include<bits/stdc++.h>
typedef long long LL;

using namespace std;
const int MAXN=1e6+10,MODD=1e9+7,NN=2e5+10;
int n,m,q; 
int c[NN];
char ch1[NN],ch2[NN];
struct daduoli {
	int l,r,id;
}a[MAXN],ls_a[MAXN],ls_b[MAXN],ls_c[MAXN]; 
LL ans[MAXN],f[2][NN][32],v[2][NN][32];
void add(LL &x,LL y) {
	x=(x+y>=MODD?x+y-MODD:x+y);
}
void zx(int l,int r,int L,int R) {
	if(L>R) return ;
	if(l==r) {
		if(m!=1||ch2[1]!=ch1[l]) return ;
		for(int i=L;i<=R;++i) {
			ans[a[i].id]=c[i];
		}
		return ;
	}
	int mid=(l+r)/2;
	int cnt=0,cnt1=0,cnt2=0;
	for(int i=L;i<=R;++i) {
		if(a[i].l<=mid&&mid<=a[i].r) {
			ls_c[++cnt]=a[i];
		}
		else {
			if(a[i].r<=mid) ls_a[++cnt1]=a[i];
			else ls_b[++cnt2]=a[i];
		}
	}
	for(int i=0;i<=m;++i) {
		for(int j=l;j<=mid+1;++j) {
			memset(f[0][j],0,sizeof(f[0][j]));
			memset(v[0][j],0,sizeof(v[0][j]));
		}
		for(int j=mid;j<=r;++j) {
			memset(f[1][j],0,sizeof(f[1][j]));
			memset(v[1][j],0,sizeof(v[1][j]));
		}
		f[0][mid+1][i+1]=1; 
		for(int j=mid;j>=l;--j) {
			for(int q=0;q<=i+1;++q) {
				f[0][j][q]=f[0][j+1][q];
				v[0][j][q]=v[0][j+1][q];
				if(ch1[j]==ch2[q]) {
					add(f[0][j][q],f[0][j+1][q+1]);
					add(v[0][j][q],(v[0][j+1][q+1]+f[0][j+1][q+1]*c[j]%MODD)%MODD);
				}
			}
		}
		f[1][mid][i]=1;
		for(int j=mid+1;j<=r;++j) {
			for(int q=m;q>=i;--q) {
				f[1][j][q]=f[1][j-1][q];
				v[1][j][q]=v[1][j-1][q];
				if(ch1[j]==ch2[q]) {
					add(f[1][j][q],f[1][j-1][q-1]);
					add(v[1][j][q],(v[1][j-1][q-1]+f[1][j-1][q-1]*c[j]%MODD)%MODD);
				}
			}
		}
		for(int j=1;j<=cnt;++j) {
			int ll=ls_c[j].l,rr=ls_c[j].r;
			add(ans[ls_c[j].id],((LL)f[0][ll][1]*v[1][rr][m]%MODD+(LL)f[1][rr][m]*v[0][ll][1]%MODD)%MODD);
		}
	}
	for(int i=1;i<=cnt1;++i) a[L+i-1]=ls_a[i];
	for(int i=1;i<=cnt2;++i) a[L+cnt1+i-1]=ls_b[i];
	zx(l,mid,L,L+cnt1-1);
	zx(mid+1,r,L+cnt1,L+cnt1+cnt2-1);
}
int main () {
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i) {
		scanf("%d",&c[i]);
	}
	scanf("%s",ch1+1);
	scanf("%s",ch2+1);
	for(int i=1;i<=q;++i) {
		scanf("%d%d",&a[i].l,&a[i].r);
		a[i].id=i;
	}
	zx(1,n,1,q);
	LL ls=0;
	for(int i=1;i<=q;++i) {
		ls^=ans[i];
	}
	printf("%lld\n",ls);
	return 0;
}

\(T3\) 货物运输

好题。

首先对于一个树的结构我们是很容易直接进行树形 \(dp\) 的。直接 \(dp\) 计算每条边的贡献即可。

而对于任意一条边至多在一个环中实际上就是仙人掌的结构。

而这题显然每个环之间的处理是相互独立的，也就是说我们只要会处理环上的问题再加上我们原本树形 \(dp\) 处理非环边，那么这题就做完了。

因为一个点可能在多个环中，所以我们这题要缩点双，也就是要建圆方树出来。

最后我们要解决一个问题，就是环上的点怎么处理。

如果数据范围小我们是可以跑费用流的，但是数据范围比较大，就难以跑。

\(luogu\) 有一题是这个环上的弱化版，就是不带边权的，边权全部为 \(1\) ，我们先考虑这个问题如何处理。

就是这题

首先我们记 \(x\) 为每个人给左边的人的糖果数量，那么记 \(y\) 为平均数。

如果 \(x\) 为正，则说明给左边的人糖果，否则为那左边的人的糖果。

那么有 \(y=a_i-x_i+x_{i+1}\)

移一下项，可以得到 \(x_{i+1}=y-a_i+x_i\)

然后我们把每一个 \(x\) 化开来。

\(x_{i+1}=y-a_i+(y-a_{i-1}+x_{i-1})\)

直到化到最后 \(x_1\) 。

所以对于所有 \(x_j=y(j-1)-\sum\limits_{q=1}^{j-1}a_q+x_1\)

我们记 \(S_i=\sum\limits_{j=1}^{i-1}a_j-y(i-1)\)

那么 \(x_j=x_1-S_i\)

所以我们最后要求的就是 \(\sum\limits_{i=1}^n|x_i|=\sum\limits_{i=1}^n|x_1-S_i|\)

其中 \(S_i\) 可以预处理出来的，所以我们就是要找到一个 \(x_1\) ，使得上面的式子最小。

\(x_1\) 是可以随意取的，显然我们要去中位数是可以使得上面的式子最小。

所以对于边权为 \(1\) 的情况我们处理完了。

对于边权不为 \(1\) 的，就算一个加权中位数就可以了，也是同理。

最后总的时间复杂度就是 \(O(nlogn)\)

点击查看代码 
#include<bits/stdc++.h>
typedef long long LL;

using namespace std;
const int MAXN=2e5+10;
int n,m;
int u[MAXN],v[MAXN],w[MAXN],s[MAXN];
LL res;
struct daduoli {
	int f,t,w;
}que[MAXN*2];
int cnt,h[MAXN];
void add(int f,int t,int w) {
	que[++cnt].f=h[f];
	que[cnt].t=t;
	que[cnt].w=w;
	h[f]=cnt;
}
vector<int> e[MAXN];//圆方树的边 
void upd(int x,int y) {
	e[x].push_back(y);
	e[y].push_back(x);
}
int dfn[MAXN],low[MAXN],tot,ind[MAXN],vcc;
int sz[MAXN],cost[MAXN];//点双大小，如果是割边，那么长度 
map<int,int> mp[MAXN];//边信息 
vector<pair<int,int> > sq[MAXN];//环上信息 

void dfs(int node,int fa) {
	dfn[node]=low[node]=++cnt;
	ind[++tot]=node;
	for(int i=h[node];i;i=que[i].f) {
		int t=que[i].t;
		if(t==fa) continue;
		if(!dfn[t]) {
			dfs(t,node);
			low[node]=min(low[node],low[t]);
			if(low[t]>=dfn[node]) {
				++vcc; upd(vcc,node); ++sz[vcc];
				int lt=node;
				while(1) {
					++sz[vcc];
					upd(vcc,ind[tot]);
					sq[vcc].push_back(make_pair(ind[tot],mp[lt][ind[tot]]));
					lt=ind[tot]; --tot;
					if(ind[tot+1]==t) break;
				}
				sq[vcc].push_back(make_pair(node,mp[lt][node]));
				if(sz[vcc]==2) {
					cost[vcc]=que[i].w;
				}
			}
		}
		else low[node]=min(low[node],dfn[t]);
	}
}
LL ans,tot_sz[MAXN],tot_su[MAXN],ued[MAXN],yy[MAXN];
struct ddd {
	LL c,w;
}c[MAXN];
bool cmp(ddd a,ddd b) {
	return a.c<b.c;
}
void zx(int node) {
	LL total=0;
	if(!sq[node].size()) return ;
	int len=sq[node].size(),tt=sq[node][len-1].first;
	for(int i=0;i<len;++i) {
		int t=sq[node][i].first;
		yy[i+1]=s[t]-ued[t]; c[i+1].w=sq[node][i].second;
		total+=c[i+1].w;
	}
	total=(total+1)/2;
	yy[len]+=(tot_sz[node]+tot_sz[tt])*res-(tot_su[node]+tot_su[tt]);
	ued[tt]+=(yy[len]-res);
	LL res=0;
	for(int i=1;i<=len;++i) {
		res+=yy[i];
	}
	res/=len; 
	for(int i=1;i<=len;++i) {
		c[i].c=c[i-1].c+yy[i]-res;
	}
	int ss=c[1].w;
	for(int i=1;i<len;++i) {
		swap(c[i].w,c[i+1].w);
	}
	c[len].w=ss;
	sort(c+1,c+1+len,cmp);
	LL mid=0;
	for(int i=1;i<=len;++i) {
		if(total<=c[i].w) {
			mid=c[i].c;
			break;
		}
		total-=c[i].w;
	}
	for(int i=1;i<=len;++i) {
		ans+=c[i].w*abs(mid-c[i].c);
	}
}
void DFS(int node,int fa) {
	if(node<=n) {
		tot_sz[node]=1; 
		tot_su[node]=s[node];
	}
	for(auto t:e[node]) {
		if(t==fa) continue;
		DFS(t,node);
		tot_sz[node]+=tot_sz[t]; tot_su[node]+=tot_su[t];
	}
	if(node<=n) return ;
	if(sz[node]==2) {
		ans=(ans+(LL)cost[node]*abs(res*tot_sz[node]-tot_su[node]));
		ued[fa]+=(LL)res*tot_sz[node]-tot_su[node];
		return ;
	}
	zx(node);
}
int main () {
	scanf("%d%d",&n,&m); vcc=n;
	for(int i=1;i<=n;++i) {
		scanf("%d",&s[i]);
		res+=s[i];
	} res/=n;
	for(int i=1;i<=m;++i) {
		scanf("%d%d%d",&u[i],&v[i],&w[i]);
		add(u[i],v[i],w[i]);
		add(v[i],u[i],w[i]);
		mp[u[i]][v[i]]=mp[v[i]][u[i]]=w[i];
	} cnt=0;
	dfs(1,0);
	DFS(1,0);
	printf("%lld\n",ans);
	return 0;
}

\(T4\) 士兵游戏

要 \(min\_25\) 我不会，不写。

标签：node,10,vcc,8.22,int,tot,MAXN,测试,LGJOJ
From： https://www.cnblogs.com/ddl1no2home/p/17660097.html

相关文章

  • Python单元测试——深入理解unittest
    单元测试的重要性就不多说了，可恶的是python中有太多的单元测试框架和工具，什么unittest,testtools,subunit,coverage,testrepository,nose,mox,mock,fixtures,discover，再加上setuptools,distutils等等这些，先不说如何写单元测试，光是怎么运行单元测试就有N多种方法，再因为它......
  • 测试
    测试啊 2a=10b=20c=a+bprint(c) pusfffsdsdf2023-08-2623:04:49jhlkhh5lkhhpuh46434kkjg......
  • HyperLedger Fabric基础：搭建Fabric测试网络（三）
    在本系列第二篇中，我们介绍了如何创建通道与在通道上启动链码的问题。本篇将探索如何使用Peer客户端与区域链网络通信。启动测试网络后，可以使用Peer节点CLI与网络进行交互。Peer节点CLI允许您从CLI调用已部署的智能合约、更新通道或安装和部署新的智能合约。确定当前我们仍处于test-......
  • 8.22 lb模拟赛
    小寄()\(100+0+100+25\)\(rk9\)\(T4\)没开\(long\long\)挂\(25pts\)实属不该T1当时看到字符串差点给跳过了()结果是呆呆签到题#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'#definemid(l+r>>1)#defineinlinline#defineebemplac......
  • ChatGPT-测试应用
    一、测试用例设计场景测试用例是未某个特殊目标而编制的一组测试输入、执行条件及预期结果，一边测试某个程序路径或核实是否满足某个特定需求。目标：程序做了它该做的事情，程序没有做它不该做的事情。好的测试用例特征：具体、有针对性、可重复性、有数据支撑ChatG......
  • 优化Redis缓存淘汰机制解决性能测试中报错率逐渐攀升问题
    在某个查询场景的性能测试过程中，遇到了一个问题：测试过程中报错率逐渐攀升。进一步检查后发现，在查询业务所在应用的后台日志和平台应用的后台日志中，都出现了用户登录相关的报错信息。经过排查分析，发现了问题的根源，并做出了解决方案。问题描述在测试过程中，发现报错率逐渐增加，并且......
  • AppSpider Pro 7.4.054 for Windows - Web 应用程序安全测试
    AppSpiderPro7.4.054forWindows-Web应用程序安全测试Rapid7DynamicApplicationSecurityTesting(DAST)请访问原文链接：https://sysin.org/blog/appspider/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.orgappspider没有任何应用程序未经测试，没有未知风险......
  • Acunetix v23.7 (Linux, Windows) - 漏洞扫描 (Web 应用程序安全测试)
    Acunetixv23.7(Linux,Windows)-漏洞扫描(Web应用程序安全测试)Acunetix|WebApplicationSecurityScanner请访问原文链接：https://sysin.org/blog/acunetix-23/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.org重要提示AcunetixPremium现在使用日历化版本......
  • Invicti v23.8 for Windows - 企业应用安全测试
    Invictiv23.8forWindows-企业应用安全测试InvictiStandard17Aug2023v23.8.0.41720请访问原文链接：https://sysin.org/blog/invicti/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.orgInvicti是一种自动化但完全可配置的Web应用程序安全扫描程序，使您能够扫......
  • HCL AppScan Standard v10.3.0 (Windows) - 应用程序安全测试
    HCLAppScanStandardv10.3.0(Windows)-应用程序安全测试请访问原文链接：https://sysin.org/blog/appscan-10/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.orgESG技术评论：使用HCLAppScan实现持续的应用程序安全“AppScan通过直接集成到软件开发生命周期来支......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99