题目大意
小Y是一个爱好旅行的OIer。一天，她来到了一个新的城市。由于不熟悉那里的交通系统，她选择了坐地铁。
她发现每条地铁线路可以看成平面上的一条曲线，不同线路的交点处一定会设有换乘站
。通过调查得知，没有线路是环线，也没有线路与自身相交。任意两条不同的线路只会在若干个点上相交，没有重合的部分，且没有三线共点的情况。即，如图所示的情况都是不存在的：
小Y坐着地铁$0$号线，路上依次经过了$n$个换乘站。她记下了每个换乘站可以换乘的线路编号，发现每条线路与她所乘坐的线路最多只有$2$个换乘站。现在小Y想知道，除掉她经过的换乘站以外，这个城市里最少有几个换乘站。只有你告诉她正确的答案，她才会答应下次带你去玩呢。
题目分析
只需要考虑所有的二元组即可，单独出现的显然对答案无贡献。
对所有二元组按照左端点排序，考虑用右端点限制条件。
考虑到连边方式只有$4$种，其他方式全部等价或不优。
分为两类，分割线在上面。
与分割线在下面（与上类似）。
不妨搜索所有选择方案，用树状数组统计交点个数。
时间复杂度$O(t\cdot 2^{22}\log22)$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
#define mp make_pair
#define pii pair<int,int>
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=55;
int n;
struct BIT {
int c[maxn];
#define lowbit(x) x&(-x)
void add(int x,int v) {
for(int i=x; i<=n; i+=lowbit(i))c[i]+=v;
}
int sum(int x) {
int ans=0;
for(int i=x; i>=1; i-=lowbit(i))ans+=c[i];
return ans;
}
} up,down;
vector<pii> vec;
int a[maxn],ans;
void Dfs(int Depth,int sum) {
if(sum>=ans)return;
if(Depth==vec.size()) {
ans=sum;
return;
}
pii Now=vec[Depth];
int tmp=sum+min(up.sum(Now.second)-up.sum(Now.first-1),down.sum(n)-down.sum(Now.first-1)+up.sum(n)-up.sum(Now.second-1));
up.add(Now.second,1);
Dfs(Depth+1,tmp);
up.add(Now.second,-1);
tmp=sum+min(down.sum(Now.second)-down.sum(Now.first-1),up.sum(n)-up.sum(Now.first-1)+down.sum(n)-down.sum(Now.second-1));
down.add(Now.second,1);
Dfs(Depth+1,tmp);
down.add(Now.second,-1);
}
int main() {
int t=Get_Int();
while(t--) {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
vec.clear();
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
if(a[i]==a[j])vec.push_back(mp(i,j));
ans=INT_MAX;
Dfs(0,0);
printf("%d\n",ans);
}
return 0;
}
|
