SRM 503 DIV1 500pt ( 求期望题.贪心，枚举，概率计算 ) 答案分成两点之间的答案，再组合数统计即可。注意dist相同的情况，可以规定优先级。。先连city，再按顺序连village，这样就很方便了。。ll没开怎么死都不知道！！
SRM 507 DIV1 900pt ( dp+组合数学基础 ) 直接暴力dp即可
SRM 495 DIV1 975pt(数学， dp）一开始不会，可耻的去膜题解，然后发现了诡异的转移。。看了很久没看懂，YY了很久，终于在一个晚上想明白了。。我是个傻逼。。。题意是给你高度为H的楼房，让你用n个电梯覆盖，覆盖是这样的，保持电梯的相对位置不变，不遗漏的覆盖完，问方案数。如H=8,N=4 12123434。然后令f(H,N)表是前两个是不同的电梯覆盖，g(H,N)表示是相同的电梯覆盖，然后观察序列，发现1-N序列连续的块大小是定值，然后就f(H,N)就枚举块的大小,有f(H,N) = sigma g(H/d,N/d) (d>1, d|N) 现在考虑g(H,N)的转移,有g(H,N) = f)H,H/N) 可以这样理解，着相当于将所有的1由1-H/N替代，由于前两个都是1，这样的方案对应一个前两个是不同的电梯覆盖的方案。这样就可以了。:-D
TCO'10 Wildcard Round 500pt
题意：给你一堆带符号的卡片包含（+,-,*），随机抽取成排列，求期望表达式的值
注意到每一个非乘号后面均是等价的，所以分开来算，只要把所有非乘号的卡片的和加起来再乘上每一段的期望。而每一段的期望等价于开头全是乘号的期望积，枚举连续的K个，简单统计即可。很拙，思考了很久。
SRM 498 DIV1 1000pt
题意:求从(0,0)走到(Tx,Ty)且步长不超过(Mx,My)且有一些bad走法(dx=dy且为10倍数)问方案数
没想出来，看题解的。容斥走了几步坏的,注意到步子是可以交换的，然后dp再组合数统计没了。。感觉很厉害
TCO'10 Semifinal 1 950pt
一开始想残了，然后YY了很久才搞出来。。比较恶心的dp.枚举再前后dp一遍即可
SRM 522 DIV1 1050pt
题意：给你一些y[i]代表点(i,y[i])，每一次可以删除以两个点为对角线矩形内的点，问最终点剩余的可能方案
一开始没想法，其实这题是很好想的。首先我们观察最终留下的状态，那么显然是左右端点以及ymax与ymin的点，唯一有变化的是与左右y坐标相同的一些点，简单dp即可。
SRM 521 DIV1 500pt
题意：给你一些点，可以选择边长在lown到highn之间选择正方形去覆盖，问可能的集合数
显然不会太多，然后枚举左上与右下，简单判即可
SRM 481 DIV1 500pt
题意：给你一些人的任务，同一个人有多个任务。求安排任务顺序，使得平均等待时间最小。只有一台机器，且在最优方案中等概率选择，问每个任务完成的期望
每个人的任务总是连在一起的，简单计算即可。
SRM 521 DIV1 1000pt
题意：一个烟囱是由4个1*2的砖垒成一层，问你垒N层的方案数（只有下面的堆玩才能堆上面的）
一开始想不出状态定义，感觉很复杂，后来开了一下脑洞，只要考虑放第i层第一个后前两层的状态，只有4种情况，转移矩阵系数挺烦的，暴力状压算即可。
SRM 520 DIV1 500pt
sb背包
SRM 520 DIV1 1000pt
题意：给你一些哪些人cha过人以每个人被cha的转态，询问cha不同的序列数。每个人仅cha一次，而且被cha以后不会去cha别人。
非常神。一开始没有什么想法，去膜题解。好巧妙！当你搞不清关系时，可以列表，转换成形象的图形。而且显然可以将人分类。先放既cha人又被cha的，再放其他人。dp+组合排列
SRM 519 DIV1 600pt
ac自动机+dp
SRM 519 DIV1 900pt
枚举2,3相互搞的数量，再剩下与5,7匹配即可。注意怎么开数组（vector)
SRM 518 DIV1 500pt
貌似随便写了个贪心过了
SRM 518 DIV1 1000pt
本来是fwt的，但不会，学习了简单易懂的分治乘，而且复杂度是NlogN的。
SRM 517 DIV1 600pt
题意：操作i可以是a[i]与a[i+1]交换，给你一个目标排列，问你用1-i-1的i-1个操作排列使1--i-1变成目标排列，问排列方案数
很考思维，注意到操作i之前左右的数值不会交换，令f[i][j]为将i--j搞成有序的方案数，那么枚举最后一个操作，就变成了两个子问题。关键是要发现dp子问题的性质。
SRM 517 DIV1 900pt
题意：给你一个字符board，每次可以染一行或一列。问你最小次数
首先这种问题一般方法是先枚举一下，再推出一些信息。可以证明肯定有一行或一列不用染（反正，如果都染，那么第一次的会被全部覆盖),然后就知道了一行或一列的染色，再看不合法的点肯定让另一维染，搞出拓扑图判断。注意如果行列颜色都一样就没有限制关系！！
SRM 516 DIV1 500pt
简单的贪心
SRM 515 DIV1 550pt
题意：给你一些人到达店买剑的时间，价钱以及概率，每个人最多买一把剑，问你最多买K把剑的最优期望
可以dp[mask][i][j]表示mask的到过店，有i把剑，时间为t，dp即可。我觉的最难的是他告诉你每个时间到达店的概率，这样没法dp，而我们能做到的dp是用p[i]表示到以及(1-p[i])表示不到的概率进行转移，所以要把概率转一下，这点非常非常关键！！
SRM 515 DIV1 1000pt
题意：给你N*M的棋盘，有一些障碍点，三种人分别有他们的起始位置，各部相同，等概率出现在对应的位置上，三种人到达同一点，求走最短路的期望，两种人数<=20(N,M<=50)
一开始感觉很困难，两种人显然是要枚举的，但第三种人感觉很难再N*M的复杂的内求出。看了题解之后，忽然感觉很简单，N*M的复杂度只能BFS一遍，那么就考虑一种构图方法，使得求出的第三种人的距离为三个人最短路的答案，那么就很简单了，先枚举前两个人，再枚举三个人的聚集地点，然后对于每种前两个人到达聚集点的距离建一个点，距离i向距离i+1连边，然后每个距离向合法的到达点连边，再跑一遍BFS即可。很巧妙，关键是要想到可以直接BFS最终的距离和。
SRM648 DIV1 850pt
题意：求N个点K个桥带标号的图的个数
好难，首先图可以分成一个一个联通块背包do，然后一个联通块可以将桥拆掉变成若干个双联通分量，由矩阵树定理可得：N个带标号的点S个联通块(大小为mi)加S-1条边使图联通的方案数为N^(S-2)*pi(ai)。然后就算N个点的双联通分量有几个，可以先算出所有的联通图数量，再减去1-N-1座桥的图的数量。
SRM 510 DIV1 500pt
题意：仅有4,7构成的数是lucky number，A从[a,b]中选出连续的L1个，B从A选出的中选出连续的L2个。A要最大化lucky number的数量，B要最小化lucky number的数量，问最终结果(a,b<=10^10)
一开始很乱，感觉直接贪心边界十分不好处理，情况也非常多。然后去看了题解，看了将B从x选起的结果用F(X)表示出来，立马就懂了，可以发现函数值是连续的，就可以分成一些段搞了。然后枚举答案，看是否存在L1长度连续的即可。关键思路是将复杂的东西具体化，暴力化，用函数表示出来，就很显然了。
SRM 510 DIV1 1000pt
题意：仅有4,7构成的数是lucky number，给你N(N<=1e16)，问你有多少D是的ND进制下每一位是lucky number
首先方案不会太多，可以考虑枚举。但怎么枚呢？首先考虑假如有很多位那么D应很小，爆枚即可。当有2-3位时，看似很难枚，但由于数字只能是4,7构成，爆搜一下发现发难数都很少，check一下就可以了。关键是要先转化到位数很少的情况，再考虑爆枚。
SRM 658 DIV1 850pt
二分图最大匹配，然后判一判即可
SRM 658 DIV1 650pt
题意：给你N个怪物(N<=20),每个怪的血值(<=60)，每次attck可以选择三个，分别扣血1,3,9滴，问你最少几次
首先可以二分答案，然后呢,发现如果选完3,9，剩下的只能选一到满，令dp[o][k][l]表示搞到第i个人3,9用了j,k个的最少1个数。dp即可。关键在于发现1取到满即可的性质
TCO Round3 2A 1000pt
题意：问你A^B有多少种不同的数，1<=A<=1e9, 1<=B<=1e9
首先可以将每个A^X表示成(r^k)^X,其中r为不能表示成更小的指数幂形式，那么可以知道k<=30，故暴力枚举k，先考虑如何统计最大次幂为k的r有几个，可以考虑容斥，答案等于sigma(i,mu[i]*这段区间中能表示成i次幂的数的个数)。
好，然后考虑对一个r不同的方案数，那么可以转换成k*X的方案数。这个怎么算呢，首先观察到k很小，考虑分段，对于(i*X,(i+1)*X]这段的答案，显然只有i+1到k乘才会合法，而对于i能覆盖所有i的倍数覆盖的点，那么考虑容斥，只要考虑哪些不构成倍数关系的数即可，这样最多只有15个左右，就可以了。关键是要想到优化容斥，直接容斥是2^30次，而分段则可以优化很多。
1的情况要特殊考虑。
TCO Round3 2A 600pt
题意：一个Magic Matrix定义为所有行和列的和的最后一位相同。每个格子只能填0-9.问你在N(<=1)个格子已填的基础上，有多少种不同的方案。
首先，如果N很大，那么可以将空的一行和一列交换到最后，这样可以直接算出！！
如果N很小，暴力搞死消元。关键是要想到可以交换的性质。
SRM578 DIV1 1000pt
题意：给你N个节点的树(N<=50),让你割掉一些边形成若干个联通子树，选出两棵子树，使它们同构。问最大点数
好难！首先可以考虑对于两棵有根树该怎么办，可以递归算出两个儿子分别匹配的答案，然后最优匹配即可。
然后可以枚举一条边删掉，然后枚举两个联通快的根，统计答案取max
关键是想到对于两棵有根树该怎么做。可以递归得到儿子答案，在最优匹配合并。/(ㄒoㄒ)/~~
SRM578 DIV1 500pt
题意长度为N(<=300)的线段上每个点可能有fox，现在给你一些条件，形如[L,R]这段区间至多有两个fox。问方案数
首先观察N的范围，考虑N^3的dp。令dp[i][j]表示i,j上有为相邻fox的方案数。这道题关键是用到最多两个的性质，直接上两维状态表示即可。O(∩_∩)O
TCO13 Semifinal1 550pt
题意：给你一个DAG的拓扑序列，一个DAG序列生成的方式是等概率随机当前入度为0的集合中的一个点加到序列。问你这个DAG中有A->B这条边的概率是多少
可以从后往前dp，设dp[i][j]表示到第i个点，后面的点是不是入度为0(用j表示一个二进制)的概率。直接算即可。最后必须有这条边的概率与所有概率除一除即可 O(∩_∩)O
SRM 509 DIV1 1000pt
题意：给你一个凸多边形，以及内部的N个点，每个点分配周长的1/N，问你内部的点到分配的点的最大值的最小值是多少？
二分，然后怎么判，先枚举每条线段，与每个圆作交，求出每个交点，在对每一段建点，跑网络流看是否满流即可。判线段与圆的交，设交点为X+w*d，d为直线向量，这样比较方便。注意eps。关键是讲复杂的交法转换成每一条边与每一个圆的交，算计技巧以很重要。/(ㄒoㄒ)/~~
SRM 507 DIV1 500pt
题意：给你Ns个1*1*1的方块和Nb个L*L*L个方块，用体积最小的长方体装下这些方块，求最小体积(要求平行）
一开始不会做，后来抱着试试看的心态，写了L*L*x，发现过了4个点，然后就发现答案最大值最多加L*L-1，然后写了个爆枚体积，分解因数判断的。。
后来看了题解，发现傻逼了。。由于题目中给出体积小于int，故直接枚举最短边，次短边在算第三条边即可。。关键是想到题解很小，而且爆枚两个最小边的复杂度很小。。。^_^
Read full article from 除草 - nblt's Blog
No comments:
Post a Comment