WEEK_3（蓝桥杯）

发布于：2024-04-21 ⋅ 阅读:(141) ⋅ 点赞:(0)

虽然题目是蓝桥杯，而且我也的确去参加了蓝桥杯，但是我并不打算写蓝桥杯的题目（主要是我真的没做出来几题www |_|)（要是想看怎么做蓝桥杯题目，建议去B站看BrotherCall大佬的题解），那么这一周，要我来写总结的话，我就写点备赛情况吧

我先回去看自己写的博客，看一节做一点题目，把之前的知识复习一遍，然后开始做题

针对之前没有的算法，我就没有重点看了，主要是看了往年考过的算法，然后根据自己意愿又做了几道其他的题，如下：

P3385 【模板】负环

到今天才写这一题。。因为觉着没啥必要写，但是，一写我发现，还真没有太大必要。。

怎么说呢，可能我做的题目还不多，我还不知道这个SPFA到底有啥用，就按照别人说的，遇到了可以多次判断更短路径的时候就说明有负环，然后整体算法和dij很像

代码：

#include<bits/stdc++.h>
using namespace std;
#define pr pair<int,int>
#define ll long long
#define INF 0x3f3f3f3f
const int N=1e5+5;
int t;
int n,m;
int cnt;
int head[N<<2];
int dis[N<<1];
int tot[N<<1];
int vis[N<<1];
priority_queue<pr,vector<pr>,greater<pr> >q;
struct ee
{
	int to,from,val;
}edge[N<<2];
void add(int u,int v,int w)
{
	cnt++;
	edge[cnt].to=v;
	edge[cnt].val=w;
	edge[cnt].from=head[u];
	head[u]=cnt;
}
bool bfs()
{
	dis[1]=0;
	tot[1]=0;
	vis[1]=1;
	q.push(make_pair(1,0));
	while(!q.empty())
	{
		pr k;
		k=q.top();
		q.pop();
		int u=k.first;
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].from)
		{
			int v=edge[i].to;
			int w=edge[i].val;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				tot[v]=tot[u]+1;
				if(tot[v]>n)
				return true;
				if(!vis[v])
				{
					q.push(make_pair(v,dis[v]));
					vis[v]=1;
				}
			}
		}
	}
	return false;
}
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		memset(vis,0,sizeof(vis));
		memset(tot,0,sizeof(tot));
		memset(edge,0,sizeof(edge));
		memset(head,0,sizeof(head));
		memset(dis,INF,sizeof(dis));
		for(int i=1;i<=m;i++)
		{
			int u,v,w;
			cin>>u>>v>>w;
			add(u,v,w);
			if(w>=0)
			add(v,u,w);
		}
		if(bfs())
		cout<<"YES"<<endl;
		else
		cout<<"NO"<<endl;
	}
}

P2023 [AHOI2009] 维护序列

很普通的一道线段树，主要是用来熟熟手的，不过里面lazy标记我觉得挺不错，给我拓宽了眼界hhh，就是乘法和加法的结合：（其实也就是先乘后加）

void pushdown(ll rt)
{
	tree[rt<<1].num=(tree[rt<<1].num*tree[rt].lazymul)%p;
	tree[rt<<1|1].num=(tree[rt<<1|1].num*tree[rt].lazymul)%p;
	tree[rt<<1].num=(tree[rt<<1].num+tree[rt].lazyadd*(tree[rt<<1].right-tree[rt<<1].left+1))%p;
	tree[rt<<1|1].num=(tree[rt<<1|1].num+tree[rt].lazyadd*(tree[rt<<1|1].right-tree[rt<<1|1].left+1))%p;
	tree[rt<<1].lazymul=(tree[rt<<1].lazymul*tree[rt].lazymul)%p;
	tree[rt<<1|1].lazymul=(tree[rt<<1|1].lazymul*tree[rt].lazymul)%p;
	tree[rt<<1].lazyadd=(tree[rt<<1].lazyadd*tree[rt].lazymul+tree[rt].lazyadd)%p;
	tree[rt<<1|1].lazyadd=(tree[rt<<1|1].lazyadd*tree[rt].lazymul+tree[rt].lazyadd)%p;
	tree[rt].lazyadd=0;
	tree[rt].lazymul=1;
}

然后就是常规操作了，代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
ll n,p,m;
ll op;
ll a[N];
struct tt
{
	ll left;
	ll right;
	ll num;
	ll lazyadd;
	ll lazymul;
}tree[N<<2];
void pushup(ll rt)
{
	tree[rt].num=(tree[rt<<1].num+tree[rt<<1|1].num)%p;
}
void pushdown(ll rt)
{
	tree[rt<<1].num=(tree[rt<<1].num*tree[rt].lazymul)%p;
	tree[rt<<1|1].num=(tree[rt<<1|1].num*tree[rt].lazymul)%p;
	tree[rt<<1].num=(tree[rt<<1].num+tree[rt].lazyadd*(tree[rt<<1].right-tree[rt<<1].left+1))%p;
	tree[rt<<1|1].num=(tree[rt<<1|1].num+tree[rt].lazyadd*(tree[rt<<1|1].right-tree[rt<<1|1].left+1))%p;
	tree[rt<<1].lazymul=(tree[rt<<1].lazymul*tree[rt].lazymul)%p;
	tree[rt<<1|1].lazymul=(tree[rt<<1|1].lazymul*tree[rt].lazymul)%p;
	tree[rt<<1].lazyadd=(tree[rt<<1].lazyadd*tree[rt].lazymul+tree[rt].lazyadd)%p;
	tree[rt<<1|1].lazyadd=(tree[rt<<1|1].lazyadd*tree[rt].lazymul+tree[rt].lazyadd)%p;
	tree[rt].lazyadd=0;
	tree[rt].lazymul=1;
}
void build(ll rt,ll l,ll r)
{
	tree[rt].left=l;
	tree[rt].right=r;
	tree[rt].lazyadd=0;
	tree[rt].lazymul=1;
	if(l==r)
	{
		tree[rt].num=a[l]%p;
		return ;
	}
	ll mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	pushup(rt);
}
void pointchange(ll rt,ll l,ll r,ll k)
{
	if(tree[rt].left>=l&&tree[rt].right<=r)
	{
		tree[rt].num=((tree[rt].num%p)*k)%p;
		tree[rt].lazymul=((tree[rt].lazymul%p)*k)%p;
		tree[rt].lazyadd=((tree[rt].lazyadd%p)*k)%p;
		return ;
	}
	if(tree[rt].lazyadd||tree[rt].lazymul!=1)
	pushdown(rt);
	ll mid=(tree[rt].left+tree[rt].right)>>1;
	if(l<=mid)
	pointchange(rt<<1,l,r,k);
	if(r>mid)
	pointchange(rt<<1|1,l,r,k);
	pushup(rt);
}
void pointadd(ll rt,ll l,ll r,ll k)
{
	if(tree[rt].left>=l&&tree[rt].right<=r)
	{
		tree[rt].num=(tree[rt].num%p+k*(tree[rt].right-tree[rt].left+1))%p;
		tree[rt].lazyadd=(tree[rt].lazyadd%p+k)%p;
		return ;
	}
	if(tree[rt].lazyadd||tree[rt].lazymul!=1)
	pushdown(rt);
	ll mid=(tree[rt].left+tree[rt].right)>>1;
	if(l<=mid)
	pointadd(rt<<1,l,r,k);
	if(r>mid)
	pointadd(rt<<1|1,l,r,k);
	pushup(rt);
}
ll query(ll rt,ll l,ll r)
{
	ll ans=0;
	if(tree[rt].left>=l&&tree[rt].right<=r)
	return tree[rt].num%p;
	if(tree[rt].lazyadd||tree[rt].lazymul!=1)
	pushdown(rt);
	ll mid=(tree[rt].left+tree[rt].right)>>1;
	if(l<=mid)
	ans=(ans%p+query(rt<<1,l,r)%p)%p;
	if(r>mid)
	ans=(ans%p+query(rt<<1|1,l,r)%p)%p;
	return ans%p;
}
int main()
{
	cin>>n>>p;
	for(ll i=1;i<=n;i++)
	cin>>a[i];
	build(1,1,n);
	cin>>m;
	for(ll i=1;i<=m;i++)
	{
		ll x,y,z;
		cin>>op;
		cin>>x>>y;
		if(op==1)
		{
			cin>>z;
			pointchange(1,x,y,z);
		}
		if(op==2)
		{
			cin>>z;
			pointadd(1,x,y,z);
		}
		if(op==3)
		cout<<query(1,x,y)%p<<endl;
	}
}

P2865 [USACO06NOV] Roadblocks G

最短路模版题，额，也不能说模版，我看是最短路和树形dp的树的直径求次大值结合起来的算法——将每一次判断大的赋给用来存最大值的变量，最大值存给次大值，或者直接存给次大值。

注意最后要判断，为了防止最后找到的是最短路，因此需要加上两次最短两点距离，表示重复走，作为次短路，代码：

#include<bits/stdc++.h>
using namespace std;
#define pr pair<ll,ll>
#define ll long long
#define INF 0x3f3f3f3f
const int N=2e5+5;
ll minn=1e9;
ll dis;
ll n,r;
ll cnt;
ll head[N<<2];
ll dis1[N<<1],dis2[N<<1];
ll vis[N<<1];
priority_queue<pr,vector<pr>,greater<pr> >q;
inline int read()
{
	int sum=0;
	char a=getchar();
	while(a<'0'||a>'9')
	a=getchar();
	while(a>='0'&&a<='9')
	{
		sum=(sum<<3)+(sum<<1)+a-'0';
		a=getchar();
	}
	return sum;
}
struct ee
{
	ll to,from,val;
}edge[N<<2];
void add(ll u,ll v,ll w)
{
	cnt++;
	edge[cnt].to=v;
	edge[cnt].val=w;
	edge[cnt].from=head[u];
	head[u]=cnt;
}
void bfs()
{
	memset(dis1,INF,sizeof(dis1));
	memset(dis2,INF,sizeof(dis2));
	dis1[1]=0;
	dis2[2]=0;
	q.push(make_pair(1,0));
	while(!q.empty())
	{
		pr k=q.top();
		ll u=k.first;
		ll dis=k.second;
		q.pop();
		for(ll i=head[u];i;i=edge[i].from)
		{
			ll v=edge[i].to;
			ll w=edge[i].val;
			if(dis1[v]>dis+w)
			{
				dis2[v]=dis1[v];
				dis1[v]=dis+w;
				q.push(make_pair(v,dis1[v]));
			}
			else if(dis2[v]>dis+w)
			{
				dis2[v]=dis+w;
				q.push(make_pair(v,dis2[v]));
			}
		}
	}
}
int main()
{
	r=read();n=read();
	for(ll i=1;i<=n;i++)
	{
		ll u,v,w;
		u=read(),v=read(),w=read();
		add(u,v,w);
		add(v,u,w);
		minn=min(w,minn);
	}
	bfs();
	if(dis1[r]==dis2[r])
	dis2[r]+=2*minn;
	cout<<dis2[r];
}

P5004 专心OI - 跳房子

矩阵快速幂，推导过程比较麻烦：

首先我们可以知道这样的式子：

dp[i]=1(i<=m+1)     因为只能向右跳格子，并且每次跳格子中间需要有m个空位，因此从无限远跳到小于等于m+1的格子有的情况只有一种

我们再这样想，i位置有的情况一定是i-m-1位置和前面位置的情况数之和，因为所有在i-m-1位置之前所有的点都有可能跳到i位置，因此有dp[i]=dp[i-m-1]+dp[i-m-2]+...+dp[1]，于是这样的式子会让我们自然地想到作差，因此s[i]=dp[i]-dp[i-1]=dp[i-m-1]，所以可以得到状态转移方程

\left\{\begin{matrix} dp[i]=i+1(i<=m+1)\\ dp[i]=dp[i-1]+dp[i-m-1](i>=m+1) \end{matrix}\right.

然后我们通过列举并画图，我们可以构造出矩阵：

\begin{bmatrix} 1&0 &0 &... &1 \\ 1& 0 & 0 & ...& 0\\ 0& 1 & 0 & ... & 0\\ 0& 0 &1 & ... & 0\\ \vdots &\vdots& \vdots & &0\\ 0& 0& 0& ... & 1 \end{bmatrix}

然后套模版，over

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=17,md=1e9+7;
ll n,m;
struct mat
{
	ll a[N][N];
}matrix;
mat ch(mat l,mat p)
{
	mat c;
	memset(c.a,0,sizeof(c.a));
	for(int i=1;i<=m+1;i++)
	for(int j=1;j<=m+1;j++)
	for(int k=1;k<=m+1;k++)
	c.a[i][j]=(c.a[i][j]%md+((l.a[i][k]%md)*(p.a[k][j])%md)%md)%md;
	return c;
}
mat fast_pow(mat ma,ll ti)
{
	ll k=ti;
	mat l;
	memset(l.a,0,sizeof(l.a));
	for(int i=1;i<=m+1;i++)
	l.a[i][i]=1;
	while(k)
	{
		if(k%2)
		l=ch(l,ma);
		ma=ch(ma,ma);
		k/=2;
	}
	return l;
}
int main()
{
	cin>>n>>m;
	matrix.a[1][1]=1;
	matrix.a[1][m+1]=1;
	for(int i=2;i<=m+1;i++)
	matrix.a[i][i-1]=1;
	mat ans,p;
	memset(ans.a,0,sizeof(ans.a));
	memset(p.a,0,sizeof(p.a));
	for(int i=1;i<=m+1;i++)
	ans.a[i][1]=1;
	p=fast_pow(matrix,n);
	ans=ch(p,ans);
	cout<<ans.a[1][1]%md<<" ";
}

下周天梯赛，打麻了，哥们儿加油！！

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布