信息学奥赛-提高级 题库
有5个红色球和5个蓝色球,除颜色外完全相同,将10个球排成一排,要求任意两个蓝色球都不能相邻,有多少种不同的排列方法?
25
30
6
120
先将所有红色球排成一排,会形成6个空隙,每个空隙最多放一个蓝色球,从6个空隙中选5个放蓝球,方案数为C(6,5)=6。
对于一个1到n的排列p(即1到n中每一个数在p中出现了恰好一次),令qi为第i个位置之后第一个比pi值更大的位置,如果不存在这样的位置,则qi= n +1。举例来说,如果n = 5且p为1 5 4 2 3,则q为2 6 6 5 6。
下列程序读入了排列p,使用双向链表求解了答案。试补全程序。(第二空2分,其余 3 分)
数据范围 1 ≤ n ≤ 105。
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int L[N], R[N], a[N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
(1) ;
}
for (int i = 1; i <= n; ++i) {
R[i] = (2) ;
L[i] = i - 1;
}
for (int i = 1; i <= n; ++i) {
L[ (3) ] = L[a[i]];
R[L[a[i]]] = R[ (4) ];
}
for (int i = 1; i <= n; ++i) {
cout << (5) << " ";
}
cout << endl;
return 0;
}
(1)a[x] := i a[x] = i
(2)i + 1
(3)R[a[i]]
(4)a[i]
(5)R[i]
(排列数)输入两个正整数 n, m (1 ≤ n ≤ 20, 1 ≤ m ≤ n),在 1~n 中任取 m 个数,按字典序从小到大输出所有这样的排列。例如
输入:3 2
输出:
1 2
1 3
2 1
2 3
3 1
3 2
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 25;
bool used[SIZE];
int data[SIZE];
int n, m, i, j, k;
bool flag;
int main()
{
cin>>n>>m;
memset(used, false, sizeof(used));
for (i = 1; i <= m; i++)
{
data[i] = i;
used[i] = true;
}
flag = true;
while (flag)
{
for (i = 1; i <= m-1; i++) cout<<data[i]<<" ";
cout<<data[m]<<endl;
flag = ① ;
for (i = m; i >= 1; i--)
{
② ;
for (j = data[i]+1; j <= n; j++) if (!used[j])
{
used[j] = true;
data[i] = ③ ;
flag = true;
break;
}
if (flag)
{
for (k = i+1; k <= m; k++)
for (j = 1; j <= ④ ; j++) if (!used[j])
{
data[k] = j;
used[j] = true;
break;
}
⑤ ;
}
}
}
}
①false
②used[data[i]] = false
③j
④n
⑤break
组合数问题
【问题描述】
组合数
表示的是从 n 个物品中选出 m 个物品的方案数。举个例子,从 (1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3) 这三种选择方法。根据组合数的定义,我们可以给出计算组合数
的一般公式:

其中 n!=1×2×…×n 。
小葱想知道如果给定 n,m 和 k,对于所有的 0≤i≤n,0≤j≤min(i,m) 有多少对 (i,j) 满足
是 k 的倍数。
【输入格式】
从文件problem.in中读入数据。
第一行有两个整数 t,k,其中 t 代表该测试点总共有多少组测试数据,k 的意义见【问题描述】。
接下来 t 行每行两个整数 n,m,其中 n,m 的意义见【问题描述】。
【输出格式】
输出到文件problem.out中。
t 行,每行一个整数代表所有的 0≤i≤n,0≤j≤min(i,m) 中有多少对 (i,j) 满足
是 k 的倍数。
【样例1输入】
1 2
3 3
【样例1输出】
1
【样例1说明】
在所有可能的情况中,只有
是 2 的倍数。
【样例2输入】
2 5
4 5
6 7
【样例2输出】
0
7
【子任务】

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=2011;
int c[maxn][maxn],ans[maxn][maxn];
int t,k;
void check()
{
c[0][0]=1;
for(int i=1;i<=2001;i++)
{
c[i][0]=1;
for(int j=1;j<=i;j++)
{
c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
if(!c[i][j]) ans[i][j]++;
}
ans[i][i+1]=ans[i][i];
}
}
int main()
{
cin>>t>>k;
check();
for(int i=1;i<=t;i++)
{
int n,m;
cin>>n>>m;
int cnt=(m>n?ans[n][n]:ans[n][m]);
cout<<cnt<<endl;
}
return 0;
}
贪吃蛇(snakes)
【题目描述】
草原上有 n 条蛇,编号分别为 1,2, ⋯ , n。初始时每条蛇有一个体力值ai,我们称编号为 x 的蛇实力比编号为 y 的蛇强当且仅当它们当前的体力值满足 ax > ay,或者 ax = ay 且 x > y。
接下来这些蛇将进行决斗,决斗将持续若干轮,每一轮实力最强的蛇拥有选择权,可以选择吃或者不吃掉实力最弱的蛇:
1. 如果选择吃,那么实力最强的蛇的体力值将减去实力最弱的蛇的体力值,实力最弱的蛇被吃掉,退出接下来的决斗。之后开始下一轮决斗。
2. 如果选择不吃,决斗立刻结束。
每条蛇希望在自己不被吃的前提下在决斗中尽可能多吃别的蛇(显然,蛇不会选择吃自己)。
现在假设每条蛇都足够聪明,请你求出决斗结束后会剩几条蛇。
本题有多组数据,对于第一组数据,每条蛇体力会全部由输入给出,之后的每一组数据,会相对于上一组的数据,修改一部分蛇的体力作为新的输入。
【输入格式】
输入文件名为 snakes.in。
第一行一个正整数 T,表示数据组数。
接下来有 T 组数据,对于第 1 组数据,第一行一个正整数 n,第二行 n个非负整数表示 ai。
对于第 2 组到第 T 组数据,每组数据:
第一行第一个非负整数 k 表示体力修改的蛇的个数。
第二行 2k 个整数,每两个整数组成一个二元组 (x, y),表示依次将 ax的值改为 y。一个位置可能被修改多次,以最后一次修改为准。
【输出格式】
输入文件名为 snakes.out。
输出 T 行,每行一个整数表示最终存活的蛇的条数。
【样例 1 输入】
2
3
11 14 14
3
1 5 2 6 3 25
【样例 1 输出】
3
1
【样例 1 解释】
第一组数据,第一轮中 3 号蛇最强,1 号蛇最弱。若 3 号蛇选择吃,那么它将在第二轮被 2 号蛇吃掉。因此 3 号蛇第一轮选择不吃,3 条蛇都将存活。
对于第二组数据,3 条蛇体力变为 5,6,25。第一轮中 3 号蛇最强,1 号蛇最弱,若它选择吃,那么 3 号蛇体力值变为 20,在第二轮中依然是最强蛇并能吃掉 2 号蛇,因此 3 号蛇会选择两轮都吃,最终只有 1 条蛇存活。
【样例 2 输入】
2
5
13 31 33 39 42
5
1 7 2 10 3 24 4 48 5 50
【样例 2 输出】
5
3
【数据范围与提示】
对于 20%的数据:n = 3。
对于 40%的数据:n ≤ 10。
对于 55%的数据:n ≤ 2000。
对于 70%的数据:n ≤ 5 × 10^4。
对于 100%的数据:3 ≤ n ≤ 10^6,1 ≤ T ≤ 10,0 ≤ k ≤ 10^5,0 ≤ ai, y ≤10^9。
保证每组数据(包括所有修改完成后的)的 ai 以不降顺序排列。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=1e6+100,INF=1e9;
struct Node
{
int val,num;
#define val(i) a[i].val
#define num(i) a[i].num
bool operator < (const Node y)
{
return val==y.val?num<y.num:val<y.val;
}
bool operator == (const Node y)
{
return val==y.val && num==y.num;
}
}a[N];
int T,n,k,ph,pb;
queue<Node> q;
Node blank={0,0},black={INF,INF};
Node Max(Node x,Node y)
{
return (x<y)?y:x;
}
Node Min(Node x,Node y)
{
return (x<y)?x:y;
}
bool query(Node la)
{
int cnt=0;
Node bk=Min(pb<ph?a[pb+1]:black,q.size()?q.back():black);
while(1)
{
Node hd=Max(pb<ph?a[ph]:blank,q.size()?q.front():blank);
if(a[ph]==hd)
ph--;
else
if(q.size())
q.pop();
if(hd==bk)
break;
hd.val-=la.val;
if(bk<hd)
break;
la=hd;cnt++;
}
return cnt&1;
}
int main()
{
scanf("%d",&T);
for(int i=1;i<=T;i++)
{
if(i==1)
{
scanf("%d",&n);
for(int j=1;j<=n;j++)
scanf("%d",&val(j)),num(j)=j;
}
else
{
scanf("%d",&k);
for(int j=1,x,y;j<=k;j++)
{
scanf("%d%d",&x,&y);
val(x)=y;
}
}
ph=n,pb=1;
while(q.size())
q.pop();
while(pb<=ph)
{
Node x=Max((ph>pb)?a[ph]:blank,q.size()?q.front():blank);
if(a[ph]==x)
ph--;
else
q.pop();
x.val-=val(pb);
if(x<a[pb+1] && n-pb>1)
{
if(query(x))
pb++;
break;
}
q.push(x);pb++;
}
printf("%d\n",n-pb+1);
}
return 0;
}
格雷码
【题目描述】
通常,人们习惯将所有n位二进制串按照字典序排列,例如所有2位二进制串按 字典序从小到大排列为:00, 01, 10, 11
格雷码(Gray Code)是一种特殊的n位二进制串排列法,它要求相邻的两个二进 制串间恰好有一位不同.特别地,第一个串与最后一个串也算作相邻。
所有2位二进制串按格雷码排列的一个例子为:00, 01, 11, 10。
n位格雷码不止一种,下面给出其中一种格雷码的生成算法:
1.1位格雷码由两个1位二进制串组成,顺序为:0, 1。
2.n + 1位格雷码的前2^n个二进制串,可以由依此算法生成的n位格雷码(总共 2^n个n位二进制串)按顺序排列,再在每个串前加一个前缀0构成。
3.n + 1位格雷码的后2^n个二进制串,可以由依此算法生成的n位格雷码(总共 2^n个n位二进制串)按逆序排列,再在每个串前加一个前缀1构成。
综上,n + 1位格雷码,由n位格雷码的2^n个二进制串按顺序排列再加前缀0,和 按逆序排列再加前缀1构成,共2^n+1个二进制串。另外,对于n位格雷码中的2^n个 二进制串,我们按上述算法得到的排列顺序将它们从0~2^n - 1编号。
按该算法,2位格雷码可以这样推出:
1.己知1位格雷码为0, 1
2.前两个格雷码为00, 01.后两个格雷码为11, 10。合并得到00, 01, 11, 10, 编号依次为0〜3。
同理,3位格雷码可以这样推出:
1.己知2位格雷码为:00, 01, 11 10。
2.前四个格雷码为:000, 001, 011.010。后四个格雷码为:110, 111, 101, 100。合并得到:000, 001. 011, 010, 110, 111. 101, 100,编号依次为 0 ~7。
现在给出n,k请你求出按上述算法生成的n位格雷码中的k号二进制串。
【输入格式】
从文件code.in中读入数据。
仅一行两个整数n,k意义见题目描述。
【输出格式】
输出到文件code.out中。
仅一行一个n位二进制串表示答案。
【样例1输入】
23
【样例1输出】
10
【样例1解释】
2位格雷码为:00, 01, 11. 10,编号从0〜3,因此3号串是10。
【样例2输入】
35
【样例2输出】
111
【样例2解释】
3 位格雷码为:000, 001. 011, 010, 110, 111. 101, 100,编号从 0 〜7,因此 5 号串是111。
【数据范围】
对于50%的数据:n≤ 10
对于80%的数据:k≤5x10^6
对于95%的数据:k≤ 2^63 - 1
对于 100% 的数据:1 ≤ n ≤ 64,0 ≤ k≤2^n
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
unsigned long long k;
cin>>n>>k;
unsigned long long s;
for(int i=n;i>=1;i--)
{
s=pow(2,i);
if(k>=(s/2))
{
k=s-k-1;
printf("1");
}
else
printf("0");
}
return 0;
}
#include <iostream>
using namespace std;
string s;
long long magic(int l, int r) {
long long ans = 0;
for (int i = l; i <= r; ++i) {
ans = ans * 4 + s[i] - 'a' + 1;
}
return ans;
}
int main() {
cin >> s;
int len = s.length();
int ans = 0;
for (int l1 = 0; l1 < len; ++l1) {
for (int r1 = l1; r1 < len; ++r1) {
bool bo = true;
for (int l2 = 0; l2 < len; ++l2) {
for (int r2 = l2; r2 < len; ++r2) {
if (magic(l1, r1) == magic(l2, r2) && (l1 !=
l2 || r1 != r2)) {
bo = false;
}
}
}
if (bo) {
ans += 1;
}
}
}
cout << ans << endl;
return 0;
}
输入:abacaba
输出:_________
输出:16
对于一个1到n的排列p(即1到n中每一个数在p中出现了恰好一次),令qi为第i个位置之后第一个比pi值更大的位置,如果不存在这样的位置,则qi = n +1。举例来说,如果n = 5且p为1 5 4 2 3,则q为2 6 6 5 6。
下列程序读入了排列p,使用双向链表求解了答案。试补全程序。(第二空2 分,其余 3 分)
数据范围 1 ≤ n ≤ 105。
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int L[N], R[N], a[N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
(1) ;
}
for (int i = 1; i <= n; ++i) {
R[i] = (2) ;
L[i] = i - 1;
}
for (int i = 1; i <= n; ++i) {
L[ (3) ] = L[a[i]];
R[L[a[i]]] = R[ (4) ];
}
for (int i = 1; i <= n; ++i) {
cout << (5) << " ";
}
cout << endl;
return 0;
}
(1)a[x] = i
(2)i+1
(3)R[a[i]]
(4)a[i]
(5)R[i]
国王游戏
【问题描述】
恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 n 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。
【输入】
输入文件为 game.in。
第一行包含一个整数 n,表示大臣的人数。
第二行包含两个整数 a 和 b,之间用一个空格隔开,分别表示国王左手和右手上的整数。
接下来 n 行,每行包含两个整数 a 和 b,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。
【输出】
输出文件名为 game.out。
输出只有一行,包含一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
【输入输出样例】

【输入输出样例说明】
按 1、2、3 号大臣这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;
按 1、3、2 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;
按 2、1、3 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;
按 2、3、1 这样排列队伍,获得奖赏最多的大臣所获得金币数为 9;
按 3、1、2 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;
按 3、2、1 这样排列队伍,获得奖赏最多的大臣所获得金币数为 9。
因此,奖赏最多的大臣最少获得 2 个金币,答案输出 2。
【数据范围】
对于 20%的数据,有 1≤ n≤ 10,0 < a、b < 8;
对于 40%的数据,有 1≤ n≤20,0 < a、b < 8;
对于 60%的数据,有 1≤ n≤100;
对于 60%的数据,保证答案不超过
对于 100%的数据,有 1 ≤ n ≤1,000,0 < a、b < 10000。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int len = 1;//表示高精度数据的长度
int sum[100001] = {0,1};//高精度数据计算结果
struct minister{
ll left;
ll right;
} m[1000001];
bool cmp(minister a,minister b){
return a.left * a.right < b.left * b.right;
}
void multiplicative(ll x){//高精度乘法
for(int i = 1;i <= len; i++){
sum[i] *= x; //各位数乘x,如1111×20 = (1000+100+10+1)×20
}
for(int i = 1;i <= len; i++){
sum[i + 1] += sum[i] / 10;//获得进位,因为相乘结果可能为 10 3 13 4,需转化为 1 0 4 3 4
sum[i] %= 10;
}
len++;//因为是sum[i+1],所以肯定会计算到sum[len+1],所以需要len++
while(sum[len] / 10){//观察最高位是否有进位,因为可能有经过前面的操作后可能有 100 3的情况
sum[len + 1] = sum[len] / 10;
sum[len] %= 10;
len++;
}
//经过前面的一波操作后,最后可能会导致sum[len]的位置上有0,若为0则需要消除
if(sum[len] == 0)
len--;
}
void division(){//高精度除法,这里只需要进行一次操作,所以不需要参数
//思路依旧很简单,如2345/5=(2000+300+40+5)/5,小学生除法
//->2 3 4 5 ->0 23(3 + 2%5*10) 4 5 -> 0 4 34(4 + 23%5*10) 5 -> 0 4 6 45(5 + 34%5*10)
for(int i = len; i >= 1; i--){
sum[i - 1] += (sum[i] % m[n].right * 10);
sum[i] /= m[n].right;
}
//这波操作必然导致一堆前导0,需消除
while(!sum[len]){
len--;
}
//防止除完了
if(len == 0) cout << "1" << endl;
}
int main(){
cin >> n;
cin >> m[0].left >> m[0].right;
for(int i = 1;i <= n; i++)
cin >> m[i].left >> m[i].right;
sort(m + 1, m + 1 + n, cmp);
for(int i = 0;i < n; i++){
multiplicative(m[i].left);
}
division();
for(int i = len; i >= 1; i--)
cout << sum[i];
}