本文章由 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;
}
鲁ICP备2025150228号