大家好，又见面了，我是你们的朋友全栈君。

题目链接

A组真题

题目结构

第一题 随意组合

• 问题重现

  小明被绑架到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)}
  是同一种方案。

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

• 解题思路

  由于这组两种数据已经给出了，且数据量特别小，我们完全可以暴力全排列，为了避免重复，所以我们只需要对一组数据进行全排列配对判断即可。

• 代码

/** *@filename:随意组合 *@author: pursuit *@CSDNBlog:unique_pursuit *@email: 2825841950@qq.com *@created: 2021-03-21 17:24 **/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;
//答案为24种。
int a[]={ 
2,3,5,8};
int b[]={ 
1,4,6,7};
void solve(){ 

int ans=0,temp1,temp2;
do{ 

temp1=pow(a[0]*10+b[0],2)+pow(a[1]*10+b[1],2)+pow(a[2]*10+b[2],2)+pow(a[3]*10+b[3],2);
temp2=pow(b[0]*10+a[0],2)+pow(b[1]*10+a[1],2)+pow(b[2]*10+a[2],2)+pow(b[3]*10+a[3],2);
if(temp1==temp2){ 

cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<endl;
ans++;
}
}while(next_permutation(a,a+4));
cout<<ans<<endl;
}
int main() { 

solve();
return 0;
}

• 答案

  $24$。

第二题 拼棋盘

• 问题重现

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

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QUpveHNU-1616515786984)(第七届蓝桥杯（软件类）C++决赛A组题解.assets/image-20210323152742472.png)]

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

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

  要求：

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

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

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

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

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

  比如：10 10 26 54

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

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

• 解题思路

  见下图即可：

• 答案

  $882856$

第三题 打靶

• 问题重现

小明参加X星球的打靶比赛。

比赛使用电子感应计分系统。其中有一局，小明得了96分。

这局小明共打了6发子弹，没有脱靶。

但望远镜看过去，只有3个弹孔。

显然，有些子弹准确地穿过了前边的弹孔。

不同环数得分是这样设置的：

$1,2,3,5,10,20,25,50$

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

下面的程序解决了这个问题。

仔细阅读分析代码，填写划线部分缺失的内容。

#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, _____________ , 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;
}

• 解题思路

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

• 答案

  i==0?ho:ho-1

第四题 路径之谜

• 问题重现

  小明冒充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

  资源约定：
  峰值内存消耗 < 256M
  CPU消耗 < 1000ms

  请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

• 解题思路

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

• 代码

/** *@filename:路径之谜 *@author: pursuit *@CSDNBlog:unique_pursuit *@email: 2825841950@qq.com *@created: 2021-03-22 20:27 **/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 25;
const int mod = 1e9+7;
int n;
bool vis[maxn][maxn];
int go[][2]={ 
{ 
-1,0},{ 
1,0},{ 
0,-1},{ 
0,1}};
int col[maxn],row[maxn];
bool flag;//判断是否已经找到路径。
vector<int> path;//记录路径。
bool check(){ 

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

if(row[i]||col[i]){ 

return false;
}
}
return true;
}
void dfs(int x,int y){ 

if(x==n&&y==n){ 

if(check()){ 

flag=true;
return;
}
}
for(int i=0;i<4;i++){ 

int tx=x+go[i][0];
int ty=y+go[i][1];
if(tx<1||tx>n||ty<1||ty>n||vis[tx][ty]||!row[tx]||!col[ty])continue;
vis[tx][ty]=true;
row[tx]--;
col[ty]--;
path.push_back((tx-1)*n+(ty-1));
dfs(tx,ty);
if(flag)return;
row[tx]++;
col[ty]++;
path.pop_back();
vis[tx][ty]=0;
}
}
void solve(){ 

flag=false;
dfs(1,1);
int len=path.size();
for(int i=0;i<len;i++){ 

cout<<path[i];
i==len-1?cout<<endl:cout<<" ";
}
}
int main() { 

while(cin>>n){ 

memset(vis,false,sizeof(vis));
for(int i = 1;i <= n;i++){ 

cin>>col[i];
}
for(int i = 1;i <= n;i++){ 

cin>>row[i];
}
path.clear();
vis[1][1]=true;
row[1]--,col[1]--;
path.push_back(0);
solve();
}
return 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’四种字母

  资源约定：
  峰值内存消耗 < 256M
  CPU消耗 < 1000ms

  请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

  所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

  注意: main函数需要返回0
  注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
  注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。

  提交时，注意选择所期望的编译器类型。

• 解题思路

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

• 代码

/** *@filename:碱基 *@author: pursuit *@CSDNBlog:unique_pursuit *@email: 2825841950@qq.com *@created: 2021-03-22 21:36 **/
#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;
}

第六题 圆圈舞（待补）

• 问题重现

  春天温暖的阳光照耀着大地，正是草原上的小动物们最快乐的时候。小动物们在草原上开了一个舞会，欢度这美好的时光。

  舞会上最重要的一个环节就是跳圆舞曲，n只小动物手拉手围成一大圈，随着音乐跳起来。在跳的过程中，小动物们可能会变换队形。它们的变换方式是动物A松开自己右手，动物B松开自己的左手，动物A和B手拉到一起，而它们对应的松开的手（如果有的话）也拉到一起。

  例如，假设有10只小动物，按顺序围成一圈，动物1的右手拉着动物2的左手，动物2的右手拉着动物3的左手，依次类推，最后动物10的右手拉着动物1的左手。如果通过动物2和8变换队形，则动物2的右手拉着动物8的左手，而对应的动物3的左手拉着动物7的右手，这样形成了1-2-8-9-10和3-4-5-6-7两个圈。如果此时通过动物2和6变换队形，则将形成1-2-6-7-3-4-5-8-9-10一个大圈。注意，如果此时通过动物1和2变换队形，那么队形不会改变，因为动物1的右手和动物2的左手松开后又拉到一起了。

  在跳舞的过程中，每个动物i都有一个欢乐值Hi和一个感动值Fi。
  如果两个动物在一个圈中，欢乐值会彼此影响，产生欢乐能量。如果两个动物i, j（i≠j）在同一个大小为t的圈中，而动物i在动物j右手的第p个位置（动物j右手的第1个位置就是动物j右手所拉着的动物，而第2个位置就是右手第1个位置的动物右手拉着的动物，依次类推），则产生的欢乐能量为(t-p)HjFi。在跳舞的过程中，动物们的欢乐值和感动值有可能发生变化。

  圆舞曲开始的时候，所有的动物按编号顺序围成一个圈，动物n右手的第i个位置正好是动物i。现在已知小动物们变换队形的过程和欢乐值、感动值变化的过程，求每次变换后所有动物所产生的欢迎能量之和。

  【输入格式】
  输入的第一行包含一个整数n，表示动物的数量。
  接下来n行，每行两个用空格分隔的整数Hi, Fi，按编号顺序给出每只动物的欢乐值和感动值。
  接下来一行包含一个整数m，表示队形、欢乐值、感动值的变化次数。
  接下来m行，每行三个用空格分隔的整数k, p, q，当k=1时，表示小动物们通过动物p和动物q变换了队形，当k=2时，表示动物p的欢乐值变为q，当k=3时，表示动物p的感动值变为了q。

  【输出格式】
  输出m行，每行一个整数，表示每次变化后所有动物产生的能量之和。
  答案可能很大，你需要计算答案除以1000000007的余数。

  【样例输入】
  10
  1 1
  1 1
  1 1
  1 1
  1 1
  1 1
  1 1
  1 1
  1 1
  1 1
  9
  1 2 8
  1 2 6
  2 8 10
  3 5 10
  1 1 2
  1 2 1
  2 5 5
  1 4 8
  1 4 5

  【样例输出】
  100
  450
  855
  1341
  1341
  811
  923
  338
  923

  【数据规模与约定】
  对于20%的数据，2<=n,m<=100。
  对于30%的数据，2<=n,m<=1000。
  另有20%的数据，只有k=1的操作且Hi,Fi均为1。
  另有20%的数据，只有k=1或2的操作且Fi均为1。
  对于100%的数据，2<=n,m<=100000，0<=Hi,Fi<=10^{9，1<=k<=3，k=1时1<=p,q<=n且p≠q，k=2或3时1<=p<=n且0<=q<=10}9。

  资源约定：
  峰值内存消耗 < 256M
  CPU消耗 < 2500ms

  请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

  所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

  注意: main函数需要返回0
  注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
  注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。
  =1的操作且Hi,Fi均为1。
  另有20%的数据，只有k=1或2的操作且Fi均为1。
  对于100%的数据，2<=n,m<=100000，0<=Hi,Fi<=10^{9，1<=k<=3，k=1时1<=p,q<=n且p≠q，k=2或3时1<=p<=n且0<=q<=10}9。

  资源约定：
  峰值内存消耗 < 256M
  CPU消耗 < 2500ms

  请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

  所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

  注意: main函数需要返回0
  注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
  注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。

  提交时，注意选择所期望的编译器类型。