本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-14 20:58:03

C.十年灯

题意

给出 $n$ 个点 $m$ 条边的无向图，在出发前可以进行下面两种操作其中一种任意次。

• 选择一个点的两条出边交换权值。
• 选择一个点连着的任意两条边交换权值。

求在最优操作后 $1$ 到 $n$ 的最短路。

思路

本题的关键在于两种操作，我们分别来分析。

对于第一种操作，我们考虑到最短路只会经过每个点最多一次，因此每个点的所有出边只会走最多一条，此时把最小的出边权值交换到这条边上即可。所以记录每个点最小的出边权值，在跑最短路更新时均用该权值更新即可。

对于第二种操作，我们发现实际上由于操作次数不限，整张图上所有边的权值均可以随意交换，因此我们只需要 Bfs 找到 $1$ 到 $n$ 所需的最少边数 $k$，再将最小的 $k$ 个边权交换过来即可。

代码

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=2e5+10;
const int M=4e5+10;
const int inf=1e18;
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;
}
int id,n,m,cnt,md[N],mn[N],d[N],s[M];
bool v[N];
struct edg
{
	int v,w;
};
vector <edg> edge[N];
void sol1()
{
	priority_queue <pii > q;
	for(int i=1;i<=n;i++)
	{
		mn[i]=d[i]=inf;
		for(edg e:edge[i]) mn[i]=min(mn[i],e.w);
	} 
	d[1]=0,q.push({0,1});
	while(!q.empty())
	{
		int u=q.top().second; q.pop();
		if(v[u]) continue;
		v[u]=1;
		for(edg e:edge[u])
		{
			int ne=e.v;
			if(d[ne]>d[u]+mn[u])
			{
				d[ne]=d[u]+mn[u];\/\/使用最小出边权更新 
				q.push({-d[ne],ne});
			}
		}
	}\/\/Dijkstra 
	cout<<d[n];
}
void sol2()
{
	queue <int> q;
	for(int i=1;i<=n;i++)
	{
		d[i]=inf;
		for(edg e:edge[i]) s[++cnt]=e.w;
	}
	sort(s+1,s+1+cnt);
	d[1]=0,q.push(1);
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		if(v[u]) continue;
		v[u]=1;
		for(edg e:edge[u])
		{
			int ne=e.v;
			if(!v[ne])
			{
				d[ne]=min(d[ne],d[u]+1);
				q.push(ne);
			}
		}
	}\/\/Bfs求1到每个点需要的最小边数 
	int res=0;
	for(int i=1;i<=d[n];i++) res+=s[i];\/\/选最小的若干个边权 
	cout<<res;
}
signed main()
{
	id=read(),n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),w=read();
		edge[u].push_back({v,w});
	}
	if(id==1) sol1();
	else sol2(); 
	return 0;
}

D.百战名

题意

给出一元二次方程 $ax^2+bx+c=0$ 以及 $n,p$，求该方程 $(x_1^n+x_2^n)\mod p$ 的值。

思路

考虑递推，需要推式子。

设 $f_i=x_1^i+x_2^i$，则有 $f_0=2,f_1=x_1+x_2$

$(x_1^{i-1}+x_2^{i-1})(x_1+x_2)=x_1^i+x_2^i+x_1^{i-1}x_2+x_1x_2^{i-1}=(x_1^i+x_2^i)+x_1x_2(x_1^{i-2}+x_2^{i-2})$

即 $(x_1+x_2)f_{i-1}=f_i+x_1x_2f_{i-2}$

整理得 $f_i=(x_i+x_2)f_{i-1}-x_1x_2f_{i-2}$

发现 $f_i$ 只与 $f_{i-1},f_{i-2}$ 有关，考虑构造矩阵加速递推。

因此有 $\begin{pmatrix} f_i & f_{i-1} \end{pmatrix} =\begin{pmatrix} f_{i-1} & f_{i-2} \end{pmatrix} \begin{pmatrix} x_1+x_2 & 1 \ -x_1x_2 & 0 \end{pmatrix}$，

即有$\begin{pmatrix} f_n & f_{n-1} \end{pmatrix} =\begin{pmatrix} f_{1} & f_{0} \end{pmatrix} \begin{pmatrix} x_1+x_2 & 1 \ -x_1x_2 & 0 \end{pmatrix}^{n-1}$

使用矩阵快速幂即可，要注意负数的取模。

代码

#include<iostream>
#define int long long
using namespace std;
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;
}
int a,b,c,p,n;
struct mat
{
	int s[2][2];
	void unit()
	{
		s[0][0]=s[1][1]=1,s[0][1]=s[1][0]=0;
	}
	void init()
	{
		s[0][0]=s[1][1]=s[0][1]=s[1][0]=0;
	}\/\/矩阵初始化 
	mat operator * (const mat &b) const
	{
		mat res; res.init();
		for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++)
			res.s[i][j]=(res.s[i][j]+s[i][k]*b.s[k][j]%p)%p;
		return res;
	}\/\/定义矩阵乘法 
}ini,base;
mat mpo(mat a,int b)
{
	mat res; res.unit();
	while(b)
	{
		if(b&1) res=res*a;
		a=a*a,b>>=1;
	}
	return res;
}\/\/矩阵快速幂 
int po(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1) res=res*a%p;
		a=a*a%p,b>>=1;
	}
	return res;
}
int inv(int a)
{
	return po(a,p-2);
}\/\/快速幂求逆元 
signed main()
{
	a=read(),b=read(),c=read(),p=read(),n=read();
	a%=p,b%=p,c%=p;
	int add=(-b*inv(a)%p+p)%p,cdot=c*inv(a)%p;
	ini.init();
	ini.s[0][0]=add,ini.s[0][1]=2;\/\/初始值 
	if(n==0) cout<<ini.s[0][1];
	else if(n==1) cout<<ini.s[0][0];
	else
	{
		base.s[0][0]=add,base.s[1][0]=-cdot,base.s[0][1]=1,base.s[1][1]=0;
		mat res=ini*mpo(base,n-1);
		cout<<(res.s[0][0]%p+p)%p;
	}
	return 0;
}

G.十万家

题意

每次给定整数 $N$，求使各位数字均不同且和为 $N$ 的最小值，无解输出 $-1$。

思路

显然，在数中有非前导 $0$ 会比去掉该 $0$ 后的值大，而数位和不变。因此答案中不含 $0$，这里只需考虑 $1$ 到 $9$。

还是显然，因为 $\sum_{i=1}^9 i=45$，所以 $45$ 及以下的数均可凑出解，而 $45$ 以上的数不可能凑出解。

那么对于有解的 $N$，首先要尽量使其位数少，因此从 $9$ 到 $1$ 依次枚举。其次要让高位尽量小，所以把 $9$ 到 $1$ 从低位向高位依次填即可。

代码

#include<iostream>
#define int long long
using namespace std;
const int N=2e5+10;
const int K=60+10;
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;
}
signed main()
{
	int T=read();
	while(T--)
	{
		int n=read();
		if(n>45) cout<<"-1"<<"\n";\/\/判无解 
		else for(int i=9;i>=1;i--)
		{
			if(n-i<=0)
			{
				cout<<n;
				for(int j=i+1;j<=9;j++) cout<<j;
				cout<<"\n";
				break; 
			}\/\/求完后输出 
			n-=i;
		}
	}
	return 0;
}

H.百万师

题意

给出长度为 $N$ 的数组 $A$，每个数可以 $+1,-1$ 或不变，问是否能将其变为等差数列。若能，求最小修改次数，修改次数最小的方案数和这些方案。

思路

考虑找等差数列中的首项 $A_1$ 和公差 $k$，发现对于前两个数 $A_1,A_2$ 来说，每个数有三种情况，因此两个数共有九种不同的首项和公差。

那么对于每一种可能的情况，暴力扫一遍整个数组，判断是否能够通过操作使其变为目标数列，再维护最小值和方案数即可。如此总时间复杂度为 $O(9N)$。

关于方案输出，只要记录每种方案的首项和公差，即可计算并输出该数列的每一项，同时也能按照要求排序。但是由于std中的枚举顺序为 $A_1$ 递增后 $A_2$ 递增，此处实际上不用排序。

代码

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e7+10; 
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;
}
void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x\/10);
	putchar(x%10+'0');
}
int T,n,cnt,mn,a[N];\/\/cnt为方案数，mn为最小操作数
struct nod
{
	int st,gc;
}ans[10];\/\/st,gc分别为首项和公差 
bool cmp(nod a,nod b)
{
	if(a.st==b.st) return a.gc<b.gc;\/\/公差小的第二项就小 
	else return a.st<b.st;
} 
signed main()
{
	T=read();
	while(T--)
	{
		n=read(),cnt=0,mn=n+1;
		for(int i=1;i<=n;i++) a[i]=read();
		for(int i=-1;i<=1;i++) for(int j=-1;j<=1;j++)
		{
			int tc=0,k=a[2]+j-(a[1]+i);\/\/tc为本次次数，k为公差 
			if(i!=0) tc++;
			if(j!=0) tc++;\/\/前两项所需操作 
			for(int l=3;l<=n;l++) 
			{
				int bz=a[1]+i+k*(l-1);\/\/这一项需要达到的值 
				if(a[l]==bz) continue;\/\/相等不操作 
				if(a[l]>=bz-1&&a[l]<=bz+1) tc++;\/\/相差1则操作数+1 
				else
				{
					tc=-1;
					break;
				} \/\/无法操作使其为这个等差数列，退出 
			}
			if(tc==-1) continue;\/\/同上 
			else
			{
				if(tc==mn)
				{
					cnt++;
					ans[cnt]={a[1]+i,k};
				}\/\/若有更多种最优情况，增加方案数 
				else if(tc<mn)
				{
					mn=tc;
					cnt=1;
					ans[cnt]={a[1]+i,k};
				}\/\/更新最优情况 
			}
		}
		if(!cnt)
		{
			write(-1);
			putchar('\n'); putchar('\n');
			continue;
		}\/\/无解 
		sort(ans+1,ans+1+cnt,cmp);\/\/按要求排序 
		write(mn); putchar('\n');
		write(cnt); putchar('\n');
		for(int i=1;i<=cnt;i++)
		{
			for(int j=0;j<n;j++) write(ans[i].st+j*ans[i].gc),putchar(' ');
			putchar('\n');
		}
		putchar('\n');\/\/按题意输出 
	}
	return 0;
}