• 2022牛客多校联赛加赛 题解

    比赛传送门
    作者： fn

    目录

    签到题

    M题 Maimai DX 2077

    题目大意
    有个音游叫 Maimai DX 2077。
    这个音游有四种音符，每种音符有五个判定。
    不同音符的不同判定会获得不同基础分数。
    绝赞的判定单独计算分数。
    给定一次游玩每种音符每种判定的数量，问达成度。

    考察内容
    模拟

    分析
    将判定的表作为 4 × 5 数组输入程序。
    读入时直接计算 A , A 0 , B , B 0 A, A_0,B,B_0 A,A0​,B,B0​ 即可。

    #pragma GCC optimize(3)
#include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
int t;
int n,m;
int a[5][10];
double b[5][10] = {{0,0,0,0,0},{0,1.0,1.0,0.8,0.5,0},{0,2.0,2.0,1.6,1.0,0},{0,3.0,3.0,2.4,1.5,0},{0,5.0,5.0,2.5,2,0}};
using namespace std;
int main(){ // AC 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	double suma = 0;
	double sumb = 0;
	double cnt1 = 0;
	double cnt2 = 0;
	for(int i = 1;i<=4;i++){
		int sum = 0;
		for(int j = 1;j<=5;j++){
			cin>>a[i][j];
			sum+=a[i][j];
		}
		cnt1+=sum*b[i][1];
	}
	for(int i = 1;i<=4;i++){
		for(int j = 1;j<=5;j++){
			suma+=a[i][j]*b[i][j];
		}
	}
    sumb = a[4][1]*1.0+a[4][2]*0.5+a[4][3]*0.4+a[4][4]*0.3+a[4][5]*0.0;
	cnt2 = (a[4][1]+a[4][2]+a[4][3]+a[4][4]+a[4][5])*1.0;
	
	double ans = suma/cnt1*100+sumb/cnt2; // 完成度 
	printf("%.9f",ans);
}

    • 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

    H题 Here is an Easy Problem of Zero-chan / 一个简单的后缀零问题

    题目大意
    有一颗 n 个节点且以 1 为根的有根树。
    第 i 个点的点权为 i。
    多次查询编号为 x 的点,
    ∏ i = 1 n l c a ( i , x ) ∏^n_{i=1} lca(i, x) ∏i=1n​lca(i,x) 的末尾有多少个零。

    考察内容
    dfs序，差分

    分析
    末尾零的个数即因子中2的个数和5的个数取min。

    要求多次询问，所以考虑预处理出答案。

    预处理子树大小 s z [ i ] sz[i] sz[i] ，预处理dfs序。遍历每一个结点，更新答案的时候对子树进行区间更新，也就是在dfs序上差分。

    复杂度 O ( n ) O(n) O(n) 。

    #include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N = 1e5+5;
int n, m;

vector<int> g[N];

ll num2[N];
ll num5[N];
ll sz[N]; // 子树大小 
ll dfs_[N],len; // dfs序 
ll pos[N]; // 指向dfs序中的位置 

ll c2[N],c5[N]; // dfs序的答案的差分 

ll dfs2(int x,int fa){ // 预处理sz 
	sz[x]=1; // 自己算1个 
	for(auto a1:g[x]){
		if(a1==fa)continue;
		
		sz[x]+=dfs2(a1,x);
	}
	return sz[x];
}
void dfs3(int u,int fa){ // 求dfs序 
    dfs_[++len]=u;  
    int sz=g[u].size();
    for(int i=0;i<sz;i++){
        if(g[u][i]!=fa){
            dfs3(g[u][i],u);
        }
    }
}

void dfs4(int x,int fa){ // 更新x的答案 
	ll d=x; 
	ll cnt2=0,cnt5=0; 
	while(d%2==0){
		cnt2++;
		d/=2;
	}
	while(d%5==0){
		cnt5++;
		d/=5;
	}	
	c2[pos[x]]+=cnt2*sz[x];
	c2[pos[x]+1]-=cnt2*sz[x]; // 单点更新 
		
	c5[pos[x]]+=cnt5*sz[x];
	c5[pos[x]+1]-=cnt5*sz[x];
	
	
	for(auto a1:g[x]){ // 枚举子树,更新子树 
		if(a1==fa)continue;
		
		ll r=pos[a1]+sz[a1]-1; // dfs序上的右边界 
		ll val=sz[x]-sz[a1]; // 除了这个子树的大小 
		
		c2[pos[a1]]+=cnt2*val;
		c2[r+1]-=cnt2*val;
		
		c5[pos[a1]]+=cnt5*val;
		c5[r+1]-=cnt5*val;
	}
	
	for(auto a1:g[x]){
		if(a1==fa)continue;
		
		dfs4(a1,x);
	}
}

int main(){ // dfs序+差分
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i=1; i<=n-1; i++){
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for(int i=0;i<=n;i++){
    	num2[i]=num5[i]=0; // 初始化 
    }
    
    dfs2(1,0); // 预处理子树大小sz 
	
	len=0; 
	dfs3(1,0); // 求dfs序 

	for(int i=1;i<=n;i++){
		pos[dfs_[i]]=i; // i指向dfs序中pos[i]的位置 
	} 
	
	dfs4(1,0); // 更新答案 
	
	dfs_[0]=0; 
	
	for(int i=1;i<=n;i++){
		num2[i]=num2[i-1]+c2[i]; // 对c作前缀和 
		num5[i]=num5[i-1]+c5[i];
	}
	  
    for(int i=1; i<=m; i++){
        int x; cin>>x;
	 	cout<<min(num2[pos[x]],num5[pos[x]])<<endl;   
    }
}
/*
5 5
2 3
5 4
2 5
1 5
1 2 3 4 5

*/

    • 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

    基本题

    E题 Everyone is bot / 人人都是复读机

    题目大意

    有 n 个人打算在群里复读。一次复读的过程如下：
    每一轮，n 个人按照编号从小到大依次选择是否复读，每个人最多只会复读一次。

    如果某一轮没有人进行复读，那么复读的过程结束。

    对于第 i 个人，如果他是所有人中第 j 个进行复读的，他会获得 ai,j 瓶冰红茶。
    但是如果他是所有进行了复读的人当中倒数第 p 个进行复读的人，那么他会被禁言，他不会获得任何冰红茶，并且倒扣 154 杯冰红茶。

    每个人都想最大化自己获得的冰红茶数量，求最终每个人各自拿到多少冰红茶。

    考察内容
    博弈论

    分析

    例1
    输入：

    5 2
1000 4 3 2 1
4 1000 3 2 1
4 3 1000 2 1
4 3 2 1000 1
4 3 2 1 1000

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    举例， p = 2 p=2 p=2 时
    首先，轮到每个人要拿的时候必须立刻选择，所以每个人只能拿自己那行的主对角线上的格子。

    假设所有人全部拿格子，则最后两人（第4，第5人）必然要等对方先拿，自己再拿，这样对方禁言，自己没事。结果就是最后两个人“打架”，都不拿，只有前3个人拿。
    前3个人拿格子，同理，最后两人（第2，第3人）必然要等对方先拿，自己再拿，结果就是两个人都拿不了，一轮轮空复读直接结束。
    所以只剩下第一个人拿。第一个人可以方向拿，因为已经分析过了，2345都不敢拿。
    拿到格子的人数是 n − p − p = 5 − 2 − 2 = 1 n-p-p=5-2-2=1 n−p−p=5−2−2=1 即 n n n % p = 1 p=1 p=1

    例2
    输出：

    1000 0 0 0 0

    • 1

    输入：

    5 3
1000 4 3 2 1
4 1000 3 2 1
4 3 1000 2 1
4 3 2 1000 1
4 3 2 1 1000

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    p = 3 p=3 p=3 时，同理。
    最后3个人“打架”，前面两个人把对角线拿掉。
    拿到格子的人数是 n − p = 5 − 3 = 2 n-p=5-3=2 n−p=5−3=2 即 n n n % p = 2 p=2 p=2

    输出：

    1000 1000 0 0 0

    • 1

    显然可以推广。

    得出结论：前 n n n % p p p 个人可以拿。所有答案是主对角线左上角前 n n n % p p p 个，后面的人都拿不了，直接输出0。

    #include
#define ll long long
#define int long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1005;
ll n,m,p,a[N][N];

signed main(){ // 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>p;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}

	int h=n%p;
	for(int i=1;i<=h;i++){ // 
		if(i==n)cout<<a[i][i]; // 拿斜对角线 
		else cout<<a[i][i]<<' ';
	}
	for(int i=h+1;i<=n;i++){
		if(i==n)cout<<0;
		else cout<<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

    J题 Jellyfish and its dream / 水母和它的梦想

    题目大意
    给一个序列，值域为 { 0 , 1 , 2 } \{0,1,2\} {0,1,2} 。
    如果 ( a i + 1 ) m o d    3 = a i + 1 m o d    n (a_i + 1) \mod 3 = a_{i+1 \mod n} (ai​+1)mod3=ai+1modn​ （取模意义下加一等于后一个数），就可以将 a i a_i ai​ 赋值为 ( a i + 1 ) m o d    3 (a_i + 1) \mod 3 (ai​+1)mod3（后一个数）。

    问有限次操作后是否能使所有元素均相等。
    1 ≤ ∑ n ≤ 1 0 6 1 ≤∑n ≤ 10^6 1≤∑n≤106

    考察内容
    单调栈

    分析

    解法不唯一。

    看作一个单调栈，序列 a a a 中的元素依次入栈。每次入栈之前把栈顶相同的或者小1的元素pop出来。

    最后再把整个序列入栈一遍，处理一下环形就可以。

    #include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e6+10;
ll n,m,a[N];
int len=0;

int main(){ // 单调栈 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		len=0; 
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i]; // 0,1,2
		}
		
		deque<ll> b;
		
		ll n2=n;
		
		for(int i=n;i>=2;i--){
			if(a[i]==a[1] || (a[i]+1)%3==a[1]){
				n2=i-1;
			}
			else{
				break;
			}
		}
		
		for(int i=1;i<=n;i++){
			if(i==1){
				len++;
				b.push_back(a[i]);
			}	
			else{ // i>=2
				while(len>=1 && (b.back()==a[i] || (b.back()+1)%3==a[i])){
					len--;
					b.pop_back();
				}
				len++;
				b.push_back(a[i]);
			}
		}
		
		
		for(int i=1;i<=n;i++){ 
			if(len>=2){ 
				ll t1=a[i]; // 

				while(len>=1 && (b.back()==t1 || (b.back()+1)%3==t1)){
					len--;
					b.pop_back();
				}
				len++;
				b.push_back(t1);
			}
			else{ // len<=1
				break;
			}
		} 
		
		if(len<=1)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}
/*
1
6
2 0 2 1 0 1

*/ 

    • 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

    进阶题

    K题 Killer Sajin’s Matrix / 杀手萨金的矩阵

    题目大意
    在一个大小为 n ∗ m n * m n∗m 的二维网格中放置 k k k 个 1，使该网格的每一行和每一列的和均为奇数。

    考察内容
    构造

    分析
    k题1
    k题2
    p.s. 赛后数据有加强。

    #include
using namespace std;
int n,m,k,l,t,r,stx[100010],sty[100010],stc;
bool b;

int main(){ // 构造 
	scanf( "%d", &t );
	while ( t-- ){
		scanf( "%d%d%d", &n, &m, &k );
		r = max( n, m ); // 大的一边 
		l = min( n, m ); // 小的一边 
		long long sup = ( (long long) n) * m - ( (r & 1) ? 0 : r);
		if ( ( (n & 1) ^ (m & 1) ) || ( (r & 1) ^ (k & 1) ) || k < r || k > sup || ( (r & 1) && k == ( (long long) n) * m - 2ll) ){
			printf( "No\n" ); // 方案不存在 
			continue;
		}
		
		printf( "Yes\n" ); // 方案存在 
		if ( k == r + 2 ){
			for ( int i = 1; i <= l - 3; ++i )
				printf( "%d %d\n", i, i );
			printf( "%d %d\n%d %d\n%d %d\n%d %d\n%d %d\n", l, l - 1, l - 1, l, l - 1, l - 1, l - 2, l - 1, l - 1, l - 2 );
			for ( int i = l + 1; i <= r; ++i )
				printf( "%d %d\n", b ? n : i, b ? i : m );
			continue;
		}
		
		
		b = (n <= m);
		for ( int i = 1; i <= l; ++i )
			printf( "%d %d\n", i, i );
		for ( int i = l + 1; i <= r; ++i )
			printf( "%d %d\n", b ? n : i, b ? i : m );
		k	-= r;
		stc	= 0;
		for ( int i = l + 1; k && (k ^ 6) && i <= r; i += 2 )
			for ( int j = 1; k && (k ^ 6) && j < l - 1; j += 2 ){
				k		-= 4;
				stx[stc]	= b ? j : i;
				sty[stc++]	= b ? i : j;
			}
		for ( int i = 2; k && (k ^ 6) && i <= l; i += 2 )
			for ( int j = 1; k && (k ^ 6) && j < i; j += 2 )
				if ( (i - j) ^ j ){
					k		-= 4;
					stx[stc]	= j;
					sty[stc++]	= i - j;
				}
		for ( int i = ( (l - 2) & 131070); k && (k ^ 6) && i > 0; i -= 2 )
			for ( int j = (l & 131070) - i + 1; k && (k ^ 6) && j < l; j += 2 )
				if ( ( ( (l >> 1) << 2) - i - j) ^ j ){
					k		-= 4;
					stx[stc]	= j;
					sty[stc++]	= ( (l >> 1) << 2) - i - j;
				}
		if ( k == 6 ){
			printf( "%d %d\n%d %d\n%d %d\n%d %d\n%d %d\n%d %d\n", l, l - 1, l - 1, l, l, l - 2, l - 2, l, l - 1, l - 2, l - 2, l - 1 );
			k = 0;
		}
		if ( k % 6 == 2 ){
			--stc;
			k += 4;
		}
		else if ( k % 6 ){
			stc	-= 2;
			k	+= 8;
		}
		
		for ( int i = 0; i < stc; ++i ){
			printf( "%d %d\n%d %d\n%d %d\n%d %d\n", stx[i], sty[i], stx[i]+1, sty[i], stx[i], sty[i]+1, stx[i]+1, sty[i]+1 );
		}
		for ( int i = 1; k; i += 2 ){
			k -= 6;
			printf( "%d %d\n%d %d\n%d %d\n%d %d\n%d %d\n%d %d\n", i + 1, i, i, i + 1, i, l, l, i, i + 1, l, l, i + 1 );
		}
	}
	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
  • 相关阅读:
    Excel文件转换为HTML文件
    MySQL Explain性能调优详解
    Springboot----项目整合微信支付（用户取消订单）
    java项目-第161期ssm弹幕视频网站系统_ssm毕业设计_计算机毕业设计
    目标检测论文解读复现之十四：一种基于残差网络优化的航拍小目标检测算法
    物联网（IoT）：连接未来的万物之网
    20240309-1-校招前端面试常见问题-前端框架及常用工具
    IntStream用来提供对int类型数据进行相关的stream操作 && Map && mapToObj
    基于Java+SpringBoot+Thymeleaf+Mysql医院预约挂号系统设计与实现
    正确衡量研发人员绩效/生产力的几种方式
  • 原文地址：https://blog.csdn.net/weixin_51937688/article/details/126390772