NOIP真题
定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符 串”BCA”，可以将 A 移到 B 之前，变成字符串 ”ABC”。如果要将字符串 ”DACHEBGIF ”变成 "ABCDEFGHI" ，最少需要 ________ 次操作。
#include <iostream>
#include <cstring>
using namespace std;
const int SIZE = 100;
int main(){
int n, i, sum, x, a[SIZE];
cin>>n;
memset(a, 0, sizeof(a));
for (i = 1; i <= n; i++) {
cin>>x;
a[x]++;
}
i = 0; sum = 0;
while (sum < (n / 2 + 1)) {
i++;
sum += a[i];
}
cout<<i<<endl;
return 0;
}输入：
11
4 5 6 6 4 3 3 2 3 2 1
输出： _________
#include <iostream>
using namespace std;
int n;
void f2(int x, int y);
void f1(int x, int y){
if (x < n)f2(y, x + y);
}
void f2(int x, int y){
cout<<x<<' ';
f1(y, x + y);
}
int main(){
cin>>n;
f1(0, 1);
return 0;
}输入： 30
输出： _________
#include <iostream>
using namespace std;
const int V = 100;
int n, m, ans, e[V][V];
bool visited[V];
void dfs(int x, int len){
int i;
visited[x] = true;
if (len > ans)ans = len;
for (i = 1; i <= n; i++)
if ((! visited[i]) && (e[x][i] != -1))
dfs(i, len + e[x][i]);
visited[x] = false;
}
int main(){
int i, j, a, b, c;
cin>>n>>m;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
e[i][j] = -1;
for (i = 1; i <= m; i++){
cin>>a>>b>>c;
e[a][b] = c;
e[b][a] = c;
}
for (i = 1; i <= n; i++)
visited[i] = false;
ans = 0;
for (i = 1; i <= n; i++)
dfs(i, 0);
cout<<ans<<endl;
return 0;
}输入：
4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60
输出：________
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int SIZE = 10000;
const int LENGTH = 10;
int n, m, a[SIZE][LENGTH];
int h(int u, int v){
int ans, i;
ans = 0;
for (i = 1; i <= n; i++)
if (a[u][i] != a[v][i])
ans++;
return ans;
}
int main(){
int sum, i, j;
cin>>n;
memset(a, 0, sizeof(a));
m = 1;
while (1){
i = 1;
while ((i <= n) && (a[m][i] == 1))
i++;
if (i > n) break;
m++;
a[m][i] = 1;
for (j = i + 1; j <= n; j++)
a[m][j] = a[m - 1][j];
}
sum = 0;
for (i = 1; i <= m; i++)
for (j = 1; j <= m; j++)
sum += h(i, j);
cout<<sum<<endl;
return 0;
}输入： 7
输出：______
（大整数开方 ）输入一个正整数 n（1<=n<10 100 ），试用二分法计算它的平方根的整 数部分。
【程序清单】
#include <iostream>
#include <string>
using namespace std;
const int SIZE = 200;
struct hugeint {
int len, num[SIZE];
};
//其中 len 表示大整数的位数；num[1]表示个位、num[2]表示十位，以此类推
hugeint times(hugeint a, hugeint b) {
//计算大整数 a 和 b 的乘积
int i, j; hugeint ans;
memset(ans.num, 0, sizeof(ans.num));
for (i = 1; i <= a.len; i++)
for (j = 1; j <= b.len; j++)
①+= a.num[i] * b.num[j];
for (i = 1; i <= a.len + b.len; i++) {
ans.num[i + 1] += ans.num[i] / 10;
②;
}
if (ans.num[a.len + b.len] > 0)
ans.len = a.len + b.len;
else
ans.len = a.len + b.len - 1;
return ans;
}
hugeint add(hugeint a, hugeint b){
//计算大整数 a 和 b 的和
int i; hugeint ans;
memset(ans.num, 0, sizeof(ans.num));
if (a.len > b.len)
ans.len = a.len;
else
ans.len = b.len;
for (i = 1; i <= ans.len; i++) {
ans.num[i] +=③;
ans.num[i + 1] += ans.num[i] / 10;
ans.num[i] %= 10;
}
if (ans.num[ans.len + 1] > 0) ans.len++;
return ans;
}
hugeint average(hugeint a, hugeint b){
//计算大整数 a 和 b 的平均数的整数部分
int i; hugeint ans;
ans= add(a, b);
for(i = ans.len; i >= 2; i--) {
ans.num[i - 1] += (④) * 10;
ans.num[i] /= 2;
}
ans.num[1] /= 2;
if (ans.num[ans.len] == 0) ans.len--;
return ans;
}
hugeint plustwo(hugeint a) {
//计算大整数 a 加 2 后的结果
int i; hugeint ans;
ans = a;
ans.num[1] += 2;
i = 1;
While ((i <= ans.len) && (ans.num[i] >= 10)) {
ans.num[i + 1] += ans.num[i] / 10;
ans.num[i] %= 10;
i++;
}
if (ans.num[ans.len + 1] > 0)⑤;
return ans;
}
bool over(hugeint a, hugeint b){
//若大整数 a>b 则返回 true，否则返回 false
int i;
if (⑥) return false;
if (a.len > b.len) return true;
for (i = a.len; i >= 1; i--) {
if (a.num[i] < b.num[i])return false;
if (a.num[i] > b.num[i]) return true;
}
return false;
}
int main(){
string s;
int i;
hugeint target, left, middle, right;
cin>>s;
memset(target.num, 0, sizeof(target.num));
target.len = s.length();
for (i = 1; i <= target.len; i++)
target.num[i]= s[target.len - i] - ⑦;
memset(left.num, 0, sizeof(left.num));
left.len = 1;
left.num[1] = 1;
right = target;
do {
middle = average(left, right);
if (over(⑧))right = middle;
else left = middle;
} while (!over(plustwo(left), right));
for (i = left.len; i >= 1; i--)
cout<<left.num[i];
cout<<endl;
return 0;
}（笛卡尔树 ）对于一个给定的两两不等的正整数序列， 笛卡尔树是这样的一棵二叉树。首先，它是一个最小堆，即 除了根结点外， 每个结点的权值都大于父结点的权值； 其次， 它的中序遍历恰好就是给定的序列。例如，对于序列 7、2 、12 、1、10 、5、15 、3 ，下图就是一棵对应的笛卡尔树。 现输入序列的规模 n（1<=n<100 ） 和序列的 n 个元素，试求对应的笛卡尔树的深度 d（根节点深度为 1），以及有多少个叶节 点的深度为 d 。
【程序清单】
#include <iostream>
using namespace std;
const int SIZE = 100+5;
const int INFINITY = 1000000;
int n, a[SIZE], maxDeep, num;
void solve(int left, int right, int deep){
int i, j, min;
if (deep > maxDeep) {
maxDeep = deep;
num = 1;
}else if (deep == maxDeep)
①;
min = INFINITY;
for (i = left; i <= right; i++)
if (min > a[i]) {
min = a[i];
②;
}
if(left < j)③;
if(j < right)④;
}
int main(){
int i;
cin>>n;
for (i = 1; i <= n; i++)
cin>>a[i];
maxDeep = 0;
solve(1, n, 1);
cout<<maxDeep<<' '<<num<<endl;
return 0;
}如果平面上任取 n 个整点(横纵坐标都是整数)，其中一定存在两个点，它们连线的中点也是整点，那么 n 至少是____。
在 NOI 期间，主办单位为了欢迎来自各国的选手，举行了盛大的晚宴。在第 十八桌，有 5 名大陆选手和 5 名港澳选手共同进膳。 为了增进交流， 他们决定相 隔就坐，即每个大陆选手左右旁都是港澳选手， 每个港澳选手左右旁都是大陆选 手。那么，这一桌一共有 _______种不同的就坐方案。注：如果在两个方案 中，每个选手左右相邻的选手相同 ，则视为同一种方案。
#include <iostream>
using namespace std;
int a, b, c, d, e, ans;
int main(){
cin>>a>>b>>c;
d = a+b;
e = b+c;
ans = d+e;
cout<<ans<<endl;
}输入： 1 2 5
输出： _______
include<iostream>
using namespace std;
int n, i, ans;
int main(){
cin>>n;
ans = 0;
for (i = 1; i <= n; i++)
if (n % i == 0)ans++;
cout<<ans<<endl;
}输入： 18
输出： ___________
#include <iostream>
using namespace std;
int n, i, j, a[100][100];
int solve(int x, int y){
int u, v;
if (x == n)return a[x][y];
u = solve(x + 1, y);
v = solve(x + 1, y + 1);
if (u > v)
return a[x][y] + u;
else
return a[x][y] + v;
}
int main(){
cin>>n;
for (i = 1; i <= n; i++)
for (j = 1; j <= i; j++)
cin>>a[i][j];
cout<<solve(1, 1)<<endl;
return 0;
}输入：
5 2
-1 4
2 -1 -2
-1 6 4 0
3 2 -1 5 8
输出： ______________
#include <iostream>
#include <string>
using namespace std;
int n, ans, i, j;
string s;
char get(int i){
if (i < n)
return s[i];
else
return s[i-n];
}
int main(){
cin >> s;
n = s.size();
ans = 0;
for (i = 1; i <= n-1; i++){
for (j = 0; j <= n-1; j++)
if (get(i+j) < get(ans+j)){
ans = i; break;
}else if (get(i+j) > get(ans+j))
break;
}
for (j = 0; j <= n-1; j++)
cout<<get(ans+j);
cout<<endl;
}输入： CBBADADA
输出： ______
（坐标统计）输入 n 个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点（即 x、y 坐标都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。
#include<iostream>
using namespace std;
const int SIZE = 100;
int x[SIZE], y[SIZE], f[SIZE];
int n, i, j, max_f, ans;
int main(){
cin>>n;
for (i = 1; i <= n; i++)
cin >> x[i] >> y[i];
max_f = 0;
for (i = 1; i <= n; i++){
f[i] =①;
for (j = 1; j <= n; j++){
if (x[j] < x[i] && ②)
③;
}
if (④){
max_f = f[i];
⑤;
}
}
for (i = 1; i <= n; i++)
cout<<f[i]<<endl;
cout<<ans<<endl;
}（排列数）输入两个正整数 n，m（1 输入： 3 2 输出： 1 2 1 3 2 1 2 3 3 1 3 2#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 25;
bool used[SIZE];
int data[SIZE];
int n, m, i, j, k;
bool flag;
int main(){
cin>>n>>m;
memset(used, false, sizeof(used));
for (i = 1; i <= m; i++){
data[i] = i;
used[i] = true;
}
flag = true;
while (flag){
for (i = 1; i <= m-1; i++)cout<<data[i]<<"";
cout << data[m] << endl;
flag =①;
for (i = m; i >= 1; i--){
②;
for (j = data[i]+1; j <= n; j++)
if (!used[j]){
used[j] = true;
data[i] =③;
flag = true;
break;
}
if (flag){
for (k = i+1; k <= m; k++)
for (j = 1; j <=④; j++)
if (!used[j]){
data[k] = j;
used[j] = true;
break;
}
⑤;
}
}
}
}
7 个同学围坐一圈，要选 2 个不相邻的作为代表，有____种不同的选法。
某系统自称使用了一种防窃听的方式验证用户密码。密码是 n 个数 s1, s2, , , sn ，均为 0 或 1 。 该系统每次随机生成 n 个数 a1, a2, …… , an ， 均为 0 或 1 ， 请用户回答 (s1a1+ s2a2+ …… + snan) 除以 2 的余数。如果多次的回答总是正确，即认为掌握密码。该系 统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。 然而，事与愿违。例如，当 n = 4 时，有人窃听了以下 5 次问答：就破解出了密码 s1 = _________ ， s2 = _________ ，s3 = _________ ， s4 = _________ 。(答案用逗号隔开）
#include <iostream>
using namespace std;
int main(){
int a, b;
cin>>a>>b;
cout<<a<<"+"<<b<<"="<<a+b<<endl;
}输入： 3 5
输出：
#include <iostream>
using namespace std;
int main(){
int a, b, u, i, num;
cin>>a>>b>>u;
num = 0;
for (i = a; i <= b; i++)
if ((i % u) == 0) num++;
cout<<num<<endl;
return 0;
}输入： 1 100 15
输出：
#include <iostream>
using namespace std;
int main(){
const int SIZE = 100;
int n, f, i, left, right, middle, a[SIZE];
cin>>n>>f;
for (i = 1; i <= n; i++)
cin>>a[i];
left = 1;
right = n;
do {
middle = (left + right) / 2;
if (f <= a[middle])
right = middle;
else
left = middle + 1;
} while (left < right);
cout<<left<<endl;
return 0;
}输入：
12 17
2 4 6 9 11 15 17 18 19 20 21 25
输出：