Test_Day2

雅礼联考

睡过头错过考试,下午走的时候才看到题….

题目大意

T1

圆上有\(2 \times n\)个点和连接这些点的\(n\)条弦,有多少个无序的三元组,是的对应的三条弦可以通过距离的缩放中心对称.

T2

给定一个\(n \times m\)的网格.你在左下角\((n,1)\),给定网格图,+表示可以走.*表示障碍.只能向上走或者是右拐.问走到\((y,x)\)的方案数\(mod\) \(k\)的值.

T3

最大权闭合图裸题


题解:

T1

有两种做法.

分类讨论:合法情况和不合法情况.

讨论合法情况求和,输出即为答案.

讨论不合法情况求和,总情况减去不合法即为答案.

合法情况有三种

从这个草率的图中可以发现,我们要找一个满足条件的,所以有三种编号情况,转化成序列问题,解决即可.

1 2 3 4 5 6
1,2相连,3,4相连,5,6相连.
1,6相连,2,5相连,3,4相连.
1,4相连,2,5相连,3,6相连.

三种情况判断就好了.

不会啊QAQ

所以放弃这种做法.


不合法情况有三种

有两个公共点

有一个公共点

三边均没有交点.


总答案个数是\(\frac{n \times (n-1) \times (n-2)}{6}\)

合法情况又不会判断…

所以不合法情况分情况讨论.

没有交点的可以通过判断最中间的边的左(上)右(下)来算出.

答案不就是两边的边数乘起来.乘法原理QAQ

有一个交点和两个交点的特殊情况

统计一下和它相交的边的个数,乘以和他不相交的边的个数即为答案.

开一个\(pair\)统计.

默认\(first\)较小,\(second\)较大.

排序后用数据结构维护一下.

判断两次.

第一遍

枚举\(1-n\)统计\(1-first[i]\)中在这个边的左边的边数.

第二遍

枚举\(n-1\)统计\(second[i]-2*n\)中在这个边左右的边数

最后算出来就好了.

数据结构就选树状数组了,懒.

QAQ


代码实现


T2:

好像是一种神奇的递推.然而并没有做出来…


T3:

最大权闭合图裸题

拆完点后连边.

正权边与源点连对应容量的边.

负权边与汇点连对应容量的边.

剩下没有连的将两个点之间连上容量为\(inf\)的边.

然后\(Dinic\)求一下最小割就好了.

代码后面写了再放QAQ


By:Wahacer

2017.12.26

9:18

发表评论

电子邮件地址不会被公开。 必填项已用*标注