Codeforces Round #376 (Div. 2) F. Video Cards 数论+数据结构+前缀和

My Solution

//这题虽然是F题，但属于Div.2 D题难道，所以归类于 Div.2 D(或 Div.1 B)了

数论+数据结构+前缀和

就是以前用树状数组的感觉，比如有一个数x，就在以x为下标的地方插入一个 1，如果删除这个就在下标为x的地方插入一个-1， 这样要查询小于等于k的数的个数只要get(k)就好。

这里不需要维护，所以只要用一个前缀和数组，就可以直接预处理出来。

即对于每个a[i]就在 sum[a[i]]++;

读入完以后预处理出前缀和，for i = 1 ~ maxa,  sum[i] += sum[i - 1];

然后扫一遍i = 1 ~ maxa，对于每个i在a[maxn]数组中出现过的i,(即 sum[i] - sum[i - 1] > 0)的地方，

for(j = 1; j <= maxa; j += i)                                                      //每次处理从 j 到 j + i - 1 的数，这些数都会作为 j 加到 s 里去

每次 求出 这个区间上的右端点 r = min(maxa, j + i - 1); //因为最后一次的右端点可能不是 j + i - 1;

然后 s += j * (sum[r] - sum[j - 1]);                                      //从 j 到 j + i - 1 的数的个数

处理完后，刷新 ans = max(ans, s);

复杂度 O(sigma(maxa / i))  //这里大概是 sigma(maxa / i == 2.5e6

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 8;

LL a[maxn], sum[maxn];

int main()
{
    #ifdef LOCAL
    int t = 0;
    for(int i  = 1; i < (int)2e5; i++){
        t += ((int)2e5) / i;
    }
    cout << "O(sigma(maxa / i)) == " << t << "n" << endl; freopen("f.txt", "r", stdin); //freopen("d.out", "w", stdout); int T = 4; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); LL n, ans = 0; cin >> n;
    for(int i = 0; i < n; i++){ cin >> a[i];
        sum[a[i]]++;
    }


    LL i, j, s, r, maxa = 2e5;
    for(i = 1; i <= maxa; i++) sum[i] += sum[i - 1];
    sort(a, a + n);
    for( i = 1; i <= maxa; i++){
        if(sum[i] - sum[i - 1]){
            s = 0;
            for(j = i; j <= maxa; j += i){ if(j > a[n - 1]) break;
                r = min(maxa, j + i - 1);
                s += j * (sum[r] - sum[j - 1]);
            }
            ans = max(ans, s);
        }
    }

    cout << ans << endl;

    #ifdef LOCAL
    memset(sum, 0, sizeof sum);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx