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

Kevin_K edited 5 年,8 月前

前言(木有什么卵用,可以直接往下翻正文):

终于更新到最终版了,开心!( ̄▽ ̄)~$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.推出递推公式为an+1=2an-an-k
3.放缩为an+1<=2an
4.以上规律对前几项不适用,需要特判。
5.最大不超过298=316,912,650,057,057,350,374,175,801,344,也就是说可以分为两个部分存起来,低位最多存1018

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善后版):
加了一个句号。

Past Versions

Comments

Saitama

这次多项式题目基本可以照搬“一元多项式乘法”的做法,把系数和次数存数组里,遍历并特判就完了。

Saitama

楼主的c题写的太骚了

ultmaster

良心博主。

10175101159

日常%%%楼主
哪来抢饭碗一说233333

话说C题用分段存储我觉得很妙啊
翻了一下,之前1053和3332写过两次
你可以试试(滑稽)

E的题解很良心,来帮我考大学语文吧
我原来其实是不会的
感谢oi大佬oj用户@Wycers指点迷津

溜了,继续我的三(两)天速成高数(近纲)计划

cww970329

妙啊妙啊

10175101159

%%%%%%%%%%%
我其实是想写的,可是我A不了啊TuT
表示E一直写不对,高精的两个点我改了一下午都是WA
看了大触的blog才发现位数开到了32
但是我真的无法理解啊,就算所有数之和,也不会达到10000*1e18=1e22
所以我开了1e30,然后就一直WA,看完blog改成1e35就过了???喵喵喵???
附WA代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll a[10000];
ll jdg;
int rst[30];
int i;
void add(int m)
{
    int c[30];
    int cp=0,i;
    for(i=29;i>=0;--i)c[i]=a[m]%10,a[m]/=10;
    for(i=29;i>=0;--i){
        rst[i]+=c[i]+cp;
        if(rst[i]>9)rst[i]-=10,cp=1;
        else cp=0;
    }
}
int main()
{
    cin>>n;
    for(i=0;i<n;++i)cin>>a[i],jdg^=a[i];
    if(jdg)cout<<-1;
    else{
        sort(a,a+n);
        memset(rst,0,sizeof(rst));
        for(i=1;i<n;++i)add(i);
        for(i=0;;++i)if(rst[i]!=0)break;
        for(;i<30;++i)cout<<rst[i];
    }
    return 0;
}

今早改成35就过了,AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll a[10000];
ll jdg;
int rst[35];
int i;
void add(int m)
{
    int c[35];
    int cp=0,i;
    for(i=34;i>=0;--i)c[i]=a[m]%10,a[m]/=10;
    for(i=34;i>=0;--i){
        rst[i]+=c[i]+cp;
        if(rst[i]>9)rst[i]-=10,cp=1;
        else cp=0;
    }
}
int main()
{
    cin>>n;
    for(i=0;i<n;++i)cin>>a[i],jdg^=a[i];
    if(jdg)cout<<-1;
    else{
        sort(a,a+n);
        memset(rst,0,sizeof(rst));
        for(i=1;i<n;++i)add(i);
        for(i=0;;++i)if(rst[i]!=0)break;
        for(;i<35;++i)cout<<rst[i];
    }
    return 0;
}

真的是醉了???
楼楼没贴C的代码,我就代劳啦~

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

据说那天下午, 第5题的最后两个测试点被修正了, 后来又重测了

Kevin_K

感谢大佬指点!(〃’▽’〃)已经更新。(≧ω≦)/

10175101159

What???是评测数据的问题吗?我把那天下午的WA代码重新交了一遍,竟然AC了.........

jxtxzzw

良心博主,写得很详细。

风见幽香

第三题确实是高精度

Kevin_K

渣渣最终版更新完毕!已经覆盖实训所有允许使用的语言(C&C++11)。(是不可能喝咖啡玩蟒蛇的,除非允许使用了,但这样高精度就爆掉了!哈哈哈!这辈子别想了!)如果版本有错误或想吐槽改进可以回复我!祝大家码运昌隆!╰( ̄▽ ̄)╭