信息学奥赛-入门级 题库
有 5 个男生和 3 个女生站成一排,规定 3 个女生必须相邻,问有多少种不同的排列方式?
第一步,将三个女生站在一起作为一个整体(捆绑法),该整体的情况数为三个女生的全排列,为P(3,3)
而后第二步5个男生与女生整体一共6个元素,进行全排列,方案数为P(6,6)
总排列方案数为P(3,3)∗P(6,6)=3∗2∗1∗6∗5∗4∗3∗2∗1=4320,选A。
一个班级有10个男生和12个女生。如果要选出一个3人的小组,并且小组中必须至少包含1个女生,那么有多少种可能的组合?( )
1540
2200
至少包括一个女生,最多包含3个女生,所以可以分为三种情况:
①包含一个女生,有C(12,1)·C(10,2) = 540种方法;
②包含两个女生,有C(12,2)·C(10,1) = 660种方法;
③包含三个女生,有C(12,3) = 220种方法;
因此,共有540 + 660 + 220 = 1420 种方案。
五个小朋友并排站成一列,其中有两个小朋友是双胞胎,如果要求这两个双胞胎必须相邻,则有()种不同排列方法?
考察排列组合 。根据捆绑法,将两个双胞胎看成一个人,所以有A(4, 4)种可能,然后双胞胎自己也有顺序,为A(2,2), 根据分步原理:A(4,4)*A(2,2) = 48。
干支纪年法是中国传统的纪年方法,由10个天干和12个地支组合成60个 天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支°
天干=(公历年份)除以10所得余数
地支=(公历年份)除以12所得余数

例如,今年是2020年,2020除以10余数为0,査表为“庚”;2020除以12, 余数为4,査表为“子”所以今年是庚子年。
请问1949年的天干地支是()
考查取余运算,1949%10=9,所以天干对应的就是己,1949%12=5,所以地支对应的就是丑
五个小朋友并排站成一列,其中有两个小朋友是双胞胎,如果要求这两个双胞胎必须相邻,则有()种不同排列方法?
考察排列组合 。根据捆绑法,将两个双胞胎看成一个人,所以有A(4, 4)种可能,然后双胞胎自己也有顺序,为A(2,2), 根据分步原理:A(4,4)*A(2,2) = 48。
干支纪年法是中国传统的纪年方法,由10个天干和12个地支组合成60个 天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支°
天干=(公历年份)除以10所得余数
地支=(公历年份)除以12所得余数

例如,今年是2020年,2020除以10余数为0,査表为“庚”;2020除以12, 余数为4,査表为“子”所以今年是庚子年。
请问1949年的天干地支是()
考查取余运算,1949%10=9,所以天干对应的就是己,1949%12=5,所以地支对应的就是丑
GB2312-80 规定了一级汉字3755个,二级汉字3008个,其中二级汉字字库中的汉字是以( )为序排列的.
某数列有1000个各不相同的单元,由低至高按序排列;现要对该数列进行二分法检索(binary search),在最坏的情況下,需检视( )个单元.
大家知道,不同类型的存储器组成了多层次结构的存储器体系,按存取速度从快到慢的排列是( ).
外存 / 主存 / 辅存
快存 / 主存 / 辅存
T1拼数


#include <bits/stdc++.h>
using namespace std;
//循环字符串,将所有数字插入vector
//将vector排序
//倒序输出
string s;
vector<char> v;
int main() {
cin >> s;
for (char i : s) {
if (i >= '0' && i <= '9') {
v.push_back(i);
}
}
sort(v.begin(), v.end(), greater<int>());
for (char i : v) {
cout << i;
}
return 0;
}T2座位



#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, a, a1, k = 1;
cin >> n >> m >> a1;
for (int i = 1; i < n*m; i++) {
cin >> a;
if (a > a1) k++;
}
int lie = ceil(1.0 * k / n);
int g = k % n;
if (g == 0) g = n; //特殊情况
int hang;
if (lie % 2 == 0) { //偶数列:从下往上排
hang = n - g + 1;
} else { //奇数列:从上往下排
hang = g;
}
cout << lie << " " << hang;
return 0;
}T3异或和



#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
int n, k, a;
int dp[MAXN];
//存储每种异或和最后一次出现的下标
map<int, int> m;
int main() {
cin >> n >> k;
int qzh = 0;
m[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> a;
qzh ^= a;
dp[i] = dp[i-1];
if (m.find(k ^ qzh) != m.end()) dp[i] = max(dp[i], dp[m[k ^ qzh]] + 1);
m[qzh] = i;
}
cout << dp[n];
return 0;
}T4多边形



#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int MAXN = 5005;
int a[MAXN];
int cnt[MAXN][MAXN];
int dp[MAXN];
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
cnt[1][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 5001; j++) {
cnt[i+1][j] = (cnt[i+1][j] + cnt[i][j]) % mod;
cnt[i+1][min(j+a[i],5001)] = (cnt[i+1][min(j+a[i],5001)] + cnt[i][j]) % mod;
}
}
//求dp
for (int i = 1; i <= n; i++) {
dp[i] = dp[i-1];
for (int j = a[i]+1; j <= 5001; j++) dp[i] = (dp[i] + cnt[i][j]) % mod;
}
cout << dp[n];
return 0;
}车站分级
【问题描述】
一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别,最低为 1 级。现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 x,则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。(注意:起始站和终点站自然也算作事先已知需要停靠的站点)
例如,下表是 5 趟车次的运行情况。其中,前 4 趟车次均满足要求,而第 5 趟车次由于停靠了 3 号火车站(2 级)却未停靠途经的 6 号火车站(亦为 2 级)而不满足要求。

现有 m 趟车次的运行情况(全部满足要求),试推算这 n 个火车站至少分为几个不同的级别。
【输入】
输入文件为 level.in。
第一行包含 2 个正整数 n, m,用一个空格隔开。
第 i + 1 行(1 ≤ i ≤ m)中,首先是一个正整数 si(2 ≤ si ≤ n),表示第 i 趟车次有 si 个停靠站;接下来有 si个正整数,表示所有停靠站的编号,从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。
【输出】
输出文件为 level.out。
输出只有一行,包含一个正整数,即 n 个火车站最少划分的级别数。
【输入输出样例】

【数据范围】
对于 20%的数据,1 ≤ n, m ≤ 10;
对于 50%的数据,1 ≤ n, m ≤ 100;
对于 100%的数据,1 ≤ n, m ≤ 1000。
#include<bits/stdc++.h>
#define in read()
#define N 10009
#define M 9000009
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
char ch=nc();int sum=0;
while(!(ch>='0'&&ch<='9'))ch=nc();
while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
return sum;
}
int n,m,du[N],chu[N];
int nxt[M],to[M],head[N],cnt=0;
void add(int x,int y){nxt[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}
int s[N],g[1009][1009],dis[N];
bool vis[1009];
int main(){
n=in;m=in;
int i,j,k;
for(i=1;i<=m;++i){
k=in;
memset(vis,0,sizeof(vis));
for(j=1;j<=k;++j){
int hh=in;
s[j]=hh;vis[hh]=1;
}
for(j=s[1];j<=s[k];++j){
if(!vis[j]){
for(int p=1;p<=k;++p){
if(!g[s[p]][j]){
g[s[p]][j]=1;
add(s[p],j);
du[j]++;
}
}
}
}
}
queue<int> q;
for(i=1;i<=n;++i)
if(!du[i]) dis[i]=1,q.push(i);
int ans=-1;
while(!q.empty()){
int u=q.front();q.pop();
for(int e=head[u];e;e=nxt[e]){
int v=to[e];
dis[v]=dis[u]+1;
ans=max(ans,dis[v]);
du[v]--;
if(!du[v]) q.push(v);
}
}
cout<<ans;
return 0;
}
三国游戏
【问题描述】
小涵很喜欢电脑游戏,这些天他正在玩一个叫做《三国》的游戏。
在游戏中, 小涵和计算机各执一方, 组建各自的军队进行对战。 游戏中共有 N位武将 (N为偶数且不小于 4) ,任意两个武将之间有一个“默契值” ,表示若此两位武将作为一对组合作战时,该组合的威力有多大。游戏开始前,所有武将都是自由的(称为自由武将,一旦某个自由武将被选中作为某方军队的一员,那么他就不再是自由武将了) ,换句话说,所谓的自由武将不属于任何一方。游戏开始,小涵和计算机要从自由武将中挑选武将组成自己的军队,规则如下:小涵先从自由武将中选出一个加入自己的军队,然后计算机也从自由武将中选出一个加入计算机方的军队。接下来一直按照“小涵→计算机→小涵→……”的顺序选择武将,直到所有的武将被双方均分完。然后,程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武,拥有更高默契值的一对武将组合获胜,表示两军交战,拥有获胜武将组合的一方获胜。
已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合,它采取的具体策略如下:任何时刻,轮到计算机挑选时,它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对,找出所有配对中默契值最高的那对武将组合,并将该组合中的自由武将选入自己的军队。
下面举例说明计算机的选将策略,例如,游戏中一共有 6个武将,他们相互之间的默契值如下表所示

双方选将过程如下所示:

小涵想知道,如果计算机在一局游戏中始终坚持上面这个策略,那么自己有没有可能必胜?如果有,在所有可能的胜利结局中,自己那对用于比武的武将组合的默契值最大是多少?
假设整个游戏过程中,对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。为了简化问题,保证对于不同的武将组合,其默契值均不相同。
【输入】
输入文件名为 sanguo.in,共 N行。
第一行为一个偶数 N,表示武将的个数。
第 2 行到第 N 行里,第(i+1)行有(N−i)个非负整数,每两个数之间用一个空格隔开,表示 i 号武将和 i+1,i+2,……,N号武将之间的默契值(0 ≤默契值≤ 1,000,000,000)。
【输出】
输出文件 sanguo.out 共 1或 2 行。
若对于给定的游戏输入,存在可以让小涵获胜的选将顺序,则输出 1,并另起一行输出所有获胜的情况中,小涵最终选出的武将组合的最大默契值。
如果不存在可以让小涵获胜的选将顺序,则输出 0。
【输入输出样例1】

【输入输出样例说明1】
首先小涵拿走 5 号武将;计算机发现 5 号武将和剩下武将中的 4 号默契值最高,于是拿走 4 号;小涵接着拿走 3 号;计算机发现 3、5 号武将之一和剩下的武将配对的所有组合中,5 号和1 号默契值最高,于是拿走 1号;小涵接着拿走 2 号;计算机最后拿走 6 号。在小涵手里的 2,3,5 号武将中,3 号和 5 号配合最好,默契值为 32,而计算机能推出的最好组合为 1 号和 6 号,默契值为 27。结果为小涵胜,并且这个组合是小涵用尽所有方法能取到的最好组合。
【输入输出样例2】

【数据范围】
对于 40%的数据有 N ≤ 10。
对于 70%的数据有 N ≤ 18。
对于 100%的数据有 N ≤ 500。
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 5005; //定义大一点
long long a[N][N];
long long n, i, j, mx, cx, mx1;
int main()
{
freopen ("sanguo.in" , "r" , stdin);
freopen ("sanguo.out" , "w" , stdout);
scanf ("%lld", &n);
for (i = 1;i <= n - 1;i ++) {
for (j = i + 1;j <= n;j ++) {
scanf ("%lld", &a[i][j]); //输入
a[j][i] = a[i][j]; //构建一个邻接矩阵
}
}
for (i = 1;i <= n;i ++) {
cx = mx = 0; //赋初值
for (j = 1;j <= n;j ++) {
if (mx < a[i][j]) { //如果当前默契值比mx大
cx = mx; //将mx赋给cx,cx为次大值,这样下来,就可以找到最大和次大值了
mx = a[i][j]; //更新mx
}
else cx = max (a[i][j] , cx); //否则取最大值
mx1 = max (mx1 , cx); //有一个变量存将哟输出的值
}
}
printf ("1\n%lld", mx1); //输出(一定会赢)
fclose (stdin);
fclose (stdout);
return 0;
}
花生采摘
【问题描述】
鲁宾逊先生有一只宠物猴,名叫多多。这天,他们两个正沿着乡间小路散步,突然发现路边的告示牌上贴着一张小小的纸条:“欢迎免费品尝我种的花生!——熊字”。
鲁宾逊先生和多多都很开心,因为花生正是他们的最爱。在告示牌背后,路边真的有一块花生田,花生植株整齐地排列成矩形网格(如图1)。有经验的多多一眼就能看出,每棵花生植株下的花生有多少。为了训练多多的算术,鲁宾逊先生说:“你先找出花生最多的植株,去采摘它的花生;然后再找出剩下的植株里花生最多的,去采摘它的花生;依此类推,不过你一定要在我限定的时间内回到路边。”
我们假定多多在每个单位时间内,可以做下列四件事情中的一件:
1) 从路边跳到最靠近路边(即第一行)的某棵花生植株;
2) 从一棵植株跳到前后左右与之相邻的另一棵植株;
3) 采摘一棵植株下的花生;
4) 从最靠近路边(即第一行)的某棵花生植株跳回路边。
现在给定一块花生田的大小和花生的分布,请问在限定时间内,多多最多可以采到多少个花生?注意可能只有部分植株下面长有花生,假设这些植株下的花生个数各不相同。
例如在图2所示的花生田里,只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生,个数分别为13, 7, 15, 9。沿着图示的路线,多多在21个单位时间内,最多可以采到37个花生。
【输入文件】
输入文件peanuts.in的第一行包括三个整数,M, N和K,用空格隔开;表示花生田的大小为M * N(1 <= M, N <= 20),多多采花生的限定时间为K(0 <= K <= 1000)个单位时间。接下来的M行,每行包括N个非负整数,也用空格隔开;第i + 1行的第j个整数Pij(0 <= Pij <= 500)表示花生田里植株(i, j)下花生的数目,0表示该植株下没有花生。
【输出文件】
输出文件peanuts.out包括一行,这一行只包含一个整数,即在限定时间内,多多最多可以采到花生的个数。
【样例输入1】
6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
【样例输出1】
37
【样例输入2】
6 7 20
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
【样例输出2】
28
如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢,请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。

求先序排列
问题描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度<=8)。
样例
输入:BADC BDCA
输出:ABCD
设有一个N*M(l≤ N≤50, l≤ M≤ 50)的街道(如下图):

规定行人从A(1,1)出发,在街道上只能向东或北方向行走。
如下为N=3,M=3的街道图,从A出发到达B共有6条可供行走的路径:

若在N*M的街道中,设置一个矩形障碍区域(包括围住该区域的街道)不让行人通行,如图中用“*”表示的部分。
此矩形障碍区域用2对顶点坐标给出,前图中的2对顶点坐标为:(2,2),(8,4),此时从 A出发到达B的路径仅有两条。
程序要求:
任务一:给出N,M后,求出所有从A出发到达B的路径的条数。
任务二:给出N,M,同时再给出此街道中的矩形障碍区域的2对顶点坐标(X1,y1), (X2,Y2),然后求出此种情况下所有从A出发到达B的路径的条数。