题意：有两排城市，这两排之间有一些城市之间有连接的道路，给出所有道路，问有多少道路是相交的，交点不为城市所在点。
思路：开始暴力的做出来了，时间还挺短的，但知道这题可以用树状数组做，就做了一下。我们把所给的公路的坐标排序，按a升序，a相同按b升序。我们可以看出，每个点跟自己左上角和右下角的点都有交点，为了不重复统计，只统计每个点左上角的点数。就是求逆序数的个数，然后用点的个数减去就可以了。
#i...
阅读全文
Integer Inquiry
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8840 Accepted Submission(s): 2255
Problem Description
One of the first users of BIT's new supercomputer was Chip Diller. He extended his exploration of powers of 3 to go from 0 to 333 and he explored taking various sums of those numbers.
``This supercomputer is great,...
阅读全文
爱你，在这深深的夜色里看星星，总想起你闪耀着活泼的双眸那是天空最美的一颗哦，不，请原谅我竟然用这庸俗的比喻，形容你脱俗的美丽。请原谅，我文字的拙劣，但我要说即使李杜再生，文曲下凡，也一定会惊诧于你的美丽而笔尖羞涩的。爱你，在灿烂的阳光下看清爽的天空都映着你的影子，你的一颦一笑，是我全部的天空没有你，我失去了唯一的天地。爱你，在寒冷的冬季你的温柔，温暖我冰冻的心你的善良，打开我尘封已久的门你那充...
阅读全文
叉积： (其值等于两向量组成的三角形的有向面积的两倍)
AXB = A.x * B.y - A.y * B.x
Vector Cross(Vector A, Vector B) { return(A.x * B.y - A.y * B.x); }
性质：
AXB的符号判断（夹角小于180度）
AXB > 0 ：则B在A的左边
AXB < 0 ：则B在A的右边
AXB = 0 ：则A和B共线，方向同向或反向
----------------------------------------------------------------------------------------------------
zju1041
问题描述：...
阅读全文
旋转卡壳求凸包的直径的平方
板子题
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
struct Point {
int x, y;
Point(int x=0, int y=0):x(x),y(y) { }
};
typedef Point Vector;
Vector operator - (const Point& A, const Point& B) {
return Vector(A.x-B.x, A.y-B.y);
}
int Cross(const Vector& A, const Vector&a...
阅读全文
题意：
给定一个N*M的地图，地图上有若干个man和house，且man与house的数量一致。man每移动一格需花费$1（即单位费用=单位距离），一间house只能入住一个man。现在要求所有的man都入住house，求最小费用。
分析：
二分图的最大匹配
我采用的是最小费用最大流算法，重点在建图。
Code:
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include ...
阅读全文
点击打开链接
分析：
求最大流
建图：
拆点 牛拆成左边与食物相连的左牛 和 右边与饮料相连的右牛
1、s->食物 连边
2、食物->左牛
3、左牛->右牛
4、右牛->饮料
5、饮料->t
边的方向为 s->食物->左牛->右牛->饮料->t
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn =...
阅读全文
POJ 3436 ACM Computer Factory
电脑公司生产电脑有N个机器，每个机器单位时间产量为Qi。
电脑由P个部件组成，每个机器工作时只能把有某些部件的半成品电脑(或什么都没有的空电脑）变成有另一些部件的半成品电脑或完整电脑(也可能移除某些部件）。求电脑公司的单位时间最大产量，以及哪些机器有协作关系，即一台机器把它的产品交给哪些机器加工。
Sample input
3 4
15 0 0 0 0 1 0
10 0 0 0 0 1 1
30 0 1 2 1 1 1
3 ...
阅读全文
点击打开链接
多源多汇最大流，虚拟一个源点s'和一个汇点t'，原来的源点、汇点向它们连边。
#include<cstdiO>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 500 + 5;
const int INF = 100000000;
struct Edge{
int from, to, cap, flow;
};
struct Dinic{
int n, m, s, t;
ve...
阅读全文
题意：
有K台挤奶机器和C头牛(统称为物体），每台挤奶机器只能容纳M头牛进行挤奶。现在给出dis[K + C][K + C]的矩阵，dis[i][j]若不为0则表示第i个物体到第j个物体之间有路，dis[i][j]就是该路的长度。（1 <= K <= 30,1 <= C <= 200）
现在问你怎么安排这C头牛到K台机器挤奶，使得需要走最长路程到挤奶机器的奶牛所走的路程最少，求出这个最小值。
分析：
利用Floyd算法求出每个奶牛到每个挤奶机的最短距离。
则...
阅读全文