怎样把网站做的漂亮,克隆网站怎么导入wordpress,青岛高品质网站建设,多语言网站建设方案题干#xff1a;
给定一个长度为N的数组A[A1, A2, ... AN]#xff0c;已知其中每个元素Ai的值都只可能是1, 2或者3。
请求出有多少下标三元组(i, j, k)满足1 ≤ i j k ≤ N且Ai Aj Ak。
Input
第一行包含一个整数N
第二行包含N个整数A1, A2, ... …题干
给定一个长度为N的数组A[A1, A2, ... AN]已知其中每个元素Ai的值都只可能是1, 2或者3。
请求出有多少下标三元组(i, j, k)满足1 ≤ i j k ≤ N且Ai Aj Ak。
Input
第一行包含一个整数N
第二行包含N个整数A1, A2, ... AN。(1 ≤ Ai ≤ 3)
对于30%的数据1 ≤ N ≤ 100
对于80%的数据1 ≤ N ≤ 1000
对于100%的数据1 ≤ N ≤ 100000
Output
一个整数表示答案
Sample Input
6
1 3 2 1 2 3
Sample Output
3
解题报告 解题的关键在于找到关键元素“2”我们每找到一个2就看看他前面有多少个1后面有多少个3乘起来维护一个sum就好了。
AC代码
#includebits/stdc.h
#define ll long long
using namespace std;ll cnt1,cnt3,sum3;
int a[100000 5];
int main()
{int n;ll sum 0;cinn;for(int i 1; in; i) {scanf(%d,a[i]);if(a[i] 3) sum3;}for(int i 1; in; i) {if(a[i] 1) cnt1;else if(a[i] 3) cnt3;else {sum cnt1*(sum3-cnt3);}}printf(%lld\n,sum);return 0 ;
}
总结 注意这题别忘用longlong
