首页 › 题库 › 信息学奥赛 › 1 数据结构进阶

信息学奥赛-提高级 题库

共 682 道题 ,第 26 / 35 页 · 按题型筛选,点「查看答案」核对解析
章节 1 数据结构进阶 清除
501 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

消消乐(game)

【题目描述】

小L现在在玩一个低配版本的消消乐,该版本的游戏是一维的,一次也只能消除两个相邻的元素。

现在,他有一个长度为n且仅由小写字母构成的字符串。我们称一个字符串是可消除的,当且仅当可以对这个字符串进行若干次操作,使之成为一个空字符串。

其中每次操作可以从字符串中删除两个相邻的相同字符,操作后剩余字符串会拼接在一起。

小L想知道,这个字符串的所有非空连续子串中,有多少个是可消除的。

【输入格式】

从文件game.in中读入数据。

输入的第一行包含一个正整数n,表示字符串的长度。

输入的第二行包含一个长度为n且仅由小写字母构成的的字符串,表示题目中询问的字符串。

【输出格式】

输出到文件game.out中。

输出一行包含一个整数,表示题目询问的答案。


【样例1输入】

8
accabccb

【样例1输出】

5

【样例1解释】

一共有5个可消除的连续子串,分别是cc、acca、cc、bccb、accabccb。


【样例2】

见选手目录下的game/game2.in与game/game2.ans。

【样例3】

见选手目录下的game/game3.in与game/game3.ans。

【样例4】

见选手目录下的game/game4.in与game/game4.ans。

答案与解析
参考答案

题解1:


题解2:


题解3:

题目详情
502 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

种树(tree)

【题目描述】

你是一个森林养护员,有一天,你接到了一个任务:在一片森林内的地块上种树,并养护至树木长到指定的高度。

森林的地图有n片地块,其中1号地块连接森林的入口。共有n−1条道路连接这些地块,使得每片地块都能通过道路互相到达。最开始,每片地块上都没有树木。

你的目标是:在每片地块上均种植一棵树木,并使得i号地块上的树的高度生长到不低于ai米。

你每天可以选择一个未种树且与某个已种树的地块直接邻接(即通过单条道路相.连)的地块,种一棵高度为0米的树。如果所有地块均已种过树,则你当天不进行任何操作。特别地,第1天你只能在1号空地种树。

对每个地块而言,从该地块被种下树的当天开始,该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同,在第x天,i号地块上的树会长高max(bi+x∗ci,1)

米。注意这里的x是从整个任务的第一天,而非种下这棵树的第一天开始计算。

你想知道:最少需要多少天能够完成你的任务?

【输入格式】

从文件tree.in中读入数据。

输入的第一行包含一个正整数n,表示森林的地块数量。

接下来n行:每行包含三个整数ai,bi,ci,分别描述一片地块,含义如题目描述中所述。

接下来n−1行:每行包含两个正整数ui,vi,表示一条连接地块ui和vi的道路。

【输出格式】

输出到文件tree.out中。

输出一行仅包含一个正整数,表示完成任务所需的最少天数。


【样例1输入】

4
12 1 1
2 4 ‐1
10 3 0
7 10 ‐2
1 2
1 3
3 4

【样例1输出】

1 5

【样例1解释】

第1天:在地块1种树,地块1的树木长高至2米。

第2天:在地块3种树,地块1,3的树木分别长高至5,3米。

第3天:在地块4种树,地块1,3,4的树木分别长高至9,6,4米。

第4天:在地块2种树,地块1,2,3,4的树木分别长高至14,1,9,6米。

第5天:地块1,2,3,4的树木分别长高至20,2,12,7米。

【样例2】

见选手目录下的tree/tree2.in与tree/tree2.ans。

【样例3】

见选手目录下的tree/tree3.in与tree/tree3.ans。

【样例4】

见选手目录下的tree/tree4.in与tree/tree4.ans。


【数据范围】

对于所有测试数据有:1≤n≤105,1≤ai≤1018,1≤bi≤109,0≤|ci|≤109,1≤ui,vi≤n。保证存在方案能在109天内完成任务

特殊性质A:对于所有1≤i≤n,均有ci=0;

特殊性质B:对于所有1≤i<n,均有ui=i,vi=i+1;

特殊性质C:与任何地块直接相连的道路均不超过2条;

特殊性质D:对于所有1≤i<n,均有ui=1。

答案与解析
参考答案

题解1:

题解2:

题目详情
503 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

假设输入的x是不超过65535的自然数,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
504 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

阅读程序

假设输入的n是不超过1000000的自然数,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
505 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

阅读程序

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
506 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

(第k小路径)给定一张n个点m条边的有向无环图,顶点编号从0到n-1对于一条路径,我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中,“路径序列”字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n,m≤105和1≤k≤1018。

在程序中,我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量,确定路径的起点,然后可以类似地依次求出路径中的每个点。

试补全程序。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
507 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

(归并第 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);

    }

  }

} 

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
508 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

(容器分水)有两个容器,容器 1 的容量为为 a 升,容器 2 的容量为 b 升;同时允许下列的三种操作,分别为:

1)FILL(i):用水龙头将容器 i(i∈{1,2})灌满水;

2)DROP(i):将容器 i 的水倒进下水道;

3)POUR(i,j):将容器 i 的水倒进容器 j(完成此操作后,要么容器 j 被灌满,要么容器 i 被清空)。

求只使用上述的两个容器和三种操作,获得恰好 c 升水的最少操作数和操作序列。上述 a、b、c 均为不超过 100 的正整数,且 c≤max{a,b}。

试补全程序。


#include <bits/stdc++.h> 

using namespace std; 

const int N = 110; 

 

int f[N][N]; 

int ans; 

int a, b, c; 

int init; 


int dfs(int x, int y) { 

  if (f[x][y] != init)

    return f[x][y];

  if (x == c || y == c) 

    return f[x][y] = 0;

  f[x][y] = init - 1; 

  f[x][y] = min(f[x][y], dfs(a, y) + 1); 

  f[x][y] = min(f[x][y], dfs(x, b) + 1); 

  f[x][y] = min(f[x][y], dfs(0, y) + 1); 

  f[x][y] = min(f[x][y], dfs(x, 0) + 1); 

  int t = min(a - x, y); 

  f[x][y] = min(f[x][y],      ①     ); 

  t = min(x, b - y); 

  f[x][y] = min(f[x][y],      ②     ); 

  return f[x][y];

} 


void go(int x, int y) { 

  if (     ③     ) 

    return;

  if (f[x][y] == dfs(a, y) + 1) { 

    cout << "FILL(1)" << endl;

    go(a, y);

  } else if (f[x][y] == dfs(x, b) + 1) { 

    cout << "FILL(2)" << endl;

    go(x, b);

  } else if (f[x][y] == dfs(0, y) + 1) { 

    cout << "DROP(1)" << endl;

    go(0, y);

  } else if (f[x][y] == dfs(x, 0) + 1) { 

    cout << "DROP(2)" << endl;

    go(x, 0);

  } else { 

    int t = min(a - x, y); 

    if (f[x][y] ==      ④     ) { 

      cout << "POUR(2,1)" << endl;

      go(x + t, y - t); 

    } else {

      t = min(x, b - y); 

      if (f[x][y] ==      ⑤     ) { 

        cout << "POUR(1,2)" << endl;

        go(x - t, y + t); 

      } else

        assert(0);

    }

  }

} 


int main() { 

  cin >> a >> b >> c; 

  ans = 1 << 30; 

  memset(f, 127, sizeof f);

  init = **f;

  if ((ans = dfs(0, 0)) == init - 1) 

    cout << "impossible";

  else {

    cout << ans << endl;

    go(0, 0);

  }

} 

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
509 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

#include <iostream>

#include <cmath>

using namespace std;


const double r = acos(0.5);


int a1, b1, c1, d1;

int a2, b2, c2, d2;


inline int sq(const int x) { return x * x; }

inline int cu(const int x) { return x * x * x; }


int main()

{

cout.flags(ios::fixed);

cout.precision(4);


cin >> a1 >> b1 >> c1 >> d1;

cin >> a2 >> b2 >> c2 >> d2;


int t = sq(a1 - a2) + sq(b1 - b2) + sq(c1 - c2);


if (t <= sq(d2 - d1)) cout << cu(min(d1, d2)) * r * 4;

else if (t >= sq(d2 + d1)) cout << 0;

else {

double x = d1 - (sq(d1) - sq(d2) + t) / sqrt(t) / 2;

double y = d2 - (sq(d2) - sq(d1) + t) / sqrt(t) / 2;

cout << (x * x * (3 * d1 - x) + y * y * (3 * d2 - y)) * r;

}

cout << endl;

return 0;

}

假设输入的所有数的绝对值都不超过 1000,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
510 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

#include <algorithm>

#include <iostream>

using namespace std;


int n, a[1005];


struct Node

{

int h, j, m, w;


Node(const int _h, const int _j, const int _m, const int _w):

h(_h), j(_j), m(_m), w(_w)

{ }


Node operator+(const Node &o) const

{

return Node(

max(h, w + o.h),

max(max(j, o.j), m + o.h),

max(m + o.w, o.m),

w + o.w);

}

};


Node solve1(int h, int m)

{

if (h > m)

return Node(-1, -1, -1, -1);

if (h == m)

return Node(max(a[h], 0), max(a[h], 0), max(a[h], 0), a[h]);

int j = (h + m) >> 1;

return solve1(h, j) + solve1(j + 1, m);

}


int solve2(int h, int m)

{

if (h > m)

return -1;

if (h == m)

return max(a[h], 0);

int j = (h + m) >> 1;

int wh = 0, wm = 0;

int wht = 0, wmt = 0;

for (int i = j; i >= h; i--) {

wht += a[i];

wh = max(wh, wht);

}

for (int i = j + 1; i <= m; i++) {

wmt += a[i];

wm = max(wm, wmt);

}

return max(max(solve2(h, j), solve2(j + 1, m)), wh + wm);

}


int main()

{

cin >> n;

for (int i = 1; i <= n; i++) cin >> a[i];

cout << solve1(1, n).j << endl;

cout << solve2(1, n) << endl;

return 0;

}

假设输入的所有数的绝对值都不超过 1000,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
511 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

#include <iostream>

#include <string>

using namespace std;


char base[64];

char table[256];


void init()

{

for (int i = 0; i < 26; i++) base[i] = 'A' + i;

for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;

for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;

base[62] = '+', base[63] = '/';


for (int i = 0; i < 256; i++) table[i] = 0xff;

for (int i = 0; i < 64; i++) table[base[i]] = i;

table['='] = 0;

}


string encode(string str)

{

string ret;

int i;

for (i = 0; i + 3 <= str.size(); i += 3) {

ret += base[str[i] >> 2];

ret += base[(str[i] & 0x03) << 4 | str[i + 1] >> 4];

ret += base[(str[i + 1] & 0x0f) << 2 | str[i + 2] >> 6];

ret += base[str[i + 2] & 0x3f];

}

if (i < str.size()) {

ret += base[str[i] >> 2];

if (i + 1 == str.size()) {

ret += base[(str[i] & 0x03) << 4];

ret += "==";

}

else {

ret += base[(str[i] & 0x03) << 4 | str[i + 1] >> 4];

ret += base[(str[i + 1] & 0x0f) << 2];

ret += "=";

}

}

return ret;

}


string decode(string str)

{

string ret;

int i;

for (i = 0; i < str.size(); i += 4) {

ret += table[str[i]] << 2 | table[str[i + 1]] >> 4;

if (str[i + 2] != '=')

ret += (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 2]] >> 2;

if (str[i + 3] != '=')

ret += table[str[i + 2]] << 6 | table[str[i + 3]];

}

return ret;

}


int main()

{

init();

cout << int(table[0]) << endl;


int opt;

string str;

cin >> opt >> str;

cout << (opt ? decode(str) : encode(str)) << endl;

return 0;

}

假设输入总是合法的(一个整数和一个不含空白字符的字符串,用空格隔开),完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
512 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

(分数背包)小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;

}


答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
513 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

(最优子序列)取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时的最大价值。

试补全程序。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
514 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

假设输入的n和d[i]都是不超过10000的正整数,完成下面的判断题和单 选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
515 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

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

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
516 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

(2.5分)当输入的d[i]是严格单调递增序列时,第17行的 “swap”平均执行次数是()。

答案与解析
正确答案:A,B,C,D
这道题暂未补解析。
题目详情
517 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.4 并查集

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}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
518 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

(分数背包)小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;

}


答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
519 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

(最优子序列)取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时的最大价值。

试补全程序。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
520 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

#include <cstdio>

using namespace std;

int n;

int a[100];


int main( ) {

scanf(“%d”,&n);

for(int i = 1; i <= n; ++i) {

scanf(“%d”,&a[i])

int ans = 1

for (int i = 1; i <= n; ++i) {

if ( i > 1 && a[i] < a[i-1])

ans = i ;

while (ans < n && a[i] >= a[ans+1])

++ans;

printf(“%d/n”, ans);

}

return 0;

}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情