Codeforces Round 345 (Div. 2) E. Table Compression(拓扑排序)

题意: $n*m \le 10^6的矩阵,现在要压缩矩阵里的数字的大小,使得最大的数字尽量小$$压缩的要求是,保证每行或者每列的相对数字大小不变,并且每行或者每列的相等的数字压缩后还相等$     Read more
TaoSama's avatar
TaoSama Mar 08, 2016

Codeforces Round 345 (Div. 2) D. Image Preview(二分搜索)

题意: $n\le 5\times 10^5手机图片,每种图片可能是h的也可能是w的,w要观看的话就要有旋转花费b$$观看一张图片需要1单位时间,手机图片显示是个环,滑动切换的花费是a$$初始在第一张图片,切换到的图片必须要观看$$给定T\le 10^9时间,问最多能看多少图片$     Read more
TaoSama's avatar
TaoSama Mar 08, 2016

HDU 4609 3-idiots(FFT)

题意: $n\le 10^5条线段,每条长度A_i \le 10^5,问随机取3个,可以组成三角形的概率$     Read more
TaoSama's avatar
TaoSama Mar 07, 2016

Educational Codeforces Round 9 F. Magic Matrix(离线暴力、bitset)

题意: $给你一个n*n, n\le 2500的矩阵,判断这个矩阵是不是魔力矩阵$$魔力矩阵的定义为:$$1.对角线都为0$$2.矩阵对称, 即a_{ij}=a_{ji}$$3.对于任意一个格子(i,j)满足,\forall k,a[i][j]\le max(a[i][k],a[j][k])$     Read more
TaoSama's avatar
TaoSama Mar 07, 2016

Educational Codeforces Round 9 E. Thief in a Shop(FFT)

题意: $给定N,K\le 10^3,N种物品,价值A_i\le 10^3, 必须装K个物品的背包$$求所有能装的价值,从小到大输出$     Read more
TaoSama's avatar
TaoSama Mar 06, 2016

HDU 4606 Occupy Cities (计算几何、最短路、最小路径覆盖)

题意: 给出$n\le 100$个城市需要去占领,有$m\le 100$条线段是障碍物,有$p\le 100$个士兵可以用占领城市有个先后顺序,每个士兵有个背包,占领城市之后,仅能补给一次背包问背包容量最少是多少,可以用这$p$个士兵完成任务,起点任意     Read more
TaoSama's avatar
TaoSama Mar 01, 2016