edward_mj

[HDOJ3666 Regional Harbin THE MATRIX PROBLEM]【差分约束系统变形】

【题目大意】
给定一个矩阵C[i][j]，每行数都乘一个a[i]，每列数都除以一个b[i]，然后使得矩阵里每个数都L<=x<=U。
问是否存在这样的a[i],b[i]。
【算法分析】
易得不等式
(a[i]/b[i])*C[i][j]>=L
(a[i]/b[i])*C[i][j]<=U
移项
a[i]*(C[i][j]/L)>=b[i]
b[i]*(U/C[i][j])>=a[i]
那么我们建边即
然后用最短路松弛之。其实就是差分约束系统了。。。
【其它】
由于顺序问题。。。我把入栈限制限为2居然过了。。。
【CODE】
http://xiudaima.appspot.com/code/detail/1615006

[HDOJ3668 Regional Harbin Volume]【定积分】

【题目大意】
给定两个一样的圆柱，他们的底面半径为r，高为h，求非相交部分的体积。
【算法分析】
之前做过一题差不多一样的，用的暴力切块，这里精度怎么都不够。
想了几分钟发现，上一次的题目和这次的是有差别的。
上一次的如果想用定积分来求，就要反导一个带根号的式子，而在本题，由于两个圆柱是一样的。
那个根号被平方掉了！
于是用定积分一下就O(1)秒杀了。
被积的函数
g'(x)=h^2 （x∈[0,r^2-h^2/4]）
f'(x)=4*r^2-4*x^2 (x∈[r^2-h^2/4,r])
两者一加就是了。
那么反导以后的结果。
g(x)=h^2 * x
f(x)=4*r^2*x – (4/3)*x^3。
然后就得解了。
【其它】3Y。
【CODE】
http://xiudaima.appspot.com/code/detail/1687004

[HDOJ3667 Regional Harbin Transportation]【拆边费用流】

【题目大意】
求一最小费用流，边的费用是a*flow^2。
每条边的容量<=5
【算法分析】
早在我初三的时候，刚刚学习完KM算法，老师给我们做得一套模拟题里就有这个模型。。。是什么工作分配的。当时还很菜很菜，然后居然很奇葩地想到拆点然后套KM，就过了，然后和我一起学的童鞋们都毫无想法，那时兴奋了我一整天=_=。
具体思路如下：
(x+1)^2-x^2=2x+1…
就是每次加2x+1，就能使和依次为每一个完全平方数。
然后2x+1又是递增的。
那么对每一格容量拆成容量为1，费用为2x+1的边，做最小费用流就可以了。
【其他】1Y。
【CODE】
http://xiudaima.appspot.com/code/detail/1684003

重感冒~

可能是积蓄了好久的。。。
先是第一天突然喉咙超痛，没什么其他症状。
第二天的开始觉着有点晕，晚修觉得不爽，去校医室一量，38.7°，被遣送回家。
然后回到家才发现好像真得挺严重的~打了两天针才退烧，然后现在喉咙依然好痛。
医生表示等喉咙好了才去上学。
然后算算中秋3天 -> 6天上学 ->国庆7天。
其中6天上学现在已经过去4天，其中两天在打针与半昏迷状态中度过
还剩两天不知喉咙还好不好得了，汗~

[SGU154 Factorial]【二分答案】【n!素因子分解】

【题目大意】
给定一个Q，让你输出最小的n，使得n!末位的0的个数=Q。
n>=1。
如果没有，那么输出无解。
【算法分析】
显然末位0的个数随关于n单调递增，那么二分答案，并分解n!，看里面有多少个·素因子5就等于知道末位有多少个0了。
首先n!里，2肯定比5要多。而只有2*5=10。所以看5有多少个就可以了。
然后对于这个求法，你可以先把n化为5进制数，然后一位一位截过去，很容易理解这个做法。
【其它】原来外国的自然数是从1开始的，怎么我们的教材是从0开始的呢T_T。
【CODE】C++ CODE :SGU154 1 2 3 4 5 6 7 8 9101112131415161718192021222324252627282930313233 #include