比赛链接

A题

大意

要你构造一个长度为\(n(n\le 100)\)的全排列，使得其有\(k\)个波峰

波峰的定义为\(a[i-1]\le a[i]\le a[i+1]\)

如果有答案任意输出一组答案,否则输出\(-1\)

思路

显然若要构造最多的波峰为在\(2,4,6....\)这些地方全部占满

则最多只有\(ma=\frac{n-1}{2}\)个波峰

若\(k>ma\)则直接输出\(-1\)

否在在\(2,4...2\times k\)这\(k\)个位置构造波峰即可

构造方法很简单

首先先设\(a[i]=i\)

然后在这\(k\)个位置中交换\(a[i],a[i+1]\)即可以得到答案

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,k;
int a[maxn];
signed main(){
    int _;scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++) a[i]=i;
        int ma=(n-1)/2;
        if(k>ma){
            printf("-1\n");
            continue;
        }
        for(int i=1;i<=k;i++){
            swap(a[2*i],a[2*i+1]);
        }
        for(int i=1;i<=n;i++){
            printf("%d ",a[i]);
        }
        printf("\n");
    }
    return 0;
}

B题

题意

给你一个长度为\(n(n\le2e5)\)的数组\(a\)

对这个数组进行全排列,看有多少个全排列情况满足对于任意\(i\)使得

\(a[1]\&a[2]\&..a[i]=a[i+1]\&a[i+2]\&..a[n]\)

思路

首先要知道一个简单的性质

\(a\&b\le\min(a,b)\)

首先根据题意

\(a[1]=a[2]\&a[3]\&...a[n]\)

则\(a[1]\le a[n]\)

\(a[n]=a[1]\&a[2]\&...a[n-1]\)

则\(a[n]\le a[1]\)

推导为\(a[1]=a[n]\)

且\(a[1]\&a[2]\&.....a[n]=a[1]\)

则显然\(a[1]\)必定是这个数组的最小值

而且由于\(a[1]=(a[2]\&a[3]\&...a[n-1])\&a[n]\)

那么\(a[2],a[3]...a[n-1]\)任意元素&\(a[1]\)必定还是\(a[1]\)

所以求出最小值的元素数量\(cnt\)

如果\(2\le cnt\)且所有元素\(\&\)上\(a[1]\)后还是\(a[1]\)

那么答案就是\(A_{cnt}^2\times (n-2)!\)

否则答案为\(0\)

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,k;
int a[maxn];
ll fac[maxn];
signed main(){
    fac[0]=1;
    for(int i=1;i<=2e5;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    int _;scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        sort(a+1,a+1+n);
        ll cnt=0;
        ll ans=-1;
        for(int i=1;i<=n;i++){
            if(a[i]==a[1]){
                cnt++;
            }
            if((a[i]&a[1])!=a[1]){
                ans=0;
            }
        }
        if(ans==-1){
            ans=cnt*(cnt-1)%mod*fac[n-2]%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
 

C题

大意

给你一个数字\(n(n\le 1e9)\),进行\(m(m\le 2e5)\)次操作

每次操作数字上的每一位数加\(1\)

如\(1912\)经过一次操作后变为\(21023\)

求\(m\)次操作后，最后数字的长度\(mod\;1e9+7\)

思路

比赛的时候看错题目了，以为求最后变成什么直接自闭

显然是动态规划

设\(dp[i][j]\)表示\(j\)数字经过\(i\)次变化后的长度为多少

考虑转移方程

• \(j\neq9\)

\(dp[i][j]=dp[i-1][j+1]\)

• \(j=9\)

若\(j=9\)则下一步就变成了\(10\)

则\(dp[i][9]=dp[i-1][1]+dp[i-1][0]\)

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,m;
ll dp[maxn][10];
signed main(){
    for(int i=0;i<=9;i++){
        dp[0][i]=1;
    }
    // j走了i步的长度
    for(int i=1;i<=2e5;i++){
        for(int j=0;j<=8;j++){
            dp[i][j]=dp[i-1][j+1];
        }
        dp[i][9]=(dp[i-1][1]+dp[i-1][0])%mod;
    }
    int _;scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&m);
        ll ans=0;
        while(n){
            ans=(ans+dp[m][n%10])%mod;
            n=n/10;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
 

D题

大意

给你一个长度为\(n(n\le2e5)\)的数组\(a(1\le a[i] \le1e9)\)和一个参数\(p(1\le p\le 1e9)\)

• \(i\)和\(i+1\)有一个长度为\(p\)的边

• 若\(gcd(a[i],a[i+1]...a[j])=\min(a[i],a[i+1]..a[j])\)，则\(i\)和\(j\)有一条长度为\(gcd(a[i],a[i+1]..a[j])\)的边

求这个数组的最小生成树

思路

观察性质

若\(i,j\)和可以连边，那么代表这个区间的元素都是\(min(a[i],a[i+1]...a[j])\)的倍数

然后本质上是模拟\(krushkal\)算法

要发现边要么是\(p\)要么就是\(a[i]\)

首先对\(a[i]\)进行排序，然后用双指针来判断区间\([l,r]\)可以用\(a[i]\)使得\([l,r]\)变为一个点,然后对这个区间进行标记。

使答案加\(a[i]\times(r-l)\)，最后再计算需要长度为\(p\)来联通的点

参考\(rk_1\)的代码

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn=2e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,p;
int a[maxn];
pii pa[maxn];
bool vis[maxn];
signed main(){
    int _;scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&p);
        for(int i=1;i<=n;i++){
            vis[i]=0;
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            pa[i]={a[i],i};
        }
        sort(pa+1,pa+1+n);
        ll ans=0;
        int rest=n-1;
        for(int i=1;i<=n;i++){
            if(pa[i].fi>p) break;
            if(vis[pa[i].se]) continue;
            int l=pa[i].se,r=pa[i].se;
            while(l>1&&!vis[l]&&a[l-1]%pa[i].fi==0) l--;
            while(r<n&&!vis[r]&&a[r+1]%pa[i].fi==0) r++;
            for(int i=l;i<=r;i++){
                vis[i]=1;
            }
            rest-=(r-l);
            ans+=1ll*(r-l)*pa[i].fi;
        }
        ans+=1ll*rest*p;
        printf("%lld\n",ans);
    }
    return 0;
}