3338 蓝桥杯 wyz的数组IV 简单
3338 蓝桥杯 wyz的数组IV 简单
//C++风格解法1，通过率50%
#include<bits/stdc++.h>int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n; std::cin >> n;int ans = 0;std::vector<int>a(n);for(auto &x: a)std::cin >> x;for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){if(std::gcd(a[i], a[j]) == 2)ans = std::max(ans, i + j + 2); //gcd()// i + j + 2 的原因是：下标从0，但第几个从 1 开始，两个数 + 2// C++中，std::__gcd(x, y)(C98) 和 std::gcd(x,y)(C++17) 直接求 x,y 的最大公约数// n * n, n = 10^5, n * n = 10^(10),1s一般是 2 * 10^8}}std::cout << ans <<'\n';return 0;
}//C风格解法2，通过率100%
#include<bits/stdc++.h>const int N = 1e3 + 1;int mx[N]; // mx_i 表示的 i 这个数值的数在原数组的最大下标，桶int main(){int n; scanf("%d", &n); // 读入 nint ans = 0;for(int i = 1; i <= n; i++){ int x; scanf("%d", &x); // 输入 a_iif(x == 2){if(mx[2] != 0)ans = std::max(ans, mx[2] + i);}mx[x] = std::max(mx[x], i);}for(int i = 2; i <= 1000; i++){ // 枚举的是值，而不是下标，10^3for(int j = i + 1; j <= 1000; j++){ // 枚举的是值，而不是下标，10^3if(mx[i] == 0 || mx[j] == 0)continue; // 如果 i 或 j 没有出现，就 contineif(std::gcd(i,j) != 2)continue;ans = std::max(ans, mx[i] + mx[j]);}}printf("%d\n", ans);return 0;
}reference:
【C++】__gcd(x,y)函数_∑ y∈c gcd(x,y)-CSDN博客
最大公约数 —— Greatest Common Divisor(GCD) - 知乎 (zhihu.com)
[详解-vector] C++必知必会 vector常用各种操作解析 - 知乎 (zhihu.com)