首页 > 其他分享 >7.12 模拟赛总结

7.12 模拟赛总结

时间：2024-07-12 21:08:03浏览次数：9  
标签：总结 return 7.12 int 矩阵 tag maxn 模拟 mod

这是暑假的第一个模拟赛，和新高一的一起打的

T1 T2 T3 T4 tot
50pts 45pts 100pts 0pts 195tps

总的来说不是很满意，最近的状态有点低迷，但考虑到刚刚结束文化课还是情有可原，一切都会好起来的！

T1 [USACO09DEC] Cow Toll Paths G

题意：
给定 \(n,n\le300\) 个点，\(m,m\le1e4\) 条边的无向图，给出 \(q,q\le1e4\) 次询问求出点 \(u\)，\(v\) 直接的定义路径的权值（权值为路径上的点权最大值与路径上所有边权之和）

赛时做法：
我们发现直接在这个图上跑任何最短路算法都是无用的，无法把路径上点权最大值这个东西加到贡献中，所以我们可以枚举最大值然后再跑最短路的时候限制点权，时间复杂度(如果是堆优化迪杰斯特拉求单源最短路)为 \(O(300n(n+m)log_n)\)，可以优化但没必要了往下了分析了

赛事稍微优化了一点的代码 
const int maxn=330;
const int maxm=1e4+100;
int a[maxn],n,m,q;

int head[maxm<<1],to[maxm<<1],nx[maxm<<1],w[maxm<<1],cnt;
inline void add(int u,int v,int val)
{
	++cnt;
	to[cnt]=v;
	w[cnt]=val;
	nx[cnt]=head[u];
	head[u]=cnt;
}

ll dis[330][330],d[330];
bool vis[330];
priority_queue<pii>pq;

inline void dj(int o,int cp)
{
	if(cp<a[o])return;
	
	memset(vis,0,sizeof vis);
	memset(d,0x7f,sizeof d);
	
	d[o]=0;
	pq.push({-d[o],o});
	while(pq.size())
	{
		int u=pq.top().se;
		pq.pop();
		
		if(vis[u])continue;
		vis[u]=1;
		
		for(int i=head[u],v;v=to[i],i;i=nx[i])
			if(a[v]<=cp and d[v]>d[u]+w[i])
			{
				d[v]=d[u]+w[i];
				pq.push({-d[v],v});
			}
	}
	
	for(int i=1;i<=n;++i)
		dis[o][i]=min(dis[o][i],d[i]+cp);
}

bool in[330];

int main()
{
	n=read(),m=read(),q=read();
	
	for(int i=1;i<=n;++i)
		a[i]=read();
 	
 	for(int i=1;i<=m;++i)
 	{
 		int u=read(),v=read(),val=read();
 		add(u,v,val);
 		add(v,u,val);
	}
	
	memset(dis,0x7f,sizeof dis);
	
	while(q--)
	{
		int u=read(),v=read();
		if(!(in[u] or in[v]))
		{
			for(int j=1;j<=n;++j)
				dj(u,a[j]);
			in[u]=1;
		}
			
		if(!in[u])swap(u,v);
		__print(dis[u][v]==dis[0][0]?-1:dis[u][v]);
	}
 
	return 0;
}

solution：

就像之前我们发现的那样，在找到的最短路径上去寻找最大值这个东西其实是分割的，答案不一定对，所以还是得去枚举最大值，其实看见 \(n\) 的范围不难想到 \(floyed\)，此时就需要对 \(floyed\) 进行改进：
$\ \ \ \ \ \ \ $考虑到其根本原理为 \(DP\) ,可以在其基础上加东西

一般 \(floyed\)

for(int k=1;k<=n;++k)
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
             f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

最原始的 \(f\) 数组是有三维，\(f_{k,i,j}\)表示 在只经过编号小于 \(k\) 的点时，从 \(i\) 到 \(j\) 的最短路径
动态转移方程为：

\[f_{k,i,j}=\min(f_{k-1,i,j},f_{k-1,i,k}+f_{k-1,k,j}) \]

和背包同理可以优化掉一维
如果对 \(floyed\) 理解稍微深刻那么一点的话，就会想到我们可以根据点权排序这样就便于在更新最短路时知道这条路径的上的点权最大值了，即为 \(val[\max(\max(i,j),k)]\)
核心代码：

for(int k=1;k<=n;++k)
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            dis[i][j]=min(dis[i][j],f[i][k]+f[k][j]+val[max(k,max(i,j))]);
            f[i][j]=min(f[i][j],f[i][k]+f[k][j])
        }
正解 
struct node
{
	int w,id;
	bool operator < (const node A) const
	{
		return w<A.w;
	}
}nd[330];
int rk[330];

int dis[330][330],d[330][330];

int main()
{
	int n=read(),m=read(),q=read();
	for(int i=1;i<=n;++i)
		nd[i].w=read(),nd[i].id=i;
	
	sort(nd+1,nd+1+n);
	for(int i=1;i<=n;++i)
		rk[nd[i].id]=i;
	
	M(dis,0x3f),M(d,0x7f);
	for(int i=1;i<=n;++i)
		dis[i][i]=0;
		
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read(),w=read();
		u=rk[u],v=rk[v];
		dis[v][u]=dis[u][v]=min(dis[u][v],w);
	}
	
	for(int k=1;k<=n;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
			{
				d[i][j]=min(d[i][j],dis[i][k]+dis[k][j]+nd[max(k,max(i,j))].w);
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		
	while(q--)
	{
		int u=read(),v=read();
		u=rk[u],v=rk[v];
		__print(d[u][v]);
	}
	
	return 0;
}

总结：
赛时没能想到正解，有些遗憾，但确实是对 \(floyed\) 这个算法的掌握不太到位，也算是弥补了缺漏了，感觉这也是模拟赛的意义吧

T2 [POI2008] KUP-Plot purchase

题意：给定一个全为正整数的 \(n×n\) 的矩阵，求出他的一个子矩阵使其元素和在区间 \([k,2k]\)，要求输出方案

赛时做法： \(O(n^3)\) 暴力，先求出二维前缀和，枚举每个点作为一个子矩阵的右下角，然后从最左下单调优化去寻找左上角的点

solution：
分类讨论+单调栈优化
首先若直接有属于 \([k,2k]\) 的元素则直接就能输出答案
并且属于 \([2k,+∞]\) 的元素肯定是不能被选入答案矩阵的
这个时候我们如果我们找到了一个和大于 \(2k\) 且含有的全为小于 \(k\) 的子矩阵就能发现一个性质
答案肯定在这个子矩阵中
为啥？我们可以每次减去这个子矩阵的顶部的那一行，有三种情况

  1. 值还是大于 \(2k\) ，继续减去一行
  2. 值在 \([k,2k]\) ，即为答案
  3. 值小于 \(k\) ，说明减去的那一行值会大于 \(k\)，而他又只是一行，且其中的元素都小于 \(k\)，那么答案肯定就在这被减去的一行中

对于第三种情况在代码实现时一般时从上往下枚举子矩阵的下界的，所以不会有第三种情况，在枚举答案行时就已经把答案判断出来了

然后这个题目就变为了求最大子矩阵的值是多大，若大于等于 \(k\) 则有解，反之无解
类似单调栈优化题目有最大子矩阵，只不过这题是求最大面积，而这个题也类似需要枚举所有面积尽可能大的去求最大子矩阵之和

正解 
const int maxn=2200;
ll a[maxn][maxn],mp[maxn][maxn],s[maxn][maxn];

ll get(int x,int y,int a,int b)
{
	return s[a][b]-s[a][y-1]-s[x-1][b]+s[x-1][y-1];
}

ll n,k;
 
void put(int x,int y,int a,int b)
{
	for(int i=x;i<=a;++i)
		if(get(i,y,a,b)<=2*k)
		{
			cout<<y<<' '<<i<<' '<<b<<' '<<a<<endl;
			exit(0);
		}
}

ll st[maxn],top,w[maxn];

int main()
{
	
	k=read(),n=read();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
		{
			a[i][j]=read();
			if(a[i][j]>=k and a[i][j]<=2*k)
			{
				cout<<j<<" "<<i<<" "<<j<<" "<<i<<endl;
				return 0;
			}
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
			if(a[i][j]<k)mp[i][j]=mp[i-1][j]+1;
		}
	
	for(int i=1;i<=n;++i)
	{
		
		for(int j=1;j<=n+1;++j)
		{
			int tmp=0;
			while(mp[i][j]<st[top])
			{
				tmp+=w[top];
				if(get(i-st[top]+1,j-tmp,i,j-1)>=k)
					put(i-st[top]+1,j-tmp,i,j-1);
				--top;
			}
			st[++top]=mp[i][j];
			w[top]=tmp+1;
		}
		M(st,0);
		M(w,0);
		top=0;
	}
	
	puts("NIE");
	
	return 0;
}

总结：
赛时的确是嗅到了单调栈优化的味道，也想过像这样的时间复杂度明显的矩阵类题目最终一般都会转化为求最大最小矩阵类问题，最终败在了分讨思想上

T3 Please, another Queries on Array?

题意：给定一个序列，有两个操作：1.区间乘上一个数；2.求区间积的欧拉函数对 \(1e9+7\) 取模（序列元素值和修改乘上的值都小于等于300）

solution:
线段树+状压
对于欧拉函数的定义有

\[φ(n)=n*\prod\frac{p_i-1}{p_i} \]

我们可以把这个式子拆成几个部分

\[φ(n)=n*\frac{1}{\prod p_i}*\prod p_i \]

那么回到本题利用线段树能很好求出区间积，并且区间修改也非常方便，完成第一部分的求解
注意到所有值都小于300，那么质数就会有62个，可以装压维护更新区间质数的存在情况，在线段树上做一点小修改就可以了，最后对第二部分求下逆元即可

正解 
int prime[330],phi[330],top;
bool vis[330];
bitset<65>num[330];

void pre()
{
	for(int i=2;i<=300;++i)
	{
		if(!vis[i])prime[++top]=i;
		for(int j=1;j<=top and i*prime[j]<=300;++j)
		{
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
	
	for(int i=2;i<=300;++i)
	{
		for(int j=1;j<=top and prime[j]<=i;++j)
			if(i%prime[j]==0)
				num[i][j]=1;
	}
}

const int maxn=4e5+10;
const int mod=1e9+7;
int a[maxn];

ll qk(ll a,ll b,int mod)
{
	ll ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}

ll get_ny(ll a,ll mod)
{
	return qk(a,mod-2,mod);
}

struct seg
{
	struct node
	{
		int ls,rs;
		bitset<65>tmp,lz;
		ll s,tag;
		#define ls(x) tr[x].ls
		#define rs(x) tr[x].rs
		#define s(x) tr[x].s
		#define tag(x) tr[x].tag
		#define tmp(x) tr[x].tmp
		#define lz(x) tr[x].lz
	}tr[maxn<<2];
	
	void push_up(int o)
	{
		s(o)=s(ls(o))*s(rs(o))%mod;
		tmp(o)=tmp(ls(o))|tmp(rs(o));
	}
	
	void push_down(int o,int l,int r)
	{
		if(tag(o)!=1)
		{
			tmp(ls(o))|=lz(o);
			tmp(rs(o))|=lz(o);
			lz(ls(o))|=lz(o);
			lz(rs(o))|=lz(o);
			
			int mid=(l+r)>>1;
			s(ls(o))=s(ls(o))*qk(tag(o),mid-l+1,mod)%mod;
			s(rs(o))=s(rs(o))*qk(tag(o),r-mid,mod)%mod;
			tag(ls(o))=tag(ls(o))*tag(o)%mod;
			tag(rs(o))=tag(rs(o))*tag(o)%mod;
			tag(o)=1;
		}
	}
	
	void build(int o,int l,int r)
	{
		tag(o)=1;
		if(l==r)
		{
			s(o)=a[l];
			tmp(o)=num[a[l]];
			return;
		}
		ls(o)=o<<1,rs(o)=ls(o)+1;
		int mid=(l+r)>>1;
		build(ls(o),l,mid);
		build(rs(o),mid+1,r);
		push_up(o);
	}
	
	void mul(int o,int l,int r,int x,int y,ll v,bitset<65> b)
	{
		push_down(o,l,r);
		if(x<=l and r<=y)
		{
			s(o)=s(o)*qk(v,r-l+1,mod)%mod;
			tag(o)=tag(o)*v%mod;
			tmp(o)|=b;
			lz(o)|=b;
			return;
		}
		int mid=(l+r)>>1;
		if(x<=mid)mul(ls(o),l,mid,x,y,v,b);
		if(y>mid)mul(rs(o),mid+1,r,x,y,v,b);
		push_up(o);
	}
	
	pair<ll,bitset<65>> query_mul(int o,int l,int r,int x,int y)
	{
		push_down(o,l,r);
		if(x<=l and r<=y)return {s(o),tmp(o)};
		int mid=(l+r)>>1;
		ll res=1;
		bitset<65>ans;
		if(x<=mid)
		{
			auto it=query_mul(ls(o),l,mid,x,y);
			res=res*it.fi%mod;
			ans|=it.se;
		}
		if(y>mid)
		{
			auto it=query_mul(rs(o),mid+1,r,x,y);
			res=res*it.fi%mod;
			ans|=it.se;
		}
		return {res,ans};
	}
}tree;

int main()
{
	pre();
		
	int n=read(),q=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	
	tree.build(1,1,n);
	
	while(q--)
	{
		char op[5];
		cin>>op;
		int l=read(),r=read();
		if(op[0]=='M')
		{
			int v=read();
			tree.mul(1,1,n,l,r,v,num[v]);
		}
		else
		{
			auto it=tree.query_mul(1,1,n,l,r);
			ll ans=it.fi,bt=1,up=1;
			for(int i=1;i<=top;++i)
				if(it.se[i])
					bt=bt*prime[i]%mod,
					up=up*(prime[i]-1)%mod;
			bt=get_ny(bt,mod);
			printf("%lld\n",ans*bt%mod*up%mod);
		}
	}
	
	return 0;
}

T4 [POI2015] ODW

题意:给定一颗带点权的树，第 \(i\) 次询问 回答从一点到另一点，中间间隔走 \(c_i\) 个边到达的点累加其点权的值

solution：
根号分值
首先对于树上路径问题一般得求lca，这里建议用倍增求，当然长链剖这题也很好
对于间隔 \(c_i\) 大于 \(\sqrt{n}\) 的可以直接利用倍增的 \(fa\) 数组直接暴力跳，该情况时间复杂度上界为 \(O(\sqrt{n})\)
对于间隔 \(c_i\) 小于 \(\sqrt{n}\) 的我们可以预处理求出每个点在跳的间隔在 \([1,\sqrt{n}]\) 下的到根部的答案，每次回答就直接用两个点的这个预处理之和减去两点的 \(lca\) 分别往上最近匹配上的点的预处理，利用动规转移，预处理时间复杂度 \(O(n\sqrt{n}log_n)\)

细节比较多

正解 
const int maxn=50000+10;
int head[maxn],to[maxn<<1],nx[maxn<<1],cnt;
void add(int u,int v)
{
	++cnt;
	to[cnt]=v;
	nx[cnt]=head[u];
	head[u]=cnt;
}

int a[maxn],d[maxn],c[maxn],n;

int dep[maxn],fa[maxn][20],jp[maxn][240];

void dfs1(int o,int f)
{
	dep[o]=dep[f]+1;
	fa[o][0]=f;
	for(int k=1;k<=16;++k)
		fa[o][k]=fa[fa[o][k-1]][k-1];
	
	for(int i=head[o],v;v=to[i],i;i=nx[i])
		if(v!=f)
			dfs1(v,o);
}

int getfa(int o,int k)
{
	for(int i=0;i<16;++i)
		if(k&(1<<i))
			o=fa[o][i];
	
	return o;
}

int getlca(int u,int v)
{
	if(dep[u]<dep[v])swap(u,v);
	
	for(int k=16;k>=0;--k)
		if(dep[fa[u][k]]>=dep[v])u=fa[u][k];
	
	if(u==v)return u;
	
	for(int k=16;k>=0;--k)
		if(fa[u][k]!=fa[v][k])
			u=fa[u][k],v=fa[v][k];
		
	return fa[u][0];
}

void dfs2(int o,int f)
{
	for(int i=1;i*i<=n;++i)
		jp[o][i]=jp[getfa(o,i)][i]+a[o];
	
	for(int i=head[o],v;v=to[i],i;i=nx[i])
		if(v!=f)
			dfs2(v,o);
}

bool f;
int go_to(int st,int go,int l)
{
	int ans=0;
	while(dep[st]>=dep[go])
	{
		ans+=a[st];
		st=getfa(st,l);
		if(st==go)f=1;
	}
	return ans;
}

int del(int st,int go,int mod)
{
	int ans=0;
	int d=(dep[go]%mod-dep[st]%mod+mod)%mod;
	if(!d)f=1,d+=mod;
	return jp[getfa(go,d)][mod];
}

signed main()
{
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read();
		add(u,v);
		add(v,u);
	}
	
	for(int i=1;i<=n;++i)
		d[i]=read();
	
	for(int i=1;i<n;++i)
		c[i]=read();
	
	dfs1(1,0);
	dfs2(1,0);
	
	for(int i=1;i<n;++i)
	{
		int u=d[i],v=d[i+1],k=c[i];
		int lca=getlca(u,v);
		f=0;
		if(k*k<=n)__print(jp[u][k]+jp[v][k]-del(u,lca,k)-del(v,lca,k)-(f?a[lca]:0));
		else __print(go_to(u,lca,k)+go_to(v,lca,k)-(f?a[lca]:0));
	}
	
	return 0;
}

总结：这题没写暴力，因为感觉就算暴力得分也不会太乐观，错误的想法QQ，想到了倍增暴力往上跳但时间复杂度怎么分析都不对。这题算是收获最大的一道题吧，根号分治

标签：总结,return,7.12,int,矩阵,tag,maxn,模拟,mod
From： https://www.cnblogs.com/yun233/p/18299117

相关文章

  • CSP提高组模拟1
    T1很明显的最短路floyed算法，但是这个最大的点权却不是很好维护，但我们可以想到枚举最大的点权其实就可以相当于枚举floyed中的k，那么这时我们要对k进行一个排序操作，使得我们每次枚举的中转点k为枚举经过路径的点权最大的点从而达到同时走最短路并维护点权最大值。点击查看代码#......
  • 周总结7.12
    本周呢个人基本掌握了java当中的一些基本的语法，和之前所学的c++,c有很多出入，所以学习起来会轻松很多，最主要的是本人学习了MySQL语句的基础篇已经学完了，了解到了MySQL的基本语法DDL,DML,DQL,DCL根据学习呢我明白了对于以后进行软件开发主要学习的是DML与DQL增删改查的一些操作，其中......
  • JavaScript调试技巧总结
    debug javascript最全面的JavaScript调试技巧总结本文将一一讲解各种前端JS调试技巧，也许你已经熟练掌握，那让我们一起来温习，也许有你没见过的方法，不妨一起来学习，也许你尚不知如何调试，赶紧趁此机会填补空白。Thisentrywaspostedin Review andtagged debug, javasc......
  • 设计模式与分布式架构实战 总结
    在当今快速发展的软件工程领域，掌握设计模式和分布式架构对于构建高效、稳定、可扩展的系统至关重要。以下是对相关内容的进一步分析和梳理，供大家参考。架构设计的哲学：NP问题的现实映射什么是NP问题？NP问题是计算机科学中的一个重要概念，它代表了一类可以在多项式时间内验证......
  • vim命令总结
    vim命令1、touch创建文件2、vim或vi编辑文件3、vim文件名4、vim编辑器共分为三种模式：（1）命令模式esc或ctrl+c（2）编辑模式按i键（3）底层命令模式先进入命令模式=shift+：=输入命令5、快捷键（1）enter键换行（2）backspce退格键，删除光标前一......
  • CSP提高组模拟1
    我的微軟輸入法莫名其妙變成繁體了，你們有什麽頭緒嗎狀態題目20TimeExceededA最短路25TimeExceededB方格取数0TimeExceededC数组70TimeExceededD树A.最短路我赛时想了想，会不会DIJ不是很对，因为这个题在打的时候觉得，在跑最短路的时候......
  • 闲话 24.7.12
    闲话？？？？这luogu编译器怎么回事在本地和at上都能过编，在luogu上就过不了？xdm有遇到过这种事情的吗推歌：朝死暮生by北山薇etal.feat.洛天依AI补题P10324对一棵\(2n+1\)个点的有标号树，称它是好的，当且仅当树上每个点具有一个\(\{0,1,2\}\)中的权值，其中恰有\(1\)个......
  • day10-stack&Queue-part01-7.12
    tasksfortoday:1.理论基础2.232用栈实现队列3.225用队列实现栈4.20有效的括号5.1047删除字符串中所有相邻重复项--------------------------------------------------------------------------1.理论基础stack:firstinlastout     head    ......
  • 2024.7.12 模拟赛
    A容易观察到每个“\(1\)”相当于是独立的，那么其位置越靠后越优，则对于\(i=1\ton-1\)，每次都为\(a_i\)选择一个最大的满足\(i+2^t\leqn\)的\(t\)全部进行操作最优。使用__builtin_clz函数做到\(O(n)\)，暴力算\(t\)做到\(O(n\logV)\)。B要想求出每个前缀的答案，就......
  • 【 2024！深入了解 大语言模型（LLM）微调方法（总结）】
    文末有福利！引言众所周知，大语言模型(LLM)正在飞速发展，各行业都有了自己的大模型。其中，大模型微调技术在此过程中起到了非常关键的作用，它提升了模型的生成效率和适应性，使其能够在多样化的应用场景中发挥更大的价值。那么，今天这篇文章就带大家深入了解大模型微调。其中主要......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99