TopCoder SRM 620 Div1
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
------------------------------------------------------------
QAQ
------------------------------------------------------------
200:
题意是假如你有一个二元组(a,b),你每次可以做一个操作,把他变成(a+b,b)或者(a,a+b),现在给你两个二元组(x,y)和(z,w),让你选一个初始二元组(a,b)使得从(a,b)可以变到(x,y)并且可以变到(z,w),最大化a+b（x,y,z,w <= 10^6）
YY一下发现如果(a,b)能得到(c,d)，那么从(c,d)辗转相减一定能得到(a,b)
因此(x,y)辗转相减能得到的二元组集合和(z,w)辗转相减能得到的二元组集合的交集中和最大的元素就是答案
因为x+y<=2*10^6,而每一次辗转相减至少把和减少1,因此不会超过2*10^6步
------------------------------------------------------------
450:
题意是说有n个人m种技能,每个人的每种技能都有一个技能等级,每一次操作可以把人按某一个技能的技能等级排序,相同的按原来的顺序排,现在给定一个目标序列,问能不能通过若干次操作把人排成目标序列的样子,n,m<=50
假设a[i][j]表示第i个人的第j个技能的等级
倒着考虑，假如最后一次操作选了技能j,结束后变成了序列x的样子,那么说明a[x[i]][k]是一个不下降序列,也就是说其中有一些小于号和一些等于号
对于这些小于号,都是对技能j的排序造成的,而等于号要么是因为编号顺序造成的,要么是之前的排序造成的
因此小于号都可以不管了,继续往前推,之后就是要把原来等于号的地方变成小于号(除非本来那两个数就是小于关系)
而选了一个可选的技能(一个技能可选,如果他在所有当前是等于号的地方都是小于或等于),结果就是把一些等于变成了小于,这个是只赚不亏的
因此能选就选就行了
同时根据上面的推理发现一个技能最多选一次(因为选过一次之后该变成小于号的地方都变成小于号了)
因此算法就是能选就选,每个最多选一次
------------------------------------------------------------
800:
果然是我不熟悉的知识点
看了一下题解，不想写了
首先可以按照题意列出来一个模2意义下的线性方程组
然后随便跑一下可以发现，素数个数不会超过900个
然后变量个数大概就是1000来个的样子
然后按照题解的说法，这玩意儿的自由变量个数d就等于变量个数减系数矩阵的秩
（大概就是，找一个线性基，然后线性基里面的变量都可以随便取）
然后自由变量可以取0或者1，所以答案就是2^d
------------------------------------------------------------
评论 (0)
