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

信息学奥赛-提高级 题库

共 26 道题 ,第 2 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 5 数论与组合数学 清除
21 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.2 同余与逆元

神奇的幻方

【问题描述】

幻方是一种很神奇的 N * N 矩阵:它由数字 1,2,3, … … , N * N 构成,且每行、每列及两条对角线上的数字之和都相同。

当 N 为奇数时,我们可以通过以下方法构建一个幻方:

首先将 1 写在第一行的中间。

之后,按如下方式从小到大依次填写每个数 K(K = 2,3, … , N * N) :

1. 若 (K − 1) 在第一行但不在最后一列,则将 K 填在最后一行, (K − 1) 所在列的右一列;

2. 若 (K − 1) 在最后一列但不在第一行,则将 K 填在第一列,(K − 1) 所在行的上一行;

3. 若 (K − 1) 在第一行最后一列,则将 K 填在 (K − 1) 的正下方;

4. 若 (K − 1) 既不在第一行,也不在最后一列,如果 (K − 1) 的右上方还未填数,

则将 K 填在(K − 1)的右上方,否则将 K 填在 (K − 1) 的正下方。现给定 N,请按上述方法构造 N * N 的幻方。

【输入格式】

输入文件名为 magic.in。

输入文件只有一行,包含一个整数 N,即幻方的大小。

【输出格式】

输出文件名为 magic.out。

输出文件包含 N 行,每行 N 个整数,即按上述方法构造出的 N * N 的幻方。相邻两个整数之间用单个空格隔开。

【输入输出样例 1】

【数据规模与约定】

对于 100% 的数据,1 ≤ N ≤ 39 且 N 为奇数。

答案与解析
参考答案

#include <iostream>

 

using namespace std;

 

const int N = 40;

 

int n;

int a[N][N];

 

int main() {

cin >> n;

int x = 1, y = n / 2 + 1;

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

a[x][y] = i;

if (x == 1 && y == n) x++;

else if (x == 1) x = n, y++;

else if (y == n) x--, y = 1;

else if (a[x - 1][y + 1]) x++;

else x--, y++;

}

 

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

for (int j = 1; j <= n; j++)printf("%d", a[i][j]);

puts("");

}

return 0;

}

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

斗地主

【问题描述】

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的 A 到 K 加上大小王的共 54 张牌来进行的扑克牌游戏。在斗地主中,牌的大小关系根据牌的数码表示如下:3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王,而花色并不对牌的大小产生影响。每一局游戏中,一副手牌由 n 张牌组成。游戏者每次可以根据规定的牌型进行出牌,首先打光自己的手牌一方取得游戏的胜利。

现在,牛牛只想知道,对于自己的若干组手牌,分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。

需要注意的是,本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。

具体规则如下:

【输入格式】

输入文件名为 landlords.in。

第一行包含用空格隔开的 2 个正整数 T, n ,表示手牌的组数以及每组手牌的张数。

接下来 T 组数据,每组数据 n 行,每行一个非负整数对 ai, bi,表示一张牌,其中 ai表示牌的数码,bi 表示牌的花色,中间用空格隔开。特别的,我们用 1 来表示数码 A,11 表示数码 J,12 表示数码 Q,13 表示数码 K;黑桃、红心、梅花、方片分别用 1-4 来表示;小王的表示方法为 0 1,大王的表示方法为 0 2。

【输出格式】

输出文件名为 landlords.out。

共 T 行,每行一个整数,表示打光第i组手牌的最少次数。

【输入输出样例 1】

【输入输出样例 1 说明】

共有 1 组手牌,包含 8 张牌:方片 7,方片 8,黑桃 9,方片 10,黑桃 J,黑桃 5,方片 A 以及黑桃 A。可以通过打单顺子(方片 7,方片 8,黑桃 9,方片 10,黑桃 J),单张牌(黑桃 5)以及对子牌(黑桃 A 以及方片 A)在 3 次内打光。

【输入输出样例 2】

【数据规模与约定】

对于不同的测试点,我们约定手牌组数 T 与张数 n 的规模如下:

数据保证:所有的手牌都是随机生成的。


答案与解析
参考答案

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

 

int T, n, ans, s[15];

 

void dfs(int shunzi) {

    if (shunzi > ans) return ;//最优化剪枝

    int i, j, s1 = 0, s2 = 0, s3 = 0, s4 = 0;

//非顺子

    for (i = 1; i <= 14; i++)//单牌需出的次数

        if (s[i] == 1) s1++;

    for (i = 1; i <= 14; i++)//对牌需出的次数

        if (s[i] == 2) s2++;

    for (i = 1; i <= 14; i++) {//三带

        if (s[i] == 3) {

            s3++;

            if (s1 >= 1) s1--;

            else if (s2 >= 1) s2--;

        }

    }

    for (i = 1; i <= 14; i++) {//四带

        if (s[i] == 4) {

            s4++;

            if (s1 >= 2) s1 -= 2;

            else {

                if (s2 >= 2) s2 -= 2;

                else if (s2 >= 1) s2--;

            }

        }

    }

//取当前最优解

    ans = min(ans, shunzi+s1+s2+s3+s4);

    for (i = 1; i <= 8; i++) {//单顺

        for (j = i; j <= 12; j++) {

            s[j]--;

            if (s[j]<0) break;

            if (j-i >= 4) dfs(shunzi+1);

        }

        if (j == 13) j--;

        while (j>=i) {

            s[j]++;

            j--;

        }

    }

    for (i = 1; i <= 10; i++) {//双顺

        for (j = i; j <= 12; j++) {

            s[j] -= 2;

            if (s[j]<0) break;

            if (j-i >= 2) dfs(shunzi+1);

        }

        if (j == 13) j--;

        while (j>=i) {

            s[j] += 2;

            j--;

        }

    }

    for (i = 1; i <= 11; i++) {//三顺

        for (j = i; j <= 12; j++) {

            s[j] -= 3;

            if (s[j]<0) break;

            if (j-i >= 1) dfs(shunzi+1);

        }

        if (j == 13) j--;

        while (j>=i) {

            s[j] += 3;

            j--;

        }

    }

    return ;

}

 

int main() {

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

    while (T--) {

        memset(s, 0, sizeof(s));

        int i, a, b;

        ans = 54;

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

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

            if (a == 0) s[14]++;

            if (a == 1) s[12]++;

            if (a == 2) s[13]++;

            if (a>=3) s[a-2]++;

        }

        dfs(0);

        printf("%d\n", ans);

    }

    return 0;

}

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

国王游戏

【问题描述】

恰逢 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];

}

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

同余方程

【问题描述】

求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。

【输入】

输入文件为 mod.in。

输入只有一行,包含两个正整数 a, b,用一个空格隔开。

【输出】

输出文件为 mod.out。

输出只有一行,包含一个正整数 x0,即最小正整数解。输入数据保证一定有解。

【输入输出样例】

【数据范围】

对于 40%的数据,2 ≤b≤ 1,000;

对于 60%的数据,2 ≤b≤ 50,000,000;

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

答案与解析
参考答案

#include <stdio.h>

long long a,b,x,y,k;

void exgcd(long long a,long long b)

{

    if(b==0)

    {

        x=1;

        y=0;

        return;

    }

    exgcd(b,a%b);

    long long int temp_x = x;

    x=y;

    y = temp_x - a/b *y;

    return;

}

int main()

{

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

    exgcd(a,b);

    x = (x%b + b)%b;

    printf("%lld\n",x);

return 0;

}

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

计算系数

【问题描述】

给定一个多项式请求出多项式展开后项的系数。

【输入】

输入文件名为 factor.in。

共一行,包含 5 个整数,分别为 a,b,k,n,m,每两个整数之间用一个空格隔开。

【输出】

输出文件名为 factor.out。

输出共 1 行,包含一个整数,表示所求的系数,这个系数可能很大,输出对 10007 取模后的结果。

【输入输出样例】

【数据范围】

对于 30%的数据,有 0≤k≤10;

对于 50%的数据,有 a = 1,b = 1;

对于 100%的数据,有 0≤k≤1,000,0≤n, m≤k,且 n + m = k,0≤a,b≤1,000,000。

答案与解析
参考答案

#include<iostream>

using namespace std;

long long mod=10007;

long long Mood(long long a,long long b){

long long sum=1;

a%=mod;

while(b){

if(b&1)

    sum=sum*a%mod;

a=a*a%mod;

b=b>>1;

}

return sum;

}

int a,b,k,n,m;

long long ans=0;

int main(){

cin>>a>>b>>k>>n>>m;

ans=Mood(a,n)*Mood(b,m)%mod;

for(int i=1,j=k;i<=n;i++,j--){//逆元 

ans=ans*j%mod;

ans=ans*Mood(i,mod-2)%mod;

}

cout<<ans<<endl;

return 0;

}

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

笨小猴

【问题描述】

笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!

这种方法的具体描述如下:假设 maxn 是单词中出现次数最多的字母的出现次数,minn是单词中出现次数最少的字母的出现次数,如果 maxn-minn 是一个质数,那么笨小猴就认为这是个 Lucky Word,这样的单词很可能就是正确的答案。

【输入】

输入文件 word.in 只有一行,是一个单词,其中只可能出现小写字母,并且长度小于 100。

【输出】

输出文件 word.out 共两行,第一行是一个字符串,假设输入的的单词是 Lucky Word,那么输出“Lucky Word”,否则输出“No Answer”;

第二行是一个整数,如果输入单词是 Lucky Word,输出 maxn-minn 的值,否则输出 0。 

【输入输出样例 1】

【输入输出样例 1 解释】

单词 error 中出现最多的字母 r 出现了 3 次,出现次数最少的字母出现了 1 次,3-1=2,2 是质数。

【输入输出样例 2】

【输入输出样例 2 解释】

单词 olympic 中出现最多的字母 i 出现了 2 次,出现次数最少的字母出现了 1 次,2-1=1,1不是质数。

答案与解析
参考答案

#include<bits/stdc++.h>  //万能头文件

using namespace std;

int primenum(int m);  //质数的判断

int main()

{

char ch[1000];

int array[100]={0};

int m,n,i,j,k;

int maxn=-500,minn=9999;

scanf("%s",ch);

for(int m=0;m<strlen(ch);m++){

array[ch[m]-'a']++;

}

for(int m=0;m<26;m++){

if(array[m]>maxn&&array[m]!=0) maxn=array[m];

if(array[m]<minn&&array[m]!=0) minn=array[m];

}

if(primenum(maxn-minn)){

printf("Lucky Word\n%d",maxn-minn);

}else{

printf("No Answer\n0");

}

}

int primenum(int m)

{

int i;

if(m==2||m==3) return 1;

if(m==1||m==0) return 0;

if(m%6!=1&&m%6!=5) return 0;  //优化质数的判断方法

for(i=5;i<=sqrt(m);i+=5){

if(m%i==0||m%(i+2)==0){

return 0;

}

题目详情