信息学奥赛-提高级 题库
(容器分水)有两个容器,容器 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);
}
}
#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,完成下面的判断题和单选题:
#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,完成下面的判断题和单选题:
#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;
}
假设输入总是合法的(一个整数和一个不含空白字符的字符串,用空格隔开),完成下面的判断题和单选题:
(分数背包)小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;
}

假设输入的n, k和d[i]都是不超过10000的正整数,且k不超过n,并 假设rand()函数产生的是均匀的随机数,完成下面的判断题和单选题:
(分数背包)小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;
}
#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;
}
#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;
}
本题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]的子序列。
(取石子)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;
}
甲乙丙丁四人在考虑周末要不要外出郊游。
已知①如果周末下雨,并且乙不去,则甲一定不去;②如果乙去,则丁一定去;③如果丙去,则丁一定不去;④如果丁不去,而且甲不去,则丙一定不去。如果周末丙去了,则甲________(去了/没去)(1 分),乙________(去了/没去)(1 分),丁________(去了/没去)(1 分),周末________(下雨/没下雨)(2 分)。(2018年提高组)
去了
没去
没去
没下雨
方程 a*b = (a or b) * (a and b),在 a,b 都取 [0, 31] 中的整数时,共有_____组解。(*表示乘法;or 表示按位或运算;and 表示按位与运算)(2018年提高组)
454
一只小猪要买 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]]


