全国大学生算法竞赛秋季赛习题

Problem A 智慧果

题面
已知序列 a：
$a_1=1,a_2=2,a_3=3$
$a_i=a_{i-1}{a}_{i-2}{a}_{i-3}+a_{i-1}+a_{i-2}+a_{i-3}$
求 $a_{1000}$ 对 100000 取模的值。

题解
$暴力计算每一项对100000取模的值即可。$
$时间复杂度O(n)，其中n为项数。$

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){//经典了，竞赛的手动读入模板，需要记忆
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int p=100000;
// int qp(int x,int y)
// {
// 	int res=1;
// 	for(int t=x; y; y>>=1,t=t*t%p) if(y&1) res=res*t%p;
// 	return res;
// }//快速幂模板，写着玩玩，在这题不用
int a[100003];
signed main()
{
	a[1]=1;
	a[2]=2;
	a[3]=5;//初始化
	for(int i=4; i<=1000; ++i)
	{
		a[i]=a[i-1]*a[i-2]*a[i-3]+a[i-1]+a[i-2]+a[i-3];//带入公式
		a[i]%=p;//暴力取模
	}
	printf("%lld\n",a[1000]);
	return 0;
}

Problem B Xanadu#

题面

$给定一个n\times n的01矩阵$，$和n个点的图。你可以花费1的代价$$将矩阵中的一个1变成0。$
$操作完成后，记第i行从左到右第一个为1的位置为j，$$则在图上从i到j之间连一条有向边。$
(言下之意，为利用稀疏矩阵表示拓扑图)

问至少要花费多少代价，才能让图上存在一条从 1 到 n 的路径，如果无法达成输出 −1。

$n\le 300$

题解

基环树：无向图，一个环，环上每个点都是树根

不难发现最后得到的一定是一棵基环树，因此如果有路径，必然存在一条无环的路径，即每个点仅经过一次。
我们对于矩阵建图。假设第$i$ 行的第 $j$ 个位置是该行第 $k个1$，我们就从 $i到j建一条费用为k-1$ 的边。

不难发现，最后得到的每条从 1 到 n 的路径的边权总和就是这个方案要花费的代价，因此直接在原图上跑最短路即可。

时间复杂度$O(n^2)$或 $O(n^{2}logn)$。
简而言之，就是最短路径问题！
注意本题是有向图，因此矩阵不是对称矩阵。

样例

输入

4
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0

输出

0//因为已经连通了

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){//读入数据的模板
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > q;//把STL用到极致了
vector<pair<int,int> > v[1000003];
int dis[1000003];
bool vis[1000003];
signed main()//int main的另一种写法
{
    int n=read();//nxn矩阵
    int s=1;
    memset(dis,0x3f,sizeof(dis));//初始化距离为最大值
    for(int i=1; i<=n; i++) 
	{
		int s=0;
		for(int j=1;j<=n;j++)
		{
			int x=read();
			if(x==0)continue;
			v[i].push_back(make_pair(j,s));//读入某列，然后是第几个，
			//这个第几个是要干嘛呢？
			s++;
		}
	}
    dis[s]=0/*最后点数为什么是0？*/,q.push(make_pair(0,s));
    while(!q.empty())
    {
    	int x=q.top().second;
    	q.pop();
    	if(vis[x]) continue;
    	vis[x]=1;
    	for(pair<int,int> y:v[x]) 
    		if((!vis[y.first])&&dis[y.first]>dis[x]+y.second) 
    			dis[y.first]=dis[x]+y.second,
    			q.push(make_pair(dis[y.first],y.first));
    }
    	if(dis[n]>1e12) puts("-1");
    	else printf("%lld\n",dis[n]);
	return 0;
}

Problem C 这是一道大难题

题面

给定一张图，求其必须包含给定一条边的最小生成树。
$n\le 10^5,m\le 2\times 10^5$。

题解

直接先加入这条边，然后跑 $Kruskal$算法即可。
正确性显然。

时间复杂度为 $O(mlogm+n\alpha (n))$。

代码

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
/* 编译优化的奇技淫巧
1 #pragma comment(linker, "/stack:200000000")
2 #pragma GCC optimize("Ofast,no-stack-protector")
3 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
4 #pragma GCC optimize("unroll-loops")
*/
#include <stdio.h>
#include <string.h> 
#include <algorithm>
#include <bitset>
#define od(x) printf("%d",x)
#define odb(x) printf("%d ",x)
#define odl(x) printf("%d\n",x)
#define odp(x,y) printf("%d %d\n",x,y)
#define ol(x) puts("")
#define old(x) printf("%lld",x)
#define oldb(x) printf("%lld ",x)
#define oldl(x) printf("%lld\n",x)
#define oldp(x,y) printf("%lld %lld\n",x,y)//plus
#define rg(x) for(int i=1;i<=(x);i++){
#define gr }
#define rrg(x) for(int i=0;i<(x);i++)
#define rdln(a) a[i]=read();
#define rdln0(a,x) rrg(x) rdln(a) gr
#define rdln1(a,x) rg(x) rdln(a) gr
#define int long long
inline int read()//自定义一个读入
{
	int num=0,f=1;char c=getchar();
	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
	while(c>47&&c<58)num=num*10+(c^48),c=getchar();
	return num*f;
}
inline int re1d()
{
	char c=getchar();
	while(c<48||c>49)c=getchar();
	return c&1;
}
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
int fa[200005];
inline int find(int x)
{
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
inline int uni(int x,int y)
{
	int fx=find(x),fy=find(y);
	if(fx==fy)return 0;
	fa[fx]=fy;
	return 1;
}
struct e{
	int u,v,w;
	bool operator<(const e &b)const
	{
		return w<b.w;
	}
}a[200005];
signed main()
{
	int n=read(),m=read();
	long long c=0;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)a[i].u=read(),a[i].v=read(),a[i].w=read();
	int x=read();
	c+=uni(a[x].u,a[x].v)*a[x].w;
	std::sort(a+1,a+1+m);
	for(int i=1;i<=m;i++)c+=uni(a[i].u,a[i].v)*a[i].w;
	oldl(c);
	return 0;
}

Problem D zeal

题面

$给定长度为n的序列a，m次求[l,r]中出现k次的元素数量。$

$n,m,a_i\le 4\times 10^4$

题解

直接上莫队算法即可。

#### 样例
输入

10 2
1 2 3 1 1 2 1 2 3 1
1 5 3
2 9 3

输出

1
2

时间复杂度 $O(n\sqrt{m}$

文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_54227557/article/details/120923053