题意:给你两个排列A和B,统计A,B有多少个子集是相等,序列要求连续的,长度要大于1。
思路:记录一下B序列的各个整数的位置,然后在从A开始统计,因为他是集合关系的相等,所以要求长度相同,元素相同,接着枚举长度的同时,又因为我们要求的序列是连续的,所以我们找出位置的最大和最小的位置,然后他们的长度如果和我们枚举的长度相等的话,那么这个显然就是正确的了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 4000; int a[MAXN],b[MAXN],c[MAXN]; int n; int main(){ while (scanf("%d",&n) != EOF && n){ for (int i = 0; i < n; i++) scanf("%d",&a[i]); for (int i = 0; i < n; i++){ scanf("%d",&b[i]); c[b[i]] = i; } int ans = 0; for (int i = 0; i < n; i++){ int Max = c[a[i]],Min = c[a[i]]; int num = 1; for (int j = i+1; j < n; j++){ if (c[a[j]] < Min) Min = c[a[j]]; if (c[a[j]] > Max) Max = c[a[j]]; num++; if (Max-Min+1 == num) ans++; } } printf("%d\n",ans); } return 0; }