牛客小白月赛57题解

A.最大面积

签到题，题目中已经定义了什么是矩形的长，什么是矩形的宽。 因此输出 $\min (a,c)\times \min (b,d)\backslash min(a,c)\; \backslash times\; \backslash min(b,\; d)$ 即可。

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << min(a, c) * min(b, d) << endl;
	return 0;
}

B.种树

如果所有地都已经种上了树，那直接输出 $00$。

考虑答案为 $11$ 的情况，第 $11$ 块地上有树，那可以直接走到第 $nn$ 块地。或者是第 $nn$ 块地有树，直接走到第 $11$ 块地。

剩下的所有情况都可以在第 $22$ 天种满，比如我选择第 $ii$ 块有树的地，在第一天从 $ii$ 走到 $11$， 第二天从 $11$ 走到 $nn$。

#include <bits/stdc++.h>

using namespace std;

int main(){
	int n;
	cin >> n;
	string s;
	cin >> s;
	if (s.find('0') == s.npos) cout << 0;
	else if (s[0] == '1' || s[n - 1] == '1') cout << 1;
	else cout << 2 << endl;
	return 0;
}

C.奇怪的电梯

如果 $n\le kn\; \backslash leq\; k$，除 $a=ba\; =\; b$ 外，那无论怎样都到不了。

从 $aa$ 到 $bb$ 有三种情况，第一种，$a=ba\; =b$，不用坐电梯；第二种，按一次按钮后 $aa$ 可以直接去 $bb$；第三种，按多次按钮，需要楼层进行中转，那我们可以选中转楼层为 $11$ 或 $nn$，不妨令 ，注意到 $11$ 一定可以到 $nn$， 因此我们不妨按照 $a\to 1\to n\to ba\; \backslash rightarrow\; 1\; \backslash rightarrow\; n\; \backslash rightarrow\; b$ 的顺序。再考虑 $a>ba\; >\; b$，可以按照 $b\to n\to 1\to ab\; \backslash rightarrow\; n\; \backslash rightarrow\; 1\; \backslash rightarrow\; a$。因此对于第三种可以总结为 $aa$ 和 $bb$ 可以分别到 $11$ 或 $nn$。

#include <bits/stdc++.h>
#define ll long long

using namespace std;

inline void solve(){
	ll n, k, a, b;
	cin >> n >> k >> a >> b;
	if (a == b){
		cout << "YES\n";
		return;
	}
	if (abs(a - b) > k) cout << "YES\n";
	else if (n <= k) cout << "NO\n";
	else if ((abs(a - 1) > k || abs(a - n) > k) && (abs(b - 1) > k || abs(b - n) > k)) cout << "YES\n";
	else cout << "NO\n";	
}

int main(){
	int test;
	cin >> test;
	while(test--) solve();
	return 0;
}

D.最大 $\gcd \backslash gcd$

枚举 $gcdgcd$，再枚举当前 $gcdgcd$ 的倍数，如果所有倍数在 $aa$ 中出现的次数大于等于 $22$，那么这就是一个合法的公约数，对所有合法的公因数取 $\max \backslash max$。

时间复杂度 $o(n\log n)o(n\backslash log\; n)$

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 10;

int n;
int m[maxn];

int main(){
	cin >> n;
	int maxx = 0, tmp;
	for (int i = 1; i<= n; i++){
		scanf("%d", &tmp);
		m[tmp]++;
		maxx = max(maxx, tmp);
	} 
	int ans = 1, cnt = 0;
	for (int i = 2; i <= maxx; i++){
		cnt = 0;
		for (int j = i; j <= maxx; j += i){
			cnt += m[j];
		}
		if (cnt >= 2) ans = max(ans, i);
	}
	cout << ans;
	return 0;
}

E.一道难题

解法一：题目给的是十进制的数，但是观察题目的要求的，发现满足条件的十进数与具有相同位数的二进制数一一对应。于是先求不超过 $nn$ 的最大的仅包含 $11$ 或 $00$ 的数，然后把这个数当成一个二进制数看，再转换为一个十进制数，接着暴力枚举，依次判断哪个数满足条件。比如 $n=2001n\; =\; 2001$，那我实际上只需要算 $n=1111n\; =\; 1111$，把这个 $11111111$ 当成一个二进制来看，仅需要去枚举 $1-151-15$，每个数再暴力判断是否符合条件。

解法二： $\text{dfs}\backslash text\{dfs\}$ + 优化。比如在搜索的时候记录当前连续 $11$ 的个数，或者用字符串存储数字。

解法三：状态压缩+剪枝。每一位 $00$ 或 $11$，方案数最多 $2^{23}2^\{23\}$ 种，枚举每一种方案，看看是否大于 $nn$，同时要特判字符串长度等于 $2424$ 的情况，在该情况下实际上的 $n=11111111111111111111111n\; =\; 11111111111111111111111$ ，($2323$ 个 $11$)。

下面给出解法 $11$ 的代码。

#include <bits/stdc++.h>

using namespace std;

bool check (int n){
	int len = 0;
	int tmp;
	while(n){
		tmp = (n & 1);
		n >>= 1;
		if (tmp) len ++;
		else len = 0;
		if (len == 3) return true; 
	}
	return false;
}

int main(){
	string s;
	cin >> s;
	ll n = 0;
	bool flag = false;
	for (int i = 0; i < s.length(); i++){
		if (flag){
			n += (1ll << (s.length() - i - 1));
			continue;
		}
		if (s[i] > '1') flag = true, n += (1ll << (s.length() - i - 1));
		if (s[i] == '1') n += (1ll << (s.length() - i - 1));
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++){
		if (check(i)) ans++;	
	}
	cout << ans;
    return 0;
}

F.序列操作

因为 $x+px\; +\; p$ 和 $xx$ 在模 $pp$ 下意义相同，不难发现 $xx$ 一定位于 $[0,p-1][0,\; p\; -\; 1]$ 内。特判 $x=0x\; =\; 0$，枚举 $x(1\le x\le p-1)x(1\backslash leq\; x\; \backslash leq\; p\; -\; 1)$，通过解同余方程求出每个 $xx$ 下 $A\to BA\backslash rightarrow\; B$ 的操作次数，对每个 $a_{i}a\_i$ 来说，解

因为 $pp$ 是质数，因此次数

对于每个 $xx$，解 $nn$ 个同余方程后得到一个次数数组，因为题目要求是对一个子序列操作，所以次数数组里的最大值即为这个 $xx$ 对应的操作次数。

最小次数所对应的最小的 $xx$ 即为答案。

时间复杂度 $O(n(\log p+p))O(n(\backslash log\; p\; +\; p))$ 。但这个复杂度显然会超时，我们需要进一步优化。

注意到 $(b_i-a_i)\mathrm{\%}p(b\_i\; -\; a\_i)\backslash \%\; p$ 的结果最多只有 $pp$ 个，若 $(b_t-a_t)\mathrm{\%}p=(b_k-a_k)\mathrm{\%}p(b\_t\; -\; a\_t)\backslash \%\; p\; =\; (b\_k\; -\; a\_k)\backslash \%\; p$，那么解对应的同余方程所得到的结果是一样的，所以我们可以把这两个位置上的数当成一个来看，因此最多只需要解 $pp$ 个同余方程，时间复杂度进一步优化成 $O(p(\log p+p))O(p(\backslash log\; p\; +\; p))$。

#include <bits/stdc++.h>
#define pb(x) push_back(x)

using namespace std;

const int maxn = 1e5 + 10;

int qpow(int a, int b, int p){
    int ans = 1;
    while(b){
        if (b & 1) ans = (ans * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return ans % p;
}


int main(){
    int n, p;
	scanf("%d%d", &n, &p);
    vector <int> a(n), b(n);
    for (auto &i : a) scanf("%d", &i);
    for (auto &i : b) scanf("%d", &i);
    for (auto &i : a) i %= p;
    if (a == b){
       	printf("0");
        return 0;
    }
    vector <int> c(p);
    for (int i = 0; i < n; i++) c[(b[i] - a[i] + p) % p] = 1;
    int ans , minn = 1e9;
    for (int x = 1; x < p; x++){
        int tmp = qpow(x, p - 2, p);
        int times = -1;
        for (int i = 0; i < p; i++) if (c[i]) {
            times = max(times, tmp * i % p);
        }
        if (times < minn){
            minn = times;
            ans = x;
        }
    }
    printf("%d", ans);
    return 0;
}