集训队一次作业试题准备seaarc.pdfVIP

SEAARC解题报告

江苏省常州高级中学

题目大意

给定依次排列在一条直线上的n个点，第i号点具有颜色a。任意一对同色点之间都

i

恰好连了一条圆弧，求有多少对异色圆弧相交。

时间限制：5s

数据规模

•对于10%的数据，n≤100；

•对于40%的数据，|c|≤100；

55

•对于100%的数据，1≤n≤10，1≤|c|,a≤10。

i

算法分析

为了方便的讨论，不妨记cnti为第i种颜色的总点数，记prei,j为前i个点中

具有颜色j的点数。由于题中所求的相交圆弧情形比较难以处理，因此我们尝试补集转

化思想：记所有异色圆弧对总数为s，形如AABB的异色圆弧对数为s1，形如ABBA

的异色圆弧对数为s，形如ABAB的异色圆弧对数为s，则s=s+s+s，即

23123

s=s−s−s，而s即为所求。下面依次讨论s、s和s的求解。

312312

异色圆弧对总数s

()

cnt(cnt−1)

由于已知每种颜色的点数cnti,则第i种颜色的圆弧数为cnti=ii，于是

∑()()22

cntcnt

s=ijij，