2020 CCPC Wannafly Winter Camp Day5 E

2020 CCPC Wannafly Winter Camp Day5 E
链接：https://ac.nowcoder.com/acm/contest/4120/E
来源：牛客网

示例1

输入

10
1 5 5 4 1 4 3 3 4 4
3 3 2 1

输出

20

先枚举后三个数字 a2 a3 a4，再比较 a1
1.设立cnt数组，cnt[Max][Max]，每次读入a[i]前记录第i个数字之前各个数字出现次数cnt[i[[j]=cnt[i-1][j]
随后读入a[i]，并记录cnt[i][a[i]]++
2.进行枚举判断 诸如(b[4]==b[3])^(a[i]==a[j])来进行判断，如果一个相等一个不相等则continue，进入下一个循环，都相等或都不等则继续执行
3.继续执行，直到calculate中判断

#pragma warning (disable :4996)
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int Max = 310;
int a[Max], b[10];
int cnt[Max][Max];
long long sum = 0;
int n;
void read() {
    scanf("%d", &n);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cnt[i][j] = cnt[i - 1][j];  //记录第i个数字之前各个数字出现次数
        }
        scanf("%d", &a[i]);
        cnt[i][a[i]]++;  //记录第i个数字 
    }
    for (int i = 1; i <= 4; i++)
        scanf("%d", &b[i]);
}
int calculate(int m, int a4, int a3, int a2) {
    int res;
    res = m; //m-->k位之前数的个数 k-1
    res -= cnt[m][a4]; 
    if (a3 != a4)  //防止有xi==xj&&yi==yj情况，重复减
        res -= cnt[m][a3];
    if (a2 != a3 && a2 != a4)
        res -= cnt[m][a2];
    return res;
}

void solve() {
    //枚举后三位数字
    for (int i = n; i >= 1; i--) {
        for (int j = i - 1; j >= 1; j--) {
            //如果b[4]==b[3]但a[i]!=a[j](a[4]!=a[3]) 或 b[4]!=b[3]但a[4]==a[3] 则该序列不成立，跳出进行下一次
            if ((b[4] == b[3]) ^ (a[i] == a[j]))
                continue;
            for (int k = j - 1; k >= 1; k--) {
                if ((b[3] == b[2]) ^ (a[j] == a[k]))
                    continue;
                if ((b[4] == b[2]) ^ (a[i] == a[k]))
                    continue;
                //判断b[1]有无与2 3 4相等的情况，倘若存在则进行sum += cnt[k - 1][a[k]]（cnt[k - 1][a[k]]是指第k位之前为a[k]的个数
                if (b[1] == b[2]) {
                    sum += cnt[k - 1][a[k]];
                    continue;
                }
                if (b[1] == b[3]) {
                    sum += cnt[k - 1][a[j]];
                    continue;
                }
                if (b[1] == b[4]) {
                    sum += cnt[k - 1][a[i]];
                    continue;
                }
                sum += calculate(k - 1, a[i], a[j], a[k]);

            }
        }
    }
}

int main()
{
    read();
    solve();
    cout << sum << endl;

}