BZOJ NOI十连测 6thTest
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-------------------------------------------------------------------
QAQ
-------------------------------------------------------------------
T1:题意和这道题一样,但是还多了个动态加边删边,每次操作后都要询问一次答案,操作次数<=10^5
可以发现如果一条边被两个人选了,那么他对差没有贡献,而两个人都不给贡献和两个人都给贡献是一样的(都对差没有影响),而且他的两个点都被选了
而一条边如果只被一个人选到,那么他只给这个人贡献,而他的点只被这个人选了
所以不难发现一条边给不给贡献只和他的点有没有被选有关
因此可以把边的贡献转换到点上:每个点的权值是和他相连的边权值之和
那么显然先手选第1大,第3大,第5大...的点
后手选第2大,第4大,第6大...的点
因此用一个线段树来维护排序后奇数和偶数位置的和就行了
-------------------------------------------------------------------
T2:题意是给定一个网格图,这个图上有一些障碍,然后给定两个大小相同的点集A和B,A点集全部在第0行,B全部在第n行,现在要找一些两个点集之间的路径(一一对应),不能交叉不能经过障碍,只能向下或者向右,问有多少种可能的路径
一颗赛艇啊...
一开始完全不会做,然后听说YJQ大爷是用行列式做的,然后就往这个方向想,然后好像就会了
首先把两个点集排序
设a[i]表示A中第i个和B中第a[i]个对应
显然合法的情况一定是a[i] = i,但是还是可能有相交的
首先考虑如果两个路径(i,j),(k,l)相交,那么改变一下两个路径的属于,就可以得到一个(i,l),(k,j)的路径(见下图)
然后就生成的一个有一个逆序对的序列a
不难证明一个没有逆序的不合法的对,和一个有逆序的对一一对应
然后就是一个容斥:没有逆序对的-有一个逆序对+有两个逆序对的...
这就是行列式的定义辣
设f[i][j]表示A中第i个到B中第j个的路径条数
那么|f|的就是答案了
-------------------------------------------------------------------
T3:
不会..神题..
-------------------------------------------------------------------
评论 (0)
