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()}}std::cout << ans <<'\n';return 0;
}

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

//C风格解法2，通过率100%
#include<bits/stdc++.h>const int N = 1e3 + 1;int mx[N]; // mx_i 表示的 i 这个数值的数在原数组的最大下标，桶// 7
// 2 2 2 2 6 6
//           存最大的位置// gcd 是最大公约数
// 6
// 6 6 8 8 2 2
//a[2] = 6，a[4(下标)] = 8(值)
//mx[6(值)] = 2(下标)，mx[8] = 4int 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] = 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]);}}// 10^6，计算机 1s 跑 2 * 10^8printf("%d\n", ans);return 0;
}

// n = 5
// 2 3 4 5 6
// mx[2] = mx[3] = mx[4] = mx[5] = mx[6] = 0
// x = 2(值)，mx[2(值)] = 1(下标)
// x = 3，mx[3] = 2
// x = 4，mx[4] = 3
// x = 5，mx[5] = 4
// x = 6，mx[6] = 5
// 输出 3 + 5 = 8，(第几个，下标)

0wzy的数组IV - 蓝桥云课 (lanqiao.cn)

reference:

【C++】__gcd(x,y)函数_∑ y∈c gcd(x,y)-CSDN博客

最大公约数 —— Greatest Common Divisor(GCD) - 知乎 (zhihu.com)​​​​​​[详解-vector] C++必知必会 vector常用各种操作解析 - 知乎 (zhihu.com)