Loading... # 题目描述 小红来到了红魔馆。众所周知，红魔馆的馆主是一只495岁的吸血鬼，所以她非常喜欢495这个数。 现在小红拿到了一个数组，她认为该数组的“美丽度”为：选两个元素$a_i$和$a_j(i<j)$，乘积为495的倍数的方案数。 小红可以进行最多1次操作：选择一个元素，使其加1。请你帮小红求出最多1次操作后，数组的最大美丽度。 # 输入 第一行输入一个正整数$n$，代表每个人数组的大小。 第二行输入$n$个正整数$a_i$，代表数组的元素。 $1\leq n,a_i \leq 400000$ # 输出 一个整数，代表最多一次操作后，数组的最大美丽度。 # 解题思路 这道题主要是对代码量进行了考察 看到**乘积为495的倍数**， 首先考虑对495进行质因数分解： $$ 495 = 3 * 3 * 5 * 11 $$ 因此， 对于任意的$i < j, a_i * a_j$只需要保证$a_i$和$a_j$各自的质因数加在一起满足有两个3， 一个5, 一个11即可 不妨考虑利用二进制状态压缩来存储全部的状态：采用四位二进制数， 从低到高分别表示 |第3位 |第2位 |第1位 |第0位 | |-------|------|------|------| |11的倍数|5的倍数|9的倍数|3的倍数| 考虑满足题目条件的$a_i$和$a_j$: - 如果$a_i | a_j == 1111_2$, 则$a_i * a_j$一定是495的倍数 - 如果$a_i | a_j == 1101_2$， 且有$a_i \& 1 == 1 \wedge a_j \& 1 == 1$, 则也可以推出$a_i * a_j$是495的倍数 注意到题目中的判断条件要求$i < j$，因此可以考虑用前缀数组$pre[i][j]$来表示前$i$个元素中有多少个状态为$j$的元素 考虑到最多进行一次$+1$操作， 因此可以先找出不进行$+1$操作时的方案数， 然后分别枚举每一个数字， 查找进行$+1$操作时候方案的最大值 如果对$val[i]$元素进行$+1$操作， 他所影响到的方案数既包括$j < i \wedge a[j] * a[i] \% 495 == 0$， 又包括$i < k \wedge a[j] * a[k] \% 495 == 0$ 因此还需要维护一个后缀数组$suf[i][j]$， 代表从$i$到$n$一共有多少的状态为$j$的元素 # AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #define endl '\n' using namespace std; typedef long long LL; const int N = 4e5 + 10; vector<vector<int>>pre(N, vector<int>(20)), suf(N, vector<int>(20)); vector<int> a(N), val(N); int n; int mapping(int x) { int ans = 0; if(x % 3 == 0) ans |= 1; if(x % 9 == 0) ans |= 2; if(x % 5 == 0) ans |= 4; if(x % 11 == 0) ans |= 8; return ans; } bool check(int x, int y) { if((x | y) == 15 || ((x | y) == 13 && x & 1 && y & 1)) return true; return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; LL ans = 0; for(int i = 1; i <= n; i ++) { int x; cin >> x; val[i] = x; a[i] = mapping(x); for(int j = 0; j < 20; j ++) if(check(a[i], j)) ans += pre[i - 1][j]; pre[i] = pre[i - 1]; pre[i][a[i]] ++; } for(int i = n; i >= 1; i --) { suf[i] = suf[i + 1]; suf[i][a[i]] ++; } int mx = 0; for(int i = 1; i <= n; i ++) { int x = val[i]; x ++ ; int tmp = mapping(x); int res = 0; for(int j = 0; j < 20; j ++) if(check(tmp, j)) res += pre[i - 1][j] + suf[i + 1][j]; for(int j = 0; j < 20; j ++) if(check(a[i], j)) res = res - pre[i - 1][j] - suf[i + 1][j]; mx = max(mx, res); } cout << ans + mx << endl; return 0; } ``` 最后修改：2025 年 01 月 11 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏