🎉为备战蓝桥杯，从今天开始更几期蓝桥杯的内容，总结相关试题，分析解题思路，铺好康庄大道，直到巅峰🎉

🎉🎉目前持续总结更新🎉🎉

💗 大家好🤗🤗🤗，我是左手の明天！💗

📆  最近更新：2022 年 4 月 7 日，左手の明天的第 219 篇原创博客

目录

🚩网友年龄

🚩生日蜡烛

🚩方格填数

🚩快速排序

🚩消除尾一

🚩寒假作业

🚩剪邮票

🚩四平方和

🚩最大比例

🚩随意组合

🚩拼棋盘

🚩棋盘多项式

🚩水仙花

🚩打靶

🚩路径之谜

🚩碱基

---

👍👍👍👍👍👍

🌟🌟 预祝各位能够得到好的名次 🌟🌟

---

🚩网友年龄

⭐️题目

某君新认识一网友。当问及年龄时，他的网友说：“我的年龄是个2位数，我比儿子大27岁，如果把我的年龄的两位数字交换位置，刚好就是我儿子的年龄”。请你计算：网友的年龄一共有多少种可能情况？

提示：30岁就是其中一种可能哦.

请填写表示可能情况的种数。

⭐️思路

第一点：网友年龄为两位数，则年龄取值范围为10-99
第二点：n表示网友年龄，m表示网友儿子年龄，n交换个位和十位得到儿子 年龄，既表达式m=（n % 10）* 10 + n / 10;
第三点：当满足n=m+27时，答案answer+1，最后输出answer的值即可

⭐️案例验证

n=30时，m1 = （30 % 10 ）x 10 = 0，m2 = 30 / 10=3，则m=0+3=3，n=m+27成立。

⭐️代码

#include <iostream>
using namespace std;
int main()
{
	int n,m=0,answer=0;		//n表示网友的年龄，m表示儿子的年龄
	for(n=10; n<100; n++)
	{
		m=(n % 10)*10+ n/10;
		if(n==m+27)
			answer ++;
	}
	cout << answer << endl;
	return 0;
}

⭐️结果

🎉答案：7

---

🚩生日蜡烛

⭐️题目

某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。现在算起来，他一共吹熄了236根蜡烛。请问，他从多少岁开始过生日party的？

请填写他开始过生日party的年龄数。

注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

⭐️思路

从他第一年开始举办生日party吹蜡烛数和以后每年吹的蜡烛数是一个等差数列，我们可以采用枚举（1-100比较合理）的方法，判断他是从那一年开始举办party的。

⭐️代码

#include<iostream>
using namespace std;
int main(){
    int i,j;
    int sum=0;
    for(i=1;i<=100;i++){    //年龄
        sum=0;
        for(j=i;j<=100;j++){    //蜡烛数
            sum=sum+j;
            if(sum==236){
                cout<<i<<endl;
              break;
            }
        }
    }
}

⭐️结果

🎉答案：26

---

🚩方格填数

⭐️题目

如下的10个格子

 

填入0~9的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）

一共有多少种可能的填数方案？

请填写表示方案数目的整数。

⭐️思路

这个题目有点表述不明，不知道0~9 可不可以重复使用。现在看来是不能重复使用的。

可以把表格当做3行4列的数组，去掉一头一尾。

步骤：填数字->判断是否满足要求：相邻位置数字不能相邻。

需要注意的地方：保证数字没有重复使用：借助数组，存储使用的数字，当所要填写的数字不在数组中时才可以填入。填入后存进数组。

⭐️代码

🍊方法一：用dfs求

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=4;
int mp[maxn][maxn];
int flag[10];
int ans=0;
int init() {
    memset(mp,-10, sizeof mp);
    memset(flag,0, sizeof flag);
}
int fx[4]= {0,-1,-1,-1},fy[4]= {-1,-1,0,1};
int check(int i,int j) {
    for(int f=0; f<4; f++) {
        if(abs(mp[i][j]-mp[i+fx[f]][j+fy[f]])!=1||i+fx[f]<1||j+fy[f]>4||j+fy[f]<1 )
            continue;
        else
            return 0;
    }
    return 1;
}
void dfs(int i,int j) {
    if(i==3&&j==4) {
        ans++;
        return ;
    }
    for(int num=0; num<=9; num++) {
        if(!flag[num]) {
            mp[i][j]=num;
            flag[num]=1;
            if(check(i,j))
                if(j==4)
                    dfs(i+1,1);
                else
                    dfs(i,j+1);
            flag[num]=0;
        }
    }
}
int main() {
    init();
    dfs(1,2);
    cout<<ans;
}

🍊方法二：暴力求解

#include <iostream>
using namespace std;
int ans=0;
void swap(int *a,int *b)
{
    int *c;
    c=a;
    a=b;
    b=c;
}
int f(int a[])//判断这种排列组合是否符合题意
{
    if(a[0]-a[4]==-1||a[0]-a[4]==1)
        return 0;
    if(a[3]-a[4]==-1||a[3]-a[4]==1)
        return 0;
    if(a[5]-a[4]==-1||a[5]-a[4]==1)
        return 0;
    if(a[7]-a[4]==-1||a[7]-a[4]==1)
        return 0;
    if(a[8]-a[4]==-1||a[8]-a[4]==1)
        return 0;
    if(a[9]-a[4]==-1||a[9]-a[4]==1)
        return 0;
    if(a[1]-a[4]==-1||a[1]-a[4]==1)
        return 0;
    if(a[1]-a[5]==-1||a[1]-a[5]==1)
        return 0;
    if(a[1]-a[6]==-1||a[1]-a[6]==1)
        return 0;
    if(a[0]-a[5]==-1||a[0]-a[5]==1)
        return 0;
    if(a[2]-a[5]==-1||a[2]-a[5]==1)
        return 0;
    if(a[8]-a[5]==-1||a[8]-a[5]==1)
        return 0;
    if(a[9]-a[5]==-1||a[9]-a[5]==1)
        return 0;
    if(a[6]-a[5]==-1||a[6]-a[5]==1)
        return 0;
    if(a[6]-a[9]==-1||a[6]-a[9]==1)
        return 0;
    if(a[6]-a[2]==-1||a[6]-a[2]==1)
        return 0;
    if(a[3]-a[0]==-1||a[3]-a[0]==1)
        return 0;
    if(a[3]-a[7]==-1||a[3]-a[7]==1)
        return 0;
    if(a[8]-a[7]==-1||a[8]-a[7]==1)
        return 0;
    if(a[8]-a[3]==-1||a[8]-a[3]==1)
        return 0;
    if(a[9]-a[8]==-1||a[9]-a[8]==1)
        return 0;
    if(a[1]-a[0]==-1||a[1]-a[0]==1)
        return 0;
    if(a[1]-a[2]==-1||a[1]-a[2]==1)
        return 0;
}
void perm(int a[],int m,int len)//列举出0-9所有的组合进行判断
{
    if(m==len-1)
    {
        if(f(a))
            ans++;
        return ;
    }
    for(int i=m;i<len;i++)
    {
        swap(a[m],a[i]);
        perm(a,m+1,len);
        swap(a[m],a[i]);
    }
}
int main()
{    
    int  a[10] = {0,1,2,3,4,5,6,7,8,9};
    perm(a,0,10);
    cout<<ans<<endl;
    return 0;
}

⭐️结果

🎉答案：1580

---

🚩快速排序

⭐️题目

排序在各种场合经常被用到。快速排序是十分常用的高效率的算法。其思想是：先选一个“标尺”，用它把整个队列过一遍筛子，以保证：其左边的元素都不大于它，其右边的元素都不小于它。这样，排序问题就被分割为两个子区间。再分别对子区间排序就可以了。

⭐️分析

swap是一个交换函数，交换数组中的两个值的位置。

partition函数是进行一轮排序，p是最左的数组索引，r是最右的数组索引。其中把最左边的数也就是索引为p的数取为基准数，x是基准数的值，最后把一轮排序后的基准数的索引给返回，之后while循环，i一直从左往右直到找到一个比基准数大的数，j从右往左直到找到一个比基准数小的数，然后交换位置，最后i和j相遇时一轮排序结束，最后将当前的基准数（此题是最左边那个）与i和j停下来的那个位置互调。

⭐️代码一

#include <stdio.h>
 
void swap(int a[], int i, int j)
{
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}
 
int partition(int a[], int p, int r)
{
    int i = p;
    int j = r + 1;
    int x = a[p];
    while(1){
        while(i<r && a[++i]<x);
        while(a[--j]>x);
        if(i>=j) break;
        swap(a,i,j);
    }
    swap(a,p,j);
    
    return j;
}
 
void quicksort(int a[], int p, int r)
{
    if(p<r){
        int q = partition(a,p,r);
        quicksort(a,p,q-1);
        quicksort(a,q+1,r);
    }
}
    
int main()
{
    int i;
    int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};
    int N = 12;
    
    quicksort(a, 0, N-1);
    
    for(i=0; i<N; i++) printf("%d ", a[i]);
    printf("\n");
    
    return 0;
}

⭐️代码二 

#include <stdio.h>
int a[101],n;//定义全局变量，这两个变量需要在子函数中使用
void quicksort(int left, int right) {
    int i, j, t, temp;
    if(left > right)
        return;
    temp = a[left]; //temp中存的就是基准数
    i = left;
    j = right;
    while(i != j) { //顺序很重要，要先从右边开始找
        while(a[j] >= temp && i < j)
            j--;
        while(a[i] <= temp && i < j)//再找右边的
            i++;       
        if(i < j)//交换两个数在数组中的位置
        {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    //最终将基准数归位
    a[left] = a[i];
    a[i] = temp;
    quicksort(left, i-1);//继续处理左边的，这里是一个递归的过程
    quicksort(i+1, right);//继续处理右边的 ，这里是一个递归的过程
}
int main() {
    int i;
    //读入数据
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    quicksort(1, n); //快速排序调用
    //输出排序后的结果
    for(i = 1; i < n; i++)
        printf("%d ", a[i]);
    printf("%d\n", a[n]);
    return 0;
}

---

🚩消除尾一

⭐️题目

下面的代码把一个整数的二进制表示的最右边的连续的1全部变成0

如果最后一位是0，则原数字保持不变。

如果采用代码中的测试数据，应该输出：

000000000000

000000000000

⭐️思路

1、采取异或去一；

2、采取加一去一；

⭐️代码

#include <stdio.h>
void f(int x)
{
    int i;
    for(i=0; i<32; i++) printf("%d", (x>>(31-i))&1);
    printf("   ");
    
    x = x&(x+1);
    
    for(i=0; i<32; i++) printf("%d", (x>>(31-i))&1);
    printf("\n");    
}
int main()
{
    f(103);
    f(12);
    return 0;
}

⭐️解析

(x>>(31-i)) & 1 可以分解成：

• [1] 31-i ：减法，31减去1。
• [2] x>>(31-i) ：x 按2进制数值 右移 （31-i) 位
• [3] 右移 后的结果 与 1 做 “按位与” 计算，

显然 x 按2进制数值 右移 （31-i) 位 后 如果 最右一位 是 1，结果输出 1 ，如果 最右一位 是 0，结果输出 0 。

---

🚩寒假作业

⭐️题目

现在小学的数学题目也不是那么好玩的。

看看这个寒假作业：

□ + □ = □

□ - □ = □

□ × □ = □

□ ÷ □ = □

每个方块代表1~13中的某一个数字，但不能重复。

比如：

6 + 7 = 13

9 - 8 = 1

3 * 4 = 12

10 / 2 = 5

以及：

7 + 6 = 13

9 - 8 = 1

3 * 4 = 12

10 / 2 = 5

就算两种解法。（加法，乘法交换律后算不同的方案）

你一共找到了多少种方案？

请填写表示方案数目的整数。

⭐️思路

由题可知，题中的序列是固定的，只有1-13这13个元素，所以可以枚举这13个元素的全部全排列，对每个排列根据条件进行筛选。最容易想到的思路就是对1~13进行全排列，然后取前12个数字逐一赋值给每个空，在12个数全部确定后，再进行四个等式的判断。同时，对于C++的STL库有着现成的函数-next_permutation实现起来也就更加简单了。

易错点：除法应该转换为乘法，因为int数作除法会丢掉结果的小数部分，导致错误结果。

⭐️代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13};
bool check()
{  
    bool b1=(a[0]+a[1]==a[2]);
    bool b2=(a[3]-a[4]==a[5]);
    bool b3=(a[6]*a[7]==a[8]);
    bool b4=(fabs((a[9]*1.0)/(a[10]*1.0)-a[11]*1.0)<=0.00000000000001);
    if(b1 && b2 &&b3 && b4)
       return true;
    else
       return false;
}
int main()
{
    int res=0;
    do
    {
        if(check())
        {
            res++;
        }
    }while(next_permutation(a,a+13));
    cout<<res<<endl;
    return 0;
}

/////////

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
int res=0;
int a[]={1,2,3,4,5,6,7,8,9,10,11,12,13};
void dfs(int start)
{
    if(start>=3 )
      if(a[0]+a[1]!=a[2]) return ;//对确定的前面三个数字进行等式判断，不符合，就不继续往下搜索
    if(start>=6)
      if(a[3]-a[4]!=a[5]) return ;//同理进行第二个等式的判断，进行剪枝
    if(start>=9)
      if(a[6]*a[7]!=a[8]) return ;
    if(start>=12)
      if(a[11]*a[10]==a[9])
      {
          for(int i=0;i<12;i++)
            cout<<a[i]<<" ";
          cout<<endl;
        res++;
        return ;
      } 
    for(int i=start;i<=12;i++)
    {
        int temp=a[start];
        a[start]=a[i];
        a[i]=temp;
        
        dfs(start+1);
        
        temp=a[start];
        a[start]=a[i];
        a[i]=temp;
    }
}
int main()
{
    dfs(0);
    cout<<res<<endl;
    return 0;
}

⭐️结果

🎉答案：64

---

🚩剪邮票

⭐️题目

如【图1.jpg】，有12张连在一起的12生肖的邮票。

现在你要从中剪下5张来，要求必须是连着的。

（仅仅连接一个角不算相连）

比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

【图1.jpg】

【图2.jpg】

 【图3.jpg】

 

 请你计算，一共有多少种不同的剪取方法。

请填写表示方案数目的整数。

⭐️思路

先找到5个数的组合，然后从第一个数字开始遍历，经过上下左右操作检测5个数是否都被访问一遍，如果5个数都可以遍历到则种类+1。

在原图中向上为-4，向下为+4，向左为-1，向右为+1，但是3,4,5,7,8这种情况是不符合要求的，但是5在4+1后被错误判定为符合情况，如果要解决这种BUG，要附加上更多的判断条件，所以重构一下原图：

 

这样，向上为-5，向下为+5，向左为-1，向右为+1，避免了每行最后一个+1后等于下一行第一个的情况。

这样在4,9,14增加1后，都不会达到左边边缘，解决了这种BUG。

在得到了一种组合后，如何判断是否满足相邻要求，是难点，可以利用DFS判断是否满足从一个点出发是否可以搜索到全部的点。

 ⭐️代码

#include <iostream>
using namespace std;
int mp[12]= {1,2,3,4,6,7,8,9,11,12,13,14};
int aa[5],vis[5],sum=0;
int b[4]= {-1,1,-5,+5};
void dfs(int n)
{
    for(int i=0; i<4; i++)
    {
        int t=aa[n]+b[i];
        if(t<1||t>14||t==5||t==10) continue;
        for(int j=0; j<5; j++)
            if(!vis[j]&&aa[j]==t)
            {
                vis[j]=1;
                dfs(j);
            }
    }
}
 
int main()
{
 
    for(int a=0; a<12; a++)
        for(int b=a+1; b<12; b++)
            for(int c=b+1; c<12; c++)
                for(int d=c+1; d<12; d++)
                    for(int e=d+1; e<12; e++)
                    {
                        aa[0]=mp[a];
                        aa[1]=mp[b];
                        aa[2]=mp[c];
                        aa[3]=mp[d];
                        aa[4]=mp[e];
                        for(int i=0; i<5; i++)
                            vis[i]=0;
                        vis[0]=1;
                        dfs(0);
                        int flag=1;;
                        for(int i=0; i<5; i++)
                        {
                            if(vis[i]!=1)
                            {
                                flag=0;
                                break;
                            }
                        }
                        if(flag==0) continue;
                        else
                            sum++;
                    }
 
    cout<<sum<<endl;
 
    return 0;
}

⭐️结果

🎉答案：116

---

🚩四平方和

⭐️题目

四平方和定理，又称为拉格朗日定理：

每个正整数都可以表示为至多4个正整数的平方和。

如果把0包括进去，就正好可以表示为4个数的平方和。

比如：

5 = 0^2 + 0^2 + 1^2 + 2^2

7 = 1^2 + 1^2 + 1^2 + 2^2

（^符号表示乘方的意思）

对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对4个数排序：

0 <= a <= b <= c <= d

并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法

程序输入为一个正整数N (N<5000000)

要求输出4个非负整数，按从小到大排序，中间用空格分开

例如，输入：

5

则程序应该输出：

0 0 1 2

再例如，输入：

12

则程序应该输出：

0 2 2 2

再例如，输入：

773535

则程序应该输出：

1 1 267 838

⭐️思路

一开始想到的便是四重for循环，但时间复杂度太大，会超时，本题可将c,d值的平方和放入哈希表中，然后以c作为value标记这个平方和，这时可将四重循环分解为两个二重循环，以空间换时间。

⭐️代码

🍊暴力解法：四重for循环

#include<cstdio>
#include<cmath>
int main()
{
    int n,a,b,c,d;
    scanf("%d",&n); 
    for(a=0;a<3000;++a)
    {
        for(b=a;b<3000;++b)
        {
            for(c=b;c<3000;++c)
            {
                d=sqrt(n-a*a-b*b-c*c);
                if(n==a*a+b*b+c*c+d*d)
                {
                    if(c>d)
                    {
                        int temp=d;
                        d=c;
                        c=temp;
                    } 
                    printf("%d %d %d %d\n",a,b,c,d);
                    return 0;
                } 
            } 
        } 
    } 
} 

🍊哈希求解 

#include<iostream>
#include<cmath>
#include<unordered_map>
using namespace std;
int main()
{
	unordered_map<int ,int> map;
	int a, b, c, d, n;
	cin >> n;
	for(c = 0; c*c <= n / 2; c++) //枚举c,d
	  for(d = c ; d*d <= n; d++)
	  {
	    if(map.find(c*c + d*d) == map.end()) //若哈希表中没有c,d的平方和这个值，就将它存入，并用c标记
		map[c*c + d*d] = c;    // 每个平方和就对应一个c值，注意这里的c值可对应多个平方和
	  }
        
	for(a = 0; 4*a*a <= n; a++)
		{
		    for(b = a; 3*b*b <= n ; b++)
		    {
			if(map.find(n - a*a - b*b) != map.end()) //如果n - 较小的前两项平方和 的值可在哈希表中找到，就将对应的值赋给c
			{
			 c = map[n - a*a -b*b];
			 d = int(sqrt(n - a*a - b*b - c*c) + 1e-3); 
			cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
			return 0; //跳出两个循环
			}
		    }
		}
   return 0;
}

---

🚩最大比例

X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。并且，相邻的两个级别间的比例是个固定值。也就是说：所有级别的奖金数构成了一个等比数列。比如：

16,24,36,54

其等比值为：3/2

现在，我们随机调查了一些获奖者的奖金数。请你据此推算可能的最大的等比值。

输入格式：

第一行为数字 N (0<N<100)，表示接下的一行包含N个正整数

第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额

要求输出：

一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数

测试数据保证了输入格式正确，并且最大比例是存在的。

例如，输入：

3

1250 200 32

程序应该输出：

25/4

再例如，输入：

4

3125 32 32 200

程序应该输出：

5/2

再例如，输入：

3

549755813888 524288 2

程序应该输出：

4/1

⭐️思路

我们假设这个最大的公比是

q=(q1/q2) //q1,q2均为正整数且互质

我们将这个序列按照升序排列之后,a1,a2,a3…an，可以得出a2/a1=q1x1/q2x1, a3/a2=q1x2/q2x2…由于这个q一定是存在的，所以现在的问题就是分别找到分子和分母，既然前提假设了q是确定的，那么q1,q2也一定是确定的，要想从 q1x1,q1x2,…q1xn中找到q1，我们可以利用类似于求gcd的辗转相除法，我们将所有的ai/ai-1进行约分确立分子和分母，然后分别对所有的分子和分母进行辗转相除，最后约分输出就好了。还要注意的一点就是一定要对数组去重= =，不然会认为存在一个qx==1

注意点：

• 1.先对数据排序并去重
• 2.两两保存约分后的比值（把a1约掉）
• 3.求n个数的qgcd时，ans用第一个值赋初值，用后面的数更新就好，ans=qgcd(ans,a[i]);
• 4.qgcd模仿gcd算法

🍊gcd算法：

a=k*b+r;

a和b的公因子c = k和r的公因子c

但是r和b是不断变小的，可以求出c

最后一定会出现整除的情况，所以r会等于0，此时gcd就是除数b。比如12,8。

综上

ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}

🍊qgcd算法：

要想从 q1x1,q1x2,…q1xn中找到q1，就是q的1次方，q的2次方，和1q，2q的思路不一样。

我们发现，qn/qm=q(n-m)，qn和qm的公因子q也就是qm和q(n-m)的公因子q

所以，qn和qm的q = qm和q(n-m)的q

最后，一定会出现除数qn和商q(n-m)相等的情况，此时就是q。注意被除数要大，除数要小，b/a，所以每次a要选qm和q(n-m)中小的，b要选qm和q(n-m)中大的。

⭐️代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[110],q1[110],q2[110];
ll t1,t2;
ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
   return gcd(b,a%b);
}
ll qgcd(ll a,ll b)
{
    if(a==b)
        return a;
    return qgcd(min(b/a,a),max(b/a,a));
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    int N = unique(a+1,a+1+n) - (a+1);
   for(int i=1;i<=N-1;i++)
    {
        ll j = i+1;
        int x=gcd(a[i],a[j]);
        q1[++t1]=a[j]/x;
        q2[++t2]=a[i]/x;
    }
    ll ans1=q1[1],ans2=q2[1];
    for(int i=2;i<=t1;i++){
        ans1=qgcd(ans1,q1[i]);
        ans2=qgcd(ans2,q2[i]);
    }
    printf("%lld/%lld\n",ans1,ans2);
    return 0;
}

---

🚩随意组合

⭐️题目

小明被绑架到X星球的巫师W那里。其时，W正在玩弄两组数据 (2 3 5 8) 和 (1 4 6 7)

他命令小明从一组数据中分别取数与另一组中的数配对，共配成4对（组中的每个数必被用到）。

小明的配法是：{(8,7),(5,6),(3,4),(2,1)}

巫师凝视片刻，突然说这个配法太棒了！

因为：

每个配对中的数字组成两位数，求平方和，无论正倒，居然相等：

87^2 + 56^2 + 34^2 + 21^2 = 12302

78^2 + 65^2 + 43^2 + 12^2 = 12302

小明想了想说：“这有什么奇怪呢，我们地球人都知道，随便配配也可以啊！”

{(8,6),(5,4),(3,1),(2,7)}

86^2 + 54^2 + 31^2 + 27^2 = 12002

68^2 + 45^2 + 13^2 + 72^2 = 12002

巫师顿时凌乱了。。。。。

请你计算一下，包括上边给出的两种配法，巫师的两组数据一共有多少种配对方案具有该特征。

配对方案计数时，不考虑配对的出现次序。

就是说：

{(8,7),(5,6),(3,4),(2,1)}

与

{(5,6),(8,7),(3,4),(2,1)}

是同一种方案。

注意：需要提交的是一个整数，不要填写任何多余内容（比如，解释说明文字等）

⭐️思路

由图易知当第一组为(2,1)时，共有6种情况，而第一组共有4种可能，所以总共有6x4=24种可能。
而且易知：一组数据不动，另一组数据全排列即可。

即求全排列，只不过不是一个数组的全排列，而是两个数组，可以一个数组不变，而另一个数组全排列，然后依次对应，这样既可以讨论完全，也不会重复。

用next_permutation()神器！

⭐️代码

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int a[4] = {2,3,5,8},b[4] = {1,4,6,7};
    int cnt = 0;
    
    do{
        int c[4],d[4];
        for(int i = 0; i < 4; i++){
            c[i] = a[i]*10+b[i];
            d[i] = a[i]+b[i]*10;
        }
        
        int sum1,sum2;
        sum1 = sum2 =0;
        for(int i = 0; i < 4; i++){
            sum1 += c[i]*c[i];
            sum2 += d[i]*d[i];
        }
        if (sum1 == sum2)
            cnt++;
    }while(next_permutation(b,b+4));
    
    cout << cnt << endl;
    return 0;
} 

⭐️结果

🎉答案：24

---

🚩拼棋盘

⭐️题目

有 8x8 和 6x6 的棋盘两块（棋盘厚度相同，单面有棋盘，背面无图案）。参见图：

组成棋盘的小格子是同样大小的正方形，黑白间错排列。

现在需要一个10x10的大棋盘，希望能通过锯开这两个棋盘，重新组合出大棋盘。

要求：

1。 拼好的大棋盘仍然保持黑白格间错的特性。

2。 两个已有的棋盘都只允许锯一锯（即锯开为两块），必须沿着小格的边沿，可以折线锯开。

3。 要尽量保证8x8棋盘的完整，也就是说，从它上边锯下的那块的面积要尽可能小。

要求提交的数据是：4块锯好的部分的面积。按从小到大排列，用空格分开。

（约定每个小格的面积为1）

比如：10 10 26 54

当然，这个不是正确答案。

请严格按要求格式提交数据，不要填写任何多余的内容（比如，说明解释等）

⭐️结果

🎉答案：8 8 28 56

---

🚩棋盘多项式

⭐️题目

八皇后问题是在棋  盘上放皇后，互相不攻击，求方案。变换一下棋子，还可以有八车问题，八马问题，八兵问题，八王问题，注意别念反。在这道题里，棋子换成车，同时棋盘也得  换，确切说，是进行一些改造。比如现在有一张n*n的棋盘，我们在一些格子上抠几个洞，这些洞自然不能放棋子了，会漏下去的。另外，一个车本来能攻击和它  的同行同列。现在，你想想，在攻击的过程中如果踩到一个洞，便会自取灭亡。故，车的攻击范围止于洞。

此题，给你棋盘的规模n，以及挖洞情况，求放k个车的方案数(k从0到最多可放车数)

【输入样式】

第一行一个整数n表示棋盘大小 

接下来n行，每行n个用空格隔开的数字0或1，0的形状表示洞，1表示没有洞 

数据规模和约定
n< =8

【输出样式】

若干行，第i行表示放i个车的方案数 

【输入样例】

3
1 0 1
1 1 1
1 0 1

【输出样例】

7
12
4

⭐️思路

类似八皇后问题，但由于洞的存在，不能像八皇后那样逐行递归搜索，而是逐行并逐列地递归搜索。

⭐️算法

1. 逐行、逐列地递归 DFS，由 dfs(int row, int col, int cnt) 实现，
   注意：在棋盘上放置一个车，则当前棋子总数对应的方案数加一，求出所有方案数只需一次 DFS

2. bool check(int row, int col) 检查一个坐标能否放置车，由于搜索自上而下、自左向右，check 函数只向上、向左检查。

   • 遇到洞，则跳出这个方向的检查
   • 遇到别的车，则不能在此处放置

⭐️数据结构

• bool vis[maxn][maxn] 记录当前位置是否已搜索过
• int solutions[maxn * maxn] 中 solutions[i] 的值为 在棋盘上放置 i个车有 solutions[i] 种方案

⭐️代码

// DFS
#include <cstdio>
using namespace std;
const int maxn = 10;
int N;
bool board[maxn][maxn];     // false 为洞
bool vis[maxn][maxn];  // 该位置是否放置了
int solutions[100];    // solution[1] 为只放一个车有多少方法
bool check(int row, int col){
    if (row > N || col > N || row < 1 || col < 1)
        return false;
    // 向上查看, 不需要向下和向右, 因为搜索的顺序是自上而下, 自左而右
    for (int rr = row - 1; rr > 0; rr--){
        if (!board[rr][col])    // 遇到洞
            break;
        if (vis[rr][col]){
            return false;
        }
    }
    // 向左查看
    for (int cc = col - 1; cc > 0; cc--){
        if (!board[row][cc])
            break;
        if (vis[row][cc])
            return false;
    }
    return true;
}
void dfs(int row, int col, int cnt){     // 坐标, 已经放了多少个车, 返回最多放了多少个车
    if (cnt <= N * N)
        solutions[cnt]++;
    for (int rr = row; rr <= N; rr++){
        int cc;     // 不加入这一部分则时间超限
        if (rr == row)  // 仍在当前行
            cc = col;
        else    // 不在当前行则从第一列开始
            cc = 1;
        for (; cc <= N; cc++){
            if (vis[rr][cc] || !board[rr][cc])
                continue;
            if (check(rr, cc)){
                vis[rr][cc] = true;
                dfs(rr, cc, cnt+1);
                vis[rr][cc] = false;
            }
        }
    }
}
int main(){
    scanf("%d", &N);
    for (int i = 1; i < N+1; i++) {
        for (int j = 1; j < N + 1; j++) {
            scanf("%d", &board[i][j]);
        }
    }
    dfs(1, 1, 0);
    for (int i = 1; i <= N * N; i++)
        if (solutions[i])
            printf("%d\n", solutions[i]);
    return 0;
}

---

🚩水仙花

⭐️题目

判断给定的三位数是否  水仙花  数。所谓  水仙花  数是指其值等于它本身  每位数字立方和的数。例  153  就是一个  水仙花  数。  153=1+125+27

【输入样式】

一个整数。

数据规模和约定
一个三位的整数,是水仙花数输出"YES",否则输出" NO"

【输出样式】

是水仙花数,输出" YES" ,否则输出" NO" (不包括引号) 

【输入样例】

123 

【输出样例】

NO

⭐️代码

#include <cstdio>
#include <cmath>
using namespace std;
int main(){
    int N, sum = 0;
    scanf("%d", &N);
    int M = N;
    for (int i = 0; i < 3; i++){
        sum += pow(N % 10, 3);
        N /= 10;
    }
    if (sum == M)
        printf("YES");
    else
        printf("NO");
    return 0;
}

---

🚩打靶

⭐️题目

小明参加X星球的打靶比赛。比赛使用电子感应计分系统。其中有一局，小明得了96分。这局小明共打了6发子弹，没有脱靶。但望远镜看过去，只有3个弹孔。显然，有些子弹准确地穿过了前边的弹孔。

不同环数得分是这样设置的：
1,2,3,5,10,20,25,50

那么小明的6发子弹得分都是多少呢？有哪些可能情况呢？

⭐️思路

是为了得到所有可能的情况，那么我们再看这f函数的参数列表分别对应什么，不难得知 ta[i] 为环数得分，因为这是最后输出的数组，那么对应的 k==N 以及 k 的初值，说明 k 表示当前所枚举的子弹环数。还有其他的参数也可根据初值以及所处位置推出。清楚了这些，我们再看函数内部，其中正式在枚举打中的子弹数，然后继续往下一环遍历枚举。那么在这改变下，得分要变，子弹剩余数要变，同时还有的就是弹孔数，由于这个值只有 1 和 0 的消费范围，故我们只要判断我们有没有枚举打中即可。

⭐️代码

#include <stdio.h>

#define N 8
void f(int ta[], int da[], int k, int ho, int bu, int sc){
   //我们发现ta[i]即为环数i得分，da[i]表示打中环数i的子弹数，k表示当前的子弹环数。ho表示弹孔数。bu表示子弹数，sc表示得分。
   int i,j;
   if(ho<0 || bu<0 || sc<0) return;

   if(k==N){
       if(ho>0 || bu>0 || sc>0) return;
       for(i=0; i<N; i++){
       for(j=0; j<da[i]; j++)
           printf("%d ", ta[i]);
       }
       printf("\n");
       return;
   }
   for(i=0; i<=bu; i++){
       da[k] = i;//枚举打中k环的子弹数。
       //f(ta, da, k+1, i==0?ho:ho-1, bu-i, sc-ta[k]*i); 
   }
   da[k] = 0;
}
int main()
{
   int ta[] = {1,2,3,5,10,20,25,50};//得分表。
   int da[N];
   f(ta, da, 0, 3, 6, 96);
   return 0;
}

---

🚩路径之谜

⭐️题目

小明冒充X星球的骑士，进入了一个奇怪的城堡。城堡里边什么都没有，只有方形石头铺成的地面。假设城堡地面是 n x n 个方格。【如图1.png】所示。

 按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但不能斜着走，也不能跳跃。每走到一个新方格，就要向正北方和正西方各射一箭。（城堡的西墙和北墙内各有 n 个靶子）

同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？有时是可以的，比如图1.png中的例子。

本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）

输入：

第一行一个整数N(0<N<20)，表示地面有 N x N 个方格

第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）

第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）

输出：

一行若干个整数，表示骑士路径。

为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3....

比如，图1.png中的方块编号为：

0 1 2 3

4 5 6 7

8 9 10 11

12 13 14 15

示例：

用户输入：

4

2 4 3 4

4 3 3 3

程序应该输出：

0 4 5 1 2 3 7 11 10 9 13 14 15

⭐️思路

对于这种类型的题，我们需要使用 dfs 来求解。我们已知每次走到一个点都会向所在行与所在列射一箭，也就是说，我们最后找出来的路径必须符合箭数相等，所以我们就可以根据给定的行箭数和列箭数来进行模拟判断走到最后一点后所有箭数是不是都清 0 了。 那么我们就可以据此模拟来跑 dfs，为了避免重复，我们需要一个 vis 数组来标记各点状态，由于此题点是顺序编号的，所以我们可以不用建立图，完全可以根据坐标来确定编号。值得注意的是，我们每次走完一条路后都要还原状态，这是为了避免所有情况都遍历到，同时，我们也需要一个 flag 标记变量来确定路径是否已找到，避免已经确定的路径被覆盖。

⭐️代码

#include<iostream>
using namespace std;
typedef struct m
{
    int flag;//判断是否走过 
}map;
map a[50][50];//二维地图 
int bei[50];//保存北边 
int xi[50];//保存西边 
int n;
int result[100];//结果序列 
int ri=0;// 结果序列 下标 
int rflag=0;//是否有结果？ 
int fangxiang[4][2]={-1,0,1,0,0,-1,0,1};//控制方向 
int check1(int t,int w1,int w2)
{
    w1+=fangxiang[t][0];
    w2+=fangxiang[t][1];//用形参假设判断 
    if(w1<0||w1>=n||w2<0||w2>=n)
    return 0;//如果超界跳过 
    if(a[w1][w2].flag==1)
    return 0;//如果 这个位置有人走过 
    return 1;
}
int check2()
{
    int tb[100]={0};
    int tx[100]={0};
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
        {
            if(a[i][j].flag)
                tx[i]++;
            if(a[j][i].flag)
                tb[i]++;
        }
        if(tx[i]!=xi[i]||tb[i]!=bei[i])
            return 0;
    }
    return 1;//收集每个北向或西向与给出的对比 
}
void  dfs(int w1,int w2)//回溯查找 
{
    if(w1==n-1&&w2==n-1)//如果达到东南角 
    {
        if(check2())
        {
            for(int i=0;i<ri;i++)
                cout<<result[i]<<" ";
                cout<<endl;
            rflag=1;//标志找到了 
        }
        return;
    }
    for(int i=0;i<4;i++)
    {
        if(check1(i,w1,w2))
        {
            w1+=fangxiang[i][0];
            w2+=fangxiang[i][1];
            a[w1][w2].flag=1;
            result[ri]=w1*n+w2;
            ri++;
            dfs(w1,w2);
            if(rflag==1)
            return;
            ri--; 
            a[w1][w2].flag=0;
            w1-=fangxiang[i][0];
            w2-=fangxiang[i][1];        
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>bei[i];
    for(int i=0;i<n;i++)
    {
        cin>>xi[i];
        for(int j=0;j<n;j++)
            a[i][j].flag=0;
    }
    a[0][0].flag=1;
    result[ri]=0;//读入以及初始化 
    ri++;
    dfs(0,0);
} 

---

🚩碱基

⭐️题目

生物学家正在对n个物种进行研究。其中第i个物种的DNA序列为s[i]，其中的第j个碱基为s[i][j]，碱基一定是A、T、G、C之一。生物学家想找到这些生物中一部分生物的一些共性，他们现在关注那些至少在m个生物中出现的长度为k的连续碱基序列。准确的说，科学家关心的序列用2m元组(i1,p1,i2,p2…im,pm)表示，满足：1<=i1<i2<…<im<=n;且对于所有q(0<=q<k), s[i1][p1+q]=s[i2][p2+q]=…=s[im][pm+q]。

现在给定所有生物的DNA序列，请告诉科学家有多少的2m元组是需要关注的。如果两个2m元组有任何一个位置不同，则认为是不同的元组。

【输入格式】

输入的第一行包含三个整数n、m、k，两个整数之间用一个空格分隔，

意义如题目所述。

接下来n行，每行一个字符串表示一种生物的DNA序列。

DNA序列从1至n编号，每个序列中的碱基从1开始依次编号，

不同的生物的DNA序列长度可能不同。

【输出格式】

输出一个整数，表示关注的元组个数。

答案可能很大，你需要输出答案除以1000000007的余数。

【样例输入】

3 2 2
ATC
TCG
ACG

【样例输出】

2

再例如：
【样例输入】

4 3 3
AAA
AAAA
AAA
AAA

【样例输出】

7

【数据规模与约定】

对于20%的数据，k<=5,所有字符串总长L满足L <=100s
对于30%的数据，L<=10000
对于60%的数据，L<=30000
对于100%的数据，n<=5,m<=5,1<=k<=L<=100000
保证所有DNA序列不为空且只会包含’A’ ’G’ ’C’ ’T’四种字母

⭐️思路

这道题比较新颖有趣。我们既然是要找长度为 k 的子字符串进行配对，那么我们完全可以先将这所有的子字符串给找出来，统计它们的出现次数以及不同的子字符串。为了方便，我们采用哈希表来存储每个字符串对应子字符串的个数，用 set 来统计不同的字符串。存储好之后就可以判断匹配了，每次用 set 里的字符串去跑一遍 dfs 来枚举我们可能配对成功的字符串，统计元组个数即可。

⭐️代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const ll mod = 1e9+7;

int n,m,k;
string s[6];
int s_index[6];//存储配对好的字符串索引。
bool vis[6];//vis[i]表示第i个字符串是否被选取。
ll ans=0;//统计方案数。
map<string,ll> res[6];
set<string> cal;
void dfs(string str,int step){
    if(step>m){
        //说明当前已经填充了m个字符串。
        for(int i=1;i<m;i++){
            if(s_index[i]>s_index[i+1]){
                //为了避免出现重复情况，我们设置字符串序号升序。
                return;
            }
        }
        ll sum=1;
        for(int i=1;i<=m;i++){
            if(!res[s_index[i]][str])return;
            sum*=res[s_index[i]][str];
        }
        ans+=sum,ans%=mod;
        return;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=true;
            s_index[step]=i;
            dfs(str,step+1);
            vis[i]=false;
        }
    }
}
void solve(){
    //接下来开始进行判断配对。
    for(auto &x:cal){
        dfs(x,1);
    }
    cout<<ans%mod<<endl;
}
int main() {
    while(cin>>n>>m>>k){
        for(int i=1;i<=5;i++){
            res[i].clear();
        }
        cal.clear();
        memset(vis,false,sizeof(vis));
        for(int i=1;i<=n;i++){
            cin>>s[i];
        }
        string temp;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=s[i].length()-k;j++){
                temp=s[i].substr(j,k);
                cal.insert(temp);
                res[i][temp]++;
            }
        }
        solve();
    }
    return 0;
}

---

📢📢📢

未完待续。。。敬请期待

📢📢📢

🍊🍊🍊

总结不易，看到这那就来个三连吧，肝。。。🍺🍺🍺

🍊🍊🍊

署名：左手の明天