不开long long见祖宗（论数据怎么能这么水）

赛时想不出来正解，写了一个玄学复杂度的做法，最坏复杂度是

O\left( {{n^3}} \right)

的，然后第6、7、11～15个点用前缀和或者直接计算区间长度能优化到最坏

O\left( {{n^2}} \right)

。而1～7&11～15的点显然是不可能爆int的，于是我就手贱没开long long，，，，期望得分其实只有20pts（前5个点，因为后面1e6的数据玄学复杂度根本没想到能过）

结果出分48pts，发现1～7 和 11～15 AC，一边窃喜数据水一边看别的点，仔细一看是WA不是TLE？结果一看答案爆int了，int改long long直接AC，数据也太水了吧。。。另外不要根据期望得分决定要不要long long，直接define int long long从来就没出过锅。

附代码，正解不可能就这么写吧

CPP

#include <bits/stdc++.h>
using namespace std;


int n;
long long ans = INT_MAX;
int a[1000005], sum[1000005];
int fo[1000005], lo[1000005];
int co[1000005], v[1000005], f[1000005];
int flv = 1, flf = 1;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &co[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &f[i]);
    for (int i = 1; i <= n; i++) if (v[i] != 1) flv = 0;
    for (int i = 1; i <= n; i++) if (f[i] != 1) flf = 0;
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + v[i];
    for (int i = 1; i <= n; i++) if (!fo[co[i]]) fo[co[i]] = i;
    for (int i = n; i >= 1; i--) if (!lo[co[i]]) lo[co[i]] = i;
    for (int i = 1; i <= n; i++) {
        int maxm = lo[co[i]];
        if (fo[co[i]] != i) continue;
        for (int j = i; j <= n; j++) {
            if (fo[co[j]] < i) break;
            maxm = max(maxm, lo[co[j]]);
            if (j >= maxm) {
                if (flv) ans = (ans < j - i + 1 ? ans : j - i + 1);
                if (flf) ans = (ans < sum[j] - sum[i - 1] ? ans : sum[j] - sum[i - 1]);
                else {
                    long long cnt = 0;
                    for (int k = i; k <= j; k++) {
                        cnt += (long long)f[k - i + 1] * (long long)v[k];
                    }
                    ans = (ans < cnt ? ans : cnt);
                }
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

不开long long见祖宗（论数据怎么能这么水）

讨论操作

回复

相关推荐

不开long long见祖宗（论数据怎么能这么水）