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

Kevin_K edited 5 年，10 月前

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

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:

穷尽毕生所学绕开了万恶的高精度。（其实也没差）详细下次更。只能说我有点投机取巧。
更新：投机取巧内容如下：
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

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~~~）的这类题的正确写法。

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改大一点我的就会炸，而大佬的不会（或者说改动一小点就可以过）。（大概吧）

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

前言（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题详解。
将前言改为后记，方便阅读。
改善排版。

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

服务

首页 反馈 Polygon Wiki

开源

Github eJudge

关于我们

团队: @ultmaster, @zerol, @kblack.
联系方式: acmsupport@admin.ecnu.edu.cn