DS集训练习题第一天（2020/12/28）——题解

1.由于是北大OJ所以代码部分万能头文件不能用，整体思路就是按行枚举，找到‘#’同时判断对应行列标记数组是否已经被标记，本题唯一的坑在于，按行遍历的起始行需要在上一层的行数基础上+1枚举下一行，否则会导致后面的与前面重复配对，而且你还没来得及WA就TLE了。http://poj.org/problem?id=1321

#include<iostream>
#include<stdio.h>
using namespace std;
char a[9][9];
int col[9]={0};
int n,k;
int sum=0;
void dfs(int u,int x)
{
    if(u==k)
    {
        sum++;
        return;
    }
    else
    {
        for(int i=x;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(a[i][j]=='#'&&!col[j])
                {
                    col[j]=1;
                    dfs(u+1,i+1);
                    col[j]=0;
                }
            }
        }
    }

}
int main()
{
    while(1)
    {
        scanf("%d%d",&n,&k);
        if(n==-1&&k==-1)
        {
            break;
        }
        else
        {
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    cin>>a[i][j];
                }
            }
        }
        dfs(0,0);
        printf("%d\n",sum);
        sum=0;
    }
    return 0;
}

2.暴力枚举+氧气优化（不优化TLE），和dfs没什么关系。https://www.luogu.com.cn/problem/P2105

#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
#define N 20020
using namespace std;
int n,m,K;
int sum;
int a[N],b[N],c[N*2],d[N*2];
int main()
{
    scanf("%d%d%d",&n,&m,&K);
    for(int i=1;i<=K;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[x]=1;
        b[y]=1;
        c[x+y]=1;
        d[x-y+N]=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]) continue;
            for(int j=1;j<=m;j++)
            {
                if(!a[i]&&!b[j]&&!c[i+j]&&!d[i-j+N])
                {
                    sum++;
                }
            }
    }
    printf("%d\n",sum);
    return 0;
}

3. 下面的(x,y)相当于(u,i)
   （1）反对角线 y=x+b,截距b=y−x，因为我们要把b当做数组下标，所以 bb 不能是负的，所以我们 +n，保证是结果是正的
   （2）而对角线 y=−x+b,截距是 b=y+x这里截距一定是正的，所以不需要加偏移量
   核心目的：找一些合法的下标来表示dg或udg是否被标记过，所以如果你愿意，你取 udg[n+n−u+i]也可以，只要所有(u,i)对可以映射过去就行。
   https://www.luogu.com.cn/problem/P1219

   #include <bits/stdc++.h>
   using namespace std;
   const int N = 30;
   // bool数组用来判断搜索的下一个位置是否可行
   // col列，dg对角线，udg反对角线
   // g[N][N]用来存路径
   int n;
   int g[N];
   bool col[N], dg[N], udg[N];
   int sum=0;
   void dfs(int u)
   {
    // u == n 表示已经搜了n行，故输出这条路径
    if (u == n)
    {
        if(sum<3)
        {
            for (int i = 0; i < n; i ++ ) printf("%d ",g[i]);   // 等价于cout << g[i] << endl;
            puts("");  // 换行       
        }
        sum++;
        return;
    }
   
    //对n个位置按行搜索
    for (int i = 0; i < n; i ++ )
        // 剪枝(对于不满足要求的点，不再继续往下搜索)              udg[n - u + i]，+n是为了保证大于0
        if (!col[i] && !dg[u + i] && !udg[n - u + i])
        {
            g[u]=i+1;
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            // 恢复现场 这步很关键
            col[i] = dg[u + i] = udg[n - u + i] = false;
        }
   }
   int main()
   {
    cin >> n;
    dfs(0);
    printf("%d\n",sum);
    return 0;
   }