2017级测试20190106解题报告

19 1.18

##题一：波浪数
- 题面：
- 算法分析：
规律题，波浪数数字个数为$（n-2）个$
字典序最小的波浪数为：第一位不动，第二位与第三位互换，第三位与第四位互换···以此类推。

AC代码

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    int a[20000];
    cin>>n;
    cout<<n-2<<endl;
    cout<<"1 ";
    for(int i=1; i<=n; i++) {
        a[i]=i;
    }
    if(n%2==0) {
        for(int i=2; i<n-1; i+=2) {
            swap(a[i],a[i+1]);
        }
        for(int i=2; i<n; i++)
            cout<<a[i]<<" ";
        cout<<n;
    } else {
        for(int i=2; i<=n; i+=2) {
            swap(a[i],a[i+1]);
        }
        for(int i=2; i<n; i++)
            cout<<a[i]<<" ";
        cout<<n-1;
    }
    return 0;  
}

题二：进制转换（八进制转十六进制）

• 题面：
  
• 算法分析：
  
  1. 由八进制正整数小于等于1000位可得需要用数组模拟；
  2. 从八进制到十六进制，可通过二进制作为桥梁；
  3. 八转二 1换3 二转十六 4换1；
  4. 注意处理前导0。

AC代码

#include<bits/stdc++.h>
#include<string>
using namespace std;
int ei[1010],tw[3030],si[1010];//ei八进制 tw二进制 si十六进制;
int main() {
    string n;
    int len=0;
    cin>>n;
    cout<<"("<<n<<")8=(";
    len=n.length();
    for(int i=0; i<len; i++) {
        ei[len-i-1]=n[i]-'0';
    }
    int t=3*len-1;
    for(int i=0; i<len; i++) {
        tw[t]=ei[i]%2;
        ei[i]/=2;
        t--;
        tw[t]=ei[i]%2;
        ei[i]/=2;
        t--;
        tw[t]=ei[i]%2;
        ei[i]/=2;
        t--;
    }
    int p=1;
    int q=3*len-1;
    while(q>=0) {
        si[p]+=tw[q];
        q--;
        si[p]+=tw[q]*2;
        q--;
        si[p]+=tw[q]*4;
        q--;
        si[p]+=tw[q]*8;
        q--;
        p++;
    }
    int fg=1;//输出标记
    for(int i=p-1; i>0; i--) {
        if(fg==0) {
            if(si[i]<10) cout<<si[i];
            if(si[i]==10)cout<<"A";
            if(si[i]==11)cout<<"B";
            if(si[i]==12)cout<<"C";
            if(si[i]==13)cout<<"D";
            if(si[i]==14)cout<<"E";
            if(si[i]==15)cout<<"F";
        }
        if(fg==1 ) {
            if(si[i]!=0) {
                if(si[i]<10) cout<<si[i];
                if(si[i]==10)cout<<"A";
                if(si[i]==11)cout<<"B";
                if(si[i]==12)cout<<"C";
                if(si[i]==13)cout<<"D";
                if(si[i]==14)cout<<"E";
                if(si[i]==15)cout<<"F";
                fg=0;
            }
        }
    }
    cout<<")16";
    return 0;
}

题三：万圣节的游戏

题四：筷子

• 题面：
  
  
• 算法分析：
  DP题，以f[i][j]表示前i根筷子选出j双的最小值；易知，选筷子因选择最接近的两只，故先排序。

AC代码

#include<bits/stdc++.h>
using namespace std;
int ch[200];
int n,k,b;
int ans=0;
int f[200][55];
int main() {
    cin>>n>>k;
    k+=3;
    for(int i=1; i<=n; i++) {
        cin>>ch[i];
    }          
    if(n<2*k)  {
        cout<<"-1";
        return 0;
    }          
    for(int i=0; i<200; i++)
    for(int j=0; j<55; j++) {
            f[i][j]=124123431;
    }
    f[0][0]=0;
    sort(ch+1,ch+1+n);
    for(int i=1; i<=n; i++)
    for(int j=1; j<=min(i/2,k); j++) {//两只为一双
            f[i][j]=min(f[i-1][j],f[i-2][j-1]+(ch[i]-ch[i-1])*(ch[i]-ch[i-1]));
        }
    cout<<f[n][k];
}