2022牛客蔚来杯第六场

G.Icon Design

• 题意

  • 签到题，根据n的大小输出对应尺寸的符号矩阵，n<=5

• 题解

  • 打表或者直接根据规律填充字符，需要一点耐心

• 代码

打表

#include 

using namespace std;

int main() {
    int n;
    cin>>n;
    if(n==1){
        printf("********************************\n");
        printf("*..............................*\n");
        printf("*..@...@..@@@@@..@......@@@@@..*\n");
        printf("*..@@..@..@......@......@......*\n");
        printf("*..@.@.@..@@@@@..@......@@@@@..*\n");
        printf("*..@..@@..@......@..........@..*\n");
        printf("*..@...@..@......@@@@@..@@@@@..*\n");
        printf("*..............................*\n");
        printf("********************************\n");
    }
    if(n==2){
        printf("*********************************************\n");
        printf("*...........................................*\n");
        printf("*...........................................*\n");
        printf("*...@.....@...@@@@@@@...@.........@@@@@@@...*\n");
        printf("*...@@....@...@.........@.........@.........*\n");
        printf("*...@.@...@...@.........@.........@.........*\n");
        printf("*...@..@..@...@@@@@@@...@.........@@@@@@@...*\n");
        printf("*...@...@.@...@.........@...............@...*\n");
        printf("*...@....@@...@.........@...............@...*\n");
        printf("*...@.....@...@.........@@@@@@@...@@@@@@@...*\n");
        printf("*...........................................*\n");
        printf("*...........................................*\n");
        printf("*********************************************\n");
    }
    if(n==3){
        printf("**********************************************************\n");
        printf("*........................................................*\n");
        printf("*........................................................*\n");
        printf("*........................................................*\n");
        printf("*....@.......@....@@@@@@@@@....@............@@@@@@@@@....*\n");
        printf("*....@@......@....@............@............@............*\n");
        printf("*....@.@.....@....@............@............@............*\n");
        printf("*....@..@....@....@............@............@............*\n");
        printf("*....@...@...@....@@@@@@@@@....@............@@@@@@@@@....*\n");
        printf("*....@....@..@....@............@....................@....*\n");
        printf("*....@.....@.@....@............@....................@....*\n");
        printf("*....@......@@....@............@....................@....*\n");
        printf("*....@.......@....@............@@@@@@@@@....@@@@@@@@@....*\n");
        printf("*........................................................*\n");
        printf("*........................................................*\n");
        printf("*........................................................*\n");
        printf("**********************************************************\n");
    }
    if(n==4){
        printf("***********************************************************************\n");
        printf("*.....................................................................*\n");
        printf("*.....................................................................*\n");
        printf("*.....................................................................*\n");
        printf("*.....................................................................*\n");
        printf("*.....@.........@.....@@@@@@@@@@@.....@...............@@@@@@@@@@@.....*\n");
        printf("*.....@@........@.....@...............@...............@...............*\n");
        printf("*.....@.@.......@.....@...............@...............@...............*\n");
        printf("*.....@..@......@.....@...............@...............@...............*\n");
        printf("*.....@...@.....@.....@...............@...............@...............*\n");
        printf("*.....@....@....@.....@@@@@@@@@@@.....@...............@@@@@@@@@@@.....*\n");
        printf("*.....@.....@...@.....@...............@.........................@.....*\n");
        printf("*.....@......@..@.....@...............@.........................@.....*\n");
        printf("*.....@.......@.@.....@...............@.........................@.....*\n");
        printf("*.....@........@@.....@...............@.........................@.....*\n");
        printf("*.....@.........@.....@...............@@@@@@@@@@@.....@@@@@@@@@@@.....*\n");
        printf("*.....................................................................*\n");
        printf("*.....................................................................*\n");
        printf("*.....................................................................*\n");
        printf("*.....................................................................*\n");
        printf("***********************************************************************\n");
    }
    if(n==5){
        printf("************************************************************************************\n");
        printf("*..................................................................................*\n");
        printf("*..................................................................................*\n");
        printf("*..................................................................................*\n");
        printf("*..................................................................................*\n");
        printf("*..................................................................................*\n");
        printf("*......@...........@......@@@@@@@@@@@@@......@..................@@@@@@@@@@@@@......*\n");
        printf("*......@@..........@......@..................@..................@..................*\n");
        printf("*......@.@.........@......@..................@..................@..................*\n");
        printf("*......@..@........@......@..................@..................@..................*\n");
        printf("*......@...@.......@......@..................@..................@..................*\n");
        printf("*......@....@......@......@..................@..................@..................*\n");
        printf("*......@.....@.....@......@@@@@@@@@@@@@......@..................@@@@@@@@@@@@@......*\n");
        printf("*......@......@....@......@..................@..............................@......*\n");
        printf("*......@.......@...@......@..................@..............................@......*\n");
        printf("*......@........@..@......@..................@..............................@......*\n");
        printf("*......@.........@.@......@..................@..............................@......*\n");
        printf("*......@..........@@......@..................@..............................@......*\n");
        printf("*......@...........@......@..................@@@@@@@@@@@@@......@@@@@@@@@@@@@......*\n");
        printf("*..................................................................................*\n");
        printf("*..................................................................................*\n");
        printf("*..................................................................................*\n");
        printf("*..................................................................................*\n");
        printf("*..................................................................................*\n");
        printf("************************************************************************************\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

一点点填充，还是有点烦人的，因为没有那么简单qwq

#include 
using namespace std;

char s[53][103];
int main() {
  int n;
  cin >> n;
  int len = 13 * n + 19, height = 4 * n + 5;
  //处理背景
  for (int j = 1; j <= len; j++) s[1][j] = '*';
  for (int i = 2; i < height; i++) {
    s[i][1] = s[i][len] = '*';
    for (int j = 2; j < len; j++) s[i][j] = '.';
  }
  for (int j = 1; j <= len; j++) s[height][j] = '*';
  
  //处理横线
  int top = n + 2, mid = 2 * n + 3, bottom = 3 * n + 4;
  for (int j = 4 * n + 7; j <= 6 * n + 9; j++) s[top][j] = s[mid][j] = '@';
  for (int j = 7 * n + 11; j <= 9 * n + 13; j++) s[bottom][j] = '@';
  for (int j = 10 * n + 15; j <= 12 * n + 17; j++) s[top][j] = s[mid][j] = s[bottom][j] = '@';

  //处理竖线
  for (int i = top; i <= mid; i++)
    s[i][n + 3] = s[i][3 * n + 5] = s[i][4 * n + 7] = s[i][7 * n + 11] = s[i][10 * n + 15] = '@';
  for (int i = mid; i <= bottom; i++)
    s[i][n + 3] = s[i][3 * n + 5] = s[i][4 * n + 7] = s[i][7 * n + 11] = s[i][12 * n + 17] = '@';

  //处理斜线
  for (int i = top; i <= bottom; i++) s[i][i + 1] = '@';

  //输出
  for (int i = 1; i <= height; i++) {
    for (int j = 1; j <= len; j++) {
      cout << s[i][j];
    }
    cout << endl;
  }

  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

J.Number Game

• 题意

  • 给定a,b,c,x
  • 可以将b变成a-b；可以将c变成b-c
  • 问能否通过如上变化把c变成x

• 题解

  • 连续使用两个一样的操作是无效的，相当于没有操作。故只能两个操作交替使用才有效

  • 枚举先1后2和先2后1两种交替方式，发现最终c的值为特定的几种形式(k整数)
    x ? = c = { k × ( a − 2 b ) + c k × ( a − 2 b ) + b − c k × ( a − 2 b ) + a − b − c x?=c=

    {k×(a−2b)+ck×(a−2b)+b−ck×(a−2b)+a−b−c" role="presentation" style="position: relative;">⎧⎩⎨k×(a−2b)+ck×(a−2b)+b−ck×(a−2b)+a−b−c$$\{\begin{array}{l}k\times (a-2b)+c\\ k\times (a-2b)+b-c\\ k\times (a-2b)+a-b-c\end{array}$$
    x?=c=⎩ ⎨ ⎧​k×(a−2b)+ck×(a−2b)+b−ck×(a−2b)+a−b−c​

  • 只需检验以上式子能否等于x即可。枚举k太繁琐，可以转换成左边为k的式子，为检验看是否为整数即可。注意不能除以0的情况要特判

• 代码

#include 

using namespace std;

bool solve() {
    int a,b,c,x;
    cin>>a>>b>>c>>x;
    
    if(a==2*b) {//不能转换为左边为k的式子，特判
        if(c==x) return 1;
        if(b-c==x) return 1;
        return 0;
    }
  
  //能转换时，判断三种形式下k是否为整数
    if((x-c)%(a-2*b)==0) return 1;
    if((x-b+c)%(a-2*b)==0) return 1;
    if((x-a+b+c)%(a-2*b)==0) return 1;
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    int t;
    cin>>t;
    while(t--) cout<<(solve() ? "Yes":"No")<<'\n';
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

M.Z-Game on grid

• 题意

  • n*m的矩阵，有’A’,‘B’,'.'三种符号
  • 游戏Alice 先走，Bob后走，从(1,1)只能向右和向下走。当走到A那么Alice赢，走到B那么Bob赢，否则直到走到(n,m)没有胜负，就是平局
  • 问不论Bob怎么下，Alice是否存在一种路径使得必胜、必平或必输

• 题解

  • 把必胜、必平、必输三种情况分开看

  • 先解决必胜。如果从头到尾走，要搜索所有路径，每个点还要判断所有后面的子路径是否存在必胜，就是dfs了，复杂度写不了。既然都跟后面相关，那么我直接倒推，发现能够考虑到所有路径的情况，然后dp复杂度也够

  • dp

    定义：f[i,j]表示路径包含(i,j)时，能否达到Alice想要的必胜、平、输

    转移：

    如果Alice必胜，那么路径上有A必胜，有B必败；如果Alice平局，那么路径上所有AB都导致不平局，相当于必败态；如果Alice必输，那么路径上的所有A为必败态，B为必胜态。

    如果此点(i+j)%2=0说明此步为Alice选择，那么Alice一定选自己想要的状态就可能可以完成问题。而Bob我们假定一定阻止Alice达到想要的状态。即在最大阻力情况下存在想要路径，那么一定存在。

    转移方程直接贴代码里面了

• 代码

#include 
#include 

using namespace std;
const int N=510;

int t,n,m;
int f[N][N];
char g[N][N];

void solve() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>g[i]+1;
    
    memset(f,0,sizeof f);//重置数组
    for(int i=n;i>=1;i--)
        for(int j=m;j>=1;j--) {
            if(!((i+j)&1)) {//Alice动手，右和下如果存在必胜态则此点必胜
                if(i+1<=n) f[i][j]|=f[i+1][j];
                if(j+1<=m) f[i][j]|=f[i][j+1];
            }
            else {//Bob动手，只有右和下都必胜才会使得Alice此点必胜
                if(i+1<=n&&j+1<=m) f[i][j]=(f[i+1][j]&f[i][j+1]);
                else if(i+1<=n) f[i][j]|=f[i+1][j];
                else if(j+1<=m) f[i][j]|=f[i][j+1];
            }
            if(g[i][j]=='A') f[i][j]=1;//只要此点是必胜，路径直接必胜
            if(g[i][j]=='B') f[i][j]=0;//只要此点是必败，那么一票否决
        }
    cout<<(f[1][1] ? "yes":"no")<<' ';
    
    memset(f,0,sizeof f);//重置
    f[n][m]=1;//假设是平局
    for(int i=n;i>=1;i--)
        for(int j=m;j>=1;j--) {
            if(!((i+j)&1)) {
                if(i+1<=n) f[i][j]|=f[i+1][j];
                if(j+1<=m) f[i][j]|=f[i][j+1];
            }
            else {
                if(i+1<=n&&j+1<=m) f[i][j]=(f[i+1][j]&f[i][j+1]);
                else if(i+1<=n) f[i][j]|=f[i+1][j];
                else if(j+1<=m) f[i][j]|=f[i][j+1];
            }
            if(g[i][j]!='.') f[i][j]=0;//只要路径上出现不是平局，那么必败
        }
    cout<<(f[1][1] ? "yes":"no")<<' ';
    
    memset(f,0,sizeof f);//重置
    for(int i=n;i>=1;i--)//与第一个一样
        for(int j=m;j>=1;j--) {
            if(!((i+j)&1)) {
                if(i+1<=n) f[i][j]|=f[i+1][j];
                if(j+1<=m) f[i][j]|=f[i][j+1];
            }
            else {
                if(i+1<=n&&j+1<=m) f[i][j]=(f[i+1][j]&f[i][j+1]);
                else if(i+1<=n) f[i][j]|=f[i+1][j];
                else if(j+1<=m) f[i][j]|=f[i][j+1];
            }
            if(g[i][j]=='B') f[i][j]=1;
            if(g[i][j]=='A') f[i][j]=0;
        }
    cout<<(f[1][1] ? "yes":"no")<<'\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>t;
    while(t--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

B.Eezie and Pie

• 题意

  • 给一颗以1节点为根的树，以及每个节点向根节点方向走能走的最远距离di
  • 求每个点能有几个点能够到达此点

• 题解

  • 画图可知，每个点能送到的点为： 从该点出发到根节点路径中，长度为di的这些点
  • 上述覆盖的段路径ans都要+1，很想区间+c操作，所以差分思路，即树链差分
  • dfs所有路径，起点+1，终点上一点-1,完成差分处理。最后再dfs一遍统计答案

• 代码

#include 
#include 
#include 

using namespace std;
const int N=2e6+10;

int n;
int sz[N];//差分数组兼任答案数组
int d[N];
int h[N],e[2*N],ne[2*N],idx;//无向图，开两倍

void add(int a,int b) {
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

vector path;//记录dfs中的某条路径
void dfs(int u,int fa) {//无向图，链式向前星会有父节点，传入父节点去掉上述情况
    path.push_back(u);//路径加入此节点
    sz[u]++;//差分数组，起点+1
    int len=path.size();
    if(len-d[u]-2>=0) sz[path[len-d[u]-2]]--;//如果终点上一节点存在，-1
    for(int i=h[u];i!=-1;i=ne[i]) {//dfs子节点
        int j=e[i];
        if(j!=fa) dfs(j,u);//不是父节点dfs
    }
    path.pop_back();//此点所有路径处理完毕，丢出路径数组
}

void cal(int u,int fa) {//计算差分的前缀和，计算答案
    for(int i=h[u];i!=-1;i=ne[i]) {
        int j=e[i];
        if(j!=fa) cal(j,u),sz[u]+=sz[j];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>n;
    memset(h,-1,sizeof h);//初始化
    for(int i=1;i>u>>v;
        add(u,v);add(v,u);//无向边
    }
    for(int i=1;i<=n;i++) cin>>d[i];
    
    dfs(1,0);//处理差分数组
    cal(1,0);//计算答案
    for(int i=1;i<=n;i++) cout<

#include 
#include 
#include 

using namespace std;
const int N=2e6+10;

int n;
int sz[N],d[N];
int h[N],e[2*N],ne[2*N],idx;

void add(int a,int b) {
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

vector path;
int dfs(int u,int fa) {
    path.push_back(u);
    sz[u]++;
    int len=path.size();
    if(len-d[u]-2>=0) sz[path[len-d[u]-2]]--;
    for(int i=h[u];i!=-1;i=ne[i]) {
        int j=e[i];
        if(j!=fa) sz[u]+=dfs(j,u);
    }
    path.pop_back();
    
    return sz[u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i>u>>v;
        add(u,v);add(v,u);
    }
    for(int i=1;i<=n;i++) cin>>d[i];
    
    dfs(1,0);
    for(int i=1;i<=n;i++) cout<