首页 › 题库 › 信息学奥赛 › 综合练习

信息学奥赛-提高级 题库

共 511 道题 ,第 22 / 26 页 · 按题型筛选,点「查看答案」核对解析
421 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

阅读程序

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

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

阅读程序

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

(容器分水)有两个容器,容器 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);

  }

} 

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

#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,完成下面的判断题和单选题:

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

#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,完成下面的判断题和单选题:

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

#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;

}

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

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

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

}


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

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

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

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

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

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

答案与解析
正确答案:A,B,C,D
这道题暂未补解析。
题目详情
431 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

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

}


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

#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;

}

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

#include <cstdio>

using namepace std ;


const int maxn =1000;

int n;

int fa[maxn],cnt [maxn];


int getroot(int v ) {

if (fa[v] == v) return v;

return getroot(fa[v]);

}


int main ( ) {

cin >> n;

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

fa[i]=i;

cnt[i]=1;

}

int ans = 0 ;

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

int a,b,x,y,;

cin >>a>>b

x=getRoot(a);

y=getRoot(b);

ans +=cnt[x]cnt[y];

fa[x]=y;

cnt[y] +=cnt[x];

}

cout<<ans<<endl;

return 0;

}

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

本题t是s的子序列的意思是:从s中删去若干个字符,可以得到t;特别的,如果s=t,那么t也是s的子序列;空串是任何串的子序列。例如“acd”是“abcde”的子序列,“acd”是“acd”的子序列,但“adc”不是“abcde”的子序列。

S[x…y]表示s[x]…s[y]共y-x+1个字符构成的字符串,若x>y则s[x…y]是空串。t[x…y]同理。

#include <cstdio>

#include <algorithm>

using namespace std;

const int max1 = 202;

string s, t ;

int pre[max1], suf[max1]


int main() {

cin>>s>>t;

int slen =s. length(), tlen= t. length();

for (int I = 0 ,j = 0 ; i< slen; ++i) {

if (j< tlen&&s[i]t[j] ) ++j;

pre[i] = j;// t[0…j-1]是s[0…i]的子序列

 }

for (int I = slen -1 ,j= tlen -1; I >=0;–i) {

if(j>=0&& s[i] == t [j]) –j;

suf [i]= j; //t[j+1…tlen-1]是s[i…slen-1]的子序列

}

suf[slen] = tlen -1;

int ans = 0;

for (int i=0, j=0, tmp=o; i<=slen; ++i){

while(j<=slen && tmp >=suf[j] + 1) ++j;

ans =max(ans, j – I – 1);

tmp = pre[i];

}

cout <<ans << end1;

return 0;

}

提示:

t[0…pre[i]-1]是s[0…i]的子序列;

t[suf[i]+1…tlen-1]是s[i…slen-1]的子序列。

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

(取石子)Alice和Bob两个人在玩取石子游戏。他们制定了n条取石子的规则,第i条规则为:如果剩余石子的个数大于等于a[i]且大于等于b[il, 那么他们可以取走b[i]个石子。他们轮流取石子。如果轮到某个人取石子, 而他无法按照任何规则取走石子,那么他就输了。一开始石子有m个。请问先取石子的人是否有必胜的方法?

输入第一行有两个正整数,分别为规则个数n(1≤n≤64),以及石子个数m(≤10^7)。

接下来n行。第i行有两个正整数a[i]和b[i](1≤a[i]≤10^7,1≤b[i]≤64)

如果先取石子的人必胜,那么输出“Win”,否则输出“Loss”

提示:

 可以使用动态规划解决这个问题。由于b[i]不超过64,所以可以使用64位无符号整数去压缩必要的状态。

 status是胜负状态的二进制压缩,trans是状态转移的二进制压缩。

试补全程序。

代码说明:

 “~”表示二进制补码运算符,它将每个二进制位的0变成1、1变为0; 

 而“^”表示二进制异或运算符,它将两个参与运算的数中的每个对应的二进制位一一进行比较,若两个二进制位相同,则运算结果的对应二进制位为0,反之为1。

ull标识符表示它前面的数字是unsigned long long 类型。

#include <cstdio>

#include<algorithm>

using namespace std ;


const int maxn =64;


int n,m;

int a[maxn],b[maxn];

unsigned long long status ,trans;

bool win;


int main() {

scanf("%d%d", &n, &m);

for (int i = 0; i<n; ++i)

scanf("%d%d", &a[i], &b[i]);

for(int i = 0; i < n; ++i)

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

if (a[i] > a[j]) {

swap(a[i],a[j]);

swap(b[i],b[j]);

}

status = ___(1)___;

trans = 0;

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

while (j < n && ___(2)___) {

___(3)___

++j;

}

win = ___(4)___;

___(5)___;

}

puts(win ? "Win" : "Loss");

return 0;

}

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

NOIP初赛中,选手可以带入考场的有( )。

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

甲乙丙丁四人在考虑周末要不要外出郊游。

已知①如果周末下雨,并且乙不去,则甲一定不去;②如果乙去,则丁一定去;③如果丙去,则丁一定不去;④如果丁不去,而且甲不去,则丙一定不去。如果周末丙去了,则甲________(去了/没去)(1 分),乙________(去了/没去)(1 分),丁________(去了/没去)(1 分),周末________(下雨/没下雨)(2 分)。(2018年提高组)

答案与解析
参考答案

去了

没去

没去

没下雨

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

方程 a*b = (a or b) * (a and b),在 a,b 都取 [0, 31] 中的整数时,共有_____组解。(*表示乘法;or 表示按位或运算;and 表示按位与运算)(2018年提高组)

答案与解析
参考答案

454

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

一只小猪要买 N 件物品(N 不超过 1000)。

它要买的所有物品在两家商店里都有卖。第 i 件物品在第一家商店的价格是a[i],在第二家商店的价格是 b[i],两个价格都不小于 0 且不超过 10000。如果在第一家商店买的物品的总额不少于 50000,那么在第一家店买的物品都可以打 95 折(价格变为原来的 0.95 倍)。

求小猪买齐所有物品所需最少的总额。

输入:第一行一个数 N。接下来 N 行,每行两个数。第 i 行的两个数分别代表 a[i],b[i]。

输出:输出一行一个数,表示最少需要的总额,保留两位小数。

试补全程序。(第一空 2 分,其余 3 分)


#include <cstdio>

#include <algorithm>

using namespace std;


const int Inf = 1000000000;

const int threshold = 50000;

const int maxn = 1000;


int n, a[maxn], b[maxn];

bool put_a[maxn];

int total_a, total_b;

double ans;

int f[threshold];


int main() {

scanf("%d", &n);

total_a = total_b = 0;

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

scanf("%d%d", a + i, b + i);

if (a[i] <= b[i]) total_a += a[i];

else total_b += b[i];

}

ans = total_a + total_b;

total_a = total_b = 0;

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

if (      (1)      ) {

put_a[i] = true;

total_a += a[i];

} else {

put_a[i] = false;

total_b += b[i];

}

}

if (      (2)      ) {

printf("%.2f", total_a * 0.95 + total_b);

return 0;

}

f[0] = 0;

for (int i = 1; i < threshold; ++i)

f[i] = Inf;

int total_b_prefix = 0;

for (int i = 0; i < n; ++i)

if (!put_a[i]) {

total_b_prefix += b[i];

for (int j = threshold - 1; j >= 0; --j) {

if (      (3)      >= threshold && f[j] != Inf)

ans = min(ans, (total_a + j + a[i]) * 0.95

                                +       (4)      );

f[j] = min(f[j] + b[i], j >= a[i] ?      (5)      : Inf);

}

}

printf("%.2f", ans);

return 0;

}

答案与解析
参考答案

(1)a[i] * 0.95 <= b[i] 或 b[i] >= a[i] * 0.95

(2)total_a >= threshold 或 threshold <= total_a 或 total_a >= 50000 或 50000 <= total_a

(3)total_a + j + a[i]

(4)f[j] + total_b - total_b_prefix

(5)f[j - a[i]]

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

对于入栈顺序为a,b,c,d,e,f,g的序列,下列( )不可能是合法的出栈序列

答案与解析
正确答案:C
这道题暂未补解析。
题目详情