随机化 - hzwer.com

「FJ2015集训」贪吃蛇
最近lwher迷上了贪吃蛇游戏，在玩了几天却从未占满全地图的情况下，他不得不承认自己是一个弱菜，只能改去开发一款更弱的贪吃蛇游戏。在开发的过程中，lwher脑洞大开，搞了一个多条蛇的模式。但由于这种模式太难操作，于是他只好改变游戏的玩法，稍微变化一下游戏目标。新的游戏是这样的：一些蛇覆盖了一个网格。每个格子要么是一个障碍物，要么是蛇的一部分。每条蛇占据了一条折线(拐角处只能水平和竖直连接)，且只是占据两个格子...
62015年7月13日7,368费用流,有上下界网络流,随机化

NEERC 2014 填坑计划(7 / 12)
7/12已弃A简单贪心[crayon-6740150ba287a335855746/]B按B/A排序后贪心[crayon-6740150ba2888387640009/]E写的题解被吞了。。。奇怪的随机化直接看代码好了[crayon-6740150ba2893518577546/]F主要是读题上的困难，得出每个文件的二进制串，用bitset判包含[crayon-6740150ba289d859021434/]I将出现次序作为权，发现合法状态是一个递增序列拼上递减序列然后就是dp啦[crayon-6740150ba28a5615927822/]J搜索可过，因为不合法状态...
22015年5月15日4,731模拟,贪心,STL,构造,深度搜索,随机化
「CF364D」Ghd
JohnDoeofferedhissisterJaneDoefindthegcdofsomesetofnumbersa.Gcdisapositiveintegerg,suchthatallnumberfromthesetareevenlydivisiblebygandthereisn'tsuchg'(g' > g),thatallnumbersofthesetareevenlydivisiblebyg'.UnfortunatelyJanecouldn'tcopewiththetaskandJohnofferedhertofindtheghdofthesamesubsetofnumbers.Ghdisapositiveintegerg,suchthatatleasthalfofnumbersfromthesetareevenlydivisiblebygandthe...
02015年1月20日3,815随机化,最大公约数与最小公倍数
「codechef」January Challenge 2015
CHEFSTON[crayon-6740150ba3d40750311123/]GCDQgcd满足区间加法TAT，所以维护前缀和后缀和就好了[crayon-6740150ba3d4e144285277/]SEAVOTE去掉所有0后若∑bi<tot或∑bi>=100+n则无解否则有解[crayon-6740150ba3d57204788021/]ONEKING按照右端点排序，选择第一个的右端点，删去覆盖其的线段。。。剩下的线段同理[crayon-6740150ba3d5f262645160/]CLPERM答案根据第一个不能合成的数奇偶性得...
02015年1月12日6,200模拟,贪心,构造,数学,快速幂,随机化,容斥原理,最大公约数与最小公倍数
「BZOJ2823」[AHOI2012] 信号塔
Description在野外训练中，为了确保每位参加集训的成员安全，实时的掌握和收集周边环境和队员信息非常重要，集训队采用的方式是在训练所在地散布N个小型传感器来收集并传递信息，这些传感器只与设在集训地中的信号塔进行通信，信号塔接收信号的覆盖范围是圆形，可以接收到所有分布在该集训区域内所有N个小型传感器（包括在该圆形的边上）发出的信号。信号塔的功率与信号塔接收范围半径的大小成正比，因为是野外训练，只能使用事...
02014年12月29日5,328几何,随机化
「BZOJ3707」「FJ2014集训」圈地
「题目描述」2维平面上有n个木桩，黄学长有一次圈地的机会并得到圈到的土地，为了体现他的高风亮节，他要使他圈到的土地面积尽量小。圈地需要圈一个至少3个点的多边形，多边形的顶点就是一个木桩，圈得的土地就是这个多边形内部的土地。（因为黄学长非常的神，所以他允许圈出的第n点共线，那样面积算0）「输入格式」第一行一个整数n，表示木桩个数。接下来n行，每行2个整数表示一个木桩的坐标，坐标两两不同。「输出格式」仅一行，...
32014年8月31日6,222几何,随机化
平面上的最接近点对
http://218.5.5.242:9018/JudgeOnline/problem.php?id=1431题目描述给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的。输入第一行：n；2≤n≤60000接下来n行：每行两个实数：xy，表示一个点的行坐标和列坐标，中间用一个空格隔开。输出仅一行，一个实数，表示最短距离，精确到小数点后面4位。题解随机分块可水[crayon-6740150ba6152078734086/] ...
02014年8月20日3,636随机化
「BZOJ3632」外太空旅行
Description在人类的触角伸向银河系的边缘之际，普通人上太空旅行已经变得稀松平常了。某理科试验班有n个人，现在班主任要从中选出尽量多的人去参加一次太空旅行活动。可是n名同学并不是和平相处的。有的人，比如小A和小B整天狼狈为奸，是好朋友；但还有的人，比如杜鲁门和赫鲁晓夫就水火不相容。这n名同学，由于是理科生，都非常的理性，所以“朋友的朋友就是朋友”和“敌人的朋友就是敌人”这两句话对这些同学无效。换句话说，...
92014年6月16日4,221随机化
「BZOJ1336 / 1337」[Balkan2002] Alien最小圆覆盖
Description给出N个点，让你画一个最小的包含所有点的圆。Input先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)Output输出圆的半径，及圆心的坐标SampleInput68.09.04.07.51.02.05.18.79.02.04.51.0 SampleOutput5.005.005.00HINT用传说中的随机增量法，请自行百度[crayon-6740150ba7600768814738/] ...
12014年5月22日4,451随机化
「BZOJ2396」神奇的矩阵
Description 给出三个行数和列数均为N的矩阵A、B、C，判断A*B=C是否成立。Input 题目可能包含若干组数据。对于每组数据，第一行一个数N，接下来给出三个N*N的矩阵，依次为A、B、C三个矩阵。Output 对于每组数据，若A*B=C成立，则输出Yes，否则No。每个答案占一行。SampleInput122100SampleOutputNoHINT 对于90%的数据，N不超过100；对于100%的数据，N不超过1000，矩阵中的数字...
12014年4月29日3,966随机化