题目链接
本次考试试题中，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;
}
};
剩下的也没什么难度，只要你不在每次循环时都嵌套循环计算阶乘就没问题（否则复杂度）：
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;
}
看不懂我循环内写的内容？
举个例子：
这就能明白了吧。
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;
}
网友评论