题解：P15018 [UOI 2020 II Stage] 日历

· · 题解

先读原题在食用喔。

我一开始的想法（暴力枚举 TLE）

我第一反应：直接枚举 x,y,z 然后检查 6 个条件。复杂度 O(n^3)，n\le 5000 肯定炸。

优化

把 6 个条件写出来：

日.月.年：x\le a_y

日.年.月：x\le a_z

月.日.年：y\le a_x

月.年.日：z\le a_x

年.月.日：z\le a_y

年.日.月：y\le a_z

按 x,y,z 整理一下：

直接固定两个数，快速算第三个数。

试一下固定 x 和 y：

从 x 的条件：x\le a_z → a_z\ge x。

从 y 的条件：y\le a_z → a_z\ge y。

从 z 的条件：z\le a_x 且 z\le a_y → z\le \min(a_x,a_y)。

另外 x 和 y 自己也要满足：x\le a_y 且 y\le a_x。

怎么快速统计 z 的个数？

可以想到预处理 。 定义 cnt[t][i] = 有多少个 z\le i 满足 a[z]\ge t。

code

#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
    cin>>n;
    vector<int> a(n + 1);
    for (int i=1; i<=n; i++)  cin>>a[i];
    vector<vector<int>> pref(n+2,vector<int>(n+1,0));
    for (int t=1; t<=n; t++){
        for(int i=1; i<=n; i++)  pref[t][i] = pref[t][i-1]+(a[i]>=t?1:0);
    }
    long long ans=0;
    for (int X=1; X<=n; X++) {
        for (int Y=1; Y<=n; Y++) {
            if X>a[Y]||Y>a[X]) continue;
            int low=max(X,Y);
            int up=min(a[X],a[Y]);
            if(up>=1)  ans+=pref[low][up];
        }
    }
    cout<<ans<<endl;
    return 0;
}

坑点

  1. 开 long long：答案可能很大，要用 long long。
  2. 数组大小：n \le 5000，数组要开 5005。

萌新第一篇题解 求过QAQ。