Pinely Round 3 (Div. 1 + Div. 2)

标签：int Pinely ll 2x cin ans Div Round

A

构造题，分两种情况考虑

• 上下都行，左右选一个
• 左右都行，上下选一个

void solve() {
	int n;
	cin >> n;
	vector<pair<int, int> > a(n);
	for(auto &t : a) cin >> t.x >> t.y;
	sort(a.begin(), a.end());
	bool okx = a[0].x * a.back().x >= 0;
	for(auto &t : a) swap(t.x, t.y);
	sort(a.begin(), a.end());
	bool oky = a[0].x * a.back().x >= 0;
	cout << (okx | oky ? "YES\n" : "NO\n");
}

B

也是构造，这里介绍两种方法

法一 ： 二进制拆分

考虑只去模 \(2^k\)
把每个数二进制拆分，模 \(2^k\) 的结果即为这个数的 $[0, k - 1] $位
一直往上枚举 \(k\)，直到所有数的 $[0, k - 2] $位相同，第 \(k - 1\) 位不同

void solve() {
	int n;
	cin>> n;
	vector<ll> a(n);
	for(ll &x : a) cin >> x;
	auto check = [&](ll p) -> bool {
		set<ll> se;
		for(int i = 0; i < n; ++ i) se.insert(a[i] % p); 
		return se.size() == 2;
	};
	for(int i = 1; ; ++ i) {
		if(check(1ll << i)) {
			cout << (1ll << i) <<'\n';
			return;
		}
	}
}

法二 ： 数学

令

\[x = gcd\{a[1] - a[0], a[2] - a[1], a[3]- a[2], ... , a[n - 1] - a[n - 2]\} \]

此时

\[ans = 2x \]

考虑去如何证明
不难得到

\[\forall i \in [1, n),\hspace{0.3cm} x \mid a[i] - a[i - 1] \]

换句话说，此时所有数模\(x\)结果相同
不妨设

\[a[i] = p_ix + q \]

• 若\(p_i\)为偶数，则\(a[i] \bmod 2x = q\)
• 若\(p_i\)为奇数，则\(a[i] \bmod 2x = x + q\)

由于\(q < x\), 所以\(x + q < 2x\)
又\(x \neq 0\), 所以 \(q \neq x + q\)

1. p中既有奇数又有偶数，显然成立
2. p全为奇数或全为偶数，则此时\(gcd\{a[i] - a[i - 1]\}\)一定为\(2x\)的倍数， 与最大为\(x\)矛盾

void solve() {
	int n;
	cin >> n;
	ll ans = 0;
	vector<ll> a(n);
	for(int i = 0; i < n; ++ i) {
		cin >> a[i];
		if(i) ans = gcd(ans, abs(a[i] - a[i - 1]));
	}
	cout << ans * 2 << '\n';
}

标签：int,Pinely,ll,2x,cin,ans,Div,Round
From： https://www.cnblogs.com/Lu-xZ/p/17924255.html