信息学奥赛-提高级 题库
对右图使用Dijkstra算法计算S点到其余各点的最短路径长度时,到B点的距离d[B]初始时赋为8,在算法的执行过程中还会出现的值有( )。

平面图可以在画在平面上,且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至少有6条边,如右图所示。那么,5个顶点的平面图至少有 条边。

9
定义一种字符串操作,一次可以将其中一个元素移到任意位置。举例说明,对于字符串“BCA”可以将 A 移到 B 之前,变字符串“ABC”。如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要________次操作。
4
(大整数开方) 输入一个正整数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];
return 0;
}
① ans.num[i + j - 1]
② ans.num[i] %= 10(或 ans.num[i] = ans.num[i] % 10) ③ a.num[i] + b.num[i]
④ ans.num[i] % 2(或 ans.num[i] & 1)
⑤ ans.len++(或 ++ans.len 或 ans.len += 1 或 ans.len = ans.len + 1)
⑥ a.len < b.len
⑦ '0'(或 48)
⑧ times(middle, middle), target
(笛卡尔树)对于一个给定的两两不等的正整数序列,笛卡尔树是这样的一棵二叉树:首先,它是一个最小堆,即除了根结点,每个节点的权值都大雨父节点的权值;其次,它的中序遍历恰好就是给定的序列。例如,对于序列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;
}
① num++
② j = i
③ solve(left, j – 1, deep + 1)
④ solve(j + 1, right, deep + 1)

假设输入的n, k和d[i]都是不超过10000的正整数,且k不超过n,并 假设rand()函数产生的是均匀的随机数,完成下面的判断题和单选题:

01 #include <iostream>
02 #include <queue>
03 using namespace std;
04
05 const int max1 = 2000000000;
06
07 class Map (
08 struct item {
09 string key; int value;
10} d[max1];
11int cnt;
12public:
13int find(string x) {
14for (int i = 0; i < cnt; ++i)
15if (d[i].key == x)
16return d[i].value;
17return -1;
18}
19static int end() { return -1; }
20void insert(string k, int v) {
21d[cnt].key = k; d[cnt++].value = v;
22}
23} s[2];
24
25class Queue {
26string q[max1];
27int head, tail;
28public:
29void pop() { ++head; }
30string front() { return q[head + 1]; }
31bool empty() { return head == tail; }
32void push(string x) { q[++tail] = x; }
33} q[2];
34
35string st0,stl;
36int m;
37
38string LtoR(string s, int L, int R) {
39string t = s;
40char tmp = t[L];
41for (int i = L; i < R; ++i)
42t[i] = t[i + 1];
43t[R] = tmp;
44return t;
45}
46
47string RtoL(string s, int L,int R) {
48string t = s;
49char tmp = t[R];
50for (int i = R; i > L; --i)
51t[i] = t[i - 1];
52t[L] = tmp;
53return t;
54}
55
56bool check(string st, int p,int step) {
57if (s[p].find(st) != s[p].end())
58return false;
59++step;
60if (s[p ^ 1].find(st) == s[p].end()) {
61s[p].insert(st, step);
62q[p].push(st);
63return false;
64}
65cout << s[p ^ 1].find(st) + step << end1;
66return true;
67}
68
69int main() {
70cin >> st0 >> stl;
71int len = st0.length();
72if (len != stl.length()) {
73cout << -1 << end1;
74return 0;
75}
76if (st0 == st1) {
77cout << 0 << end1;
78return 0;
79}
80cin >> m;
81s[0].insert(st0, 0); s[1].insert(st1, 0);
82q[0].push(st0); q[1].push(st1);
83for (int p = 0;
84!(q[0].empty() && q[1].empty());
85p ^=1) {
86string st - q[p].front(); q[p].pop();
87int step = s[p].find(st);
88if ((p == 0 &&
89(check(LtoR(st,m, len - 1), p, step) ||
90check(RtoL(st, 0, m), p, step)))
91||
92(p == 1 &&
93(check(LtoR(st,0, m), p, step) ||
94check(RtoL(st, m, len - 1), p, step))))
95return 0;
96}
97cout << -1 << end1;
98return 0;
99}
(分数背包)小S有n块蛋糕,编号从1到n第i块蛋糕的价值是wi, 体积是vi。他有一个大小为B的盒子来装这些蛋糕,也就是说装入盒子的 蛋糕的体积总和不能超过B。
他打算选择一些蛋糕装入盒子,他希望盒子里装的蛋糕的价值之和尽量 大。
为了使盒子里的蛋糕价值之和更大,他可以任意切割蛋糕。具体来说,他 可以选择一个a (0<a<l),并将一块价值是w,体枳为v的蛋糕切割成两 块.其中一块的价值是a・w,体枳是a・v,另一块的价值是(l-a)・w.体 积是(l-a)v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值,以分数的形式输出。
比如n=3, B=8,三块蛋糕的价值分别是4、4、2,体枳分别是5、3、2。 那么最优的方案就是将休积为5的蛋糕切成两份,一份体积是3,价值是 2.4,另一份体积是2,价值是1.6,然后把休积是3的那部分和后两块蛋 糕打包进盒子。最优的价值之和是8.4,故程序输出42/5。
输入的数据范围为:1≤n≤1000,1≤B≤10^5;1≤wi,vi≤100。
提示:将所有的蛋糕按照性价比wi/vi从大到小排序后进行贪心选择。
试补全程序。
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n,B, w[maxn], v[maxn];
int gcd(int u, int v) {
if(v == 0)
return u;
return gcd(v, u % v);
}
void print(int w, int v) {
int d = gcd(w> v);
w = w / d;
v = v / d;
if(v == 1)
printf(”%d\n”, w);
else
printf(”%d/%d\n”, w, v);
}
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
int main() {
scanf("%d %d", &n, &B);
for(int i = 1; i <= n; i ++) {
scanf(”%d%d,&w[i], &v[i]);
}
for(int i = 1; i < n; i ++)
for(int j = 1; j < n; j ++)
if(①){
swap(w[j], w[j + 1]);
swap(v[j],v[j + 1]);
}
int curV, curW;
if(②) {
③
} else {
print(B * w[1], v[1]);
return 0;
}
for(int i = 2; i <= n; i ++)
if(curV + v[i] <= B) {
curV += v[i];
curW += w[i];
} else {
print(④);
return 0;
}
print (⑤);
return 0;
}
(最优子序列)取m=6,给出长度为n的整数序列a1,a2,……an(0 ≤ ai<2m)。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1,b2,…,bk,定 义其子序列分值S为w(b1㊉b2)+w(b2㊉b3)+w(b3㊉b4)+……+w(bk-1㊉bk)。其中㊉表示按位异或。对于空子序列,规定其子序列分值为0。求一个子序列使得其子序列分值最大,输出这个最大值。
输入第一行包含一个整数n(1 ≤ n ≤ 40000).接下来一行包含n个整数 a1,a2,……,an。
提示:考虑优化朴素的动态规划算法,将前
位和后
位分开计算。
Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。
试补全程序。

假设输入的 n 为不大于 100 的正整数,k 为不小于 2 且不大于 100 的正整数,val[i]在int 表示范围内,完成下面的判断题和单选题:
假设输入的 n 在 int 范围内,k 为不小于 2 且不大于 36 的正整数,完成下面的判断题和单选题:
(归并第 k 小)已知两个长度均为 n 的有序数组 a1 和 a2(均为递增序,但不保证严格单调递增),并且给定正整数 k(1≤k≤2n),求数组 a1 和 a2 归并排序后的数组里第 k 小的数值。
试补全程序。
#include <bits/stdc++.h>
using namespace std;
int solve(int *a1, int *a2, int n, int k) {
int left1 = 0, right1 = n - 1;
int left2 = 0, right2 = n - 1;
while (left1 <= right1 && left2 <= right2) {
int m1 = (left1 + right1) >> 1;
int m2 = (left2 + right2) >> 1;
int cnt = ① ;
if ( ② ) {
if (cnt < k) left1 = m1 + 1;
else right2 = m2 - 1;
} else {
if (cnt < k) left2 = m2 + 1;
else right1 = m1 - 1;
}
}
if ( ③ ) {
if (left1 == 0) {
return a2[k - 1];
} else {
int x = a1[left1 - 1], ④ ;
return std::max(x, y);
}
} else {
if (left2 == 0) {
return a1[k - 1];
} else {
int x = a2[left2 - 1], ⑤ ;
return std::max(x, y);
}
}
}
