• “蔚来杯“2022牛客暑期多校训练营6 补题题解（A、B、G、J、M）

    “蔚来杯“2022牛客暑期多校训练营6

    A Array

    请添加图片描述

    大佬讲的题解
    题解看不懂的话可以去B站听听面向新手哪个讲题视频，我觉得可以理解接受
    这题就是理解一下由性质推出的构造方法

    #include

using namespace std;

#define x first
#define y second

const int N = 1e6 + 10;  //虽然a最多只有1e5个数，但是构建的数组长度可能超过这个值 

typedef pair<int, int>PII;

int a[N];
int n, m;
PII p[N];
int c[N];

int t(int q){  //得到<=x的最大2的次方数 
	int u = 1;
	while(1){
		if(u > q) return u >> 1;
		u <<= 1;  //按二进制继续向左扩大 
	}
	return u >> 1;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	 
	cin>>n;
	for(int i = 1; i <= n; i ++ ){
		cin>>a[i];
		p[i].x = t(a[i]);  //记录最长t(a[i])距离至少要有一个i 
		p[i].y = i;
	} 
	
	sort(p + 1, p + 1 + n);
	
	int m = p[n].x;  //数组c的最大长度 
	
	set<int>st;
	
	for(int i = 0; i < m; i ++ ) st.insert(i);
	
	for(int i = 1; i <= n; i ++ ){
		int len = p[i].x, id = p[i].y;  //id是要塞进去的数，每隔len距离至少有一个id 
		for(int j = *st.begin(); j < m; j += len){  //j是下标，所以从0开始，每隔len的长度就要放一个id
			c[j] = id;
			st.erase(j);  //这个下标已经赋过值了，就移出集合 
		}
	}
	cout<<m<<endl; 
	for(int i = 0; i < m; i ++ ){
		if(c[i] == 0) cout<<1<<' ';  //如果a[op]被转化为0，表示这个数最小是1 
		else cout<<c[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

    B Eezie and Pie

    树上差分模板

    #include

using namespace std;

#define int long long 

const int N = 2e6 + 10, M = 2 * N;

int depth[N];
int h[N], e[M], ne[M], idx;
int f[N];  //记录树链上的节点数
int w[N];  //树上查分数组 
int fat[N][26];  //fa[u][k]记录u节点向上k层的祖先节点 
int fa[N];
int n;
int sz[N];  //记录子树节点个数 
int d[N];

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

void dfs1(int u, int father){  //建树 
	
	//初始化 
	depth[u] = depth[father] + 1;
	sz[u] = 1;
	fa[u] = father;
	
	for(int k = 1; k <= 25; k ++ ){
		fat[u][k] = fat[fat[u][k - 1]][k - 1];
	}
	
	for(int i = h[u]; ~i; i = ne[i]){
		int j = e[i];
		if(j == father) continue;
		fat[j][0] = u;
		dfs1(j, u);
		sz[u] += sz[j];
	}
}

void dfs2(int u, int father){
	f[u] = w[u];
	
	for(int i = h[u]; ~i; i = ne[i]){
		int j = e[i];
		if(j == father) continue ;
		dfs2(j, u);
		f[u] += f[j];
	}
}

int lca(int u, int dep){  //找到a节点向上depth深度的节点 
	for(int k = 25; k >= 0; k -- ){
		if(depth[fat[u][k]] >= dep){
			u = fat[u][k];
		}
	}
	return u;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n;
	memset(h, -1, sizeof h);
	
	for(int i = 1; i < n; i ++ ){
		int a, b;
		cin>>a>>b;
		add(a, b);
		add(b, a);
	}
	
	dfs1(1, 0);
	
	for(int i = 1; i <= n; i ++ ) cin>>d[i];
	
	for(int i = 1; i <= n; i ++ ){
		int tar = depth[i] - d[i];
		tar = max(1ll, tar);
		int t = lca(i, tar);
		w[fa[t]] -- ;
		w[i] ++ ;
	}
	
	dfs2(1, 0);

	for(int i = 1; i <= n; i ++ ) cout<<f[i]<<' ';
	puts("");
	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

    G Icon Design

    最笨的方法打表，拼手速和仔细程度了

    #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;
	}
	else 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;		
	}
	else 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;	
	}
	else 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;
	}
	else 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

    推公式
    请添加图片描述
    请添加图片描述

    #include

using namespace std;

int n;
int A, B, C;
int x;

int main()
{
    cin>>n;
    while(n -- ){
        cin>>A>>B>>C>>x;
        if(x == C || B - C == x) puts("Yes");
        else if(A == 2 * B) puts("No");
        else{
            if((x - C) % (2 * B - A) == 0) puts("Yes");
            else if((x - B + C) % (2 * B - A) == 0) puts("Yes");  //当k=-1时就包含了A-B-C=x的情况 
        	//else if((x + C) % (A - B) == 0) puts("Yes");
            else puts("No");
        } 
    }
	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

    M Z-Game on grid

    请添加图片描述

    #include

using namespace std;

const int N = 1e3 + 10;

char g[N][N];  //记录字符矩阵
int f[N][N];  //记录答案
int n, m, T;

void solve(){
		cin>>n>>m;
		for(int i = 1; i <= n; i ++ ) cin>>g[i] + 1;  //从每一行的下标1开始记录字符矩阵，
		
		//第一个对应的是能否找到必胜状态 
		memset(f, 0, sizeof f);  //初始化 
		f[n][m + 1] = f[n + 1][m] = 1;
		for(int i = n; i >= 1; i -- ){
			for(int j = m; j >= 1; j -- ){
				if(!((i + j) & 1)){  //如果此时棋子下标之和为偶数，那下一步就该Alice走了 
					//这里两个if是因为只要有一条必胜态Alice肯定会选择这个格子，所以两条路都要考虑到 
					//if是判断棋子下一步不会出界 
					if(i + 1 <= n) f[i][j] |= f[i + 1][j];  //或上下一步要走到的地方 
					if(j + 1 <= m) f[i][j] |= f[i][j + 1];
				}
				else{  //Bob走下一步 
				    //当不是在边界上，Bob有选择权的时候 
				    //如果下一步两个格子有一个格子可以让Alice达不到必胜态，那Bob肯定走这个，
					//所以只有当两个格子都是Alice必胜态的时候，Bob才会走向Alice必胜态
					if(i + 1 <= n && j + 1 <= m){
						f[i][j] |= (f[i + 1][j] & f[i][j + 1]);
					}
					//在边界上时，Bob只有一条路可以走，没有选择权
					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;  //遇到Alice必胜态，记录 
				if(g[i][j] == 'B') f[i][j] = 0;  //Bob必胜态 
			}
		}
		if(f[1][1]) cout<<"yes"<<' ';
		else cout<<"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是因为只要有一条必胜态Alice肯定会选择这个格子，所以两条路都要考虑到 
					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;  //到达某个人的必胜态之后就没法平局了 
			}
		}
		if(f[1][1]) cout<<"yes"<<' ';  //只需要判断起点能否和终点相连 
		else cout<<"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是因为只要有一条必胜态Alice肯定会选择这个格子，所以两条路都要考虑到 
					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];
				}
				//Bob必胜，Alice必败 
				if(g[i][j] == 'A') f[i][j] = 0;
				if(g[i][j] == 'B') f[i][j] = 1; 
			}
		}
		if(f[1][1]) cout<<"yes"<<' ';
		else cout<<"no"<<' ';
		
		cout<<endl;	
} 

int main()
{
	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
    • 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
  • 相关阅读:
    埃夫特机器人更换编码器电池
    偶数科技亮相2023中国程序员节——数据库技术高峰论坛
    抖音矩阵系统，抖音矩阵系统，抖音矩阵系统。
    使用bert进行文本二分类
    【C++】GoogleTest进阶之gMock
    Linux下Bash控制台查看有哪些用户
    拦 截 器
    如何只使用TD跟踪微分器改进普通PID控制(附完整梯形图代码）
    广东2022年下半年系统集成项目管理工程师上午真题及答案解析
    数据可观察性如何帮助数据目录计划
  • 原文地址：https://blog.csdn.net/qiaodxs/article/details/126551557