<?php /** * Notes: * User: liubing17 * DateTime: 2019-10-17 17:10 */ function get($m, $n){ /* * 获取m*n矩阵正方形的个数 * */ if($m*$n <=0 ){ return 0; } $total = 0; while($m>=0 && $n>=0){ $total += $m*$n; $m--; $n--; } return $total; } echo get(

洛谷P2241-统计方形 题目描述: 有一个 \(n \times m\) 方格的棋盘,求其方格包含多少正方形.长方形(不包含正方形). 思路: 所有方形的个数=正方形的个数+长方形的个数.对于任意一个\(x\times y\)的矩形,以这个方形右下角的那个块作为要在矩形内选择正方形\长方形的右下角,则正方形的个数为\(min(x,y)\),长方形的个数为\(x*y\). 解释如下:对于一个\(x\times y\)的矩形,右下角的块必选,则能和这个块组成的正方形的右上角块全在这个主对角线上,而

题目链接:http://lightoj.com/volume_showproblem.php?problem=1366 题意:给出一个矩形,在内部画两个圆A和B使得AB都完全在矩形内且AB相切且AB的圆心和半径都是整数.求有多少个这样的画法? 思路:总的来说,相切有两种情况:(1)水平或垂直方向相切.这个比较简单,枚举两个圆的直径,然后分水平垂直两种情况,计算较小的那个圆可以移动的范围,其实可以移动的范围是一个矩形:(2)斜着相切.这时候两个圆心的距离必然是一个勾股数.所以枚举勾股数,然后再枚举

Intersection Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 9996   Accepted: 2632 Description You are to write a program that has to decide whether a given line segment intersects a given rectangle. An example: line: start point: (4,9) 

题目链接:https://cn.vjudge.net/contest/284294#problem/B 题目大意:查询区间内有多少个不相同的数. 具体思路:主席树的做法,主席树的基础做法是查询区间第k大或者第k小的,但是这个地方查询的是区间内不同的数的个数,我们就按照下标建立主席树,对于区间[l,r],我们存储的是区间[l,r]中有多少个不同的数,对于当前的数,如果没有出现过,我们就在第i个位置给他加上,如果已经出现过,我们在建立下一棵主席树的时候,先将之前的这个数的下标对应的值减去1.探后再在

设想这么一个简单的问题,在一个平面上有n个点,给定一个矩形,问位于矩形内的点有哪些. 这个问题的简单思路非常简单,每次遍历所有点,看其是否在给定的矩形中.时间复杂度呢?单次查询的时间就是一次遍历的时间,也就是O(n),但如果给定的点基本不变,但查询量特别大,每次查询都要以O(n)的复杂度.能不能把给定的数据预处理一下,然后以后每次查询的复杂度降低呢? 一个基本的思路是把相邻的点用最小包围矩形包起来,然后再递归地处理这些矩形,以更大的最小包围矩形包围这些相邻的矩形.下图是个简单的例子: 在查询一个

题意: 给你三个数字L, R, K,问在[L, R]范围内有多少个数字满足它每一位不同数字不超过k个,求出它们的和 分析:考虑用状态压缩 , 10给位0~9 , 如果之前出现过了某个数字x ,那就拿当前的状态 st | (1<<x) , 表示这个数字出现了 , 那st的二进制有多少的1 , 就有多少不同的数 , 这里好要考虑前导零的情况 . 个数是解决了 , 但是这里是要每个答案的和 , 贼鸡儿坑 , 经过前面的训练可以知道不可能是在(len==0) 这里判断的了 , 因为是记忆化搜索 , 所

题目链接:contest=0&problem=231">点击打开链接 题意: 求<=n内有多少对素数(a,b)使得a+b也为素数 思路: 我们发现全部素数间隔都是>=2的,且除了2都是奇数.那么: 奇数+奇数 = 偶数. 所以仅仅有一种情况2+素数=素数. 所以打个素数表,看一下有多少个素数和前面那个素数间隔是2的. #include <stdio.h> #include <string.h> #include <iostream>

1,将城市地图拆分等距拆分为矩形 数据结构如图: 2.查看高德JS API (点是否在多边形内)核心代码: a=[114.069564,22.545774]; b=[ [114.067595,22.552082], [114.077322,22.552082], [114.077322,22.543099], [114.067595,22.543099], ]; c=true lf: function(a, b, c) { var d = a[0]; a = a[1]; var f = !1,

这个题目要注意的是:给出的矩形坐标不一定是按照左上,右下这个顺序的 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define eps 1e-8 #define INF 1e9 using namespace std; const int maxn=100; typedef struct Point {

题目链接:http://lightoj.com/volume_showproblem.php?problem=1366 题意:一个H*W的矩形,现在要放入两个外切的圆,问能放多少对这样的圆,其中圆心和半径都是整数: 枚举相对的圆心坐标,根据圆心的距离,再枚举一个圆的半径: #include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<cmath&

Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this pro

Intersection 大意:给你一条线段,给你一个矩形,问是否相交. 相交:线段全然在矩形内部算相交:线段与矩形随意一条边不规范相交算相交. 思路:知道详细的相交规则之后题事实上是不难的,可是还有个坑点就是题目里明明说给的是矩形左上角跟右下角的点,但实际上不是,须要又一次推断一下...真坑. struct Point { double x, y; } A, B, C, D; struct Line { Point a, b; } L; int n; double xmult(Point p1

/** 题目:D - Sigma Function 链接:https://vjudge.net/contest/154246#problem/D 题意:求1~n内约数和为偶数的数的个数. 思路:一个数的约数和为那个数的每个素因子的等比和相乘.如题目所给公式就是等比和化简之后的式子. 那么要判断一个数约数和是否为偶数,可以通过观察它的各个素因子等比和来判断.如果存在某个素因子的等比和为偶数. 那么这个约数和肯定是偶数.否则为奇数. 素因子只有2是偶数,其他都是奇素数. 含素因子2的等比和一定为奇数

链接:https://www.nowcoder.com/acm/contest/130/B来源:牛客网 黑妹和黑弟又聚在一起玩游戏了,这次他们选择在一个n*m的棋盘上玩游戏,棋盘上的每个方格都有一个非负的分数, 游戏从左上角开始右下角结束,双方交替的选择一个方格并获得方格上相应的分数,一方选择的方格必须在上一步另一方选择的方格 的右边或者下面,黑妹先开始.现在黑妹想知道,如果双方都采取最优策略(最优策略是指双方都希望最终自己的总分数减去对方的总分数最大),她的总分数减去黑弟的总分数会是多少? 输

See you~ Time Limit: 5000/3000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 4729    Accepted Submission(s): 1515 Problem Description Now I am leaving hust acm. In the past two and half years, I learned so many kno

C. New Year and Domino   They say "years are like dominoes, tumbling one after the other". But would a year fit into a grid? I don't think so. Limak is a little polar bear who loves to play. He has recently got a rectangular grid with h rows and

戳我看题目 A:给你n个数,要求尽可能多的找出匹配,如果两个数匹配,则ai*2 <= aj 排序,从中间切断,分成相等的两半后,对于较大的那一半,从大到小遍历,对于每个数在左边那组找到最大的满足条件的数配对 用一个变量移动一下就好了.这样的配对数量肯定就是最多的. 因为 1:如果左边那一半数量取少一点,比如取a1 a2 a3...ak (k < n/2) 那实际上ak+1 ak+2 .. a n/2 这些数就没啥用了,因为后面那一半数已经足够匹配当前的这些数了,不可能后面还有某些数不匹配而拿这

花了近2个小时终于AC,好爽.. 一道类似于最优矩阵链乘的题目,受<切木棍>那道题的启示,该题的原理也是一样的,仅仅只是变成了且面积.那么对应的也要添加维度 . 显然要完整的表示状态,最少要用四维数组.分别表示它的两个对角线顶点的坐标 .   然后横切或者纵切,递归需找更小的矩形,直到矩形内仅仅剩一个樱桃的时候返回0 那么问题就是如何高速的推断一个矩形内有多少个樱桃,于是决定再开一个数组记录这个矩形内樱桃的个数.一開始就是在这个地方超时(开了个五重循环) ,后来想到一个折中的办法,将时间复杂度

Stars Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/65536 K (Java/Others) Total Submission(s): 111 Accepted Submission(s): 54   Problem Description Yifenfei is a romantic guy and he likes to count the stars in the sky.To make the problem

题目 Link 就是查询矩形内有多少个点. 分析 二维树状数组维护就好了,. Code #include <bits/stdc++.h> const int maxn = 1000 + 131; struct Point { int x, y; }; int Num[maxn][maxn]; bool Vis[maxn][maxn]; int lowbit(int x) { return x&(-x); } int Sum(int x, int y) { int ret = 0; in