全部知识点
第6541题
（烽火传递） 烽火台又称烽燧，是重要的军事防御设施，一般建在险要处或交通要道上。 一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息；夜晚燃烧干柴，以火光传递军情。在 某两座城市之间有 n 个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确地传 递，在连续的 m个烽火台中至少要有一个发出信号。现输入 n、m和每个烽火台发出信号的代 价，请计算总共最少花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确传 递。
例如，有 5 个烽火台，他们发出信号的代价依次为 1，2，5，6，2，，且 m为 3，则总共最少 花费代价为 4，即由第 2 个和第 5 个烽火台发出信号。
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
int n,m,r,value[SIZE],heap[SIZE],
pos[SIZE],home[SIZE],opt[SIZE];
//hep[i] 表示用顺序数组储存的堆 heap 中第 i 个元素的值
//pos[i] 表示 opt[i] 在堆 heap中的位置，即 heap[pos[i]]=opt[i]
//home[i] 表示 heap[i] 在序列 opt 中的位置，即 opt[home[i]]=heap[i]
void swap(int i,int j)// 交换堆中的第 i 个和第 j 个元素
{
int tmp;
pos[home[i]]=j;
pos[home[j]]=i;
tmp=heap[i];
head[i]=head[j];
heap[j]=tmp;
tmp=home[i];
home[i]=home[j];
home[j]=tmp;
}
void add(int k)// 在堆中插入 opt[k]
{
int i;
r++;
heap[r]= ① ;
pos[k]=r;
② ;
i=r;
while( (i>1) && (heap[i]<heap[i/2]) )
{
swap(i,i/2);
i/=2;
}
}
void remove(int k)// 在堆中删除 opt[k]
{
int i,j;
i=pos[k];
swap(i,r);;
r--;
if(i==r+1)
return ;
while( (i>1)&&(heap[i]<heap[i/2]) )
{
swap(i,i/2);
i/=2;
}
while(i+i<=r)
{
if( (i+i+1<=r) && (heap[i+i+1]<heap[i+i]) )
j=i+i+1;
else
③ ;
if(hea[i]>heap[j])
{
④ ;
i=j;
}
else
break;
}
}
int main()
{
int i;
cin>>n>>m;
for(i=1;i<=n;i+++)
cin>>value[i];
r=0;
for(i=1;i<=m;i++)
{
opt[i]=value[i];
add(i);
}
for(i=m+1;i<=n;i++)
{
opt[i]= ⑤ ;
remove( ⑥ );
add(i);
}
cout<<heap[1]<<endl;
return 0;
}
第6542题
每份考卷都有一个 8 位二进制序列号。当且仅当一个序列号含有偶数个 1 时，它才是有效的。例如，00000000、01010011都是有效的序列号，而 11111110 不是。那么，有效的序列号共有____个。
第6543题
定义字符串的基本操作为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。将字符串 A 变成字符串 B 的最少操作步数，称为字符串 A 到字符串 B 的编辑距离。字符串 "ABCDEFG" 到字符串 "BADECG" 的编辑距离为____。
第6544题
#include <iostream>
using namespace std;
int main(){
int i, n, m, ans;
cin>>n>>m;
i = n;
ans = 0;
while (i <= m){
ans += i;
i++;
}
cout<<ans<<endl;
return 0;
}输入： 10 20
输出： _________
第6545题
#include <iostream>
#include <string>
using namespace std;
int main(){
string map = "22233344455566677778889999";
string tel;
int i;
cin>>tel;
for (i = 0; i < tel.length(); i++)
if ((tel[i] >= '0') && (tel[i] <= '9'))
cout<<tel[i];
else if ((tel[i] >= 'A') && (tel[i] <= 'Z'))
cout<<map[tel[i] - 'A'];
cout<<endl;
return 0;
}输入： CCF-NOIP-2011
输出： _______________
第6546题
#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
输出：________
第6547题
#include <iostream>
using namespace std;
int solve(int n, int m){Preferences
int i, sum;
if (m == 1) return 1;
sum = 0;
for (i = 1; i < n; i++)
sum += solve(i, m - 1);
return sum;
}
int main(){
int n, m;
cin>>n>>m;
cout<<solve(n, m)<<endl;
return 0;
}输入： 7 4
输出： _________
第6548题
（子矩阵） 给输入一个 n1*m1 的矩阵 a，和 n2*m2 的矩阵 b，问 a 中是否存在子矩阵和 b 相等。 若存在，输出所有子矩阵左上角的坐标：若不存在输出“ There is no answer ”。
#include <iostream>
using namespace std;
const int SIZE = 50;
int n1, m1, n2, m2, a[SIZE][SIZE], b[SIZE][SIZE];
int main(){
int i, j, k1, k2;
bool good, haveAns;
cin>>n1>>m1;
for (i = 1; i <= n1; i++)
for (j = 1; j <= m1; j++)
cin>>a[i][j];
cin>>n2>>m2;
for (i = 1; i <= n2; i++)
for (j = 1; j <= m2; j++)
①;
haveAns = false;
for (i = 1; i <= n1 - n2 + 1; i++)
for (j = 1; j <= ②; j++){
③;
for (k1 = 1; k1 <= n2; k1++)
for(k2 = 1; k2 <= ④; k2++) {
if (a[i + k1 - 1][j + k2 - 1] != b[k1][k2])
good = false;
}
if (good) {
cout<<i<<' '<<j<<endl;
⑤;
}
}
if (!haveAns)
cout<<"There is no answer"<<endl;
return 0;
}
第6549题
( 大整数开方 ) 输入一个正整数 n（1≤n≤10100），试用二分法计算它的平方根的整数部分。
#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;
}
第6550题
平面图是可以画在平面上、且它的边仅在顶点上才能相交的简单无向 图。 4 个顶点的平面图至多有 6 条边，如右图所示。那么， 5 个顶点的平面 图至多有 ________ 条边。
第6551题
定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符 串”BCA”，可以将 A 移到 B 之前，变成字符串 ”ABC”。如果要将字符串 ”DACHEBGIF ”变成 "ABCDEFGHI" ，最少需要 ________ 次操作。
第6552题
#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
输出： _________
第6553题
#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
输出： _________
第6554题
#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
输出：________
第6555题
#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
输出：______
第6556题
（大整数开方 ）输入一个正整数 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;
}
第6557题
（笛卡尔树 ）对于一个给定的两两不等的正整数序列， 笛卡尔树是这样的一棵二叉树。首先，它是一个最小堆，即 除了根结点外， 每个结点的权值都大于父结点的权值； 其次， 它的中序遍历恰好就是给定的序列。例如，对于序列 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;
}
第6558题
如果平面上任取 n 个整点(横纵坐标都是整数)，其中一定存在两个点，它们连线的中点也是整点，那么 n 至少是____。
第6559题
在 NOI 期间，主办单位为了欢迎来自各国的选手，举行了盛大的晚宴。在第 十八桌，有 5 名大陆选手和 5 名港澳选手共同进膳。 为了增进交流， 他们决定相 隔就坐，即每个大陆选手左右旁都是港澳选手， 每个港澳选手左右旁都是大陆选 手。那么，这一桌一共有 _______种不同的就坐方案。注：如果在两个方案 中，每个选手左右相邻的选手相同 ，则视为同一种方案。
第6560题
#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
输出： _______