2017南宁区域赛三题题解-蒲公英云

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
![在这里插入图片描述](https://img-blog.csdnimg.cn/20191010211023395.png
https://nanti.jisuanke.com/t/A1537
H The Game of Life
根据题意我们可以确定在321轮中内，活细胞的所能到达的范围一定是在600*600这个范围内。那么我们可以在每一轮中考虑该细胞在下一轮中是不是会存活，并且该细胞的周围8个细胞中是否会有死细胞存活过来。这样的话，我们要保持的就是每个活细胞的位置了。就不需要遍历整张图，复杂度大大降低。同时，有一个地方需要注意，就是死细胞变活细胞时的情况。
如下例：
1 1
0 1
这个例子中，在遍历活细胞的时候，都会访问到0那个死细胞。会访问三次，所以我们需要标记一下，避免重复。

#include"stdio.h"
#include"string.h"
#include"queue"
#include"algorithm"
using namespace std;
typedef struct node
{
    int x,y;
    int t;
    node() {};
    node(int a,int b,int c)
    {
        x = a;
        y = b;
        t = c;
    };
} Node;
const int stand = 300;
const int dirx[8] = {-1,0,1,0,1,-1,-1,1};
const int diry[8] = {0,-1,0,1,1,-1,1,-1};
int T,n,m;
int old_Graph[610][610],new_Graph[610][610];
queue<Node> Q,P;
int main()
{
    scanf("%d",&T);
    while(T --)
    {
        while(Q.size())
            Q.pop();
        while(P.size()) P.pop();
        scanf("%d%d",&n,&m); getchar();
        for(int i = 0; i < 610; i ++)
            for(int j = 0; j < 610; j ++)
               new_Graph[i][j] = old_Graph[i][j] = 0;
        for(int i = 1; i <= n; i ++)
            {for(int j = 1; j <= m; j ++)
            {
                char x;
                scanf("%c",&x);
                new_Graph[stand + i][stand + j] = old_Graph[stand + i][stand + j] = (x == '#');
                if(old_Graph[stand + i][stand + j] == 1)
                {
                    Q.push({stand + i,stand + j,0});
                }
            }getchar();
            }
        int maxsize = Q.size(),maxcnt = 0;
        for(int i = 1; i <= 321; i ++)
        {
            while(1)
            {
                if(Q.size() == 0 || Q.front().t == i)
                    break;
                Node p = Q.front();
                Q.pop();
                int x = p.x,y = p.y,cnt = 0;
                for(int j = 0; j < 8; j ++)
                {
                    int X = x + dirx[j];
                    int Y = y + diry[j];
                    if(old_Graph[X][Y] == 1)
                    {
                        cnt ++;
                    }
                }
                if(cnt == 2 || cnt == 3)
                {
                    Q.push({x,y,p.t + 1});
                }
                else
                {
                    new_Graph[x][y] = 0;
                    P.push({x,y,0});
                }
                for(int j = 0; j < 8; j ++)
                {
                    int X = x + dirx[j];
                    int Y = y + diry[j];
                    if(old_Graph[X][Y] == 0 && new_Graph[X][Y] == 0)
                    {
                        int cnt = 0;
                        for(int j = 0; j < 8; j ++)
                        {
                            int X1 = X + dirx[j];
                            int Y1 = Y + diry[j];
                            if(old_Graph[X1][Y1] == 1)
                            {
                                cnt ++;
                            }
                        }
                        if(cnt == 3)
                        {
                            new_Graph[X][Y] = 1;
                            Q.push({X,Y,p.t + 1});
                            P.push({X,Y,1});
                        }
                    }
                }
            }
            while(P.size())
            {
                Node p = P.front(); P.pop();
                old_Graph[p.x][p.y] = p.t;
            }
            if(maxsize < Q.size())
            {
                maxsize = Q.size();
                maxcnt = i;
            }
        }
        printf("%d %d %d\n",maxcnt,maxsize,Q.size());
    }
}

https://nanti.jisuanke.com/t/A1538
I - Rake It In
看到数据范围，很容易想到dfs。直接考虑dfs即可

#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
int T,k;
int Graph[5][5];
int sum(int i,int j)
{
    return Graph[i][j] + Graph[i][j + 1] + Graph[i + 1][j] + Graph[i + 1][j + 1];
}
int tran_2(int i,int j)
{
    int x1 = Graph[i][j];
    int x2 = Graph[i][j + 1];
    int x3 = Graph[i + 1][j];
    int x4 = Graph[i + 1][j + 1];
    Graph[i][j] = x3;
    Graph[i][j + 1] = x1;
    Graph[i + 1][j + 1] = x2;
    Graph[i + 1][j] = x4;
}
int tran_1(int i,int j)
{
    int x1 = Graph[i][j];
    int x2 = Graph[i][j + 1];
    int x3 = Graph[i + 1][j];
    int x4 = Graph[i + 1][j + 1];
    Graph[i][j] = x2;
    Graph[i][j + 1] = x4;
    Graph[i + 1][j + 1] = x3;
    Graph[i + 1][j] = x1;
}
int dfs(int p)
{
    if(p == 2 * k)
    {
        int minx = 9999;
        for(int i = 1; i <= 3; i ++)
            for(int j = 1; j <= 3; j ++)
               minx = min(minx,sum(i,j));
        return minx;
    }
    if(p % 2 == 1)
    {
        int maxx = 0;
        for(int i = 1; i <= 3; i ++)
            for(int j = 1; j <= 3; j ++)
            {
                tran_1(i,j);
                maxx = max(maxx,sum(i,j) + dfs(p + 1));
                tran_2(i,j);
            }
        return maxx;
    }
    int minx = 9999;
    for(int i = 1; i <= 3; i ++)
        for(int j = 1; j <= 3; j ++)
        {
            tran_1(i,j);
            minx = min(minx,sum(i,j) + dfs(p + 1));
            tran_2(i,j);
        }
    return minx;
}
int main()
{
    scanf("%d",&T);
    while(T --)
    {
        scanf("%d",&k);
        for(int i = 1; i <= 4; i ++)
            for(int j = 1; j <= 4; j ++)
                scanf("%d",&Graph[i][j]);
        printf("%d\n",dfs(1));
    }
}

https://nanti.jisuanke.com/t/A1541L
Twice Equation
这种题，第一反应打表找规律。
发现 3 20 119
可通过oeis表也没搜到。所以一般只能线性系数不断改变来找到递推式。
可发现 f[n] = f[n -1] * 6 - f[n - 2] + 2;
数据范围大数无疑。java大数果然比C好写多了。

import java.math.*;
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner cin = new Scanner(System.in);
        BigInteger[] f = new BigInteger [1500] ;    
        BigInteger six = new BigInteger("6");
        BigInteger two = new BigInteger("2");
        f[0] = new BigInteger("3"); f[1] = new BigInteger("20");
        for(int i = 2; i < 1500; i ++)
            f[i] =  f[i - 1].multiply(six).subtract(f[i - 2]).add(two);
        int T=cin.nextInt();
        while(T != 0){
            T --;
            BigInteger x = cin.nextBigInteger();
            for(int i = 0; i < 1500; i ++)
                if(x.compareTo(f[i]) <= 0)
                {
                    System.out.println(f[i]); break;
                }
        }
    }
}