#include <bits/stdc++.h> using namespace std; int n, k, p, t, ans = 0, price, num[110], color[200100]; int main() { cin >> n >> k >> p; for (int i = 1; i <= n; i++) { cin >> color[i] >> price; if (price <= p) { for (int j = i; j > t; j--) num[color[j]]++; t = i; ans += num[color[i]] - 1; } else ans += num[color[i]]; } cout << ans; return 0; }

如果是暴力枚举客栈的话，不能同时枚举两个客栈，那样会超时，所以只能同时枚举一个。我们枚举第二个客栈，然后用第二个客栈反推出前面的方案数。 思路就是，从 111 到 nnn 枚举，输入 colorcolorcolor 和 pricepriceprice 的值，我们需要记录一个距离第二个客栈最近的咖啡厅价钱合理的客栈位置，用一个 nownownow 变量记录。 开三个辅助数组， lastlastlast [ iii ]表示最后一个以 iii 为颜色的客栈的位置， cntcntcnt [ iii ]表示以 iii 为颜色的客栈总数， sumsumsum [ iii ]可以看作是一个临时数组，用来存储当前的方案数。 可以这么想，当前枚举到一个客栈 iii ，这个 iii 是第二个客栈，那么显然第一个客栈一定在第二个客栈之前，编号必定是 000 ~ i−1i-1i−1 之间的一个数。如果我发现枚举的时候在某一个客栈前面有一个价钱合理的咖啡厅，那么在这之前的任何一个同色客栈都是第一个客 栈可以选的，那么统计一下数量，这就是当前的方案数。 然后更新 lastlastlast 数组，更新 ansansans ，让 cntcntcnt [ colorcolorcolor ] ++++++ ，这样从左到右地推过来就好了。 这个解法简化于暴力算法，暴力算法要循环三层，一层 111 客栈，二层 222 客栈， 333 层合理的位置，这样做显然不行，而我们做的 就是去优化掉两层，而是从枚举 222 客栈出发推出 111 客栈的位置和所有可行方案，所以这样做是正确的。最后输出即可。

#include <bits/stdc++.h> using namespace std; int n, k, p, t, ans = 0, price, num[110], color[200100]; int main() { cin >> n >> k >> p; for (int i = 1; i <= n; i++) { cin >> color[i] >> price; if (price <= p) { for (int j = i; j > t; j--) num[color[j]]++; t = i; ans += num[color[i]] - 1; } else ans += num[color[i]]; } cout << ans; return 0; }