题解

“Wishare杯”南邮第十一届大学生程序设计竞赛网络赛

A:简单的数学问题

大体思路为首先求出一个仅由47组成的最小的数,记为A,使其大于等于我们读入的数,。

然后再找一个最小的47数量相等的数,记为B,使B>=A。

首先我们对这个仅由47组成的数B进行讨论,我们假定这个序列长度为n

如果n为奇数很好办,因为答案要求47成对,也就是说答案长度为偶数,那么我们输出4*(n/2+1)和7*(n/2+1)即可

或者该数列长度虽然为偶数,但是它比这个长度内成对47能表示的最大数(即77…7744…44)还要大,那么我们也可以直接输出。

如果依旧不成立,我们就知道答案在这个长度内必定存在,那么我们从该数的个位开始往前比较,如果接下来能通过改变47使得该序列47数量一样多,那么我们就这样改变,并输出结果即可

因为采用了分段式做法,所以代码略长。实际上应该是有着能够一次解决的算法的。但是鉴于个人时间问题,这里就不去重写了。

#include<bits/stdc++.h>
using namespace std;
#define N 100010
char a[N],ans[N];
int num4[N],num7[N];
bool flag=false;
bool check(int n){
    for (int i=1;2*i<=n;i++)
        if (ans[i]=='4') return false;
    for (int j=n/2+1;j<=n;j++)
        if (ans[j]=='7') return true;
    return false;
}
int main(){
    scanf("%s",a+1);a[0]='0';ans[0]='0';
    int n=strlen(a);
    for (int i=1;i<n;i++){
        if (flag){
        	ans[i]='4';
        	continue;
		}
        if (a[i]=='4'||a[i]=='7') ans[i]=a[i];
        else{
            flag=true;
            if (a[i]<'4') ans[i]='4';
            else if (a[i]<'7') ans[i]='7';
            else{
                int x=i-1;
                while (a[x]=='7') x--;
                if (x>0) ans[x]='7';
                else ans[x]='4';
                for (int j=x+1;j<=i;j++) ans[j]='4';
            }
        }
    }
    if (ans[0]=='0') n--;
    else for (int i=n;i;i--) ans[i]=ans[i-1];
    if (n%2||check(n)){
        for (int i=0;i<=n/2;i++) printf("4");
        for (int i=0;i<=n/2;i++) printf("7");
    }else{
        for (int i=1;i<=n;i++){
            num4[i]=num4[i-1];
            num7[i]=num7[i-1];
            if (ans[i]=='4') num4[i]++;
            else num7[i]++;
        }
        if (2*num4[n]==n) for (int i=1;i<=n;i++) printf("%c",ans[i]);
        else
            for (int i=n;i;i--)
                if (ans[i]=='4'&&2*num4[i-1]<=n&&n<=2*(num4[i-1]+n-i)){
                    for (int j=1;j<i;j++) printf("%c",ans[j]);
                    printf("7");
                    for (int j=num4[i-1];j<n/2;j++) printf("4");
                    for (int j=num7[i-1]+1;j<n/2;j++) printf("7");
                    return 0;
                }
    }
    return 0;
}

B:柴犬的喂养艺术

这道题可以化简为求一个由123组成的序列,使得该序列对应的值最大(1表示取a[i] 2表示取b[i] 3表示取c[i]

那么我们知道诸如1321/1231/1222这样的序列是合法的

但是1331/2222/1221这样的序列并不合法(可以自己思考一下为什么

总结一下我们可以发现,对于任意一个合法序列,都有这样的性质,任意两个3之间必有一个1,任意两个1之间必有3,且2不会影响该序列的合法性。

那么我们定义f[i][0]为当前合法序列最大值

f[i][1]为特殊不合法序列的最大值,这里对[特殊不合法序列]举个例子:12232,此序列再加一个1即可转化为合法序列。

那么可以得到状态转移公式

f[i][0]=max(f[i-1][0]+b[i],f[i-1][1]+a[i]);

f[i][1]=max(f[i-1][0]+c[i],f[i-1][1]+b[i]);

ans=f[n][0];

#include<bits/stdc++.h>
using namespace std;
int f[3001][2],a[3001],b[3001],c[3001],n;
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) scanf("%d",&b[i]);
    for (int i=1;i<=n;i++) scanf("%d",&c[i]);
    f[0][0]=-2147483647;
    for (int i=1;i<=n;i++){
        f[i][0]=max(f[i-1][0]+b[i],f[i-1][1]+a[i]);
        f[i][1]=max(f[i-1][0]+c[i],f[i-1][1]+b[i]);
    }
    printf("%d\n",f[n][0]);
    return 0;
}

C:三角迷宫

因为个人时间问题不多做解释,本题来源HDU1030,感兴趣的可以去看博客。

#include<bits/stdc++.h>
using namespace std;
int m,n,cm,cn,rm,rn,lm,ln;
int main(){
    int t;scanf("%d",&t);
    while (t--){
        scanf("%d%d",&m,&n);
        cm=(int)ceil(sqrt(m));cn=(int)ceil(sqrt(n));
        rm=(m-(cm-1)*(cm-1)-1)/2+1;rn=(n-(cn-1)*(cn-1)-1)/2+1;
        lm=(cm*cm-m)/2+1;ln=(cn*cn-n)/2+1;
        int cnt=(int)(abs(cm-cn)+abs(lm-ln)+abs(rm-rn));
        printf("%d\n",cnt);
    }
    return 0;
}

D:时光的城堡

我们定义f[i]为从i号点出发又回到i号点并到达i+1号点的路径长度。

那么可以得出f[i]=f[i-1]+f[i-2]+..+f[k]+2;且 ans=f[1]+f[2]+…+f[n];

那么定义s[i]为f[i]的前i项和,可以推出s[i]=2*s[i-1]-s[k-1]+2; 且 ans=s[n];

值得注意的是计算s[i]并取模的时候要加上一个mod再对mod取模,不然会爆到负数,我在这一点wa了三次。

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007LL
#define ll long long
#define N 100001
ll s[N];
int n,x;
int main(){
    scanf("%d",&n);
    for (ll i=1;i<=n;i++){
        scanf("%d",&x);
        s[i]=(mod+2*s[i-1]-s[x-1]+2)%mod;
    }
    cout<<s[n]<<endl;
    return 0;
}

E:松松的白日梦

以一个数来举例子:12。

12的拆分是8 4,二进制表示为1100

那么一共有[8,4],[8,2,2],[8,2,1,1],[4,4,2,2],[4,4,2,1,1]一共五种拆分。

我们发现,[8,2,2]和][4,4,2,2]很接近,[8,2,1,1]和[4,4,2,1,1]很接近区别都是前面是8后面是4,4

但是为什么[8,4]没有对应的?因为4只有两个,8如果拆分为[4,4]那么是无法满足条件的。

那么我们定义:

f[i]表示从i号位开始往前的第一位的非0位

g[i][0]表示第i号位不拓展的情况下当前的总拓展方法

g[i][1]表示第i号位拓展的情况下当前的总拓展方法

那么我们推出公式有

g[i][0]=g[f[i-1]][0]+g[f[i-1]][1];

g[i][1]=g[f[i-1]][0]*(i-f[i-1]-1)+g[f[i-1]][1]*(i-f[i-1]);

那么显然 ans=max(g[i][0]+g[i][1]);

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll s[201],f[201],g[201][2],x;
int main(){
    int t;scanf("%d",&t);
    while (t--){
        memset(g,0,sizeof(g));
        ll num=0,add=1;
        for (scanf("%lld",&x);x;x/=2) s[++num]=x%2;
        while (add<=num&&s[add]==0) add++;
        f[add]=add;
        g[add][0]=1;//不拓展 
        g[add][1]=add-1;//拓展 
        ll ans=g[add][0]+g[add][1];
        for (int i=add+1;i<=num;i++)
            if (s[i]){
                f[i]=i;
                g[i][0]=g[f[i-1]][0]+g[f[i-1]][1];
                g[i][1]=g[f[i-1]][0]*(i-f[i-1]-1)+g[f[i-1]][1]*(i-f[i-1]);
                ans=max(ans,g[i][0]+g[i][1]);
            }else f[i]=f[i-1];
        printf("%lld\n",ans);
    }
    return 0;
}

F:小Z吃自助餐

本题是一道比较经典的板子题:最大m子段和(已更正,原为最小k子区间和

值得注意的是,[每次可以拿任意数量下标连续的食物],也就是说你可以每次拿0个……

那么我们在 最大m子段和 的板子上稍作修改,让dp数组与0再比较一次即可

这里因为使用了滚动数组,所以空间复杂度非常优秀(

#include<bits/stdc++.h>
using namespace std;
#define N 100010
typedef long long ll;
ll dp[2][N],a[N],n,m,ans;
int main(){
    scanf("%lld%lld",&n,&m);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for (int i=1;i<=m;i++){
        dp[i%2][i]=dp[1-i%2][i-1]+a[i];
        ll maxn=dp[1-i%2][i-1];
        for (int j=i+1;j<=n;j++){
            maxn=max(maxn,dp[1-i%2][j-1]);
            dp[i%2][j]=max(0LL,max(maxn+a[j],dp[i%2][j-1]+a[j]));
        }
    }
    for (int i=m;i<=n;i++) ans=max(ans,dp[m%2][i]);
    printf("%lld\n",ans);
    return 0;
}

G:寻找素数

这道题我的做法是先素数筛0(n)求出1e6以内的素数。因为L和R均小于1e12,所以保证L和R的每一对因子中都必有一个数小于1e6

那么我们判断一个数是不是素数的时间复杂度就是O(1e6以内的素数数量)大约是八万左右。

假定[L,R]内的最大区间为[X,Y],根据素数的分布规律,我们知道X-L和Y-R不会太大

n以内素数的个数趋向于趋近于n/logn,所以两个素数的平均距离为logn。

那么我们不断验证L是不是素数,是就停止,否则L++;R也是同理。

最后输出R-L即可。

赛后和出题人交流,发现这道题是真的水,我还拍了个素数筛上去,结果根本用不上2333 ,其实直接sqrt验证素数就行了。

#include<bits/stdc++.h>
using namespace std;
#define N 1000001
#define ll long long
ll p[N],num,a,b;
bool check[N];
void Prime(){
    for (ll i=2;i<N;i++){
        if (!check[i]) p[++num]=i;
        for (ll j=1;j<=num;j++){
            if (i*p[j]>=N) break;
            check[i*p[j]]=true;
            if (i%p[j]==0) break;
        }
    }
    check[1]=true;
}
bool s(ll x){
    for (ll i=1;i<=num&&x>p[i];i++)
        if (x%p[i]==0) return false;
    return (x>1);
}
int main(){
    Prime();
    cin>>a>>b;
    while (!s(a)) a++;
    while (!s(b)) b--;
    cout<<b-a<<endl;
    return 0;
}

H:找单词

水题,不多作解释。

#include<bits/stdc++.h>
using namespace std;
int n;
string a[101],ans;
int main(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    ans=a[1];
    for (int i=2;i<=n;i++)
        if (a[i].length()>ans.length()||(a[i].length()==ans.length()&&a[i]<ans)) ans=a[i];
    cout<<ans<<endl;
    return 0;
}

I:字符串拼接

定义f[i][j]表示用c串的前i个字符和a串的前j字符匹配完以后,剩余的子串能不能和b串的前i-j个匹配

那么ans=f[nc][na];

#include<bits/stdc++.h>
using namespace std;
char a[2010],b[2010],c[2010];
bool f[2010][2010];
int main(){
    int t;scanf("%d",&t);
    while (t--){
        scanf("%s",a+1);
        scanf("%s",b+1);
        scanf("%s",c+1);
        a[0]=b[0]=c[0]='0';
        int na=strlen(a),nb=strlen(b),nc=strlen(c);na--,nb--,nc--;
        if (na+nb!=nc){
            printf("No\n");
            continue;
        }
        memset(f,0,sizeof(f));f[0][0]=true;
        for (int i=1;i<=nc;i++){
            if (f[i-1][0]&&c[i]==b[i]) f[i][0]=true;
            for (int j=1;j<=min(na,i);j++)
                if ((f[i-1][j-1]&&c[i]==a[j])||(f[i-1][j]&&c[i]==b[i-j])) f[i][j]=true;
        }
        if (f[nc][na]) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

时间匆忙,没有说的太详细,之后有时间会详细写清(咕咕咕

4条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注