题解 CF17201 A~D2

先约分，显然答案必然是 0 或 1 或 2

相等为 0，主要考虑 1 或 2 的情况。

假设 \(a>b\)，令 \(c = a/b\)，如果 \(c\) 为整数答案为 \(1\)，否则为 \(2\)。

特别的要特判 0。

//SIXIANG

#include <iostream>

#define MAXN 100000

#define int long long

#define QWQ cout << "QWQ" << endl;

using namespace std;

int gcd(int n, int m) {

	if(!m) return n;

	else return gcd(m, n % m);

}

bool judge(int a, int b, int c, int d) {

	if(a * d > b * c) return 1;

	else return 0;

}

signed main() {

	int T; cin >> T;

	while(T--) {

		int a, b, c, d;

		cin >> a >> b >> c >> d;

		int d1 = gcd(a, b), d2 = gcd(c, d);

		a /= d1, b /= d1, c /= d2, d /= d2;

		if(a == c && b == d) {

			cout << 0 << endl;

			continue;

		}

		if((a == 0 || c == 0) && (a != c)) {

			cout << 1 << endl;

			continue;

		}

		if(!judge(a, b, c, d)) swap(a, c), swap(b, d);

		if(a * d % (c * b) != 0) cout << 2 << endl;

		else cout << 1 << endl;

	}

}

通过大眼观察法，我们可以得到是最大值+次大值-最小值-次小值。

证明应该显然罢，懒得写了 QAQ

//SIXIANG

#include <iostream>

#include <algorithm>

#define MAXN 100000

#define QWQ cout << "QWQ" << endl;

using namespace std;

int a[MAXN + 10];

int main() {

	int T, n; cin >> T;

	while(T--) {

		cin >> n;

		for(int p = 1; p <= n; p++) cin >> a[p];

		sort(a + 1, a + n + 1);

		cout << a[n] + a[n - 1] - a[1] - a[2] << endl;

	}

}

我知道这是幼儿园小朋友的 nt 写法，但是我就是幼儿园小朋友~

一点一点来

除了第一次，我们每次肯定只会 ban 掉一个 1。

我们第一次枚举一下每个 L 里面最小的 1 数量，然后 1 数量减去这个加一即可。

//SIXIANG

#include <iostream>

#define MAXN 100000

#define QWQ cout << "QWQ" << endl;

using namespace std;

char ch[1145][1145];

int main() {

	int T, n, m; cin >> T;

	while(T--) {

		cin >> n >> m;

		int cnt = 0, minn = 0x7f7f7f7f;

		for(int p = 1; p <= n; p++) {

			for(int i = 1; i <= m; i++) {

				cin >> ch[p][i];

				if(ch[p][i] == '1') cnt++;

			}

		}

		for(int p = 1; p <= n; p++) {

			for(int i = 1; i <= m; i++) {

				int a = (ch[p][i + 1] == '1'), b = (ch[p + 1][i] == '1');

				int c = (ch[p - 1][i] == '1'), d = (ch[p][i - 1] == '1');

				int e = (ch[p][i] == '1');

				if(p > 1 && i > 1 && e + c + d) minn = min(minn, e + c + d);

				if(p > 1 && i < m && e + c + a) minn = min(minn, e + c + a);

				if(p < n && i > 1 && e + b + d) minn = min(minn, e + b + d);

				if(p < n && i < m && e + b + a) minn = min(minn, e + b + a);

			}

		}

		if(!cnt) cout << cnt << endl;

		else cout << cnt - minn + 1 << endl;

	}

}

\(f_i\) 为以 \(i\) 结尾的最长 \(b\)。

则显然有 \(f_i = \max\{f_j\} + 1(a_j \operatorname{xor} i < a_i \operatorname{xor} j, j < i)\)。

下面看了题解，因为真的没有见过这个东西的处理 QAQ

首先有 \(\begin{cases}i - a_j\le a_j \operatorname{xor} i\\ a_i\operatorname{xor} j \le a_i + j\end{cases}\)

故 \(i - a_j \le a_i + j\)，故 \(i - j\le a_i + a_j\)，即 \(i - j\le 400\)

这个是真的厉害，之前没有见过这样的操作 QAQ

//SIXIANG

#include <iostream>

#include <cstring>

#define MAXN 300000

#define QWQ cout << "QWQ" << endl;

using namespace std;

int a[MAXN + 10], f[MAXN + 10];

int main() {

	int T;

	cin >> T;

	while(T--) {

		int n, maxn = 0; cin >> n;

		for(int p = 1; p <= n; p++) f[p] = 1;

		for(int p = 1; p <= n; p++) cin >> a[p];

		for(int p = 1; p <= n; p++) {

			for(int j = max(p - 400, 1); j < p; j++) {

				if((a[j] ^ (p - 1)) < (a[p] ^ (j - 1)))

					f[p] = max(f[p], f[j] + 1);

			}

			maxn = max(maxn, f[p]);

		}

		cout << maxn << endl;

	}

}

01trie，懒得打，待填坑

巴特西

题解 CF17201 A~D2

最新文章

热门文章