2018程序设计能力实训第三次机考题解（渣渣版） - Blog

Compare

Kevin_K edited 5 年，10 月前

This is a past version of blog 2018程序设计能力实训第三次机考题解（渣渣最终版）

前言（2018年6月25日21:37:36 0.0版）：
大佬@10175101159disappear了？！那我代工一份渣渣版的题解来纪念一下魔电期末考结束吧！（在此忠告一下大一的同学们并且告诫一下我自己，不该选的课不要选，该退的时候不要犹豫）不过现在大概没人看吧！所以写的略简略（包括排版），会慢慢更新的！（立个flag：暑期课程前更到最终版）
注：本文代码语言为C++11，实测AC。
注：第三题太难了（对，我是渣渣），第十个点哇掉了www，让我再想想。
A. 2333进制
hints:
将每一位存入数组，然后输出来，注意不要输出前导零！
code:

#include <bits/stdc++.h>
using namespace std;
int main(){
    int l,t,a[16],i;
    long long n;
    cin>>t;
    while (t--){
        cin>>n;
        memset(a,0,sizeof(a));
        l=0;
        while (n){
            a[l++]=n%2333;
            n/=2333;
        }
        for (i=15;i>0;i--){
            if (a[i]){
                break;
            }
        }
        for (;i>=0;i--){
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
}

B. HTTP与HTTPS
hints:
结构体排序。难点在输入。（其实就码量大了点，粘贴后发现也不大，2333~）
code:

#include <bits/stdc++.h>
using namespace std;
struct o{
    string a,b;
}ans[128];
bool cmp(o p,o q){
    if (p.a!=q.a){
        return p.a<q.a;
    }
    return p.b<q.b;
}
int main(){
    int t,i,l=0;
    string x;
    cin>>t;
    while (t--){
        cin>>x;
        if (x[4]=='s'){
            continue;
        }
        for (i=7;i<x.length();i++){
            if (x[i]=='/'){
                break;
            }
            ans[l].a+=x[i];
        }
        for (;i<x.length();i++){
            ans[l].b+=x[i];
        }
        l++;
    }
    sort(ans,ans+l,cmp);
    for (i=0;i<l;i++){
        cout<<"http://"<<ans[i].a<<ans[i].b<<endl;
    }
}

C. 数列项
hints:
unsigned long long也炸？（好像不是这个的锅）难道要用高精？但E已经有高精了啊！先浪几天，到时候再想。
code:

//现在木有啊~

D. 多项式分解
hints:
开始以为是数学题，然后看了一下时间复杂度，心里默念五字心诀：暴力出奇迹。后来发现是……这，你给我个二项式是什么意思啊！明明是考我们怎么输入a，b，c啊。emmmm~
code:

#include <bits/stdc++.h>
using namespace std;
string s,ss;
int a,b,c;
int main(){
    cin>>s;
    if (s[0]=='x'){
        a=1;
    }
    else{
        for (int i=0;i<s.length();i++){
            if (s[i]=='x'){
                break;
            }
            a=a*10+s[i]-'0';
        }
    }
    if (s.find("x",s.find("x")+1)+1){
        for (int i=s.find("^2")+3;;i++){
            if (s[i]=='x'){
                break;
            }
            b=b*10+s[i]-'0';
        }
        if (!b){
            b=1;
        }
        if (s[s.find("^2")+2]=='-'){
            b=-b;
        }
    }
    if (s[s.length()-1]!='x'){
        for (int i=1;;i++){
            ss=s[s.length()-i]+ss;
            if (!isdigit(s[s.length()-i])){
                break;
            }
        }
        stringstream sss;
        sss<<ss;
        sss>>c;
    }
    for (int i=1;i<=sqrt(a);i++){
        if (a%i){
            continue;
        }
        for (int j=-200;j<=200;j++){
            for (int k=-200;k<=200;k++){
                if (k*j==c&&i*k+j*a/i==b){
                    cout<<i<<" "<<j<<" "<<a/i<<" "<<k<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"No Answer!"<<endl;
}

E. 整数分组
hints:
做的第一道题，因为是最后一题，按照套路，以为是DP题，然后又没有仔细看题，于是以为是分为若干组……然后就心态爆炸了。
要准确的解析本题篇幅过长，容我慢慢写。不过核心思想如下：
昔者庄周梦为胡蝶，栩栩然胡蝶也，自喻适志与，不知周也。俄然觉，则蘧蘧然周也。不知周之梦为胡蝶与，胡蝶之梦为周与？周与胡蝶，则必有分矣。此之谓物化。（《庄子·齐物论》）
如何哇了一波，于是绝望的领悟到了需要我最最最最最讨厌的高精度运算之大整数加法，加上就AC了。
code:

#include <bits/stdc++.h>
using namespace std;
int n,l,a[64],ans[32],temp,i;
long long mi=1E18,x,s[10101];
int main(){
    cin>>n;
    for (i=0;i<n;i++){
        cin>>x;
        s[i]=x;
        mi=min(mi,x);
        l=0;
        while (x){
            a[l++]+=x%2;
            x/=2;
        }
    }
    for (i=0;i<64;i++){
        if (a[i]%2){
            cout<<"-1"<<endl;
            return 0;
        }
    }
    for (i=0;i<n;i++){
        if (s[i]==mi){
            s[i]=0;
            break;
        }
    }
    for (i=0;i<n;i++){
        temp=0;
        for (l=0;l<32;l++){
            x=ans[l]+s[i]%10+temp;
            temp=x/10;
            ans[l]=x%10;
            s[i]/=10;
        }
    }
    for (i=31;i>0;i--){
        if (ans[i]!=0){
            break;
        }
    }
    for (;i>=0;i--){
        cout<<ans[i];
    }
    cout<<endl;
}

总结：老师（出题人）辛苦了。不仅吃了DP，而且还把数据造白

前言（木有什么卵用，可以直接往下翻正文）：

终于更新到最终版了，开心！(￣▽￣)~$Flag没有实现有点遗憾，不过flag立就完事了。没有错误不会再自动更新了，如果找到的话直接回复即可。
给大家介绍一个EOJ的小彩蛋：Problems>PROBLEMSET单击/双击Reward/Solved是可以降序/升序排列题目的，也就是说可以短时间获得大量可以刷的（划掉）水（/划掉）题。
还是正经的聊聊实训考试吧。就这次考试而言没有DP或许是放水了？但取而代之的是更多的让人头大的高精度运算。(╯°Д°)╯︵┻━┻
考点：
A.进制转换
B.字符串处理&排序（&结构体）
C.高精度加法（虽然可以规避）
D.字符串处理（&暴模）
E.脑筋急转弯（硬要说的话应该是个math）&高精度
嗯，应该除了DP，该考的全考了。还是不能抱有侥幸心理啊。
总的来说，这几次考试一次比一次简单……
也就是：老师并不想挂人。
如何备考实训？
天资聪颖？
Yes->Play game.
No->刷题。（刷题是人类进步的电梯——高XX）
不想挂，刷就完事了，听说刷100题（我指的不是升序的前一百道），实训稳过，此言得之。
警告：大家千万别学怠惰的我！一定要多刷题啊！不然像我一样，天生渣渣，且以刷题为耻，实训绩点一点五，暑假空悲切！╥﹏╥

正文：

A. 2333进制

Hints:

将每一位存入数组，然后输出来，注意不要输出前导零！

C++11 Code:

#include <bits/stdc++.h>
using namespace std;
int main(){
    int l,t,a[16],i;
    long long n;
    cin>>t;
    while (t--){
        cin>>n;
        memset(a,0,sizeof(a));
        l=0;
        while (n){
            a[l++]=n%2333;
            n/=2333;
        }
        for (i=15;i>0;i--){
            if (a[i]){
                break;
            }
        }
        for (;i>=0;i--){
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
}

C Code:

#include <stdio.h>
#include <string.h>
int main(){
    int l,t,a[16],i;
    long long n;
    scanf("%d",&t);
    while (t--){
        scanf("%lld",&n);
        memset(a,0,sizeof(a));
        l=0;
        while (n){
            a[l++]=n%2333;
            n/=2333;
        }
        for (i=15;i>0;i--){
            if (a[i]){
                break;
            }
        }
        for (;i>=0;i--){
            printf("%d%c",a[i],i?' ':'\n');
        }
    }
}

B. HTTP与HTTPS

Hints:

结构体排序。难点在输入。（其实就码量大了点，粘贴后发现也不大，2333~）

C++11 Code:

#include <bits/stdc++.h>
using namespace std;
struct o{
    string a,b;
}ans[128];
bool cmp(o p,o q){
    if (p.a!=q.a){
        return p.a<q.a;
    }
    return p.b<q.b;
}
int main(){
    int t,i,l=0;
    string x;
    cin>>t;
    while (t--){
        cin>>x;
        if (x[4]=='s'){
            continue;
        }
        for (i=7;i<x.length();i++){
            if (x[i]=='/'){
                break;
            }
            ans[l].a+=x[i];
        }
        for (;i<x.length();i++){
            ans[l].b+=x[i];
        }
        l++;
    }
    sort(ans,ans+l,cmp);
    for (i=0;i<l;i++){
        cout<<"http://"<<ans[i].a<<ans[i].b<<endl;
    }
}

C Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct o{
    char a[512],b[512];
}ans[128];
int compare(char *p,char *q){
    while (*p==*q&&*p&&*q){
        p++;
        q++;
    }
    return (int)*p-(int)*q;
}
int cmp(struct o *p,struct o *q){
    if (compare(p->a,q->a)!=0){
        return compare(p->a,q->a);
    }
    return compare(p->b,q->b);
}
int main(){
    int t,i,l=0,m;
    scanf("%d",&t);
    while (t--){
        char x[1024];
        scanf("%s",x);
        if (x[4]=='s'){
            continue;
        }
        m=0;
        for (i=7;i<strlen(x);i++){
            if (x[i]=='/'){
                break;
            }
            ans[l].a[m]=x[i];
            m++;
        }
        m=0;
        for (;i<strlen(x);i++){
            ans[l].b[m]=x[i];
            m++;
        }
        l++;
    }
    qsort(ans,l,sizeof(struct o),cmp);
    for (i=0;i<l;i++){
        printf("http://%s%s\n",ans[i].a,ans[i].b);
    }
}
//我不想再碰C了。QAQ

C. 数列项

Hints:

穷尽毕生所学绕开了万恶的高精度。（其实也没差）详细下次更。只能说我有点投机取巧。
投机取巧内容如下：
1.将数组移动了10位来处理下标越界的问题。
2.推出递推公式为a_n+1=2a_n-a_n-k。
3.放缩为a_n+1<=2a_n。
4.以上规律对前几项不适用，需要特判。
5.最大不超过2⁹⁸=316,912,650,057,057,350,374,175,801,344，也就是说可以分为两个部分存起来，低位最多存10¹⁸

C++11 Code:

#include <bits/stdc++.h>
using namespace std;
long long a[128][2],N=1E18,x;
int k,n,l;
int main(){
    a[12][1]=a[11][1]=1;
    cin>>k>>n;
    for (int i=3;i<n;i++){
        a[i+10][1]=2*a[i+9][1]-a[i+9-k][1];
        a[i+10][0]=a[i+10][1]/N+2*a[i+9][0]-a[i+9-k][0];
        a[i+10][1]%=N;
    }
    if (a[n+9][0]){
        cout<<a[n+9][0];
        x=a[n+9][1];
        do{
            l++;
            x/=10;
        }while (x);
        for (int i=0;i<18-l;i++){
            cout<<"0";
        }
        cout<<a[n+9][1]<<endl;
    }
    else{
        cout<<a[n+9][1]<<endl;
    }
}

附上并感谢@10175101159大佬（完了，我好像抢了大佬饭碗，我错了2333~）的这类题的正确写法。

C++11 Code:

#include<bits/stdc++.h>
using namespace std;
int n,k;
char a[105][105];
int i,j;
void add(int x,int y)
{
    char z[105];
    memset(z,'0',sizeof(z));
    int cp=0,i;
    for(i=104;i>=0;--i){
        z[i]=a[x][i]-'0'+a[y][i]-'0'+cp;
        if(z[i]>9)cp=1,z[i]=z[i]-10+'0';
        else cp=0,z[i]=z[i]+'0';
    }
    for(i=0;i<105;++i)a[x][i]=z[i];
}
int main()
{
    memset(a,'0',sizeof(a));
    a[2][104]='1';
    cin>>k>>n;
    for(i=3;i<105;++i){
        for(j=1;j<=k&&i-j>0;++j){
            add(i,i-j);
        }
    }
    for(i=0;i<105;++i)if(a[n][i]!='0')break;
    if(i<105)for(j=i;j<105;++j)cout<<a[n][j];
    else cout<<0;
    return 0;
}

两者的区别在于把n改大一点我的就会炸，而大佬的不会（或者说改动一小点就可以过）。（大概吧）

C Code:

#include <stdio.h>
long long a[128][2],N=1E18,x;
int k,n,l;
int main(){
    a[12][1]=a[11][1]=1;
    scanf("%d%d",&k,&n);
    for (int i=3;i<n;i++){
        a[i+10][1]=2*a[i+9][1]-a[i+9-k][1];
        a[i+10][0]=a[i+10][1]/N+2*a[i+9][0]-a[i+9-k][0];
        a[i+10][1]%=N;
    }
    if (a[n+9][0]){
        printf("%lld",a[n+9][0]);
        x=a[n+9][1];
        do{
            l++;
            x/=10;
        }while (x);
        for (int i=0;i<18-l;i++){
            printf("%c",'0');
        }
        printf("%lld\n",a[n+9][1]);
    }
    else{
        printf("%lld\n",a[n+9][1]);
    }
}

D. 多项式分解

Hints:

开始以为是数学题，然后看了一下时间复杂度，心里默念五字心诀：暴力出奇迹。后来发现是……这，你给我个一元二次多项式是什么意思啊！明明是考我们怎么输入a，b，c啊。emmmm~

C++11 Code:

#include <bits/stdc++.h>
using namespace std;
string s,ss;
int a,b,c;
int main(){
    cin>>s;
    if (s[0]=='x'){
        a=1;
    }
    else{
        for (int i=0;i<s.length();i++){
            if (s[i]=='x'){
                break;
            }
            a=a*10+s[i]-'0';
        }
    }
    if (s.find("x",s.find("x")+1)+1){
        for (int i=s.find("^2")+3;;i++){
            if (s[i]=='x'){
                break;
            }
            b=b*10+s[i]-'0';
        }
        if (!b){
            b=1;
        }
        if (s[s.find("^2")+2]=='-'){
            b=-b;
        }
    }
    if (s[s.length()-1]!='x'){
        for (int i=1;;i++){
            ss=s[s.length()-i]+ss;
            if (!isdigit(s[s.length()-i])){
                break;
            }
        }
        stringstream sss;
        sss<<ss;
        sss>>c;
    }
    for (int i=1;i<=sqrt(a);i++){
        if (a%i){
            continue;
        }
        for (int j=-200;j<=200;j++){
            for (int k=-200;k<=200;k++){
                if (k*j==c&&i*k+j*a/i==b){
                    cout<<i<<" "<<j<<" "<<a/i<<" "<<k<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"No Answer!"<<endl;
}

C Code:

#include <stdio.h>
#include <string.h>
char s[256],ss[256],x[256],y[256],z[256];
int a,b,c;
int main(){
    scanf("%s",s);
    strncpy(x,s,strstr(s,"x^2")-s);
    if (s[0]=='x'||(s[0]=='+'&&s[1]=='x')){
        a=1;
    }
    else if(s[0]=='-'&&s[1]=='x'){
        a=-1;
    }
    else{
        a=atoi(x);
    }
    for (int i=strlen(x)+3;i<=strlen(s);i++){
        ss[i-strlen(x)-3]=s[i];
    }
    if (strstr(ss,"x")==0){
        b=0;
        strcpy(z,ss);
    }
    else{
        strncpy(y,ss,strstr(ss,"x")-ss);
        if (ss[0]=='x'||(ss[0]=='+'&&ss[1]=='x')){
            b=1;
        }
        else if(ss[0]=='-'&&ss[1]=='x'){
            b=-1;
        }
        else{
            b=atoi(y);
        }
        for (int i=strlen(y)+1;i<=strlen(ss);i++){
            z[i-strlen(y)-1]=ss[i];
        }
    }
    c=atoi(z);
    for (int i=1;i<=sqrt(a);i++){
        if (a%i){
            continue;
        }
        for (int j=-200;j<=200;j++){
            for (int k=-200;k<=200;k++){
                if (k*j==c&&i*k+j*a/i==b){
                    printf("%d %d %d %d\n",i,j,a/i,k);
                    return 0;
                }
            }
        }
    }
    printf("No Answer!\n");
}
//其实多写写也不会觉得抓狂了。

E. 整数分组

Hints:

做的第一道题，因为是最后一题，按照套路，以为是DP题，然后又没有仔细看题，于是以为是分为若干组……然后就心态爆炸了。
要准确的解析本题篇幅过长，容我慢慢写。不过核心思想如下：
昔者庄周梦为胡蝶，栩栩然胡蝶也，自喻适志与，不知周也。俄然觉，则蘧蘧然周也。不知周之梦为胡蝶与，胡蝶之梦为周与？周与胡蝶，则必有分矣。此之谓物化。（《庄子·齐物论》）
然后哇了一波，于是绝望的领悟到了需要我最最最最最讨厌的高精度运算之大整数加法，加上就AC了。
详解如下：
注：以下未经说明的讨论都是二进制数以及二进制无进位加法和二进制无退位减法！
易证二进制无进位加法满足普通加法的性质（交换律，结合律，单位元，逆元），假定存在符合条件的分组方法，那么把所有数相加时可以使用性质分为两组分别算，由假设这两组结果可以相同，于是相加后最终结果是00000……（两个相同的数相加结果为零）。
那么我们可以推出如果所有的数相加后不为00000……那么就不可能存在满足题意的分组。
讨论00000……的情况，先来解释一下核心思想为什么是庄生梦蝶，类似的，定义二进制无退位减法，此减法满足普通减法的性质，最重要的是，加一个数和减一个数的结果是一样的！所以，加法即减法，减法即加法！
因此，分为两组，一组先为空（可以认为此时两组都为00000……，即相等），由于分组一组不能为空，所以从满的一组抽一个数出来给空组，由于加法和减法效果相同，于是两边还是相等，于是我们构出了满足题意的分组，进一步，取出来的数是所有数中最小时，最大的那一组和是所有满足的情况中最大的，高精度运算出来就得到了答案！

C++11 Code:

#include <bits/stdc++.h>
using namespace std;
int n,l,a[64],ans[32],temp,i;
long long mi=1E18,x,s[10101];
int main(){
    cin>>n;
    for (i=0;i<n;i++){
        cin>>x;
        s[i]=x;
        mi=min(mi,x);
        l=0;
        while (x){
            a[l++]+=x%2;
            x/=2;
        }
    }
    for (i=0;i<64;i++){
        if (a[i]%2){
            cout<<"-1"<<endl;
            return 0;
        }
    }
    s[0]-=mi;
    for (i=0;i<n;i++){
        temp=0;
        for (l=0;l<32;l++){
            x=ans[l]+s[i]%10+temp;
            temp=x/10;
            ans[l]=x%10;
            s[i]/=10;
        }
    }
    for (i=31;i>0;i--){
        if (ans[i]!=0){
            break;
        }
    }
    for (;i>=0;i--){
        cout<<ans[i];
    }
    cout<<endl;
}

如果我什么都不会，只读的懂单个字，怎么办呢？
面向“数据”编程试试：
比如说：

C++11 Code:

#include <bits/stdc++.h>
using namespace std;
int main(){
    cout<<"-1"<<endl;
}

C Code:

#include <stdio.h>
int main(){
    printf("-1\n");
}
//这也有C版的，好像有点过分了？QAQ

结果如下：
avatar
avatar
看起来好像骗到了一点分，不过这只是没有办法的办法，祝大家考试好运吧。

C Code:

#include <stdio.h>
int n,l,a[64],ans[32],temp,i;
long long mi=1E18,x,s[10101];
int main(){
    scanf("%d",&n);
    for (i=0;i<n;i++){
        scanf("%lld",&x);
        s[i]=x;
        mi=mi<x?mi:x;
        l=0;
        while (x){
            a[l++]+=x%2;
            x/=2;
        }
    }
    for (i=0;i<64;i++){
        if (a[i]%2){
            printf("-1");
            return 0;
        }
    }
    s[0]-=mi;
    for (i=0;i<n;i++){
        temp=0;
        for (l=0;l<32;l++){
            x=ans[l]+s[i]%10+temp;
            temp=x/10;
            ans[l]=x%10;
            s[i]/=10;
        }
    }
    for (i=31;i>0;i--){
        if (ans[i]!=0){
            break;
        }
    }
    for (;i>=0;i--){
        printf("%lld",ans[i]);
    }
    printf("\n");
}

附录（后记&更新日志）：

后记（2018年6月25日21:37:36 0.0版）：
大佬@10175101159disappear了？！那我代工一份渣渣版的题解来纪念一下魔电期末考结束吧！（在此忠告一下大一的同学们并且告诫一下我自己，不该选的课不要选，该退的时候不要犹豫）不过现在大概没人看吧！所以写的略简略（包括排版），会慢慢更新的！（立个flag：暑期课程前更到最终版）
注：本文代码语言为C++11，实测AC。
注：第三题太难了（对，我是渣渣），第十个点哇掉了www，让我再想想。
更新（2018年6月25日21:41:56 0.1版）：
改了一些错别字。
更新（2018年6月26日09:39:43 1.0版）：
更新了C题代码，大更等我上完物理课。QAQ
改善了排版。
更新（2018年6月26日12:11:31 2.0版）：
更新C题详解。
将前言改为后记，方便阅读。
改善排版。
更新（2018年6月26日12:35:49 3.0版）：
更新E题详解。
修改已知错误。
更新（2018年6月27日08:36:44 3.1版）：
精简E题代码（因为只要减掉最小数即可，所以用任意一个数减都不会变为负数）。
修改一些令人窒息的错误，诸如把二进制无进位减法改为了二进制无退位减法。
更新（2018年7月6日16:44:27 3.2版）：
修改错别字，统一文本。
更新E题骗分实践。
大版本（加入C语言）准备中，敬请期待。（C语言不怎么会写，请不要期待）
更新（2018年7月8日20:02:17 4.0版）：
加入A,C,E题的C语言代码。（剩下的两题没有是因为没了string我的字符串……等我有空了把C的字符串完全学完就有了）（听说大概是明天？）
改善格式。
前排高亮显示重要更新内容！─=≡Σ(((つ•̀ω•́)つ
更新（2018年7月9日08:59:49 4.1版）：
加入B题C语言代码。（C好难www）
话说EOJ不仅删除线不显示，连字体和字色也都……TuT
更新（2018年7月9日21:53:44 4.2最终版）：
蜕变。
更新（2018年7月26日17:18:18 4.3善后版）：
加了一个句号。

2018程序设计能力实训第三次机考题解（渣渣版） (Past)

前言（木有什么卵用，可以直接往下翻正文）：

正文：

A. 2333进制

Hints:

C++11 Code:

C Code:

B. HTTP与HTTPS

Hints:

C++11 Code:

C Code:

C. 数列项

Hints:

C++11 Code:

C++11 Code:

C Code:

D. 多项式分解

Hints:

C++11 Code:

C Code:

E. 整数分组

Hints:

C++11 Code:

C++11 Code:

C Code:

C Code:

附录（后记&更新日志）：

服务

开源

关于我们