“蔚来杯“2022牛客暑期多校训练营6，签到题GJBMA

题号标题已通过代码通过率团队的状态
A Array 点击查看 388/4063
B Eezie and Pie 点击查看 1042/2840
C Forest 点击查看 38/144 未通过
D Fourier and Theory for the Universe 点击查看 11/61
E From AtCoder 点击查看 6/47
F Hash 点击查看 31/264
G Icon Design 点击查看 1499/1873
H Jumping Steps 点击查看 2/12
I Line 点击查看 211/1576
J Number Game 点击查看 1372/6243
K SolarPea and Inversion 点击查看 3/13
L Striking String Problem 点击查看 0/37
M Z-Game on grid 点击查看 694/3648

文章目录

G.Icon Design

链接：https://ac.nowcoder.com/acm/contest/33191/G
来源：牛客网

题目描述
What’s the feeling of designing an icon for a school as a programmer? Now you have a chance doing it!

The icon of Nanjing Foreign Language School (NFLS for short) is not complicated, it can be represented as an ASCII art.

Since the icon might be used in different places, you need to print the icon in different size.

Given size nn, print the icon of size nn.

Detailed format is shown below, you can also look at the sample output to confirm it.

Like which is shown in the picture, ‘*’ is used on the boundary, and ‘@’ is used for the letters.

(n+1)(n+1) '.'s are used to seperate letters and the boundary horizontally, and nn '.'s are used vertically.

Each letter is (2n+3)(2n+3) characters wide and (2n+3)(2n+3) characters in height.

The icon’s size is (4n+5) × (13n+19)(4n+5)×(13n+19).
输入描述:
The first line contains a positive integer n(1\leq n\leq 5)n(1≤n≤5), representing the size of the icon.
输出描述:
Print the icon of size nn.
示例1
输入
复制
1
输出
复制

…
…@…@…@@@@@…@…@@@@@…
…@@…@…@…@…@…
…@.@.@…@@@@@…@…@@@@@…
…@…@@…@…@…@…
…@…@…@…@@@@@…@@@@@…
…

示例2
输入
复制
3
输出
复制

…
…
…
…@…@…@@@@@@@@@…@…@@@@@@@@@…
…@@…@…@…@…@…
…@.@…@…@…@…@…
…@…@…@…@…@…@…
…@…@…@…@@@@@@@@@…@…@@@@@@@@@…
…@…@…@…@…@…@…
…@…@.@…@…@…@…
…@…@@…@…@…@…
…@…@…@…@@@@@@@@@…@@@@@@@@@…
…
…
…

题意

给出一个NFLS的图案，按照题意规则模拟 n 属于1-5时的图案，输出即可。

思路：

可以按照题意打印输出，py做法代码相对短一点，cpp也行。
而且因为数据只有5，非常的小，也可以直接手动画出图案后存到数组里输出即可。

//C++
#include
using namespace std;

int main(){
    int n;  cin>>n;
    for(int i = 0; i < 4*n+5; i++){
        for(int j=0; j < 13*n+19; j++){
            if(i==0||j==0||i==4*n+4||j==13*n+18)printf("*");
            else if((j==n+2||j==i+1||j==3*n+4||j==4*n+6||(j<=6*n+8&&j>4*n+6&&(i==n+1||i==2*n+2))||j==7*n+10||(j>7*n+10&&j<9*n+13&&(i==3*n+3))||((j==10*n+14)&&(i>=n+1&&i<=2*n+2||(i==3*n+3))||(j==12*n+16)&&(i>=2*n+2&&i<=3*n+3||(i==n+1)))||((j>10*n+14&&j<12*n+16)&&(i==n+1||i==2*n+2||i==3*n+3)))&&i>n&&i<3*n+4){
                printf("@");
            }else printf(".");
        }
        printf("\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# python3
n=int(input())
print("*"*(13*n+19))
for i in range(n):
    print("*"+"."*(13*n+17)+"*")
print("*"+"."*(n+1)+"@"+"."*(2*n+1)+"@"+"."*(n+1)+"@"*(2*n+3)+"."*(n+1)+"@"+"."*(3*n+3)+"@"*(2*n+3)+"."*(n+1)+"*")
for i in range(n):
    print("*"+"."*(n+1)+"@"+'.'*i+"@"+"."*(2*n-i)+"@"+"."*(n+1)+("@"+"."*(3*n+3))*3+"*")
print("*"+"."*(n+1)+"@"+"."*n+"@"+"."*n+"@"+"."*(n+1)+"@"*(2*n+3)+"."*(n+1)+"@"+"."*(3*n+3)+"@"*(2*n+3)+"."*(n+1)+"*")
for i in range(n):
    print("*"+"."*(n+1)+"@"+'.'*(i+n+1)+"@"+"."*(n-i-1)+"@"+"."*(n+1)+"@"+"."*(3*n+3)+"@"+"."*(5*n+5)+"@"+"."*(n+1)+"*")
print("*"+"."*(n+1)+"@"+"."*(2*n+1)+"@"+"."*(n+1)+"@"+"."*(3*n+3)+("@"*(2*n+3)+"."*(n+1))*2+"*")
for i in range(n):
    print("*"+"."*(13*n+17)+"*")
print("*"*(13*n+19))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//打表
#include
using namespace std;

int main(){
    int n;  cin>>n;
    if(n==1){
        cout<<"********************************"<<endl;
        cout<<"*..............................*"<<endl;
        cout<<"*..@...@..@@@@@..@......@@@@@..*"<<endl;
        cout<<"*..@@..@..@......@......@......*"<<endl;
        cout<<"*..@.@.@..@@@@@..@......@@@@@..*"<<endl;
        cout<<"*..@..@@..@......@..........@..*"<<endl;
        cout<<"*..@...@..@......@@@@@..@@@@@..*"<<endl;
        cout<<"*..............................*"<<endl;
        cout<<"********************************"<<endl;
    }
    if(n==2){
        cout<<"*********************************************"<<endl;
        cout<<"*...........................................*"<<endl;
        cout<<"*...........................................*"<<endl;
        cout<<"*...@.....@...@@@@@@@...@.........@@@@@@@...*"<<endl;
        cout<<"*...@@....@...@.........@.........@.........*"<<endl;
        cout<<"*...@.@...@...@.........@.........@.........*"<<endl;
        cout<<"*...@..@..@...@@@@@@@...@.........@@@@@@@...*"<<endl;
        cout<<"*...@...@.@...@.........@...............@...*"<<endl;
        cout<<"*...@....@@...@.........@...............@...*"<<endl;
        cout<<"*...@.....@...@.........@@@@@@@...@@@@@@@...*"<<endl;
        cout<<"*...........................................*"<<endl;
        cout<<"*...........................................*"<<endl;
        cout<<"*********************************************"<<endl;    
    }
    if(n==3){
        cout<<"**********************************************************"<<endl;
        cout<<"*........................................................*"<<endl;
        cout<<"*........................................................*"<<endl;
        cout<<"*........................................................*"<<endl;
        cout<<"*....@.......@....@@@@@@@@@....@............@@@@@@@@@....*"<<endl;
        cout<<"*....@@......@....@............@............@............*"<<endl;
        cout<<"*....@.@.....@....@............@............@............*"<<endl;
        cout<<"*....@..@....@....@............@............@............*"<<endl;
        cout<<"*....@...@...@....@@@@@@@@@....@............@@@@@@@@@....*"<<endl;
        cout<<"*....@....@..@....@............@....................@....*"<<endl;
        cout<<"*....@.....@.@....@............@....................@....*"<<endl;
        cout<<"*....@......@@....@............@....................@....*"<<endl;
        cout<<"*....@.......@....@............@@@@@@@@@....@@@@@@@@@....*"<<endl;
        cout<<"*........................................................*"<<endl;
        cout<<"*........................................................*"<<endl;
        cout<<"*........................................................*"<<endl;
        cout<<"**********************************************************"<<endl;
    }
    if(n==4){
        cout<<"***********************************************************************"<<endl;
        cout<<"*.....................................................................*"<<endl;
        cout<<"*.....................................................................*"<<endl;
        cout<<"*.....................................................................*"<<endl;
        cout<<"*.....................................................................*"<<endl;
        cout<<"*.....@.........@.....@@@@@@@@@@@.....@...............@@@@@@@@@@@.....*"<<endl;
        cout<<"*.....@@........@.....@...............@...............@...............*"<<endl;
        cout<<"*.....@.@.......@.....@...............@...............@...............*"<<endl;
        cout<<"*.....@..@......@.....@...............@...............@...............*"<<endl;
        cout<<"*.....@...@.....@.....@...............@...............@...............*"<<endl;
        cout<<"*.....@....@....@.....@@@@@@@@@@@.....@...............@@@@@@@@@@@.....*"<<endl;
        cout<<"*.....@.....@...@.....@...............@.........................@.....*"<<endl;
        cout<<"*.....@......@..@.....@...............@.........................@.....*"<<endl;
        cout<<"*.....@.......@.@.....@...............@.........................@.....*"<<endl;
        cout<<"*.....@........@@.....@...............@.........................@.....*"<<endl;      
        cout<<"*.....@.........@.....@...............@@@@@@@@@@@.....@@@@@@@@@@@.....*"<<endl;      
        cout<<"*.....................................................................*"<<endl;
        cout<<"*.....................................................................*"<<endl;
        cout<<"*.....................................................................*"<<endl;
        cout<<"*.....................................................................*"<<endl;
        cout<<"***********************************************************************"<<endl;
    }   
    if(n==5){
        cout<<"************************************************************************************"<<endl;
        cout<<"*..................................................................................*"<<endl;
        cout<<"*..................................................................................*"<<endl;
        cout<<"*..................................................................................*"<<endl;
        cout<<"*..................................................................................*"<<endl;
        cout<<"*..................................................................................*"<<endl;
        cout<<"*......@...........@......@@@@@@@@@@@@@......@..................@@@@@@@@@@@@@......*"<<endl;
        cout<<"*......@@..........@......@..................@..................@..................*"<<endl;
        cout<<"*......@.@.........@......@..................@..................@..................*"<<endl;
        cout<<"*......@..@........@......@..................@..................@..................*"<<endl;
        cout<<"*......@...@.......@......@..................@..................@..................*"<<endl;
        cout<<"*......@....@......@......@..................@..................@..................*"<<endl;
        cout<<"*......@.....@.....@......@@@@@@@@@@@@@......@..................@@@@@@@@@@@@@......*"<<endl;
        cout<<"*......@......@....@......@..................@..............................@......*"<<endl;
        cout<<"*......@.......@...@......@..................@..............................@......*"<<endl;
        cout<<"*......@........@..@......@..................@..............................@......*"<<endl;     
        cout<<"*......@.........@.@......@..................@..............................@......*"<<endl; 
        cout<<"*......@..........@@......@..................@..............................@......*"<<endl;     
        cout<<"*......@...........@......@..................@@@@@@@@@@@@@......@@@@@@@@@@@@@......*"<<endl;         
        cout<<"*..................................................................................*"<<endl;
        cout<<"*..................................................................................*"<<endl;
        cout<<"*..................................................................................*"<<endl;
        cout<<"*..................................................................................*"<<endl;
        cout<<"*..................................................................................*"<<endl;
        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
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

J.Number Game

链接：https://ac.nowcoder.com/acm/contest/33191/J
来源：牛客网

题目描述
There are three integers A, BA,B and CC written on the blackboard.

You can perform the following two operations as many times as you like:

Change BB to A-BA−B.
Change CC to B-CB−C.

Please note that each time you don’t need to perform all two operations. You can choose one type of operation to perform.

You are given an integer xx. Answer whether you can change CC into xx using these operations.

You need to answer TT queries independently.
输入描述:
The first line contains a positive integer T(1\leq T\leq 10 ^ 5)T(1≤T≤10
5
).

Each of the next TT lines contains four integers A, B, C, x(-10 ^ 8 \leq A, B, C, x \leq 10 ^ 8)A,B,C,x(−10
8
≤A,B,C,x≤10
8
).
输出描述:
For each test case, output “Yes” if CC can become xx, and “No” otherwise (without quotes).
示例1
输入
复制
3
2 4 3 1
2 4 3 2
4 2 2 0
输出
复制
Yes
No
Yes
说明
Please note that A, B, C, xA,B,C,x could be negative.
备注:
Please note that A, B, C, xA,B,C,x could be negative.

题意：

给出ABCx四个数，每次操作可以令B=A-B，或C=B-C。
两种操作都可以操作任意次，求最后能否存在令C=x的情况出现。

思路：

发现做两次 𝐵=𝐴−𝐵 等于没做，做两次 𝐶=𝐵−𝐶 等于没做，所以两个操作必然会交替的进行。
b1 = a-b
c1 = b-c
c2 = b1-c1 = (a-b)-(b-c)=a-2b+c = c+(a-2b)
可见每次操作会多出一个a-2b。若干次操作就是多出k个。
若两个操作使用次数相等，则 𝐶 可以成为的集合 𝑆={𝑥∣𝑥=𝐶+𝑘×(𝐴−2×𝐵)}，若次数不等，则 𝑆={𝑥∣𝑥=𝐵−𝐶+𝑘×(𝐴−2×𝐵)}
注意特判 𝐴=2×𝐵 的情况

#include
using namespace std;

int main(){
    int T;  cin>>T;
    while(T--){
        int a, b, c, x;  cin>>a>>b>>c>>x;
        if(a-2*b!=0){
            if((x-c)%(a-2*b)==0 || (x-(b-c))%(a-2*b)==0){
                cout<<"Yes\n";
            }else{
                cout<<"No\n";
            }
        }else{
            if((x-c)==0 || (x-(b-c))==0){
                cout<<"Yes\n";
            }else{
                cout<<"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

B.Eezie and Pie

链接：https://ac.nowcoder.com/acm/contest/33191/B
来源：牛客网

题目描述
Eezie, a pie maniac, would like to have some pies with her friends on a hot summer day. However, the weather is so hot that she can’t go outdoors and has to call for the delivery service.

The city Eezie lives in can be represented by NN nodes connected by N - 1N−1 edges, and the city center is node 11. In other words, the city is a rooted tree, root of which is node 11. There are NN pie houses in the city, the ii-th on node ii. For some reason, a pie house on node ii can only deliver its pie to nodes on the simple path from node ii to node 11.

Eezie is a bit worried that a pie might lose its flavor during the deliver. After some careful calculation, she decided that a pie from the ii-th pie house can maintain its flavor if the distance it is delivered does not exceed its flavor-loss-distance d_id
i

. The distance between two nodes on the tree is the number of edges on the simple path between them.

Now, Eezie wants to order some pies for all her friends who live on different nodes of the tree. Therefore, she wants you to calculate for each node how many pie houses can deliver their pie to the node without flavor loss.
输入描述:
The first line contains an integer N(1\le N \le 2\times 10^6)N(1≤N≤2×10
6
), representing the number of nodes of the city Eezie lives in.

Each of the next N - 1N−1 lines contains two integers u, v(1\le u,v \le N)u,v(1≤u,v≤N), representing an edge. It is guaranteed that the edges form a tree.

The last line contains NN integers d_1, d_2, \cdots, d_N(0\le d_i \le N)d
1

,d
2

,⋯,d
N

(0≤d
i

≤N), representing the maximum travel distances for pies from pie houses.
输出描述:
Output NN integers in a line, the ii-th integer representing the answer for node ii.
示例1
输入
复制
10
1 2
2 3
2 4
3 5
4 6
4 7
1 8
8 9
8 10
0 0 1 2 2 5 3 1 0 2
输出
复制
6 6 2 3 1 1 1 2 1 1

题意：

给出一棵有n个点的树，每个点u有一个权值，即能往上走ai步（只能走通过根节点1的路径），现在给每个点网上的路径上的点都+1，求每个点最后的值。

思路：

如果可以快速找出每个点的 𝑘 级祖先，我们就可以用树上差分来求出最终的价值。
对于k级祖先，
（1）可以利用长链剖分求 𝑘 级祖先，不过写起来麻烦，常数又大。
（2）也可以，在 dfs 时维护 dfs 栈，那么访问到点 𝑖 时，它的 𝑘 级祖先一定在当前栈内向下 𝑘 个。利用这个性质，可以 𝑂(𝑁) 求出所有的祖先。
（3）还可以倍增暴力找k级祖先。
对于树上差分，需要注意树的差分是从叶节点往根节点差的，从下到上（因为上到下会有一部分在求前缀和时被重复统计导致加的多了）。

#include 
using namespace std;
#define RG register int
#define LL long long
const int maxn = 2e6+10;

//快读模板
template<typename elemType>
inline void Read(elemType& T) {
    elemType X = 0, w = 0; char ch = 0;
    while (!isdigit(ch)) { w |= ch == '-';ch = getchar(); }
    while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    T = (w ? -X : X);
}

//存图模板
struct Graph {
    struct edge { int Next, to; };
    edge G[maxn << 1];
    int head[maxn];
    int cnt;
    Graph() :cnt(2) {}
    void clear(int n) {
        cnt = 2;fill(head, head + n + 2, 0);
    }
    void add_edge(int u, int v) {
        G[cnt].to = v;
        G[cnt].Next = head[u];
        head[u] = cnt++;
    }
};
Graph G;
int N, M;

//长链剖分模板
int Deep[maxn], Height[maxn], Anc[maxn][20], Top[maxn], Hson[maxn];
int highbit[maxn], MaxDeep[maxn];
vector<int> Up[maxn], Down[maxn], Path;
void DFS1(int u, int fa) {
    Anc[u][0] = fa;
    Height[u] = 1;
    for (int i = 1;i < 20;++i)
        Anc[u][i] = Anc[Anc[u][i - 1]][i - 1];
    for (int i = G.head[u];i;i = G.G[i].Next) {
        int v = G.G[i].to;
        if (v == fa) continue;
        Deep[v] = Deep[u] + 1;
        DFS1(v, u);
        Height[u] = max(Height[u], Height[v] + 1);
        if (Height[Hson[u]] < Height[v]) Hson[u] = v;
    }
    return;
}
void DFS2(int u, int fa, int top) {
    Path.push_back(u);
    Top[u] = top;
    MaxDeep[top] = max(MaxDeep[top], Deep[u]);
    Down[top].push_back(u);
    if (Hson[u]) DFS2(Hson[u], u, top);
    for (int i = G.head[u];i;i = G.G[i].Next) {
        int v = G.G[i].to;
        if (v == fa || v == Hson[u]) continue;
        DFS2(v, u, v);
    }
    if (u == top) {
        int len = MaxDeep[top] - Deep[u] + 1;
        for (int i = Path.size() - 1;i >= max((int)Path.size() - len - 1, 0);--i)
            Up[top].push_back(Path[i]);
    }
    Path.pop_back();
}
int KthAnc(int u, int k) {  //求u的k级祖先
    if (k > Deep[u]) return 0;
    if (k == 0) return u;
    u = Anc[u][highbit[k]];
    k -= (1 << highbit[k]);
    if (Deep[u] - k == Deep[Top[u]]) return Top[u];
    if (Deep[u] - k > Deep[Top[u]]) return Down[Top[u]][Deep[u] - k - Deep[Top[u]]];
    return Up[Top[u]][Deep[Top[u]] - (Deep[u] - k)];
}


//对树上差分求前缀和
int v[maxn];
LL s[maxn], ans[maxn];
int dfs(int u, int f){
    for (int i = G.head[u];i;i = G.G[i].Next) {
        int v = G.G[i].to;
        if (v == f) continue;
        dfs(v,u);
        ans[u] += ans[v];
    }
    ans[u] += s[u];
    return ans[u];
}

int main() {
    Read(N);
    for (int i = 1;i <= N - 1;++i) {
        int u, v;
        Read(u);Read(v);
        G.add_edge(u, v);
        G.add_edge(v, u);
    }
    DFS1(1, 0);
    DFS2(1, 0, 1);
    int Max = 1;
    for (int i = 1;i <= N;++i) {
        if ((i >> Max) & 1) ++Max;
        highbit[i] = Max - 1;
    }
    for(int i = 1; i <= N; i++){
        ans[i] = 0;  s[i] = 1; //每个点都会被+1，所以直接初始值+1
    }
    for(int i = 1; i <= N; i++){
        cin>>v[i];
        int lst = KthAnc(i,v[i]+1);  //第i个点的k+1级祖先
        s[lst]--;
    }
    dfs(1,-1);
    for(int i = 1; i <= N; i++){
        cout<<ans[i]<<" ";
    }
    cout<<"\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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

M.Z-Game on grid

链接：https://ac.nowcoder.com/acm/contest/33191/M
来源：牛客网

题目描述
Alice and Bob are playing a game on an n\times mn×m grid where each cell has either ‘A’, ‘B’ or ‘.’ written on it. They take turns moving a chess piece on the grid and Alice moves first.

Initially the piece is on cell (1,1)(1,1). In each player’s turn, he or she can move the piece one cell right or one cell down. That is, if the piece is on cell (x,y)(x,y) before the turn, the player can move it to (x+1,y)(x+1,y) or (x,y+1)(x,y+1), as long as it doesn’t go beyond the grid.

At any time, if the piece is on a cell with ‘A’, Alice wins and the game ends. If the piece is on a cell with ‘B’, Bob wins and the game ends. If the piece reaches cell (n,m)(n,m) without the game ending, then it is a draw.

Since Alice cannot decide what acts Bob will take, she would like to know if she can be in control of the situation. Given the grid they’re playing on, can you tell her if she can always find a way to win, draw or lose the game no matter what acts Bob takes?

输入描述:
In the first line an integer T\space (1 \le T \le 50)T (1≤T≤50), representing the number of test cases.

For each test case, the first line contains two integers N,M\space (1\le N,M \le 500)N,M (1≤N,M≤500), representing the grid’s size.

Each of the next NN lines for the case contains MM characters (either ‘A’, ‘B’ or ‘.’), describing the grid.
输出描述:
For each test case, output three words ‘yes’ or ‘no’ in one line, representing if Alice can find a way to win, draw or lose the game respectively (without quotes).
示例1
输入
复制
2
3 3
…B
…B
BB.
1 3
…
输出
复制
no no yes
no yes no

题意：

两个人在 𝑁∗𝑀 的网格上轮流移动一个棋子。棋子初始位为 (1,1) ，每次只能向某一维的正方向（右边或下面）移动一格。
网格上有一些特殊点，移到标 ’A’ 的点先手胜，移到标 ‘B’ 的点先手败，没有移到特殊点且不能再移动棋子则为平局。问先手是否有必胜、必平局、必败的策略。

思路：

一个局面下，对最终胜负有影响的只有棋子的位置和目前是谁的回合。棋子只能向右或向下移动，所以状态是没有后效性的。因此我们可以考虑 dp.
可以发现三种胜负结果的做法是类似的，这里我们以先手胜为例：
用一个布尔数 𝑑𝑝[𝑖][𝑗] 表示移动到 (𝑖,𝑗) ，先手是否必胜。因为每次只能移一格，A先移动，所以位置确定后也能知道当前是先手还是后手。对于先手和后手，需要分开转移：
如果现在是先手动，那么只要 (𝑖+1,𝑗) 和 (𝑖,𝑗+1) 中的一个能使先手必胜，(𝑖,𝑗) 就是先手必胜。
如果现在是后手动，那么只有 (𝑖+1,𝑗) 和 (𝑖,𝑗+1) 都能使先手胜,(𝑖,𝑗) 才能使先手必胜。

#include
using namespace std;
const int maxn = 550;
char s[maxn][maxn];
int dp[maxn][maxn], n, m; //移动到(𝑖,𝑗), 先手是否必胜/必平局/必败
int dfs(int x, int y){
    if(dp[x][y]>=0)return dp[x][y]; //记忆化
    if(s[x][y] == 'A')return 1;     //必胜（遇到x,y必胜会打断x+1,y平局之类的,走不上来）
    if(s[x][y] == 'B')return 4;     //必败
    if(x==n&&y==m)return 2;         //必平局
    if(x==n)return dp[x][y]=dfs(x,y+1);
    if(y==m)return dp[x][y]=dfs(x+1,y);
    if((x+y)%2==0){                 //当前轮到先手移动，只要两个有一个能赢/平局/输掉就行
        return dp[x][y]=dfs(x+1,y)|dfs(x,y+1);
    }else{                          //当前轮到后手移动，需要两个都能赢/平局/输掉才行
        return dp[x][y]=dfs(x+1,y)&dfs(x,y+1);
    }
}
int main(){
    int T;  cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i = 1; i <= n; i++)scanf("%s",s[i]+1);
        memset(dp,-1,sizeof(dp));
        int ans = dfs(1,1);
        if(ans&1)cout<<"yes ";else cout<<"no ";
        if(ans&2)cout<<"yes ";else cout<<"no ";
        if(ans&4)cout<<"yes\n";else cout<<"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
32
33

A.Array

链接：https://ac.nowcoder.com/acm/contest/33191/A
来源：牛客网

题目描述
Ranran has a sequence aa of nn integers a_1, a_2, \cdots, a_na
1

,a
2

,⋯,a
n

which satisfies \displaystyle \sum \dfrac 1 {a_i} \leq \dfrac 1 2∑
a
i

1

≤
2
1

and he is very proud of it, so he comes up with a problem for you.

You need to find out a sequence cc of mm integers c_0, c_1, \cdots, c_{m - 1}c
0

,c
1

,⋯,c
m−1

. With cc, you construct an infinite sequence bb, and b_ib
i

equals to c_{i\bmod m}c
imodm

. bb must satisfy the condition that in every consecutive a_ia
i

numbers of bb there exists a number equals to ii.

Please note that aa is 1-indexed and b, cb,c are 0-indexed. The value of mm is decided by you.

Can you solve the problem?
输入描述:
The first line contains an integer n\ (1\leq n\leq 10 ^ 5)n (1≤n≤10
5
).

The second line contains nn integers a_1, a_2, \cdots, a_n\ (2\leq a_i \leq 2 \times 10 ^ 5, \sum \dfrac 1 {a_i} \leq \dfrac 1 2)a
1

,a
2

,⋯,a
n

(2≤a
i

≤2×10
5
,∑
a
i

1

≤
2
1

).
输出描述:
The first line output an integer mm.

The second line output mm integers c_0, c_1, \cdots, c_{m - 1}c
0

,c
1

,⋯,c
m−1

.

You should guarantee that 1\leq m\leq 10 ^ 61≤m≤10
6
and 1\leq c_i\leq n1≤c
i

≤n.
示例1
输入
复制
1
2
输出
复制
2
1 1

题意：

给出长为n(1e5）的数组，每个数ai(<2e5)，所有数的倒数之和<1/2。
你需要构造一个长为m（<1e6）的序列，满足ci无限复制后，每ai个数中就会出现一次i。
题目保证合法方案存在。

思路：

每ai个数里出现一次i，显然ai越小需要出现的次数（频率）就越多，按照ai升序排序后，每次先去找能放的位置往上放应该是最优的。
考虑条件倒数和小于等于 1/2 怎么用。
等式两边都乘以2，左边每个分数乘2相当于分母/2，即每个数ai缩小为ai/2时，倒数和<1，然后将ai扩大，显然倒数和更小了，依然小于1。
每个 𝑎_𝑖 改成小于他最大的 2 的幂，显然倒数和小于等于 1。
然后，，构造哈夫曼树？，即带权路径长度最短的树，以及不知道为啥m=1<<18（，，
但是这题其实可以，不用小于等于1/2这个条件，因为题目保证有解（
所以贪心从小到大的放后，可以直接让m=最大值1e6，然后暴力找到前面或后面第一个能放的位置，不够就往前加，超过了就往后退，一直放到能够联通下一个循环节满足<=a[i].w即可。

//std
#include
using namespace std;
const int maxn = 1e6+10;
struct node{ int w, id;}a[maxn];
bool cmp(node x, node y){ return x.w < y.w; }
int b[maxn];

int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i].w;  a[i].id = i;
        a[i].w = (1<<31-__builtin_clz(a[i].w));
    }
    sort(a+1,a+n+1,cmp);    //从小到大排序
    int cur = 1, m = (1<<18);
    for(int i = 1; i <= n; i++){
        while(b[cur])cur++; //找到第一个能放的位置
        for(int j = cur; j <= m; j += a[i].w){
            b[j] = a[i].id;
        }
    }
    cout<<m<<"\n";
    for(int i = 1; i <= m; i++)cout<<max(1,b[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

//greedy
#include
using namespace std;
const int maxn = 2e6+10;
struct node{ int w, id;}a[maxn];
bool cmp(node x, node y){ return x.w < y.w; }
int b[maxn];

int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i].w;  a[i].id = i;
    }
    sort(a+1,a+n+1,cmp);    //从小到大排序
    int cur = 1, m = 1e6;
    for(int i = 1; i <= n; i++){
        while(b[cur])cur++; //找到第一个能放的位置
        for(int j = cur; ; j += a[i].w){
            while(b[j] || j>m)j--;  //填过了或者超过了，退退退（保证有解
            b[j] = a[i].id;
            if(m-j+cur<=a[i].w)break; //如果满足能够联通上下一个循环节，就break
        }
    }
    cout<<m<<"\n";
    for(int i = 1; i <= m; i++)cout<<max(1,b[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

相关阅读:
【Android】-- 按钮（复选框CheckBox、开关按钮Switch、单选按钮RadioButton）
nacos源码级别集群启动及拉取数据同步流程
 html大作业【NBA篮球介绍 22个页面】学生网页设计源码
 羊大师：夏日畅饮羊奶滋补又消暑
 Centos下安装MySQL，配置远程连接（无坑版）
ESP8266-Arduino网络编程实例-远程固件升级
 vm2 组件存在沙箱逃逸漏洞
 导致锁表的原因及解决方法
 autojs（意图篇之startActivity）
【编译原理】手工打造语法分析器
原文地址：https://blog.csdn.net/qq_33957603/article/details/126199772