B 

题意：给定n个字符串，互不相等，你可以任意指定字符之间的大小关系（即重定义字典序），求有多少个串可能成为字典序最小的串，并输出它们。

tags：好题

对于一个字符串，

1】如有其它字符串是它的前缀，那肯定不可能。这个直接用字典树处理就可以。

2】但如果以这个字符串为最小，怎么判定其它字符串不会矛盾呢？

其实矛盾的情况详细一点说是： 比如要以  abcd 为最小， 但又有另一个字符串 aba ，这就矛盾了。

对这种情况，在跑字典树的时候，我们对有相同父亲结点的多个儿子结点相互连边，然后每次拓扑排序判一下环即可。

#include
      
       using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a; i<=b; ++i)#define per(i,b,a) for (int i=b; i>=a; --i)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi  first#define se  secondtypedef long long ll;const int N = 30005, M = 300005;int n, cnt, tr[M][26], val[M*26];string s[N];void Insert(int ci){    int len=s[ci].size(), now=0;    rep(j,0,len-1)    {        int tmp=s[ci][j]-'a';        if(tr[now][tmp]==0) tr[now][tmp]=++cnt;        now = tr[now][tmp];    }    ++val[now];}vector< int > G[26];int in[26];queue< int > q;bool Toposort(){    rep(i,0,25) if(in[i]==0) q.push(i);    while(!q.empty())    {        int u=q.front(); q.pop();        for(int i=0; i
       
        > s[i];        Insert(i);    }    rep(i,1,n)    {        if(check(i)) ans[++ans1]=i;    }    printf("%d\n", ans1);    rep(i,1,ans1)        cout<
        
         <
        
       
      

 

E 

题意：

给你一个长为n的序列a

定义f(i,j)=(i-j)²+g(i,j)²

g是这样的一个函数

求最小的f(i,j)的值，i!=j

tags：翻译一下，就是  (i-j)^2+(sum[i]-sum[j])^2  最小， 也就是最近点对。 分治 O(nlogn)

模板：

// 分治求平面最近点对struct Point { double x, y; };struct Point point[N], *px[N], *py[N];double get_dis(Point *p1,Point *p2) {    return sqrt((p1->x-p2->x)*(p1->x-p2->x)+(p1->y-p2->y)*(p1->y-p2->y));}bool cmpx(Point *p1,Point *p2) { return p1->x
     
      x; }bool cmpy(Point *p1,Point *p2) { return p1->y
      
       y; }double min(double a,double b) { return a
       
        >1;    double ans=min(closest(s,mid),closest(mid+1,e));//递归求解    int i, j, cnt=0;    for(i=s; i<=e; i++)//把x坐标在px[mid].x-ans~px[mid].x+ans范围内的点取出来    {        if(px[i]->x>=px[mid]->x-ans && px[i]->x<=px[mid]->x+ans)            py[cnt++]=px[i];    }    sort(py, py+cnt, cmpy);//按y坐标排序    for(i=0; i
        
         y-py[i]->y>=ans)  break;            ans=min(ans,get_dis(py[i],py[j]));        }    }    return ans;}/*void Init(){    for(int i=1; i<=n; ++i) {        scanf("%lf%lf", &point[i].x, &point[i].y);        px[i] = &point[i];    }    sort(px+1, px+1+n, cmpx);}*/
        
       
      
     

// E#include
      
       using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a; i<=b; ++i)#define per(i,b,a) for (int i=b; i>=a; --i)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi  first#define se  secondtypedef long long ll;const int N = 100005;struct Point { double x, y; };struct Point point[N], *px[N], *py[N];double get_dis(Point *p1,Point *p2) {    return sqrt((p1->x-p2->x)*(p1->x-p2->x)+(p1->y-p2->y)*(p1->y-p2->y));}bool cmpx(Point *p1,Point *p2) { return p1->x
       
        x; }bool cmpy(Point *p1,Point *p2) { return p1->y
        
         y; }double min(double a,double b) { return a
         
          >1;    double ans=min(closest(s,mid),closest(mid+1,e));//递归求解    int i, j, cnt=0;    for(i=s; i<=e; i++)//把x坐标在px[mid].x-ans~px[mid].x+ans范围内的点取出来    {        if(px[i]->x>=px[mid]->x-ans && px[i]->x<=px[mid]->x+ans)            py[cnt++]=px[i];    }    sort(py, py+cnt, cmpy);//按y坐标排序    for(i=0; i
          
           y-py[i]->y>=ans)  break;            ans=min(ans,get_dis(py[i],py[j]));        }    }    return ans;}/*void Init(){    for(int i=1; i<=n; ++i) {        scanf("%lf%lf", &point[i].x, &point[i].y);        px[i] = &point[i];    }    sort(px+1, px+1+n);}*/int n;double ai, sum[N];int main(){    scanf("%d", &n);    rep(i,1,n)    {        scanf("%lf", &ai);        sum[i]=sum[i-1]+ai;        point[i].x=1.0*i, point[i].y=sum[i];        px[i] = &point[i];    }    sort(px+1, px+1+n, cmpx);    double ans = closest(1, n);    printf("%.0f\n", ans*ans);    return 0;}