2017南宁区域赛三题题解

秒速五厘米 2023-06-06 08:27 38阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
!\[在这里插入图片描述\](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;
                    }
            }
        }
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/