XJT/模拟赛1题解

数组 (array)

Array

根据合成规则容易发现一个被合成的数只会由$k^x$个连续的相同的数来组成，换句话说$b_{i}$必须满足$b_{i}=s*k^x$,所以原问题就转化成不断判断是否存在$k^x$个连续的s，我们考虑把$a_{i}$不断地除以k直到不能整除，这样就将$a_{i}$分解为$s*k^x$，接下来对$b_{i}$一个一个判断即可，详见参考代码。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=5e6;
int n,m,k;
bool flag;
int a[N],b[N],c[N],l;
int main()
{
    freopen("array.in","r",stdin);
    freopen("array.out","w",stdout);
    int t;scanf("%d",&t);
    while(t--)
    {
        flag=0;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)scanf("%d",&b[i]);
        for(int i=1;i<=n;i++)
        {
            c[i]=1;
            while(a[i]%k==0)a[i]/=k,c[i]*=k;
        }
        for(int i=1,j=1;i<=m;i++)
        {
            while(c[j]==0&&j<=n)j++;
            if(j>n){flag=1;break;}
            if(b[i]%a[j]!=0){flag=1;break;}
            int sum=b[i]/a[j];
            while(sum%k==0)sum/=k;
            if(sum!=1){flag=1;break;}
            sum=b[i]/a[j];
            if(c[j]>=sum)c[j]-=sum;
            else 
            {
                sum-=c[j];c[j]=0;
                while(a[j+1]==a[j]&&sum!=0&&j<n)
                {
                    if(sum>=c[j+1])
                    {
                        sum-=c[j+1];
                        c[j+1]=0;
                    } 
                    else c[j+1]-=sum,sum=0;
                    j++;
                }
                if(sum!=0){flag=1;break;}
            }
            if(flag)break; 
        }
        if(flag||c[n]!=0)printf("No\n");
        else printf("Yes\n");
    }
    return 0;
 }

行走 (walk)

Walk

假设在某个点之前我们已经到达了标号最小的位置，要想经过的标号最多就要使得终点标号变得尽量大，所以我们令所有的0尽可能的转化为k，但是同时也要考虑最后还要走回原点，令s为现在从头开始能走到的位置，对于每一个0能转化的值取决于后面的0的个数，设后面的0的个数为x，简单的推导可以发现这个值就是min(k,x*k-s),若得到的值小于-k则说明无法回到原点。枚举每一个时间，将该时间考虑在这个时间之前达到最小位置然后将所有的0填数字，最后取最大值，复杂度$O(n^2)$。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e4;
int cnt[N];
long long n,k;
long long ans;
long long tot;
long long a[N];
long long b[N];
int main()
{
    freopen("walk.in","r",stdin);
    freopen("walk.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i],tot+=a[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)b[j]=a[(i+j-2)%n+1];
        cnt[n+1]=0;
        for(int j=n;j>=1;j--)cnt[j]=cnt[j+1]+(b[j]==0);
        bool flag=0;
        long long s=tot,mi=b[1],ma=b[1],sum=0;
        for(int j=1;j<=n;j++)
        {
            if(b[j]==0)
            {
                b[j]=min(k,cnt[j+1]*k-s);
                if(b[j]<-k){flag=1;break;}
                s+=b[j];
            }
            sum+=b[j];
            mi=min(mi,sum);
            ma=max(ma,sum);
        }
        if(!flag&&s==0)ans=max(ans,ma-mi+1);
    }
    if(ans==0)cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

塔 (tower)

Tower

容易发现对于一个叶子节点v，任意一个经过v的路径都必然以v为端点。接下来我们将每个叶子节点的塔的效率增加1然后将其他所有节点的高度减1，直到所有的叶子节点都被删去，这时候我们加入新的叶子节点再次重复上述操作，但是此时我们增加的是被删去的节点的塔的效率，这样重复的操作下去就能得到最终的答案，当然由于题目的设定对于只剩一个节点的情况下，我们需要修改两个塔的效率，详见参考代码。

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
typedef long long ll;
using namespace std;
const int N=1e6; 
int n;
ll ans;
int d[N];
ll val[N];
vector<int>e[N];
pair<ll,int>s[N];
set<pair<ll,int>>S;
int main()
{
    freopen("tower.in","r",stdin);
    freopen("tower.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&val[i]);
        s[i]={val[i],i};
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        d[x]++;
        d[y]++;
        e[x].emplace_back(y);
        e[y].emplace_back(x);
    }
    ans=0;
    sort(s+1,s+n+1);
    for(int i=1;i<=n;i++)if(d[i]==1)S.insert({val[i],i});
    for(int i=1;i<=n;i++)
    {
        while(S.size()>0&&(*S.begin()).first<s[i].first)
        {
            int x=(*S.begin()).second;
            d[x]=-1;
            S.erase(S.begin());
            for(auto y:e[x])
            {
                d[y]--;
                if(d[y]==0||d[y]==1)S.insert({val[y],y});
            }
        }
        ans+=max(2ll,ll(S.size()))*(s[i].first-s[i-1].first);
    }
    printf("%lld",ans);
    return 0;
}

子串 (substr)

Substr

容易发现我们可以用一种朴素的dp来解决这个问题，定义$dp_{i,m}$为前i个字符中，删除序列的二进制串为m的情况下所能获得的最优答案，当然由于字符串的存储复杂所以显然时间复杂度和空间复杂度都是不合法的，因此我们考虑对这个算法进行优化。 对于存储相同长度字符串的两个状态$dp_{i1,m1},dp_{i2,m2}$，由于字典序的特殊性，显然我们只用保留字典序更小的方案，所以我们改变策略只用bool类型来存储是否有最小字典序的方案到达某个状态，详见代码。

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=1e4;
int n,m,M;
char c[N];
bool f[N][N];
int main()
{
    freopen("substr.in","r",stdin);
    freopen("substr.out","w",stdout);
    scanf("%s",c+1);
    n=strlen(c+1);
    m=log2(n);M=(1<<m)-1;
    memset(f,0,sizeof(f));
    for(int i=0;i<=n;++i)f[i][i]=1;
    for(int i=1;i<=n-M;++i)
    {
        char mi = 'z'; 
        for(int j=i-1;j-i+1<=M;j++) if(f[j][j-i+1])mi=min(mi,c[j+1]); 
        for(int j=i;j-i<=M;j++)f[j][j-i]=f[j-1][j-i]&(c[j]==mi); 
        for(int j=i;j-i<=M;j++)
        {
            for(int k=0;k<m&&j+(1<<k)-i<=M;k++)
            {
                if(!(((j-i)>>k)&1))f[j+(1<<k)][j+(1<<k)-i]|=f[j][j-i];
            }
        }
        putchar(mi);
    }
    return 0;
}

cf1696c cf1680d cf1637f cf938e