牛客多校第6场赛后学习 B（两种做法）G（两种做法）M（两种写法）J

这场打的稀烂（笑的）
J题
推导公式

看这个题目说
：给定四个数，A,B,C和X，b可以变成a-b，c可以变成b-c，求解是否有情况是的c=x；

我们要达到C=X，看看是否能在n步推导出来。
推出公式后发现是个求整数解的问题，判断取模即可。
还有一种情况是A-B=B的时候

core code

int A,B,C,X;
cin>>A>>B>>C>>X;
int b=A-B;
 if (B == b) {
        if (X + C == B) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    else {
        if ((X + C - B) % (B - b) == 0) cout << "Yes" << endl;
        else if ((X + C - b) % (b - B) == 0) cout << "Yes" << endl;
        else if ((X - C) % (B - b) == 0) cout << "Yes" << endl;
        else if ((X - C) % (b - B) == 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这题引出的就是二元一次方程求整数解的贝祖定理和EXGCD，这两个东西借助这个题今天也复习了一下。

G
图形规律题。

这个题是数据小，我们可以打表，但是ICPC绝对不会有这样的题，而且到时候真打表你就等着牌子变色吧。

思考，为什么这个题很复杂呢？
原因是每个地方要处理的细节太多了，这根本和输出个什么三角形不是一个级别的。
那么怎么处理呢我们尝试把内部图案和背景分离，先构造背景再用图案去覆盖背景即可。

但是图案还是很难做，怎么办？

分解行，列，斜行即可。

#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

比赛时的SB打表代码。

#include 

using namespace std;

int main()
{
    int n;
    cin>>n;
    if(n==1)
    cout<<
R"(********************************
*..............................*
*..@...@..@@@@@..@......@@@@@..*
*..@@..@..@......@......@......*
*..@.@.@..@@@@@..@......@@@@@..*
*..@..@@..@......@..........@..*
*..@...@..@......@@@@@..@@@@@..*
*..............................*
********************************)";
   else if(n==2)
    {
            cout<<
R"(*********************************************
*...........................................*
*...........................................*
*...@.....@...@@@@@@@...@.........@@@@@@@...*
*...@@....@...@.........@.........@.........*
*...@.@...@...@.........@.........@.........*
*...@..@..@...@@@@@@@...@.........@@@@@@@...*
*...@...@.@...@.........@...............@...*
*...@....@@...@.........@...............@...*
*...@.....@...@.........@@@@@@@...@@@@@@@...*
*...........................................*
*...........................................*
*********************************************)";
    }
    else if(n==3)
    {
        cout<<
R"(**********************************************************
*........................................................*
*........................................................*
*........................................................*
*....@.......@....@@@@@@@@@....@............@@@@@@@@@....*
*....@@......@....@............@............@............*
*....@.@.....@....@............@............@............*
*....@..@....@....@............@............@............*
*....@...@...@....@@@@@@@@@....@............@@@@@@@@@....*
*....@....@..@....@............@....................@....*
*....@.....@.@....@............@....................@....*
*....@......@@....@............@....................@....*
*....@.......@....@............@@@@@@@@@....@@@@@@@@@....*
*........................................................*
*........................................................*
*........................................................*
**********************************************************)";
    }
    else if(n==4)
    {
        cout<<
R"(***********************************************************************
*.....................................................................*
*.....................................................................*
*.....................................................................*
*.....................................................................*
*.....@.........@.....@@@@@@@@@@@.....@...............@@@@@@@@@@@.....*
*.....@@........@.....@...............@...............@...............*
*.....@.@.......@.....@...............@...............@...............*
*.....@..@......@.....@...............@...............@...............*
*.....@...@.....@.....@...............@...............@...............*
*.....@....@....@.....@@@@@@@@@@@.....@...............@@@@@@@@@@@.....*
*.....@.....@...@.....@...............@.........................@.....*
*.....@......@..@.....@...............@.........................@.....*
*.....@.......@.@.....@...............@.........................@.....*
*.....@........@@.....@...............@.........................@.....*
*.....@.........@.....@...............@@@@@@@@@@@.....@@@@@@@@@@@.....*
*.....................................................................*
*.....................................................................*
*.....................................................................*
*.....................................................................*
***********************************************************************
                 )";
    }
    else
    {
        cout<<
R"(************************************************************************************
*..................................................................................*
*..................................................................................*
*..................................................................................*
*..................................................................................*
*..................................................................................*
*......@...........@......@@@@@@@@@@@@@......@..................@@@@@@@@@@@@@......*
*......@@..........@......@..................@..................@..................*
*......@.@.........@......@..................@..................@..................*
*......@..@........@......@..................@..................@..................*
*......@...@.......@......@..................@..................@..................*
*......@....@......@......@..................@..................@..................*
*......@.....@.....@......@@@@@@@@@@@@@......@..................@@@@@@@@@@@@@......*
*......@......@....@......@..................@..............................@......*
*......@.......@...@......@..................@..............................@......*
*......@........@..@......@..................@..............................@......*
*......@.........@.@......@..................@..............................@......*
*......@..........@@......@..................@..............................@......*
*......@...........@......@..................@@@@@@@@@@@@@......@@@@@@@@@@@@@......*
*..................................................................................*
*..................................................................................*
*..................................................................................*
*..................................................................................*
*..................................................................................*
************************************************************************************
                 )";
    }
    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
105
106
107
108
109
110
111
112
113
114
115
116

B题
（真的有人会把点差分写成边差分还wa了4发才发现吗？哦，是我啊，那没事了）
题意：给定n个节点，每个节点能够给从自己到跟的这条链每个点都增加一点价值，但是每个节点的增加价值能力是有限制的，我们有x点体力，每走一条边消耗一点体力，如果体力耗尽就不能再走了。

给出树形结构，以1为根，给出每个点的体力值，求每个点最大的价值。

纯树链剖分就不用了，这东西空间大，常数大，一般不是给整个子树操作或者在线的链操作都用不到这么重量级的数据结构。
思路：LCA+树上差分，刷过题就会没刷过说了也不会就不展开说了。

这里介绍两种方法求第K级祖先。
第一种倍增LCA
主要的思路就是，目前最高能到的祖先级数就是你要求的第k级祖先的log(2)k向下取整级
那么从者级层层递减就可以了

#include 
using namespace std;
struct edge
{
    int nex,to;
};
const int N = 2e6+100;
edge e[N<<1];
int dis[N];
int head[N],tot;
void add(int from,int to)
{
    e[++tot].to=to;
    e[tot].nex=head[from];
    head[from]=tot;
}
int lg[N],fa[N][30],dep[N];
void DFS(int now,int fath)
{
    dep[now]=dep[fath]+1;
    fa[now][0]=fath;
    for(int i=1;i<=lg[dep[now]];i++)
    {
        fa[now][i]=fa[fa[now][i-1]][i-1];
    }
    for(int i=head[now];i;i=e[i].nex)
    {
        if(e[i].to!=fath)
            DFS(e[i].to,now);
    }
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y])
    {
        swap(x,y);
    }
    while(dep[x]>dep[y])
    {
        x=fa[x][lg[dep[x]-dep[y]-1]];
    }
    if(x==y)
        return x;
    for(int k=lg[dep[x]]-1;k>=0;k--)
    {
        if(fa[x][k]!=fa[y][k])
        {
            x=fa[x][k];
            y=fa[y][k];
        }
    }
    return fa[x][0];
}
long long power[N];
void get(int now,int fath)
{
    for(int i=head[now];i;i=e[i].nex)
    {
        if(e[i].to==fath)
            continue ;
        get(e[i].to,now);
        power[now]+=power[e[i].to];
    }
}
int kthparent(int u,int k)
{
    for(int i=lg[dep[u]];i>=0;i--)
        if(dep[u]-dep[fa[u][i]]<=k)
            k-=dep[u]-dep[fa[u][i]],u=fa[u][i];
    return u;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int n;
     cin>>n;
    for(int i=1,x,y;i<=n-1;i++)
    {
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>dis[i];
    }
    lg[0]=-1;
    for(int i=1;i<=n;i++)
    {
       lg[i]=lg[i>>1]+1;
    }
    DFS(1,0);
    for(int i=1;i<=n;i++)
    {
        if(dis[i]==0)
            continue;
        int a=kthparent(i,dis[i]);
        power[i]++,power[a]++,power[a]--;
        power[fa[a][0]]--;
    }
    get(1,0);
    for(int i=1;i<=n;i++)
    {
        cout<<power[i]+(int)(dis[i]==0)<<" ";
    }
    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
105
106
107
108
109
110

第二种树剖LCA

#include 
#include 
#define endl '\n'
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
using namespace std;
struct node
{
    int nex,to;
};
const int N = 2e6+100;

node edge[N<<1];
int p[N];
int dep[N],head[N],tot;
int siz[N],son[N],top[N],fa[N],dfn[N],id[N],cnt,dis[N];
void add(int from,int to)
{
    edge[++tot].nex=head[from];
    edge[tot].to=to;
    head[from]=tot;
}
bool cmp(int a,int b)
{
    return dep[a]>dep[b];
}
void DFS1(int now,int fath)
{
    fa[now]=fath;
    siz[now]=1;
    son[now]=0;
    dep[now]=dep[fath]+1;
    for(int i=head[now];i;i=edge[i].nex)
    {
        if(edge[i].to==fath)
        {
            continue;
        }
        DFS1(edge[i].to,now);
        siz[now]+=siz[edge[i].to];
        if(siz[son[now]]<siz[edge[i].to])
        {
            son[now]=edge[i].to;
        }
    }
}
void DFS2(int now,int topx)//topx，先重儿子再轻儿子
{
    top[now]=topx;
    dfn[now]=++cnt;
    id[dfn[now]]=now;
    if(son[now])
    {
        DFS2(son[now],topx);
    }
    else
        return ;
    for(int i=head[now];i;i=edge[i].nex)
    {
        if(edge[i].to!=fa[now]&&edge[i].to!=son[now])
        {
            DFS2(edge[i].to,edge[i].to);
        }
    }
}
int LCA(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
        {
            swap(x,y);
        }
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
int kth_an(int u,int k)
{
    k=min(k,dep[u]-dep[1]);
    k = dep[u] - k;
    while(dep[top[u]] > k)
    {
        u = fa[top[u]];
    }
    return id[dfn[u] - (dep[u] - k)];
}
int power[N];
void get(int now,int fath)
{
    for(int i=head[now];i;i=edge[i].nex)
    {
        if(edge[i].to==fath)
            continue;
        get(edge[i].to,now);
        power[now]+=power[edge[i].to];
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=1,a,b;i<=n-1;i++)
    {
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>dis[i];
    }
    DFS1(1,0);
    DFS2(1,1);
    for(int i=1;i<=n;i++)
    {
        int a=kth_an(i,dis[i]);
       // cout<
        power[i]++,power[a]++,power[a]--,power[fa[a]]--;
    }
    get(1,0);
    for(int i=1;i<=n;i++)
    {
        cout<<power[i]<<" ";
    }
    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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

M题
给定n*m的矩阵，矩阵有‘.’，‘A’，‘B’。三种字符，棋子初始位置于（1，1）的左上角，有两名玩家小A和小B，玩家轮流使棋子向下或向右移动，当棋子落在 ‘A’上时小A赢，同理落在‘B’上小B赢。当棋子走到右下角还无人胜出则平局。

现在请你确定是否有小A必然：赢，平局，输，三种可能的棋子移动方案。

分析，小A是我们可以控制的，小B是我们不能控制的。

试着从（1，1）推导去寻找这样一条路径，发现较为难下手，因为小A每走一步就会砍掉很多路径，这些路径就可能会包含合法路径，而砍掉了就会被忽略。所以这样去做实际上有点相当于暴力DFS。

试着从右下角去推导，发现决定（i，j）位置能否成为“合法”路径上的点和（i+1，j），（i，j+1）两个点有关，只要这两个点其中一个在合法路径上，那么（i，j）肯定也在合法路径上，这样就可以从右下角一直推到左上角，看看（1，1）是否在某条合法路径上。

小A是我们可以控制的，我们每次都会积极的选择合法路径，但是小B不是，小B必须严格控制它的两个点都在合法路径上，比如当棋子位于（i，j）并且轮到B走，如果我们想找到小A赢的路径，我们必须要让（i+1，j）和（i，j+1）都不是‘B’才行。

最后发现是个经典的二维网格DP，只不过是逆着推而已，所谓的第三维纯粹是为了方便而已。

#include 
using namespace std;
const int N = 500+100;
int dp[N][N][4];
char c[N][N];
void ini(int n,int m){
    memset(dp,0,sizeof(dp));dp[n][m][2]=1;
}
int main(){
    int t,n,m;
    for(cin>>t;t;t--){
        cin>>n>>m;
        ini(n,m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            cin>>c[i][j];
        for(int k=1;k<=3;k++){
            for(int i=n;i>=1;i--){
                for(int j=m;j>=1;j--){
                    if((i+j)&1){
                        if(i+1<=n&&j+1<=m)dp[i][j][k]|=(dp[i+1][j][k]&dp[i][j+1][k]);//必须严格控制两个方位
                        else if(i+1<=n)dp[i][j][k]|=dp[i+1][j][k];
                        else if(j+1<=m)dp[i][j][k]|=dp[i][j+1][k];

                    }
                    else{
                        if(i+1<=n)dp[i][j][k]|=dp[i+1][j][k];//只要有一个方位满足即可
                        if(j+1<=m)dp[i][j][k]|=dp[i][j+1][k];
                    }
                    if(k==1){
                        if(c[i][j]=='A')dp[i][j][k]=1;
                        if(c[i][j]=='B')dp[i][j][k]=0;
                    }
                    else if(k==2){
                        if(c[i][j]!='.')dp[i][j][k]=0;
                    }
                    else{
                         if(c[i][j]=='A')dp[i][j][k]=0;
                         if(c[i][j]=='B')dp[i][j][k]=1;
                    }
                }
            }
            if(dp[1][1][k])cout<<"yes"<<" ";
            else cout<<"no"<<" ";
        }
        cout<<endl;
    }
}

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

第二种写法就是DFS了
说过的吧，这个东西本来就很像搜索，所以当然搜索也是可以做的

#include 
using namespace std;
const int N = 500+100;
int dp[N][N][4],n,m,t;
char c[N][N];
void ini(int n,int m){
    memset(dp,0,sizeof(dp));dp[n][m][2]=1;
}
void DFS(int i,int j,int k)
{
    if(i<1)
        return ;
    if((i+j)&1)
    {
        if(i+1<=n&&j+1<=m)dp[i][j][k]|=(dp[i+1][j][k]&dp[i][j+1][k]);
        else if(i+1<=n)dp[i][j][k]|=dp[i+1][j][k];
        else if(j+1<=m)dp[i][j][k]|=dp[i][j+1][k];
    }
    else
    {
        if(i+1<=n)dp[i][j][k]|=dp[i+1][j][k];
        if(j+1<=m)dp[i][j][k]|=dp[i][j+1][k];
    }
    if(k==1)
    {
        if(c[i][j]=='A')dp[i][j][k]=1;
        if(c[i][j]=='B')dp[i][j][k]=0;
    }
    else if(k==2)
    {
        if(c[i][j]!='.')dp[i][j][k]=0;
    }
    else
    {
        if(c[i][j]=='A')dp[i][j][k]=0;
        if(c[i][j]=='B')dp[i][j][k]=1;
    }
    if(j==1)
    DFS(i-1,m,k);
    else
    DFS(i,j-1,k);

}
int main(){
    for(cin>>t;t;t--)
    {
        cin>>n>>m;
        ini(n,m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            cin>>c[i][j];
        for(int k=1;k<=3;k++)
        {
            DFS(n,m,k);
            if(dp[1][1][k])
                cout<<"yes"<<" ";
            else
                cout<<"no"<<" ";
        }
        cout<<endl;
    }
}

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