题目描述：这里
思路：
一、部分分算法
- 对于
的数据，用暴力解决即可，时间复杂度
- 对于另外
的数据(所有木棍长度相等)，考虑用组合数学，答案为
二、正解
我们考虑对整个序列进行桶排序。
我们设每个数出现的次数为
。
- 对于所有≥
的数，加上比它小的所有数出现的次数，并加上这个数
至这个数
中所有数出现的个数。 - 特别的，对于所有≥
的数，需要再次加上。
但是，我们会发现这依然过不了(TLE了一个点)。
我们再次仔细观察正解的统计方式第一条，发现这可以用前缀和优化。
于是，这道题就做完了。
下面附上代码：
#include <bits/stdc++.h> using namespace std; template < typename T > void read(T &x) { int f = 1;x = 0;char c = getchar(); for (;!isdigit(c);c = getchar()) if (c == '-') f = -f; for (; isdigit(c);c = getchar()) x = x * 10 + c - '0'; x *= f; } const long long mod = 998244353; int a[200005]; long long bin[200005]; long long sum[200005]; int main() { //freopen(".in", "r", stdin); //freopen(".out", "w", stdout); int n, binmax = INT_MIN; long long ans = 0; read(n); for(int i = 1;i <= n;i++) { read(a[i]); bin[a[i]]++; binmax = max(binmax, a[i]); } int t = a[1]; int flag = 1; for(int i = 2;i <= n;i++) if(a[i] != t) { flag = 0; break; } if(flag) { long long ans = 1; for(int i = n;i > n - 3;i--) { ans *= i; } cout << (ans / 6) % mod << endl; return 0; } if(n <= 200) { for(int i = 1;i <= n;i++) for(int j = i + 1;j <= n;j++) for(int k = j + 1;k <= n;k++) if((a[i] == a[j] || a[i] == a[k] || a[j] == a[k]) && (a[i] + a[j] > a[k]) && a[i] + a[k] > a[j] && a[j] + a[k] > a[i]) ans++; cout << ans % mod << endl; return 0; } sum[0] = 0; for(int i = 1;i <= binmax;i++) sum[i] = bin[i] + sum[i - 1]; long long front = 0; for(int i = 1;i <= binmax;++i) if(bin[i]) { if(bin[i] >= 3) { long long ansj = 1; for(int j = bin[i];j > bin[i] - 3;--j) ansj *= j; ans += ansj / 6; ans %= mod; } if(bin[i] >= 2) { long long tx = bin[i] * (bin[i] - 1) / 2; ans += front * tx; ans %= mod; long long up = min(i * 2, binmax + 1) - 1; long long ty = sum[up] - sum[i]; ans += ty * tx; ans %= mod; } front += bin[i]; } cout << ans << endl; return 0; }
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
