题面 传送门 前置芝士 最小圆覆盖 题解 我们按照\(x\)坐标排序,然后二分中间点,把点分成左右两边,对两边都做一个最小圆覆盖,那么半径大一点的那个就是答案了.然后对半径大的那一边继续二分就行了 然而这里显然会有一个问题--就是如果最优解中把点分成两个点集的那条直线是斜的该怎么办-- 那么我们就把整个坐标系转一下好了--枚举一下偏角,然后把所有点逆时针转过这个角度--实测大概每次转\({2\pi \over 100}\),转\(100\)次差不多就可以了 还有一个我很好奇的问题,如果有三点共线

Search GO 说明:输入题号直接进入相应题目,如需搜索含数字的题目,请在关键词前加单引号 Problem ID Title Source AC Submit Y 1000 A+B Problem 10983 18765 Y 1036 [ZJOI2008]树的统计Count 5293 13132 Y 1588 [HNOI2002]营业额统计 5056 13607 1001 [BeiJing2006]狼抓兔子 4526 18386 Y 2002 [Hnoi2010]Bounce 弹飞绵羊 43

题意: 一个r*c的矩形,求一个子矩形通过平移复制能覆盖整个矩形 关于一个字符串的最小覆盖子串可以看这里http://blog.csdn.net/fjsd155/article/details/6866991 把他分成对行和对列,对行覆盖最小就是n - next[n] ,然后求最小公倍数 对列的也是n - next[n], 然后求最小公倍数 #include <iostream> #include <cstdio> #include <algorithm> #inclu

参考博客:如何找取 最小覆盖点集合 题意:R*C大小的网格,网格上面放了一些目标.可以再网格外发射子弹,子弹会沿着垂直或者水平方向飞行,并且打掉飞行路径上的所有目标,计算最小多少子弹,各从哪些位置发射,才能将所有的目标全部打掉 分析:就是求最小覆盖点 以及 输出所有的覆盖点 最小覆盖点 == 最大匹配数 个人理解: 最大匹配数是用匈牙利算法求的,就是从左边一个点开始找到他看上的那个妹纸,如果那个妹纸已经名花有有主就跟那个男生换一个...沿着 ( 没匹配 - 匹配边 -... - 没匹配边)  这

Milking Grid Problem's Link:http://poj.org/problem?id=2185 Mean: 给你一个n*m的字符矩阵,让你求这个字符矩阵的最小覆盖矩阵,输出这个最小覆盖矩阵的面积. analyse: 做了上一篇博客的题目,就会求一个字符串的最小覆盖矩阵.同样的,现在求字符矩阵的最小覆盖矩阵,只是将一维推向了二维,我们在纸上画一下图,你会发现,其实二维的也是so easy! 我们将每一行的字符串的最小覆盖子串求出来,然后对这n个数求LCM,那么结果就是行覆盖的

KMP与最小覆盖子串 最小覆盖子串:对于某个字符串s,它的最小覆盖子串指的是长度最小的子串p,p满足通过自身的多次连接得到q,最后能够使s成为q的子串. 比如: 对于s="abcab",它的最小覆盖子串p="abc",因为p通过在它后面再接上一个p(即重叠0个字符),可以得到q="abcabc",此时s是q的子串. 对于s="ababab",它的最小覆盖子串为p="ab". 根据KMP算法的next数组的定

Strategic Game Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5034    Accepted Submission(s): 2297 Problem Description Bob enjoys playing computer games, especially strategic games, but somet

棋盘游戏 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 2492    Accepted Submission(s): 1452 Problem Description 小 希和Gardon在玩一个游戏:对一个N*M的棋盘,在格子里放尽量多的一些国际象棋里面的“车”,并且使得他们不能互相攻击,这当然很简单,但是 Gardon限制了只有某

其实也是个最小覆盖问题 关于最小覆盖http://blog.csdn.net/u014665013/article/details/49870029 Description As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely

题目很简单,但是需要推到出二分图最大匹配 = 最小覆盖 最小覆盖:证明过程http://blog.sina.com.cn/s/blog_51cea4040100h152.html Description Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K astero

题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=450 You are to write a program to find a circle which covers a set of points and has the minimal area. There will be no more than 100 points in one problem. 题意描述:找到一个最小圆能够包含到所有的二维坐标点. 算法

题意:给出一个大矩阵,求最小覆盖矩阵,大矩阵可由这个小矩阵拼成.(就如同拼磁砖,允许最后有残缺) 正确解法的参考链接:http://poj.org/showmessage?message_id=153316http://blog.sina.com.cn/s/blog_69c3f0410100tyjl.html 在discuss里还看到有人说可以这么简化:求横向最小长度时每次比较整列求纵向最小长度时每次比较整行真的是太神了!http://poj.org/showmessage?message_id

http://poj.org/problem?id=2226 Muddy Fields Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 9022   Accepted: 3348 Description Rain has pummeled the cows' field, a rectangular grid of R rows and C columns (1 <= R <= 50, 1 <= C <= 5

http://poj.org/problem?id=2226 Muddy Fields Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 7078   Accepted: 2622 Description Rain has pummeled the cows' field, a rectangular grid of R rows and C columns (1 <= R <= 50, 1 <= C <= 5

题意:有A,B两台机器, 机器A 有 n个模式(0, 1, 2....n-1),同样机器B有m个模式, 两个机器一开始的模式都为0,有k个作业(id,x,y) 表示作业编号id, 该作业必须在A机器在模式x下或者B机器在模式y下完成,问你至少要切换几次机器模式. 思路:很裸的最小覆盖点集,不熟悉概念的多看看蓝书吧,很容易证明 最小覆盖点集 == 最大匹配 #include <cstdio> #include <cstring> #include <vector> usi

最小覆盖(cover)..线段树 [题目描述] 给定 N 个区间[Li,Ri],需要你按照顺序选出一个区间序列使得[1,M]完全被覆盖.并且在选出来的序列中,某个区间[a,b]之前必须保证[1,a]都被已经选中的区间覆盖(即没有"断开"的地方).求出最少需要选多少区间 [输入文件] 第一行两个整数 M 和 N. 以下 N 行每行两个正整数 Li,Ri 表示这个区间. [输出文件] 一个整数,表示最少的区间数. [样例输入] 40 6 20 30 1 10 10 20 20 30 15

Maple trees Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 222 Accepted Submission(s): 79   Problem Description There are a lot of trees in HDU. Kiki want to surround all the trees with the minim

题意:x,y两台机器各在一边,分别有模式x0 x1 x2 ... xn, y0 y1 y2 ... ym, 现在对给定K个任务,每个任务可以用xi模式或者yj模式完成,同时变换一次模式需要重新启动一次机器,问最少的启动次数链接:http://acm.hdu.edu.cn/showproblem.php?pid=1150思路:稳定转化成给定k条边,使得每一条边最少被一个点覆盖,即最小覆盖点集最后求出的最大匹配数需要减一才是启动次数,注意到刚开始两台机器都是在0模式下,所以没有0模式,最后就不需要减

clear all; close all; clc; n=100; p=rand(n,2); p1=p(1,:); %取第一行的值 P1点 p2=p(2,:); %取第二行的值 P2点 r=sqrt((p1(1)-p2(1))^2+(p1(2)-p2(2))^2)/2; %求两点半径 cenp=(p1+p2)/2; %求两点中点 for i=3:n newp=p(i,:); %从第三行开始 储存新的点 d=sqrt((cenp(1)-newp(1))^2+(cenp(2)-newp(2))^2)

 最小覆盖子串(hard) (不会) 给定一个字符串 S 和一个字符串 T,请在 S 中找出包含 T 所有字母的最小子串. 示例: 输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC" 说明: 如果 S 中不存这样的子串,则返回空字符串 "". 如果 S 中存在这样的子串,我们保证它是唯一的答案. 关键:滑动窗口 参考 https://www.nowcoder.com/questionTe