缩小数据范围——nc2.4多校_A.新春游戏之数学系列

• 问题概述
• 思路分析
• 参考代码
• 做题反思

问题概述

原题参考A.新春游戏之数学系列
大致就是给出一个数组，要求求出一个公式的值，有几个数据范围值得注意一下，一是数组的长度为[0, 1e6]，二是数组元素的和不超过5e7

思路分析

赛时第一眼准备去分析公式看看有没有可以优化的，用前缀拆分优化一下，但是没找到，因此就暂时搁置，毕竟这个n的大小肯定是不能O(n²)的，之后的优化又走错方向了，想着把求二进制数的1的个数优化一下，用map记录，但是没有用，这样还是跑不掉n²的时间；
事实上，该题的重点在于上面标记的位置数组元素的和不超过5e7，根据这个我们可以求出数组中不同元素的个数事实上是小于1e4的，这样的话我们就可以通过map记录，遍历map得到答案
至于1e4是怎么得到的，1+2+...+k <= 5e7，k<1e4的这样就可以通过一个O(k²)解决该问题

参考代码

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 998244353;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 1e6+7;
map<int, int> _cnt;
int n, a[N];
ll ans = 0;
int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}
int lowbit(int x) {return x&-x;}
int cnt(int x) {
    int res = 0;
    while(x) {
        res ++;
        x -= lowbit(x);
    }
    return res;
}
void solve() {
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        _cnt[a[i]] ++;
    }
    for(auto x:_cnt) {
        for(auto y:_cnt) {
            ans += (_cnt[x.first] * _cnt[y.first] % mod) * gcd(x.first, y.first) %mod * (cnt(x.first) + cnt(y.first));
            ans %= mod;
        }
    }
    cout << ans << endl;
}
int main() {
#ifdef xrl
    freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
    FAST_IO;
    int t = 1;
    //cin >> t;
    while(t --) solve();
#ifdef xrl
    cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
    return 0;
}

做题反思

这个题没做出来其实还是做得少了，没有经验，就像是之前的拆分也是，事实上，我甚至没有注意到那个元素和小于5e7的条件，别说利用这个条件去缩小数据范围了