X6C.もしも 题解

思路

按照人类智慧，在 $a_1 = 1$ 时，序列为 $1, \, a_2 , \, 1 , \, a_2, \, 1 …$ ；在 $a_2 = 1$ 时，序列为 $a_1, \,1, \, a_1 , \, 1 , \, a_1 …$。

所以要想得到 $a_n$，$a_1$ 或 $a_2$ 为 $a_n$。

显然：

• 当 $n$ 为奇数时，$a_1 = a_n, \, a_2 = 1$；
• 当 $n$ 为偶数时，$a_1 = 1, \, a_2 = a_n$。

然后，就没有然后了。

时间复杂度 $O(T)$。

Code

#include <bits/stdc++.h>
using namespace std;

int T;

int main() {
	cin >> T;
	for (int a, b ; T-- ; ) {
		cin >> a >> b;
		if (a & 1) 
		printf("%d %d\n", b, 1);
		else printf("1 %d\n",  b);
	}
	return 0;
}

分享一下我是怎么发现这个构造的，观察数据范围，$1\le a_n \le10^9$，但是题目又要求对于任意 $1\leq i\leq n$，满足 $1\leq a_i\leq 10^9$。所以要使 $a_{n-1} = 1$，$a_{n-2}=a_n$，我们继续向前构造数的话就可以发现交替的 $\dots a_n,1,a_n,1,a_n,1\dots$ 可以满足题目的要求。

#include<bits/stdc++.h>
using namespace std;

int main(){
	int t;
	cin>>t;
	while(t--){
		int a,b;
		cin>>a>>b;
		if(a&1){
			cout<<b<<' '<<"1\n";
		}else{
			cout<<1<<' '<<b<<'\n';
		}
	}
	return 0;
}