1、前言
今天AC了一道神题，应该说神一般的AC了一道题。我自己都不清楚这就是正解，还有前人给他附上了一个高端的名词——欧拉公式。显然有一种歪打正着的感觉。
2、暴力摩托
大概题意：给出一张无向图，每次给出起点和终点，要求从起点到终点的路的权值最大与最小之差最小。
总结：做过很多次了，最小生成树的一种特殊求法。
题解：Kruskal算法求最小生成树。
3、Fish玩圈圈
大概题意：给出n个圈，他们不相切，且任意3个圆不共点，求这些圆将平面圈出封闭区域的个数。
总结：没错这就是那道要用到欧拉公式的题目，只要你知道这个公式，答案就呼之欲出了，然而我并不知道，但是通过各种奇怪的圆的组合，找到了一个奇怪的规律：封闭区域个数等于圆的交点个数加上连通块个数。这没有道理啊，但是实在没办法了就搞了这个奇怪的东西上去了。最后知道真相的我才明白这就是欧拉公式的变形（变形都算不上）。
题解：欧拉公式：F=V-E，表示封闭区域的个数等于这些圆之间交点的个数+每个圆被交点分出来的弧的个数。由于这道题还要考虑圆与圆之间的相离问题，故需要再加上圆的连通块个数。实际编写过程中，弧的个数显然不怎么好求，但是我们可以发现，弧的个数=点的个数*2，即V=2*E。那么答案也就出来了：ans=E+x，x表示连通块个数。我们只需要在读入圆的时候求得任意两个圆之间是否相交，求得交点数；同时视每个圆为一个节点，将他们连边，最后用并查集搞搞就得到连通块个数了。
---------------------------------------------------------------------------------------------------
#include<cstdio>
#include<cmath>
#define MAXN 1005
struct Circle { double x,y,r; } a[MAXN];
struct Edge { int u,v; } edge[MAXN*MAXN];
int n,set[MAXN],tot,totx;
bool dcmp(double o) { return (o>=1e-3); }
double abs(double o) { return dcmp(o-0)?o:-o; }
bool link(int i,int j)
{
double dis=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
return (dcmp(a[i].r+a[j].r-dis) && dcmp(dis-abs(a[i].r-a[j].r)));
}
int check(int o) { return (o==set[o]?o:set[o]=check(set[o])); }
int main()
{
freopen("Ring.in","r",stdin);
freopen("Ring.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%lf %lf %lf",&a[i].x,&a[i].y,&a[i].r);
for (int j=1;j<=i-1;j++)
if (link(i,j)) tot++,edge[tot]=(Edge){i,j};
}
for (int i=1;i<=n;i++) set[i]=i;
for (int i=1;i<=tot;i++)
{
int c1=check(edge[i].u),c2=check(edge[i].v);
if (c1!=c2) set[c1]=c2;
}
for (int i=1;i<=n;i++) totx+=i==set[i];
printf("%d",tot*2+totx);
return 0;
}
---------------------------------------------------------------------------------------------------
4、Fish接球
大概题意：给出n个球，对于第i个数，出现的时间为t[i]，权值为w[i]。现有m个篮子，第i个篮子最大权值为max[i]。对于每一个时间，至多取出1个数放入当前的篮子中，若当前篮子容量不够，就扔掉然后使用另一个。求最多可以取多少个球。
总结：虽然我觉得这明显是动态规划，但是实在乏力写不出。即便10分是暴力可接受的范围，但是我犯了一个非常二的错误，数组开小了20倍。这样就有40分了。但其实本身搜索过程中是有个地方写错了的，可能数据没有考虑这些吧，修改之间并没有改变分数。
题解：动态规划，暂时未知。
5、Fish下棋
大概题意：给出一个n*n的0-1目标地图，要求从空地图转换为目标地图。从空地图起每次可以给某一列或某一行放0或1，对于任意位置，如果存在相同数则将数字叠加一起，若不同则最上方的0和1同时消失。求放棋子的最小次数。
题解：全场最高分就是输出Impossible，没错。