网站建设湖南岚鸿建设,有自己做网站的soho吗,可以个人做单的猎头网站,seo企业培训班题目描述 给定三个整数数组 A [A1, A2, … AN], B [B1, B2, … BN], C [C1, C2, … CN]#xff0c; 请你统计有多少个三元组(i, j, k) 满足#xff1a;
1 i, j, k NAi Bj Ck 输入 第一行包含一个整数N。 第二行包含N个整数A1, A2, … AN。 第三行包含…题目描述 给定三个整数数组 A [A1, A2, … AN], B [B1, B2, … BN], C [C1, C2, … CN] 请你统计有多少个三元组(i, j, k) 满足
1 i, j, k NAi Bj Ck 输入 第一行包含一个整数N。 第二行包含N个整数A1, A2, … AN。 第三行包含N个整数B1, B2, … BN。 第四行包含N个整数C1, C2, … CN。 1 N 100000 0 Ai, Bi, Ci 100000 输出 一个整数表示答案 样例输入 3 1 1 1 2 2 2 3 3 3 样例输出 27
法一:
前缀和写法代码如下
#include iostream
#include cstring
using namespace std;
const int N 100010;
typedef long long LL;
int a[N], b[N], c[N], cnt[N], s[N], as[N], cs[N];int main() {int n;cin n;for (int i 0; i n; i)cin a[i], a[i];for (int i 0; i n; i)cin b[i], b[i];for (int i 0; i n; i)cin c[i], c[i];for (int i 0; i n; i)cnt[a[i]];for (int i 1; i N; i)s[i] s[i - 1] cnt[i];for (int i 0; i n; i)as[i] s[b[i] - 1];memset(s, 0, sizeof(s));memset(cnt, 0, sizeof(cnt));for (int i 0; i n; i)cnt[c[i]];for (int i 1; i N; i)s[i] s[i - 1] cnt[i];for (int i 0; i n; i)cs[i] s[N - 1] - s[b[i]];LL res 0;for (int i 0; i n; i) {res (LL)as[i] * cs[i];}cout res endl;return 0;}法二:
#include iostream
#include algorithm
using namespace std;
const int N 100010;
int a[N], b[N], c[N];int main() {int n;cin n;for (int i 0; i n; i)cin a[i];for (int i 0; i n; i)cin b[i];for (int i 0; i n; i)cin c[i];sort(a, a n);sort(b, b n);sort(c, c n);int p 0, q 0;long long res 0;for (int i 0; i n; i) {while (p n a[p] b[i])p;while (q n c[q] b[i])q;res p * (long long )(n - q);}cout res endl;return 0;
}
