题意：geometry Accepts: 324 Submissions: 622 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) 问题描述 在平面直角坐标系上有一个点PP, 他的坐标是(x, y)(x,y). 有一条直线y = kx + by=kx+b经过了PP, 且分别交x, yx,y正半轴于A, BA,B. 求|PA| * |PB|∣PA∣∗∣PB∣的最小值. 输入描述 第一行一个TT, 表示数据组数. 接下来TT行每行两个正整数x,yx,y, 表示PP的坐标. T=500, 0 < X, Y \leq …

http://codeforces.com/contest/611/problem/A 题意：两种查询，一种是 x of week,x为1.。7,对应输出2016年星期x有多少天。另一种为x of month ，对应输出2016年至少有x天的月份有多少天。 思路：直接搞。。。。竟然脑残被hack了。。。sad. #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int inf = 0x3f3f3f3f; int x; char …

http://codeforces.com/contest/611/problem/B 题意：问a到b（1E18），二进制表示中只有一个0的数有多少个。 思路：这么大的数。。。不是有循环节就是math problems.  UD:20160318讲道理还有可能是数位dp好不好。。。 我们发现可以很容易得算出1到x的二进制表示中只有一个0 的数有多少个。 problem solved. 20160318update:学了数位dp后又看到这题。。。这题显然是数位dp啊。。。亏我找规律搞了出来2333. 后面附上数位dp方法AC的代码 /* *********************************************** …

http://codeforces.com/contest/611/problem/C 题意：给出一个n*m的地图，.表示可以空，#表示墙。一个东西需要占两个相邻的格子，问给定一个矩形，放一个东西的方案数。 思路：q很大。。应该是先预处理出来直接调用答案。。。计数问题累加性。。应该是前缀和之类。。需要做的就是怎么标记。。我的做法是竖着放和横着放的个数分开来存。从左往右从上往下，每次标记到后一个点。然后二维的前缀和。然后每次询问的时候，去掉最上边和最左边两条边界上对应的多加的点。 #include <cstdio> #include <cstring> #include <iostream> …

http://codeforces.com/contest/22/problem/C 题意：要求用n个点m条边构造一个不允许有重边的图，满足当去掉点v的时候，剩下的n-1个不联通。如果有答案输出任意，没答案输出-1. 思路：首先如果n个点要联通。。至少有n-1条边，此时为一棵树。但是是不是边越多越好呢？显然是不可以的。满足去掉一个点使得n-1个点不联通的情况为，存在一个点u只和v相连，不和任意任何其他点相连，那么当去掉v点，u点就变成不可到达了。边数最多的情况就是，除了v点以外的n-1个点，每个点的度都是n-2(去掉自身以及u点还有n-2个点)，，那么除去u点以外的n-1个点的度数就是（n-1）(n-2)，边数则 …

http://codeforces.com/contest/29/problem/C 题意：给出n个边的关系，保证可以构成一条链。正向或者反向输出这个链。 思路：由于下标很大(1E9)，而关系个数只有1E5..需要离散化。。而且离散化的同时不能丢失边的关系。。。实际上。。直接用vector+map就好了。。。 map >e;即可。然后找到一个度为1的点。。做个dfs... /* *********************************************** Author :111qqz Created Time :2015年12月30日 星期三 19时55分15秒 File Name …

http://codeforces.com/problemset/problem/31/C 题意：给出n个借用教室的时间安排，可能会有冲突。要求恰好去掉一个时间安排使得剩下的时间安排不冲突。问多多少种方案。 思路：首先一个直觉是。。除非初始就没有任何冲突。。不然这个答案不会很大。。 如果没有任何冲突，那么答案为n，直接输出一遍就好。 以l为第一关键字，r为第二关键字升序sort下。 如果有一个冲突，那么要看是否有包含关系，如果有，需要去掉大的这个，方案数为1.如果只是相交，那么可以去掉任意一个。方案数为2. 如果有两个冲突，我要看这两个冲突涉及到几个时间安排，如果涉及到4个或者时间安排，那么不可能全部解决，die掉。 如果这两个冲突 …

http://codeforces.com/contest/27/problem/C 题意：给出一个序列，问是否存在一个disordered的子序列。。输出长度并输出组成子序列的下表（1..n）。如果有多组，输出任意一组。 disordered的意思是。。升序或者降序（不严格也可以)之外的情况。 思路： 首先我们可以知道，我们要找的子序列至少需要三个点。因为两个点怎么看都是有序的。而如果有k个点（k>3）组成的子序列存在。。那么机智得去掉其中一些点，可以只剩三个 ，同样满足题意。所以我们只需要找到三个点即可。如果把点以下标为横坐标，值为纵坐标花在坐标系上，就是找一个v型或者倒v型的三个点。 第二，我们可以将找三个点的问题转化成 …

http://codeforces.com/contest/30/problem/C 题意：给出n个target在一个二维平面上。给出每个target的坐标，出现的时间，以及击中的概率。target出现之后就会瞬间消失，枪移动的单位速度为1，射击不需要时间。问能击中的target的最大期望是多少。 思路：路径dp。。。按照时间升序排列。 dp[i]表示到第i个target出现的时候的期望。 /* *********************************************** Author :111qqz Created Time :2015年12月29日 星期二 18时14分45秒 File Name …

http://codeforces.com/problemset/problem/14/C 题意：给出四条边的坐标，问能否形成一个边与坐标轴平行的矩形。边可能退化成点。 思路：首先第一步，检查有没有边退化成点以及是否有不平行的边。 第二步，检查两个方向的边是否各有两条。。 第三步，将所有点的坐标排序。。然后看8个点是否会因为重合而变成4个.。 /* *********************************************** Author :111qqz Created Time :2015年12月29日 星期二 16时28分28秒 File Name :code/cf/problem/14C.cpp …