作者存档：edward_mj

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1822
【算法分析】
非常裸的模型。
求圆到线段的距离可以利用海伦公式+勾股定理。
然后剩下的就是二分时间+一个二分图匹配了。因为巫妖可能发多次，所以用网络流实现。
【其它】之前WA了∞遍，今天重敲。。。我靠，1Y。
【CODE】
#include #include #include #include #include #define sqr(x) ((x)*(x))
#define eps 1e-6
using namespace std;
const int maxn=205*2;
int Li,Wi,Tr;
bool v[maxn][maxn];
struct Lich_t{int x,y,r,t;}Lich[maxn];
struct Wise_t{int x,y;}Wise[maxn];
struct Tree_t{int x,y,r;}Tree[maxn];
struct Graph_t{
struct edge{int x,y,c;edge *next,*op;}g[maxn*maxn*4],*ls[maxn],*cur[maxn],*fa[maxn];
int d[maxn],gap[maxn],Flow,e,S,T;

void clr(){e=0; memset(ls,0,sizeof(ls));}

void add(int x,int y,int c){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
}

void relabel(int p){
cur[p]=ls[p];
int mm=T;
for (edge *t=ls[p];t;t=t->next)
if (t->c && d[t->y] mm=d[t->y];
d[p]=mm+1;
}

void change(){
Flow++;
for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c–;
fa[i]->op->c++;
}
}

void sap(){
int i;
Flow=0;
for (i=1;i<=T;i++){
cur[i]=ls[i];
d[i]=0;
gap[i]=0;
}
gap[0]=T;
i=S;
while (d[S] for (edge *&t=cur[i];t;t=t->next)
if (t->c && d[t->y]+1==d[t->x]) break;
if (cur[i]){
fa[cur[i]->y]=cur[i];
i=cur[i]->y;
if (i==T){
change();
i=S;
}
}else{
if (!–gap[d[i]]) break;
relabel(i);
++gap[d[i]];
if (i!=S) i=fa[i]->x;
}
}
}
}G;

inline int dis(int &X1,int &Y1,int &X2,int &Y2){return sqr(X1-X2)+sqr(Y1-Y2);}
inline double S(double &a,double &b,double &c){
double p=(a+b+c)/2;
return sqrt(p*(p-a)*(p-b)*(p-c));
}

bool Can(Lich_t L,Wise_t W){
if (dis(L.x,L.y,W.x,W.y)>sqr(L.r)) return false;
for (int i=1;i<=Tr;i++){
Tree_t &T=Tree[i];
double a,b,c,d;
a=sqrt(dis(W.x,W.y,T.x,T.y));
b=sqrt(dis(W.x,W.y,L.x,L.y)); if (b==0) b=eps;
c=sqrt(dis(L.x,L.y,T.x,T.y));
if (b*b+c*c>a*a && a*a+b*b>c*c) d=S(a,b,c)*2/b;
else d=min(a,c);
if (d+eps<=T.r) return false;
}
return true;
}

void init(){
ios::sync_with_stdio(false);
memset(v,false,sizeof(v));
cin >> Li >> Wi >> Tr;
for (int i=1;i<=Li;i++)
cin >> Lich[i].x >> Lich[i].y >> Lich[i].r >> Lich[i].t;
for (int i=1;i<=Wi;i++)
cin >> Wise[i].x >> Wise[i].y;
for (int i=1;i<=Tr;i++)
cin >> Tree[i].x >> Tree[i].y >> Tree[i].r;
for (int i=1;i<=Li;i++)
for (int j=1;j<=Wi;j++)
if (Can(Lich[i],Wise[j]))
v[i][j]=true;
}

bool Try(int Limit){
G.clr(); G.S=Li+Wi+1; G.T=Li+Wi+2;
for (int i=1;i<=Li;i++)
G.add(G.S,i,Limit/Lich[i].t+1);
for (int i=1;i<=Wi;i++)
G.add(Li+i,G.T,1);
for (int i=1;i<=Li;i++)
for (int j=1;j<=Wi;j++)
if (v[i][j]) G.add(i,Li+j,1);
G.sap();
if (G.Flow==Wi) return true;
return false;
}

void solve(){
int l=0,r=1000000000,mid;
while (l mid=(l+r)/2;
if (Try(mid)) r=mid;
else l=mid+1;
}
if (!Try(l)) cout << "-1n";
else cout << l << "n";
}

int main(){
init();
solve();
return 0;
}

【题目链接】http://ace.delos.com/ioiupload?init=1&a=nejLCFTaRn6
或者八中：http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1776
不过八中由于是Windows，所以要手写栈~没事可以去写一写~
Pascal的话就不用怕了，直接开编译开关：{$M 10000000}
【题目大意】
n<=20 0000
树上的每个点都涂了一种颜色，
对于每种颜色，问属于这种颜色的点中的最远点对是多少?
边权全是1。
时限2s per data
【算法分析】
做法1：
一开始看比较直观的就是对树进行基于点的分治。
时间复杂度O(n lg n)。
空间复杂度O(n lg n)。
但是由于常数过大，终究逃脱不了TLE的命运。

做法2：
首先我们画出一棵树。
然后可以发现,无论怎么画，对于同一种颜色，最长路出现时，其中一个点必然是这颗树中深度最大的点。
下面给出我的证明：
设x,y,z为三个同颜色的点，x为所有该种颜色中的深度最大的一个点。
那么我们现在要证命题：dis(y,z)<=max(dis(x,y),dis(x,z))。

可以用这个图先直观地感受一下。
下面我们采用反证法。
题设：dis(y,z)>max(dis(x,y),dis(x,z))。
将这个不等式转化成一个不等式组：
dep[x]+dep[y]-dep[LCA(x,y)]*2dep[x]+dep[z]-dep[LCA(x,z)]*2dep[x]-dep[z]<(dep[LCA(x,y)]-dep[LCA(y,z)])*2  ————①
dep[x]-dep[y]<(dep[LCA(x,z)]-dep[LCA(y,z)])*2  ————② 我们对这个两个不等式进行放大，得：
dep[LCA(x,y)]-dep[LCA(y,z)]>0
dep[LCA(x,z)]-dep[LCA(y,z)]>0
（之所以可以这样做，是因为dep[x]>=dep[z] && dep[x]>=dep[y]）

下面进行分类讨论：
1、dep[LCA(x,y)]<=dep[LCA(y,z)]。那么①式显然不成立。矛盾。
2、dep[LCA(x,y)]>dep[LCA(y,z)]。那么z的位置有两种可能。
①z是y的子孙。这样显然与题设矛盾。因为dis(x,z)>=dis(y,z)。（x到z的路径包括了y到z的路径）
②LCA(y,z)在“LCA(x,y)到y”的路径上。那么在这种情况下，我们看②式。

显然，此时LCA(x,z)=LCA(y,z)，所以②式不可能成立。于是又与题设矛盾。
所以，综上所述，①②两式不可能同时成立。于是题设不可能成立。
于是反证出命题：dis(y,z)<=max(dis(x,y),dis(x,z)) 正确。 有这个了结论，那么就可以找出每种颜色里深度最大的。然后其它的点都和它算一下距离就可以了。这里面用到了最近公共祖先(LCA)的经典算法。
【时间复杂度】O(n)
【空间复杂度】O(n)
【其它】这个代码在衡阳八中A不了，因为会栈溢出。
【时间和空间状况】
> Run 1: OK [0.011 secs, 8600 KB]
> Run 2: OK [0.011 secs, 8600 KB]
> Run 3: OK [0.022 secs, 8600 KB]
> Run 4: OK [0.022 secs, 8600 KB]
> Run 5: OK [0.011 secs, 8600 KB]
> Run 6: OK [0.140 secs, 11636 KB]
> Run 7: OK [0.151 secs, 11372 KB]
> Run 8: OK [0.378 secs, 15116 KB]
> Run 9: OK [0.367 secs, 13972 KB]
> Run 10: OK [0.464 secs, 17840 KB]
> Run 11: OK [0.572 secs, 17924 KB]
> Run 12: OK [0.745 secs, 22880 KB]
> Run 13: OK [0.680 secs, 22620 KB]
【CODE】
/*
ID:jie22221
TASK:cowpol
LANG:C++
*/
#include #include #include #include #define clr(a) memset((a),(0),sizeof(a))
using namespace std;
const int maxn=200005;
struct edge{int y;edge *next;};
int n,k;
int ans[maxn],belong[maxn],d[maxn],mdp[maxn],f[maxn];
bool v[maxn];

struct Link_t{
edge *ls[maxn];
void add(int x,int y){
edge *t=(edge*)malloc(sizeof(edge));
t->y=y; t->next=ls[x]; ls[x]=t;
}
}G,Q;

void init(){
clr(G.ls);
clr(Q.ls);
clr(d);
clr(mdp);
clr(v);
clr(ans);
scanf("%d%d",&n,&k);
for (int x,i=1;i<=n;i++){
scanf("%d%d",&belong[i],&x);
G.add(x,i);
G.add(i,x);
}
}

void dfs(int p,int fa){
for (edge *t=G.ls[p];t;t=t->next)
if (t->y!=fa){
d[t->y]=d[p]+1;
dfs(t->y,p);
}
}

void make_Q(){
for (int i=1;i<=n;i++)
if (!mdp[belong[i]] || d[i]>d[mdp[belong[i]]])
mdp[belong[i]]=i;
for (int i=1;i<=n;i++)
if (mdp[belong[i]]!=i){
Q.add(i,mdp[belong[i]]);
Q.add(mdp[belong[i]],i);
}
}

int gf(int p){
if (f[p]==p) return p;
return f[p]=gf(f[p]);
}

void solve(int p,int fa){
f[p]=p;
for (edge *t=G.ls[p];t;t=t->next)
if (t->y!=fa)
solve(t->y,p);
v[p]=true;
for (edge *t=Q.ls[p];t;t=t->next)
if (v[t->y])
ans[belong[p]]=max(ans[belong[p]],d[t->y]+d[p]-2*d[gf(t->y)]);
f[p]=fa;
}

int main(){
freopen("cowpol.in","r",stdin);
freopen("cowpol.out","w",stdout);
init();
dfs(1,0);
make_Q();
solve(1,0);
for (int i=1;i<=k;i++)
printf("%dn",ans[i]);
}

【题目链接】http://ace.delos.com/ioiupload?init=1&a=CKerK76g6Pn
or 八中
【题目大意】
给定以1为根的一棵树。点数<=10^5
然后每个点按输入顺序被染色。
每次染色前都输出，从根到该结点的路径上，有多少个点被染色过了？
【算法分析】
首先，假如一个点染色，会影响到哪些点呢？
没错，就是以他为根的子树上的所有点。
所以我们按DFS序遍历的话，会得出一张线性表，在这个表上，每一个点为根的子树就会连在一起~
进而可以用线段树或者树状数组解决。
当然，树状数组好些多了。
【其它】1Y
【CODE】
/*
ID:jie22221
TASK:slowdown
LANG:C++
*/
#include #include #include #include using namespace std;
const int N=105555;
struct edge{int y;edge *next;}*ls[N];
int n,times;
int St[N],Ed[N],w[N];

void addedge(int x,int y){
edge *t=(edge *)malloc(sizeof(edge));
t->y=y; t->next=ls[x]; ls[x]=t;
}

void init(){
memset(ls,0,sizeof(ls));
scanf("%d",&n);
for (int i=1,x,y;i scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
}

void dfs(int p,int fa){
St[p]=++times;
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa)
dfs(t->y,p);
Ed[p]=times;
}

int Get_Sum(int p){
int res=0;
for (int i=p;i;i-=i&-i)
res+=w[i];
return res;
}

void Add(int p,int x){
for (int i=p;i<=n;i+=i&-i)
w[i]+=x;
}

void solve(){
memset(w,0,sizeof(w));
for (int i=1,x;i<=n;i++){
scanf("%d",&x);
printf("%dn",Get_Sum(St[x]));
Add(St[x],1);
Add(Ed[x]+1,-1);
}
}

int main(){
freopen("slowdown.in","r",stdin);
freopen("slowdown.out","w",stdout);
init();
dfs(1,0);
solve();
return 0;
}