华一高9.6水平测试赛后总结

题目链接

本次考试试题中，CJ3为NOI分区联赛 - 1998年第四届初中组试题原题，CJ2则是原题的增强。

CJ1来自于1999年NOIp。

考试成绩

分数：400/400 pts

排名：1/20 st

试题解析

CJ1 100pts

这一题是一道高精+模拟的题目。

首先是如何判断回文数，这里直接首尾配对看是否相等即可，如果不等直接return false;即可。

下面是判断回文数的代码：

bool check(){
    for(int i = 0; i < len / 2; i++){
        if(num[i] != num[len-i-1]) return false;
    }
    return true;
}

剩下要做的就是在一个30次的循环当中，每次对数进行翻转，进行N进制的高精加，N进制高精和普通高精没什么区别：

for(int i = 0; i <= 30; i++){
        if(check()){
            cout << i;
            return 0; // return 0 直接结束程序
        }
        memset(t, 0, sizeof(t));
        for(int i = 0; i < len; i++) t[i] = num[i] + num[len-i-1];
        for(int i = 0; i < len; i++){ // 统一处理进位
            t[i+1] += t[i] / n;
            t[i] %= n;
            num[i] = t[i];
            if(t[len]) len++;
        }
    }

有一个易错点在数据读入上，16进制数会带字母，所以这里需要使用字符读入，然后再写入数组，确实有同学因为这个丢了30pts。

上完整代码：

#include<bits/stdc++.h>
using namespace std;
int n, num[105], len, t[105];
string m;
bool check(){
    for(int i = 0; i < len / 2; i++){
        if(num[i] != num[len-i-1]) return false;
    }
    return true;
}
int main(){
    freopen("cj1.in", "r", stdin);
    freopen("cj1.out", "w", stdout);
    cin >> n >> m;
    for(int i = 0; i < m.size(); i++){
        if(isdigit(m[i])) num[m.size()-i-1] = m[i] - '0';
        else num[m.size()-i-1] = m[i] - 'A' + 10;
    }
    len = m.size();
    for(int i = 0; i <= 30; i++){
        if(check()){
//          for(int j = 0; j < len; j++) cout << num[j] << " ";
//          cout << endl;
            cout << i;
            return 0;
        }
        memset(t, 0, sizeof(t));
        for(int i = 0; i < len; i++) t[i] = num[i] + num[len-i-1];
        for(int i = 0; i < len; i++){
            t[i+1] += t[i] / n;
            t[i] %= n;
            num[i] = t[i];
            if(t[len]) len++;
        }
    }
    cout << -1;
    return 0;
}

注意，程序里写了文件输入和输出

CJ2 100pts

第二题直接高精度计算，我在考场上写的是运算符重载：

struct Int{
    long long v[10005], len;
    void print(){
        for(int i = len-1; i >= 0; i--) cout << v[i];
    }
    int count(int n){
        int res = 0;
        for(int i = 0; i < len; i++) if(v[i] == n) res++;
        return res;
    }
    void operator = (const int b){
        int n = b;
        memset(v, 0, sizeof(v));
        len = 0;
        while(n){
            v[len] = n % 10;
            n /= 10;
            len++;
        }
        if(!len) len = 1;
    }
    void operator = (const Int b){
        len = b.len;
        memset(v, 0, sizeof(v));
        for(int i = b.len-1; i >= 0; i--) v[i] = b.v[i];
    }
    Int operator * (const int b){
        Int res;
        res = 0;
        res.len = len;
        for(int i = 0; i < res.len; i++) res.v[i] = v[i] * b;
        for(int i = 0; i < res.len; i++){
            res.v[i+1] += res.v[i] / 10;
            res.v[i] %= 10;
            if(res.v[res.len]) res.len++;
        }
        return res;
    }
    Int operator + (const int b){
        Int res;
        res = *this;
        res.len = len;
        res.v[0] += b;
        for(int i = 0; i < res.len; i++){
            res.v[i+1] += res.v[i] / 10;
            res.v[i] %= 10;
            if(res.v[res.len]) res.len++;
        }
        return res;
    }
};

剩下的也没什么难度，只要你不在每次循环时都嵌套循环计算阶乘就没问题（否则复杂度 $O(n^2)$ ）：

int main(){
    freopen("cj2.in", "r", stdin);
    freopen("cj2.out", "w", stdout);
    Int t, s;
    int n, digit; 
    cin >> n >> digit;
    s = 1;
    for(int i = n; i > 1; i--){
        s = s * i + 1;
    }
    cout << s.len << " " << s.count(digit);
//  cout << endl;
//  s.print();
    return 0;
}

看不懂我循环内写的内容？

举个例子：
$S_3=3!+2!+1!=3\times2\times1+2\times1+1=1\times(2+2\times3+1)+1=1\times(2\times(3+1)+1)+1$

这就能明白了吧。

CJ3 100pts

二进制+递归即可。

转二进制，不断取模：

while(n){
    bin.push_back(n % 2 + '0');
    n /= 2;
}

别的都不值得说了，直接看代码：

#include<bits/stdc++.h>
using namespace std;
void work(int n){
    if(n == 0){
        cout << 0;
        return;
    }
    string bin;
    bool couted = false;
    while(n){
        bin.push_back(n % 2 + '0');
        n /= 2;
    }
    reverse(bin.begin(), bin.end());
    for(int i = 0; i < (signed)bin.size(); i++){
        if(bin[i] == '1'){
            if(couted) cout << "+";
            else couted = true;
            cout << "2";
            if(i != (signed)bin.size()-2){
                cout << "(";
                work(bin.size()-i-1);
                cout << ")";
            }
        }
    }
}
int main(){
    freopen("cj3.in", "r", stdin);
    freopen("cj3.out", "w", stdout);
    int n;
    cin >> n;
    work(n);
    return 0;
}

CJ4 100pts

把同样的两个数当成一组看待，dfs+回溯搜索每个可能位置求解。

#include<bits/stdc++.h>
using namespace std;
int space[25] = {}, n, ans = 0;
void work(int i){
    if(i == n+1){
//      for(int j = 0; j < 2*n; j++) cout << space[j] << " ";
//      cout << endl;
        ans++;
        return;
    }
    for(int j = 0; j <= 2*n-2-i; j++){
        if(!space[j] && !space[j+i+1]){
            space[j] = space[j+i+1] = i;
            work(i+1);
            space[j] = space[j+i+1] = 0;
        }
    }
}
int main(){
    freopen("cj4.in", "r", stdin);
    freopen("cj4.out", "w", stdout);
    cin >> n;
    work(1);
    cout << ans;
    return 0;
}

华一高9.6水平测试 赛后总结