文以载道（互测赛） CDGH 题解

· · 题解

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} 有关，考虑构造矩阵加速递推。

因此有

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;
}