首页 › 题库 › 信息学奥赛 › 5 数论与组合数学

信息学奥赛-提高级 题库

共 26 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 5 数论与组合数学 清除
1 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 5.3 排列组合

有5个红色球和5个蓝色球,除颜色外完全相同,将10个球排成一排,要求任意两个蓝色球都不能相邻,有多少种不同的排列方法?


A

25

B

30

C

6

D

120

答案与解析
正确答案:C

先将所有红色球排成一排,会形成6个空隙,每个空隙最多放一个蓝色球,从6个空隙中选5个放蓝球,方案数为C(6,5)=6。

题目详情
2 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 5.2 同余与逆元

考虑一个自然数n以及一个模数m,你需要计算n的逆元(即n在模m意义下的乘法逆元)。下列哪种算法最为合适?( )

A
使用暴力方法依次尝试
B
使用扩展欧几里得解法
C
使用快速幂解法
D
使用线性筛法
答案与解析
正确答案:B

如果一个线性同余方程ax≡1(modb),则x称为a mod b的逆元,记作a-1。扩展欧几里德算法找到两个整数x和y满足ax+by=gcd(a, b)。当a和b互质时,即gcd(a,b)=1,这个方程变为ax+by=1。在模b意义下,ax与1在模b时同余,因此x就是a的模b的逆元。快速幂法使用了费马小定理,要求b是一个素数;而扩展欧几里得法只要求gcd(a,b)=1

题目详情
3 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 5.3 排列组合

函数int logic(int x,int y)的功能是()?

A
按位与
B
按位或
C
按位异或
D
以上都不是
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
4 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 5.2 同余与逆元

计算机系统用小端(Little Endian)和大端(Big Endian)来描述多字节数据的存储地址顺序模式,其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++代码段表示的程序,将分别输出什么结果?( )

 unsigned x = 0xDEADBEEF; 

 unsigned char *p = (unsigned char *)&x; 

 printf("%X", *p);

A
EF、EF
B
EF、DE
C
DE、EF
D
DE、DE
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
5 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 5.2 同余与逆元

 有 7 个一模一样的苹果,放到 3 个一样的盘子中,一共有( )种放法。

A
7
B
8
C
21
D
3
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
6 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 5.2 同余与逆元

T(n)表示某个算法输入规模为 n 时的运算次数。如果 T(1)为常数,且有递归式T(n)=2*T(n/2)+2n,那么 T(n)=( )。

A
Θ(n)
B
Θ(n log n)
C
Θ(n2)
D
Θ(n2log n)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
7 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 5.2 同余与逆元

无论是TCP/IP模型还是OSI模型,都可以视为网络的分层模型,每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”,以下最恰当的是( )。

A
中国公司的经理与伊拉克公司的经理交互商业文件
B
军队发布命令
C
国际会议中,每个人都与他国地位对等的人直接进行会谈
D
体育比赛中,每一级比赛的优胜者晋级上一级比赛
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
8 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 5.2 同余与逆元

计算机系统用小端(Little Endian)和大端(Big Endian)来描述多字节数据的存储地址顺序模式,其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++代码段表示的程序,将分别输出什么结果?( )

 unsigned x = 0xDEADBEEF; 

 unsigned char *p = (unsigned char *)&x; 

 printf("%X", *p);

A
EF、EF
B
EF、DE
C
DE、EF
D
DE、DE
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
9 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.2 同余与逆元

结构体(struct)

【题目背景】

在C++等高级语言中,除了int和float等基本类型外,通常还可以自定义结构体类型。在本题当中,你需要模拟一种类似C++的高级语言的结构体定义方式,并计算出相应的内存占用等信息。

【题目描述】

在这种语言中,基本类型共有4种:byte,short,int,long,分别占据1,2,4,8字节的空间。

定义一个结构体类型时,需要给出类型名和成员,其中每个成员需要按顺序给出类.型和名称。类型可以为基本类型,也可以为先.定义过的结构体类型。注意,定义结构体类型时不会定义具体元素,即不占用内存。

定义一个元素时,需要给出元素的类型和名称。元素将按照以下规则占据内存:

• 元素内的所有成员将按照定义时给出的顺序在内存中排布,对于类型为结构体的成员同理。

• 为了保证内存访问的效率,元素的地址占用需要满足对齐规则,即任何类型的大小和该类型元素在内存中的起始地址均应对齐到该类型对齐要求的整数倍。具体而言:

–对于基本类型:对齐要求等于其占据空间大小,如int类型需要对齐到4字节,其余同理。

–对于结构体类型:对齐要求等于其成员的对齐要求的最大值,如一个含有int和short的结构体类型需要对齐到4字节。

以下是一个例子(以C++语言的格式书写):

struct d {
    short a;
    int b;
    short c;
};
d e;

该代码定义了结构体类型d与元素e。元素e包含三个成员e.a,e.b,e.c,分别占据第0∼1,4∼7,8∼9字节的地址。由于类型d需要对齐到4字节,因此e占据了第0∼11字节的地址,大小为12字节。

你需要处理n次操作,每次操作为以下四种之一:

1.定义一个结构体类型。具体而言,给定正整数k与字符串s,t1,n1,...,tk,nk,其中k表示该类型的成员数量,s表示该类型的类型名,t1,t2,...,tk按顺序分别表示每个成员的类型,n1,n2,...,nk按顺序分别表示每个成员的名称。你需要输出该结构体类型的大小和对齐要求,用一个空格分隔。

2.定义一个元素,具体而言,给定字符串t,n分别表示该元素的类型与名称。所有被定义的元素将按顺序,从内存地址为0开始依次排开,并需要满足地址对齐规则。你需要输出新定义的元素的起始地址。

3.访问某个元素。具体而言,给定字符串s,表示所访问的元素。与C++等语言相同,采用.来访问结构体类型的成员。如a.b.c,表示a是一个已定义的元素,它是一个结构体类型,有一个名称为b的成员,它也是一个结构体类型,有一个名称为c的成员。你需要输出如上被访问的最内层元素的起始地址。

4.访问某个内存地址。具体而言,给定非负整数addr,表示所访问的地址,你需要判断是否存在一个基本类型的元素占据了该地址。若是,则按操作3中的访问元素格式输出该元素;否则输出ERR。

【输入格式】

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

第1行:一个正整数n,表示操作的数量。

接下来若干行,依次描述每个操作,每行第一个正整数op表示操作类型:

•若op=1,首先输入一个字符串s与一个正整数k,表示类型名与成员数量,接下来k行每行输入两个字符串ti,ni,依次表示每个成员的类型与名称。

•若op=2,输入两个字符串t,n,表示该元素的类型与名称。

•若op=3,输入一个字符串s,表示所访问的元素。

•若op=4,输入一个非负整数addr,表示所访问的地址。

【输出格式】

输出到文件struct.out中。

输出n行,依次表示每个操作的输出结果,输出要求如题目描述中所述。


【样例1输入】

5
1 a 2
short aa
int ab
1 b 2
a ba
long bb
2 b x
3 x.ba.ab
4 10

【样例1输出】

8 4
16 8
0
4
x.bb

【样例1解释】

结构体类型a中,int类型的成员aa占据第0∼3字节地址,short类型的成员ab占据第4∼5字节地址。又由于其对齐要求为4字节,可得其大小为8字节。由此可同理计算出结构体类型b的大小为16字节,对齐要求为8字节。

【样例2】

见选手目录下的struct/struct2.in与struct/struct2.ans。

【样例2解释】

第二个操作4中,访问的内存地址恰好在为了地址对齐而留下的“洞”里,因此没有基本类型元素占据它。

【样例3】

见选手目录下的struct/struct3.in与struct/struct3.ans。

【数据范围】

对于全部数据,满足1≤n≤100,1≤k≤100,0≤addr≤1018。

所有定义的结构体类型名、成员名称和定义的元素名称均由不超过10个字符的小

写字母组成,且都不是byte,short,int,long(即不与基本类型重名)。

所有定义的结构体类型名和元素名称互不相同,同一结构体内成员名称互不相同。

但不同的结构体可能有相同的成员名称,某结构体内的成员名称也可能与定义的结构体或元素名称相同。

保证所有操作均符合题目所述的规范和要求,即结构体的定义不会包含不存在的类型、不会访问不存在的元素或成员等。

保证任意结构体大小及定义的元素占据的最高内存地址均不超过1018。

特殊性质A:没有操作1;

特殊性质B:只有一个操作1;

特殊性质C:所有操作1中给出的成员类型均为基本类型;

特殊性质D:基本类型只有long。

【提示】

对于结构体类型的对齐要求和大小,形式化的定义方式如下:

•设该结构体内有k个成员,其大小分别为s1,...,sk,对齐要求分别为a1,...,ak;

•则该结构体的对齐要求为a=max{a1,...,ak};

•再设这些成员排布时的地址偏移量分别为o1,...,ok,则:

–o1=0;

–对于i=2,...,k,oi为满足oi−1+si−1≤oi且ai整除oi的最小值;

–则该结构体的大小s为满足ok+sk≤s且a整除s的最小值;

对于定义元素时的内存排布,形式化的定义方式如下:

•设第i个被定义的元素大小为si,对齐要求为ai,起始地址为bi;

•则b1=0,对于2≤i,bi为满足bi−1+si−1≤bi且ai整除bi的最小值。

答案与解析
参考答案

题解1:


题解2:

题目详情
10 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.3 排列组合

对于一个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]

题目详情
11 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.2 同余与逆元

在计算机显示器所使用的 RGB 颜色模型中,( )属于三原色之一。

答案与解析
正确答案:B,D
这道题暂未补解析。
题目详情
12 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.3 排列组合

(排列数)输入两个正整数 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

题目详情
13 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.3 排列组合

组合数问题

【问题描述】

组合数表示的是从 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;

}

题目详情
14 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.3 排列组合

贪吃蛇(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;

}

题目详情
15 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.3 排列组合

格雷码

【题目描述】

通常,人们习惯将所有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;

}

题目详情
16 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.1 素数与筛法

Emiya家今天的饭

【题目描述】

Emiya 是个擅长做菜的高中生,他共掌握 n 种烹饪方法,且会使用 m 种主要食材做菜。为了方便叙述,我们对烹饪方法从 1~n 编号,对主要食材从 1 ~m 编号。

Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地,Emiya 会做 ai,j 道不同的使用烹饪方法 i 和主要食材 j 的菜(1 ≤i≤n,1≤j≤m),这也意味着 Emiya 总共会做

道不同的菜。

Emiya 今天要准备一桌饭招待 Yazid 和 Rin 这对好朋友,然而三个人对菜的搭配有不同的要求,更具体地,对于一种包含 k 道菜的搭配方案而言:

(1)Emiya 不会让大家饿肚子,所以将做至少一道菜,即 k≥1

(2)Rin 希望品尝不同烹饪方法做出的菜,因此她要求每道菜的烹饪方法互不相同

(3)Yazid 不希望品尝太多同一食材做出的菜,因此他要求每种主要食材至多在一半的菜(即道菜)中被使用

这里的⌊x⌋ 为下取整函数,表示不超过 x 的最大整数。

这些要求难不倒 Emiya,但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同,当且仅当存在至少一道菜在一种方案中出现,而不在另一种方案中出现。

Emiya 找到了你,请你帮他计算,你只需要告诉他符合所有要求的搭配方案数对质数998,244,353 取模的结果。

【输入格式】

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

第 1 行两个用单个空格隔开的整数 n,m。

第 2 行至第 n+1 行,每行 m 个用单个空格隔开的整数,其中第 i + 1行的 m 个数依次为 ai,1,ai,2,⋯,ai,m。

【输出格式】

输出到文件meal.out中。

仅一行一个整数,表示所求方案数对 998,244,353 取模的结果。

【样例 1 输入】

2 3 

1 0 1

0 1 1

【样例 1 输出】

3

【样例1解释】

由于在这个样例中,对于每组i,j,Emiya都最多只会做一道菜,因此我们直接通 过给出烹饪方法、主要食材的编号来描述一道菜。

符合要求的方案包括:

•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材2的菜

•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材3的菜

•做一道用烹饪方法1、主要食材3的菜和一道用烹饪方法2、主要食材2的菜

 因此输出结果为3 mod 998,244,353 = 3。

需要注意的是,所有只包含一道菜的方案都是不符合要求的,因为唯一的主要食材 在超过一半的菜中出现,这不满足Yazid的要求。

【样例2输入】

3 3

1 2 3

4 5 0

6 0 0

【样例2输出】

190

【样例2解释】

Emiya必须至少做2道菜。

做2道菜的符合要求的方案数为100。

做3道菜的符合要求的方案数为90。

因此符合要求的方案数为100 + 90 = 190。

【样例3输入】

5 5

1 0 0 1 1

0 1 0 1 0

1 1 1 1 0

1 0 1 0 1

0 1 1 0 1

【样例3输出】

742

【数据范围】

对于所有测试点,保证 1 ≤n≤ 100, 1 ≤ m ≤ 2000, 0≤ai,j< 998,244,353。

答案与解析
参考答案

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#define mod 998244353

 

using namespace std;

typedef long long ll;

const int MAXN = 105, MAXM = 2005;

int n,m,a[MAXN][MAXM],sum[MAXN][MAXM];

ll f[MAXN][MAXN*2],g[MAXN][MAXN];

 

int main()

{

cin >> n >> m;

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

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

    {

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

        sum[i][0] = (sum[i][0]+a[i][j])%mod;

}

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

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

            sum[i][j] = (sum[i][0]-a[i][j]+mod)%mod;

    ll ans = 0;

    for(int col = 1; col<=m; col++)

    {

        memset(f,0,sizeof(f));

        f[0][n] = 1;

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

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

                f[i][j] = (f[i-1][j]+f[i-1][j-1]*a[i][col]%mod+f[i-1][j+1]*sum[i][col]%mod)%mod;

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

            ans = (ans+f[n][n+j])%mod;

}

g[0][0] = 1;

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

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

    g[i][j] = (g[i-1][j]+(j>0?g[i-1][j-1]*sum[i][0]%mod:0))%mod;

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

    ans = (ans-g[n][j]+mod)%mod;  

cout << ans*(mod-1)%mod << endl;

return 0;

}

题目详情
17 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.2 同余与逆元

划分

【题目描述】

2048年,第三十届CSP认证的考场上,作为选手的小明打开了第一题。这个题的 样例有n组数据,数据从1~n编号,i号数据的规模为ai。

小明对该题设计出了一个暴力程序,对于一组规模为u的数据,该程序的运行时 间为u^2。然而这个程序运行完一组规模为u的数据之后,它将在任何一组规模小于u 的数据上运行错误。样例中的ai,不一定递增,但小明又想在不修改程序的情况下正确 运行样例,于是小明决定使用一种非常原始的解决方案:将所有数据划分成若干个数据 段,段内数据编号连续,接着将同一段内的数据合并成新数据,其规模等于段内原数据 的规模之和.小明将让新数据的规模能够递增。

也就是说,小明需要找到一些分界点使得

注意P可以为0且此时k0 = 0,也就是小明可以将所有数据合并在一起运行。

小明希望他的程序在正确运行样例情况下,运行时间也能尽量小,也就是最小化

小明觉得这个问题非常有趣,并向你请教:给定n和ai,请你求出最优划分方案 下,小明的程序的最小运行时间。

【输入格式】

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

由于本题的数据范围较大,部分测试点的ai将在程序内生成。

第一行两个整数n.type. n的意义见题目描述,type表示输入方式。

1.若type = 0.则该测试点的ai直接给出。输入文件接下来:第二行n个以空格 分隔的整数ai,表示每组数据的规模。

2.若type = 1则该测试点的ai将特殊生成,生成方式见后文。输入文件接下来: 第二行六个以空格分隔的整数x,y,z,b1,b2,m。 接下来m行中,第i行包含三个以空格分隔的正整数pi,li,ri。

对于type = 1的23 ~ 25号测试点,ai的生成方式如下:

给定整数x,y,z,b1,b2,m,以及m个三元组(pi,li,ri)。

保证 n2。 若 n > 2,则

保证

对于所有则有ai=(bi   mod(rj-lj+1))+lj

上述数据生成方式仅是为了减少输入量大小,标准算法不依赖于该生成方式。

【输出格式】

输出到文件partition.out中。

输出一行一个整数,表示答案。

【样例1输入】

5 0

5 17 9 9

【样例1输出】

247

【样例1解释】

最优的划分方案为{5,1},{7},{9},{9}。由5 + 1<=7<=9<=9知该方案合法。

答案为(5 + 1)^2 + 7^2 + 9^2 + 9^2 = 247。

虽然划分方案{5},{1},{7},{9},{9}对应的运行时间比247小,但它不是一组合法 方案,因为5>1。

虽然划分方案{5},{1,7},{9},{9}合法,但该方案对应的运行时间为251,比247大。

【样例2输入】

10 0

5677462 13 19 9

【样例2输出】

1256

【样例2解释】

最优的划分方案为{5},{6},{7},{7},{4,6,2},{13},{19,9}。

【数据范围】

所有测试点满足:type € {0,1} , 2 < =n <= 4 x 10^7 , 1 < =ai,<= 10^9 , 1 <=m < =10^5 , 1 < =li <= ri <= 10^9 , 0 < x,y,z,b1,b2 < 2^30。

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std ;

const int N = 4e7 + 10 ;

const int M = 1e5 + 10 ;

const int mod = (1 << 30) ;

int n , type , x , y , z , m ;

int a[N] , b[N] , p[M] , l[M] , r[M] , q[N] , pre[N] ;

long long sum[N] ;

inline long long d(int x) { return sum[x] - sum[pre[x]] ; }

signed main() {

  ios :: sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ;

  cin >> n >> type ;

  if(type) {

cin >> x >> y >> z >> b[1] >> b[2] >> m ;

    for(register int i = 1 ; i <= m ; i ++) { cin >> p[i] >> l[i] >> r[i] ; }

    for(register int i = 3 ; i <= n ; i ++) { b[i] = (0ll + 1ll * b[i - 1] * x + 1ll * b[i - 2] * y + z) % mod ; }

    for(register int i = 1 ; i <= m ; i ++)

      for(register int j = p[i - 1] + 1 ; j <= p[i] ; j ++) { a[j] = (b[j] % (r[i] - l[i] + 1)) + l[i] ; sum[j] = sum[j - 1] + a[j] ; }

}

  else {

  for(register int i = 1 ; i <= n ; i ++) { cin >> a[i] ; sum[i] = sum[i - 1] + a[i] ; }

} int h , t ; q[h = t = 0] = 0 ;

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

    while(h < t && d(q[h + 1]) + sum[q[h + 1]] <= sum[i]) ++ h ; 

pre[i] = q[h] ;

    while(h < t && d(q[t]) + sum[q[t]] >= d(i) + sum[i]) -- t ;

    q[++ t] = i ;

  }  int now = n ; __int128 ans = 0 , tmp = 1 ;

while(now) { tmp = d(now) ; tmp *= d(now) ; ans += tmp ; now = pre[now] ; }

int st[50] , tp = 0 ;

while(ans) { st[++ tp] = ans % 10 ; ans /= 10 ; }

while(tp) { cout << st[tp --] ; }

  return 0 ;

}

题目详情
18 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.3 排列组合

#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

题目详情
19 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.3 排列组合

对于一个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]

题目详情
20 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.2 同余与逆元

小凯的疑惑

【问题描述】

小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中,最贵的价值是多少金币?注意:输入数据保证存在小凯无法准确支付的商品。

【输入格式】

输入文件名为 math.in。

输入数据仅一行,包含两个正整数 a 和 b,它们之间用一个空格隔开,表示小凯手中金币的面值。

【输出格式】

输出文件名为 math.out。

输出文件仅一行,一个正整数 N,表示不找零的情况下,小凯用手中的金币不能准确支付的最贵的物品的价值。

【输入输出样例 1】

【输入输出样例 1 说明】

小凯手中有面值为3和 7的金币无数个,在不找零的前提下无法准确支付价值为 1、2、4、5、8、11 的物品,其中最贵的物品价值为 11,比 11 贵的物品都能买到,比如:

12 = 3 * 4 + 7 * 0 

13 = 3 * 2 + 7 * 1 

14 = 3 * 0 + 7 * 2 

15 = 3 * 5 + 7 * 0

……

【数据规模与约定】

对于 30%的数据: 1 ≤ a,b ≤ 50。

对于 60%的数据: 1 ≤ a,b ≤ 10,000。

对于 100%的数据:1 ≤ a,b ≤ 1,000,000,000。

答案与解析
参考答案

//#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

using namespace std;

int main(){

long long a,b;

scanf("%lld %lld",&a,&b);

printf("%lld",a*b-a-b);

return 0;

}

题目详情