首页题解

# 20240716

# 目录

[TOC]

# A. Matrix Rotation

# solution:

要使每一行每一列的第一个数小于第二个数字，我们先设矩阵从上到下从左到右四个数字分别为 a，b,c,d，那么满足如下条件：a < b，a < c，b < d，c < d。也就是说，第一个数字 a 是四个数字中最小的，最后一个数字 d 是四个数字中最大的，对于第二个和第三个数字不作其他要求。因此只需要第一个数字最小，第四个数字最大则为符合条件的矩阵。而这个矩阵可以进行顺时针的旋转，因此第二个数字最小，第三个数字最大也符合条件（顺时针旋转三次即可得到符合题目条件的矩阵），第四个数字最小，第一个数字最大也符合条件（顺时针旋转两次即可），第三个数字最小，第二个数字最大也符合条件（顺时针旋转一次即可）。

# std:

void solve(){
    cin>>a>>b>>c>>d;
    int mn=std::min({a,b,c,d}), mx=std::max({a,b,c,d});
    if(mn==a&&mx==d||mn==d&&mx==a){
        cout<<"YES\n";
    }
    else if(mn==c&&mx==b||mn==b&&mx==c){
        cout<<"YES\n";
    }
    else{
        cout<<"NO\n";
    }
}

# B. XOR = Average

# solution:

本题需要用到异或的性质：a ^ a = 0, a ^ 0 = a

我们对 n 的奇偶性分情况讨论：

  • 当 n 为奇数，我们只需构造一个个数都相同的序列。令这个数为 C，显然 a 的平均值为 C，而前 n-1 个数的异或和被两两抵消，所以最终整个 a 的异或和也为 C。
  • 当 n 为偶数，此时前面的方法不再适用，因为这偶数个相同数的异或和为 0，但 a 中的数一定大于 0，则平均值也一定大于 0，所以这种方法不满足条件。

我们可以从一些小数据入手，对于 n = 2，我们找到了一组解 a = {1,3}。此时 a 的平均值和异或和都为 2。

对于其他 n 为偶数的情况，就相当于在上述解的基础上增加偶数个数，因为异或和会将增加的数都消掉，所以这些数只要能使平均值不变即可，所以我们可以令这 n-2 个数都为 2，则此时 a 的异或和仍然为 2，平均值也依然为 2。

综上，我们得到了如下构造方法：

  • 当 n 为奇数时，输出 n 个 1。
  • 当 n 为偶数时，先输出 n-2 个 2，再输出特解 1,3。

# std:

void solve(){
	cin>>n;
	if(n&1){
		for(int i=1;i<=n;i++)	cout<<2<<' ';
	}
	else {
		for(int i=1;i<=n-2;i++)	cout<<2<<' ';
		cout<<1<<' '<<3;
	}
	cout<<'\n';
}

# C. Red Versus Blue

# solution:

  • 因为 b 严格小于 r，所以考虑将 r 分成 b+1 段。那么每一段的 R 数量就是 (r/(b + 1))。当然可能存在余数，只要把余数部分均分到前面每一段里即可。注意因为是余数，最大不会超过 b，最多最多就是前面每一段加一个。所以是可行的。

# std:

void solve(){
	cin>>n>>r>>b;
	int p=r/(b+1),q=r%(b+1);
	for(int i=0;i<q;i++)    cout<<string(p+1,'R')<<'B';
	for(int i=q;i<b;i++)    cout<<string(p,'R')<<'B';
	cout<<string(p,'R');
	cout<<'\n';
}

# D. Playing with GCD

# solution1:

  • 对于ai,ai+1a_i, a_{i+1}， 都有bib_i 的贡献，所以bib_i 必为ai,ai+1a_i, a_{i+1} 的公倍数，最后遍历bib_i 验证，此处bib_i 取ai,ai+1a_i, a_{i+1} 的最小公倍数即可

# std:

void solve(){
	cin>>n;
	std::vector<int> a(n+2),b(n+2);
	a[0]=1,a[n+1]=1;
	for(int i=1;i<=n;i++)	cin>>a[i];
	
	for(int i=1;i<=n+1;i++)
		b[i]=a[i]*a[i-1]/std::gcd(a[i],a[i-1]);
	
	for(int i=1;i<=n;i++)
		if(std::gcd(b[i],b[i+1])!=a[i]) return cout<<"No\n",void();
		
	cout<<"Yes\n";
}

# solution2:

  • 当 n 为 1,2 时，上述构造一定成立。
  • 当n≥2n \ge 2 时，数列aa 中存在ai,ai+2a_i, a_{i+2}，它们的最大公约数为pp，有gcd⁡(bi+1=lcm(ai,ai+1),bi+2=lcm(ai+1,ai+2))=lcm(ai+1,p)\gcd(b_{i+1}=lcm(a_i,a_{i+1}),b_{i+2}=lcm(a_{i+1},a_{i+2})) = lcm(a_{i+1},p)，易得仅当ai+1a_{i+1} 为 p 的倍数时可以使构造成立。

# std:

void solve(){
	cin>>n;
	std::vector<int> a(n+2);
	a[0]=1,a[n+1]=1;
	
	for(int i=1;i<=std::min(2,n);i++)	cin>>a[i];
	for(int i=3;i<=n;i++){
		cin>>a[i];
		if(a[i-1]%std::gcd(a[i-2],a[i])!=0)	return cout<<"No\n",void();
	}
	
	cout<<"Yes\n";
}

# E. Almost All Multiples

设k∗x≤n(1≤k≤c)k*x\le n(1\le k \le c)，（即 x 在 n 以内有 c 个倍数），p1p_1 占了一个，若pnp_n 最后不为 x 的倍数，那么剩余c−1c-1 个位置，总共却有 c 个位置，无解，因此当 $n \mod x \neq 0 $ 时无解

# solution1:

首先字典序最小一定是从 1~n 的排列，后来赋值an=1,a1=xa_n=1,a_1=x，那么其它位上已经满足字典序最小的条件，我们只需要与 x 的有关的位上进行调整。

从i→pii \rightarrow p_i 连边，由于pi=x,pn=1p_i=x,p_n=1，所以我们只需要链 x，满足x→a1→...→ai→...→nx \rightarrow a_1 \rightarrow ... \rightarrow a_i \rightarrow ... \rightarrow n，其中前一个数是后一个数的约数。

举例说明：

  • 当 n=8,x=2n = 8, x = 2 时： 首先我们构造的排列为：P[]=[2,8,3,4,5,6,7,1]P[] = [2, 8, 3, 4, 5, 6, 7, 1] 。此时可以发现，PxP_x 和 P4P_4 可以交换，因为 Pxmod  i=0P_x \mod i = 0 且 P4mod  x=0P_4 \mod x = 0。互换后为 P[]=[2,4,3,8,5,6,7,1]P[] = [2, 4, 3, 8, 5, 6, 7, 1]，满足字典序最小。

# std:

void solve() {
	int n, x;
	cin >> n >> x;
	if (n % x) {
		cout << "-1\n";
		return;
	}
	std::vector<int> ans(n + 1);
	for(int i=1;i<=n;i++)	ans[i]=i;
	ans[n] = 1;
	ans[1] = x;
	while (x < n)
		for (int i = x * 2; i <= n; i += x)// 满足 i% x==0
			if (n % i == 0) {
                ans[x] = i;
                x = i;
                break;
			}
	for (int i = 1; i <= n; ++i)
		cout << ans[i] << " \n"[i==n];
}