题目：AcWing 3385. 玛雅人的密码

https://www.acwing.com/problem/content/description/3388/
没想到清华的题目设了这么多陷阱，下面在代码段一一分析
思路不难，就是纯BFS

思路

整体思路是用BFS暴搜
存在队列中的基本元素是pair<string,int>
+ 前者表示经过多次交换后当下的字符串的组成
+ 后者表示达到当下的字符串状态，经过的交换次数

因为数字本身可能会重复出现，而且对于一个字符串交换它两个不同相邻位置得到的新字符串，也可能产生重复，但我们要求的是最少交换次数，因为BFS的性质，保证了可以实现最小，所以可以设置一个map映射组，来存储已经出现过的字符串情况，防止重复对相同组成的字符串再入队处理，以作到剪枝的作用，降低时间复杂度。

这道题进入BFS暴搜前，要做一些基本的判断，很容易就考虑不到，要做好了。

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
typedef pair<string,int> PII;
#define x first
#define y second
int n;
string str,add;
map<string,int> M;
bool is2012(string u)  //判断字符串里是否有连续的2012
{                      //这里可以用KMP算法改进，但是规模不大，不用也没事
    for(int i=0;i<u.size()-3;i++)
        if(u[i]=='2'&&u[i+1]=='0'&&u[i+2]=='1'&&u[i+3]=='2')
            return true;
    return false;
}

int main()
{
    scanf("%d",&n);
    if(n<4)  //如果输入串/初始串本身长度<4，则不可能到达对应状态
    {
        printf("-1");
        return 0;
    }

    cin>>str;
    int is0=0,is1=0,is2=0;  //记录一个0，1，2的个数
    for(int i=0;i<n;i++)
    {
        if(str[i]=='0') is0++;
        if(str[i]=='1') is1++;
        if(str[i]=='2') is2++;
    }

    if(is0<1||is1<1||is2<2) //如果012的个数组不成2021，那也不可能达到目标状态
    {
        printf("-1");
        return 0;
    }

    if(is2012(str))  //如果初始状态就是目标状态，那直接输出即可
    {
        printf("0");
        return 0;
    }
    //BFS暴搜
    queue<PII> Q;
    Q.push({str,0}); //初始串入队，交换次数为0
    M[str]++;  //记录下已经出现过它

    while(!Q.empty())
    {
        string temp=Q.front().x;
        int d=Q.front().y;
        Q.pop();

        for(int i=1;i<temp.size();i++)
        {   //遍历，交换所有相邻位置
            add=temp;
            add[i]=temp[i-1];
            add[i-1]=temp[i];

            if(is2012(add)) //判断是否达到目的状态
            {   //达到了就输出后退出
                printf("%d",d+1);
                return 0;
            }
            if(!M[add])    //利用map判断该串是否处理过，处理过就不处理
            {
                Q.push({add,d+1});  //交换次数+1
                M[add]++;  //在map里记录一下，表示已经处理过
            }
        }
    }
    printf("-1");  //如果暴搜完了还没退出，表示没有答案
    return 0;
}

题目：AcWing 3402. 等差数列

https://www.acwing.com/problem/content/3405/
这题是真难啊

思路

基本性质：每一行、每一列中，至少要有两个元素，就可以恢复出一整行、一整列来

用行号、列号来指代行、列，为了不重复且唯一，将行号映射为本身，即$[0,n-1]$，把列号$[0,m-1]$通过$+n$映射为$[n,n+m-1]$。

整理了下思路步骤：
1. 在处理输入的过程中同时记录每行有多少个真实有效值、每列有多少个真实有效值，输入处理完了将符合条件的、可以恢复的行、列序号入队
2. 开始BFS处理
根据从队首取出的行（列）序号，针对取出的这一行（列）进行处理，恢复出该行（列）所有元素值（在前面入队的条件中，保证了我们入队的行（列）一定是可以全部被恢复的），每恢复一个元素，都会相应的影响对应列（行）上真实有效的值的个数，再对这些列（行）去进行判断，把符合条件且没处理过的列（行）入队。
一直处理，直到队列为空为止，即可不重不漏的把可以恢复的元素恢复出来。
3. 最后对存放结果的数组进行适当的排序处理，再输出。

代码

int g[N][N];//存储矩阵

int rows[N],cols[N];//动态记录每一行、每一列有多少个值是真实有效的

//队列数据结构
//队列中存放的是列号或者行号，总和最大不超过M
int hh,tt=-1;
int q[M];

PII ans[N*N];//记录恢复出来的点的座标
int top;

bool st[M];//判重数组，对于处理完的行、列不再进行处理

完整源码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second

const int N=1010,M=2*N;

int g[N][N];
PII ans[N*N];
int top;
int rows[N],cols[N];
int hh,tt=-1;
int q[M];
int m,n;
bool st[M];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {    
            scanf("%d",&g[i][j]);
            if(g[i][j])
            {//在输入的过程中同时记录每行有多少个真实有效值、每列有多少个真实有效值
                rows[i]++;
                cols[j]++;
            }
        }
    for(int i=0;i<n;i++)   //遍历每一行，把可以经过操作进而恢复出一整行的行入队处理
        if(rows[i]>=2&&rows[i]<m)
        {  //如果该行真实有效的值的个数大于2个（可以恢复出一整行的下限），且小于m个（这时这行元素都真实有效，无须恢复）
            q[++tt]=i;   //把行号入队
            st[i]=true;  //判重数组记录一下已经处理过
        }
    for(int i=0;i<m;i++)  //遍历每一列，把可以经过操作进而恢复出一整列的列入队处理
        if(cols[i]>=2&&cols[i]<n)
        { //如果该列真实有效的值的个数大于2个（可以恢复出一整列的下限），且小于n个（这时这列元素都真实有效，无须恢复）
            q[++tt]=i+n; //把列号入队
            st[i+n]=true;//判重数组记录一下已经处理过
        }

    while(hh<=tt)  //开始BFS
    {
        auto t=q[hh++];  //取出队首元素并出队
        if(t<n)   //从队列中取出的元素是行号
        {
            PII p[2];
            int cnt=0;

            for(int i=0;i<m;i++)
            {//对于该行，遍历它的每一列
                if(g[t][i])
                {  //只需要找到两个元素就可以了，前面入队的条件也保证了我们必然可以找到
                    p[cnt++]={i,g[t][i]};
                    if(cnt==2) break;
                }

            }

            int d=(p[1].y-p[0].y)/(p[1].x-p[0].x); //公差
            int a=p[1].y-p[1].x*d; //首项

            for(int i=0;i<m;i++)
            {//对于该行，遍历它的每一列
                if(!g[t][i])
                { //按照计算出的公差和首项恢复出该行的需要恢复的列
                    g[t][i]=a+d*i;
                    ans[top++]={t,i}; //把被恢复的元素座标放入结果

                    cols[i]++; //此时，该列上真实有效的值的个数增加了
                    if(cols[i]>=2&&cols[i]<n&&!st[i+n])
                    { //如果该列没被处理过，且符合条件，将它入队
                        q[++tt]=i+n;
                        st[i+n]=true; //标记一下，表示处理过了
                    }
                }
            }
        }
        else      ////从队列中取出的元素是列号
        {
            t-=n; //根据映射关系，恢复出真正的列号
            PII p[2];
            int cnt=0;

            for(int i=0;i<n;i++)
            {//对于该列，遍历它的每一行
                if(g[i][t])
                { //只需要找到两个元素就可以了，前面入队的条件也保证了我们必然可以找到
                    p[cnt++]={i,g[i][t]};
                    if(cnt==2) break;
                }

            }

            int d=(p[1].y-p[0].y)/(p[1].x-p[0].x);//公差
            int a=p[1].y-p[1].x*d;//首项

            for(int i=0;i<n;i++)
            {//对于该列，遍历它的每一行
                if(!g[i][t])
                {//按照计算出的公差和首项恢复出该列的需要恢复的行
                    g[i][t]=a+d*i;
                    ans[top++]={i,t};//把被恢复的元素座标放入结果

                    rows[i]++;//此时，该行上真实有效的值的个数增加了
                    if(rows[i]>=2&&rows[i]<m&&!st[i])
                    {//如果该行没被处理过，且符合条件，将它入队
                        q[++tt]=i;
                        st[i]=true;//标记一下，表示处理过了
                    }
                }
            }
        }
    }

    sort(ans,ans+top); //将存放结果的数组按照行优先排序
    for(int i=0;i<top;i++)
    { //输出
        auto p=ans[i];
        printf("%d %d %d\n",p.x+1,p.y+1,g[p.x][p.y]);
    }  //注意这里的座标实际上是1-n和1-m，要注意+1
    return 0;
}