总体上来说JSOI2010是一套好题(话说连通数这样的题是怎么混进来的233= =），然后就是无限T,WA,RE。

     给这一套题分一下难度吧：奇（SANG)神(XIN)无(BING)比(KUANG):1824 下棋问题。 1825 蔬菜庆典。

   难度适中：1820 快递服务 1822 冷冻波 1823满汉全席

   比（SHUA)较(SHUI)简(QING)单(RU):1821 部落划分 1826 缓存交换 2208 连通数

   比较简单——1821 部落划分

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int a[1001][2];
int fa[1001];
struct node{int l,r;double sum;}bian[1000001];
int i,j,m,n,p,k,tot,p1,p2;
inline bool cmp(node a,node b)
 { return a.sum<b.sum; }
int getfather(int num)
{ if (fa[num]==num) return num;
 fa[num]=getfather(fa[num]);
 return fa[num];
}
int main()
{scanf("%d%d",&n,&k);
  for (i=1;i<=n;i++)
   scanf("%d%d",&a[i][0],&a[i][1]);
for (i=1;i<=n;i++)
 for (j=i+1;j<=n;j++)
  {  bian[++tot].l=i;
     bian[tot].r=j;
     bian[tot].sum=(double)sqrt((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1]));
}
sort(bian+1,bian+tot+1,cmp);
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=tot;i++)
 { p1=getfather(bian[i].l);
   p2=getfather(bian[i].r);
    if (p1==p2) continue;
     if (n==k) break;
     n--;
     fa[p1]=p2;
}
printf("%.2lf\n",bian[i].sum);
//for(;;);
return 0;
}

 1826 缓存交换 

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
struct node{int num;int len;}heap[1000001];
struct node1{int num;int next;}a[100001];
node b[100001];
int fox[100001],flag[100001];
int i,j,m,n,p,k,k1,ans;
int len[100001];
inline bool cmp(node a,node b) {return a.num<b.num;}
void up(int num)
 {int t; while (num>1&&heap[num].len>heap[num/2].len)
         {  t=len[heap[num].num]; len[heap[num].num]=len[heap[num/2].num];
            len[heap[num/2].num]=t; 
            t=heap[num].num; heap[num].num=heap[num/2].num;
            heap[num/2].num=t; 
            t=heap[num].len; heap[num].len=heap[num/2].len;
            heap[num/2].len=t;
            num/=2;
            }
} 
void down(int num)
 { int t; while (num*2<=k&&(heap[num*2].len>heap[num].len||heap[num*2+1].len>heap[num].len))
           {  if (heap[num*2].len>heap[num*2+1].len)
              {t=len[heap[num].num]; len[heap[num].num]=len[heap[num*2].num];
            len[heap[num*2].num]=t; 
            t=heap[num].num; heap[num].num=heap[num*2].num;
            heap[num*2].num=t; 
            t=heap[num].len; heap[num].len=heap[num*2].len;
            heap[num*2].len=t;
            num*=2; } else
               {t=len[heap[num].num]; len[heap[num].num]=len[heap[num*2+1].num];
            len[heap[num*2+1].num]=t; 
            t=heap[num].num; heap[num].num=heap[num*2+1].num;
            heap[num*2+1].num=t; 
            t=heap[num].len; heap[num].len=heap[num*2+1].len;
            heap[num*2+1].len=t;
            num*=2;  num++;}
}
}
inline int read()
{
    char ch;int f=0;
    int a=0;while(!((((ch=getchar())>='0')&&(ch<='9'))||(ch=='-')));  
    if(ch!='-')a*=10,a+=ch-'0';else f=1;
    while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0';  
    if(f)a=-a;return a;  
}
int main()
 {
 scanf("%d%d",&n,&m);
   for (i=1;i<=n;i++)
     a[i].num=read(),b[i].num=a[i].num,b[i].len=i;
    sort(b+1,b+n+1,cmp);
    k=0;
    for (i=1;i<=n;i++)
     { if (b[i].num!=b[i-1].num) k++;
         a[b[i].len].num=k;
         }
    for (i=1;i<=n;i++)
      {  a[fox[a[i].num]].next=i;
         fox[a[i].num]=i;
         }
   for (i=1;i<=k;i++)
     a[fox[i]].next=n+1;
     k1=0;
     k=0;
  for (i=1;i<=n;i++)
   { if (flag[a[i].num]) { heap[len[a[i].num]].len=a[i].next;
      down(len[a[i].num]); up(len[a[i].num]); }
     else {  if (k<m) {flag[a[i].num]=1;heap[++k].len=a[i].next; ans++; heap[k].num=a[i].num; len[a[i].num]=k; up(k); }
              else { flag[heap[1].num]=0;
                    flag[a[i].num]=1; 
                   heap[1].num=a[i].num;
                   heap[1].len=a[i].next; ans++; len[a[i].num]=k; down(1); }
              }
}
  printf("%d\n",ans);
  return 0;   
}  

2208 连通数

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int vis[2001];
int fox[2001];
char c[2001];
int que[2001];
int l,r,ans;
struct node{int ed;int before;}s[5000001];
int i,j,m,n,p,k,k1;
void add(int p1,int p2)
 { s[++k1].ed=p2; 
 s[k1].before=fox[p1]; 
 fox[p1]=k1;}
 int main()
 {scanf("%d",&n);
   for (i=1;i<=n;i++)
    { scanf("%s",&c);
       for (j=1;j<=n;j++)
        if (c[j-1]=='1') add(i,j);
}
for (int i1=1;i1<=n;i1++)
 { que[1]=i1;
   memset(vis,0,sizeof(vis));
   vis[i1]=1;
   l=r=1;
   while (l<=r) 
    { p=que[l];
      for (i=fox[p];i;i=s[i].before)
        if (!vis[s[i].ed])
         {que[++r]=s[i].ed;
           ans++;
           vis[s[i].ed]=1;
           }
        l++;
        }
}
   printf("%d\n",ans+n);
   return 0;
}

 难度适中——1820 快递服务

     一开始给我的感觉是四维DP，F[I][J][K][L]，到第I个请求，三辆车的点是J,K,L。然后发现当I确定时，J,K,L中必然有一个时第I个请求的地点。所以可以压掉一维，时间效率（N^3)。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int i,j,m,n,p,k,flag,ans=(int)1e9,last;
int f[2][201][201];
int a[201][201];
void doit(int &x,int y) { x=min(x,y);}
int main()
 {
          scanf("%d",&m);
   for (i=1;i<=m;i++)
    for (j=1;j<=m;j++) scanf("%d",&a[i][j]);
    memset(f,60,sizeof(f));
    f[0][1][2]=0;
    last=3;
   for (flag=1,i=1;scanf("%d",&p)!=EOF;i++,flag^=1)
    {   memset(f[flag],60,sizeof(f[flag]));
      if (p==4)
        p=4;
        for (i=1;i<=m;i++)
          for (j=1;j<=m;j++)
            if (f[flag^1][i][j]<(int)1e9)
             {    if (i==p)
                   { doit(f[flag][j][last],f[flag^1][i][j]);
                     continue;
                     }
                  if (j==p)
                  { doit(f[flag][i][last],f[flag^1][i][j]);
                    continue;
                    }
                  if (last==p)
                  { doit(f[flag][i][j],f[flag^1][i][j]);
                     continue;
                     }
                  doit(f[flag][j][last],f[flag^1][i][j]+a[i][p]);
                  doit(f[flag][i][last],f[flag^1][i][j]+a[j][p]);
                  doit(f[flag][i][j],f[flag^1][i][j]+a[last][p]);
                  }
          last=p;
  }
 flag^=1;
 for (i=1;i<=m;i++)
   for (j=1;j<=m;j++)
     ans=min(ans,f[flag][i][j]);
     printf("%d\n",ans);
}

1822 冷冻波（正解暂缺)

     典型的二分答案+最大流验证。貌似没有分类讨论线段到圆心的距离（如果圆心作垂线不在线段上要分类讨论），但是竟然能过数据233，请大大们自行去YY一下= =应该很好讨论。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int i,j,m,n,p,k,k1=1,K,st,ed,l,r,mid;
struct node{int ed,before,flow;}s[100001],s1[100001];
int fox1[100001],fox[100001],dis[1001],que[1001];
struct node1{int x,y,r,sum;}a[100001],b[100001],c[100001];
inline int sqr(int x)
{ return x*x; }
bool check(int x,int y)
 { double A,B,C,P,SUM;
 int i; A=(double)sqrt(sqr(a[x].x-b[y].x)+sqr(a[x].y-b[y].y));
       if (A>a[x].r) return false;
     for (i=1;i<=k;i++)
     {  A=(double)sqrt(sqr(a[x].x-b[y].x)+sqr(a[x].y-b[y].y));
       if (A>a[x].r) return false;
       B=(double)sqrt(sqr(a[x].x-c[i].x)+sqr(a[x].y-c[i].y));
       C=(double)sqrt(sqr(b[y].x-c[i].x)+sqr(b[y].y-c[i].y));
       if (A==B+C) continue;
       P=(A+B+C)/2.0;
       SUM=(double)sqrt(P*(P-A)*(P-B)*(P-C));
      if (SUM*2/A<c[i].r) return false;
      }
 return true;
}
inline int bfs()
 { int i,j,p,k,l,r;
   memset(dis,-1,sizeof(dis));
    l=r=1;
    dis[st]=0;
   que[1]=st;
   while (l<=r)
    { p=que[l];
      for (i=fox[p];i;i=s[i].before)
        if (s[i].flow>0)
        if (dis[s[i].ed]==-1)
         { 
           que[++r]=s[i].ed;
           dis[s[i].ed]=dis[p]+1;
           }
      l++;
}
 if (dis[ed]==-1) return 0;
 return 1;
}
int dfs(int num,int flow)
 {  int i,a,p,nowans=0;
   if (num==ed) return flow;
     for (i=fox[num];i&&flow;i=s[i].before)
       if (s[i].flow>0&&dis[s[i].ed]==dis[num]+1)
        if(a=dfs(s[i].ed,min((int)s[i].flow,flow)))
         { s[i].flow-=a;
           s[i^1].flow+=a;
           flow-=a;nowans+=a;
           }if (!nowans) dis[num]=(int)1e9;
   return nowans;
}
            
int maxflow()
  { int i,j;
  int ans=0;
    while (bfs())
    { j=dfs(st,(int)1e9);  while (j) ans+=j,j=dfs(st,(int)1e9); }
 return ans;
}
void add(int p1,int p2)
 { s1[++k1].ed=p2; s1[k1].flow=1; s1[k1].before=fox1[p1]; fox1[p1]=k1;
   s1[++k1].ed=p1; s1[k1].flow=0; s1[k1].before=fox1[p2]; fox1[p2]=k1; }
   void add1(int p1,int p2,int flow)
 { s[++k1].ed=p2; s[k1].flow=flow; s[k1].before=fox[p1]; fox[p1]=k1;
   s[++k1].ed=p1; s[k1].flow=0; s[k1].before=fox[p2]; fox[p2]=k1; }
int main()
{
scanf("%d%d%d",&n,&m,&k);
st=n+m+1;
ed=st+1;
  for (i=1;i<=n;i++)
   scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].r,&a[i].sum);
  for (i=1;i<=m;i++)
   scanf("%d%d",&b[i].x,&b[i].y),add(n+i,ed);
  for (i=1;i<=k;i++)
   scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].r);
  for (i=1;i<=n;i++)
   for (j=1;j<=m;j++)
     if (check(i,j))
      add(i,j+n);
K=k1;
for (l=0,r=5000000;mid!=(l+r)>>1;)
 { mid=(l+r)>>1;
  k1=K;
    memset(s,0,sizeof(s));
    memcpy(s,s1,sizeof(s));
    memcpy(fox,fox1,sizeof(fox1));
    for (i=1;i<=n;i++)
      add1(st,i,mid/a[i].sum+1);
    if (maxflow()==m) r=mid; else l=mid;
}
if (r==5000000) printf("-1\n");else printf("%d\n",r);
}

    1823——满汉全席 

    典型的2-SAT例题。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int i,j,m,n,p,k,k1,flag,p1;
char c;
struct node{int ed,before;}s[10001];
node s1[10001];
int fox[10001],fox1[10001],ssc[10001],vis[10001],numk[10001],kk;
int t;
void add(int p1,int p2)
 { s[++k].ed=p2; 
 s[k].before=fox[p1]; 
 fox[p1]=k;
 s1[++k1].ed=p1;
   s1[k1].before=fox1[p2]; 
   fox1[p2]=k1;
}
void dfs(int num)
 { int i;
    vis[num]=true;
   for (i=fox[num];i;i=s[i].before)
      if (!vis[s[i].ed]) dfs(s[i].ed);
   ssc[++p]=num;
}
void ndfs(int num)
  { int i;
     numk[num]=kk;
      vis[num]=true;
       for (i=fox1[num];i;i=s1[i].before)
         if (!vis[s1[i].ed]) ndfs(s1[i].ed);
} 
void doit()
 {  p=0;
    memset(vis,false,sizeof(vis));
     for (i=1;i<=n;i++)
       if (!vis[i]) dfs(i);
         memset(vis,false,sizeof(vis));
     for (i=n;i>=1;i--)
       if (!vis[ssc[i]])
          { kk++;
            ndfs(ssc[i]);
            }
}
int main()
{ 
    scanf("%d",&t);
  for (;t--;)
  {   if (t==2)
    t=2;
      scanf("%d%d",&n,&m); k1=k=0;
    memset(ssc,0,sizeof(ssc));
    memset(s,0,sizeof(s));
    memset(s1,0,sizeof(s1));
    memset(fox,0,sizeof(fox));
    memset(fox1,0,sizeof(fox1));
    memset(numk,0,sizeof(numk));
    kk=0;
    for (i=1;i<=m;i++)
    {  for (c=getchar();c!='h'&&c!='m';c=getchar());
        if (i==3)
           i=3;
         scanf("%d",&p);
         if (c=='m') p+=n;
         for (c=getchar();c!='h'&&c!='m';c=getchar());
         scanf("%d",&p1);
         if (c=='m') p1+=n; 
         if (p>n) add(p-n,p1); else add(p+n,p1);
         if (p1>n) add(p1-n,p); else add(p1+n,p);
}
 n*=2;
    doit();
 n/=2;
    flag=0;
    for (i=1;i<=n;i++)
     if (numk[i]==numk[i+n])
     {  printf("BAD\n");
        flag=1;
        break;
     }
     if (!flag) printf("GOOD\n");
     }
}

SXBK——1824 下棋问题

  看这题看了很长时间，YY了无数种方案全部失败，最后对着花神大大的程序，才终于知道了做法(OTZ 花神大大）

  加入一个点时，将之前加入的所有点根据当前点分为4个象限，在四个象限中都能得到一条单调上升或下降的序列（注意：这里的单调队列指的是找到一个Y比当前结尾高（低）的点就加入，具体可以考虑什么样的点能和当前点构成无障碍四方形）。这个点添加的贡献就是四个队列中的点数和，但是还要考虑删除的贡献。（注，接下来的点都指单调队列中的点）相邻象限中的四方形不会产生贡献，考虑相对象限的点。对于1,3象限，枚举在第一象限中的每一个点，然后在第二象限中找到第一个Y值比枚举点小的点，在第三象限中找到X值比这个点小的点数，然后在第四象限中找X值比枚举点小的X最大的点，然后得出Y比他小的数，两者相减得出答案。由于X,Y都有单调性，所以枚举时可以一直向下，时间效率（N^2).

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5005;
long long Ans[2];
struct node{int x,y,id;}a[N],b[N];
int i,j,m,n,p,k,ans,x,y,now;
int M=(int)1e7;
struct Queue{
  node R[N];int h,ed,t;
  void New(int z) { h=ed=t=0; R[0].x=now; R[0].y=z*M;}
  void add(node a,int z){ if ((a.y<R[ed].y)^z) R[++ed]=a; }
  void X(int x,int z) { while (h<=ed&&((R[h].x<x)^z)) h++; h?h--:0; }
  void Y(int y,int z) { while (t<=ed&&((R[t].y<y)^z)) t++; }
}Q1,Q2,Q3,Q4;
inline bool cmp(node a,node b){ return a.x<b.x; }
int main()
{ // freopen("chess.in","r",stdin);
 //  freopen("chess.out","w",stdout);
    scanf("%d",&n);
  for (i=1;i<=n;i++)
   scanf("%d%d",&a[i].x,&a[i].y),a[i].id=i;
  memcpy(b,a,sizeof(a));
sort(b+1,b+n+1,cmp);
for (i=1;i<=n;i++)
 {  if (i==14)
            i=14;
                now=a[i].x;   Q1.New(1); Q2.New(1); Q3.New(-1); Q4.New(-1);
   for (k=1;b[k].x<a[i].x;k++);
   for (j=k-1;j;j--)if (b[j].id<i) 
   if (b[j].y>a[i].y) Q2.add(b[j],0); else Q3.add(b[j],1);
   for (j=k+1;j<=n;j++) if (b[j].id<i)
   if (b[j].y>a[i].y) Q1.add(b[j],0); else Q4.add(b[j],1);
   ans+=Q1.ed+Q2.ed+Q3.ed+Q4.ed;
   for (j=1;j<=Q1.ed;j++)
   {  x=Q1.R[j].x; y=Q1.R[j].y; if (!Q3.ed) break;
     Q2.Y(y,1); int xx=(Q2.t>Q2.ed)?-M:Q2.R[Q2.t].x;
     Q3.X(xx,1); Q4.X(x,0); int yy=Q4.R[Q4.h].y;
     Q3.Y(yy,0);  Q3.t?0:Q3.t++; ans-=max(Q3.h-Q3.t+1,0);}
   Q2.h=Q2.t=Q3.h=Q3.t=Q4.h=Q4.t=1;
   for (j=1;j<=Q2.ed;j++)
   { x=Q2.R[j].x; y=Q2.R[j].y; if (!Q4.ed) break;
     Q1.Y(y,1); int xx=(Q1.t>Q1.ed)?M:Q1.R[Q1.t].x;
     Q4.X(xx,0); Q3.X(x,1); int yy=Q3.R[Q3.h].y;
     Q4.Y(yy,0); Q4.t?0:Q4.t++; ans-=max(Q4.h-Q4.t+1,0);}
   Ans[i&1]+=(long long)ans;
  // printf("%d\n",ans);
}
printf("%lld %lld\n",Ans[1],Ans[0]);
}

 1825 蔬菜庆典

  OTZ了Silly Cross大大的题解，终于A掉了。http://hi.baidu.com/sillycross/item/58925d5b2e6df703aaf6d7b0

  第一次WA掉是因为没有考虑清楚无限节点和活节点的关系= =。

 #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200005;
long long ans,INF=1ll<<60,Ans;
int Dec[N];
int fa[N],fox[N],i,j,m,n,p,k,k1,Q[N],dis[N],Sum[N],l,r;
struct node{int ed,before;}s[N];
void Add(int p1,int p2) { s[++k1].ed=p2; s[k1].before=fox[p1]; fox[p1]=k1; }
inline bool cmp(int a,int b) { return a>b;}
long long Do(int x)
{l=r=1; Q[1]=x; int i; int Now=0,cnt=0,flag=1;  Ans=0;
 for (;l<=r;l++)
  { p=Q[l]; if (Sum[p]>1) { Now=p; cnt++; } Ans+=dis[p]; Dec[l]=dis[p]-dis[fa[p]]; 
     for (i=fox[p];i;i=s[i].before) Q[++r]=s[i].ed; }
  for (i=1;i<r;i++) if (Dec[i]!=Dec[i+1]) {flag=0;break;}
  if (flag) return Ans; if (cnt>1) return INF;
  int R=dis[s[fox[Now]].ed];
  for (i=fox[Now];Now&&i&&!flag;i=s[i].before) if (Sum[s[i].ed]||dis[s[i].ed]!=R) {flag=1;}
  if (flag) return INF;
  if (Now) r-=Sum[Now]-1;sort(Dec+1,Dec+r+1,cmp);long long No=dis[1]; Ans=0;
    for (i=1;i<=r;i++) Ans+=No+=Dec[i]; return Ans+(long long)(Sum[Now]-1)*R;
}
int main()
{ 
    scanf("%d",&n);
   for (;n;scanf("%d",&n))
    {   for (i=0;i<=n;i++)fox[i]=Sum[i]=0;k1=0; 
 for (i=1;i<=n;i++){ scanf("%d%d",&fa[i],&dis[i]);if (i==1) fa[i]++;Sum[fa[i]]++;Add(fa[i],i);}
 ans=dis[1]; for (i=fox[1];i&&ans<INF;i=s[i].before) ans+=Do(s[i].ed);
 if (ans>INF/2ll) printf("+inf\n"); else printf("%lld\n",ans);
}
}