标签存档：Topcoder

最近rating直线下降…

250

给$$a_0$$, $$a_n$$, 在保证$$a_i \geq 0$$和$$|a_i – a_{i + 1}| \leq 1$$以及包含某个+1, -1片段的前提下，问能否构成目标序列。

$$O(n * history.size())$$的应该超级好写…显然整个过程可以看成先加若干再减若干.然后模拟就好了。
$$O(1)$$的也不难，设+1的数目为u，-1的数目为d，则$$u + d = n$$ 且$$u – d = a_n – a_0$$，可以解出u, d，再把+的都放在history前面，看能否可行即可。不过相比上面的略显麻烦。

#include 
#include 
#include 

550

预处理(把图作传递闭包，然后删除强连通中的点)完以后相当于，给定一个DAG图，若取了一个点，则其可达的点都不能取，问最多能取多少个点。

DAG图以及传递性保证了这是一个偏序集...于是这就是裸的最大反链
和HDOJ3335是一样的...把这个翻出来发现自己做过却完全想不来，太圡了。
反链科普：http://baike.baidu.com/view/2272728.htm
具体做法是传递闭包以后，得出这个有向图的邻接矩阵，把这个看成是点拆成两边的二分图，然后做最大匹配，答案就n-最大匹配。
之前一直不知道这个是怎么证明。
今天去看了一下，发现有个Dilworth's theorem 定理。
这个定理说明了：对于一个偏序集合，最大反链=最小路径覆盖，而且反链里的每个点，都属于不同的路径里面。
于是就是求最小路径覆盖就行了，最大匹配对应最小路径覆盖的证明就很简单了...
嗯，然后就这样...

#include 
#include 
#include 

1000
给定n($$n \leq 50$$)个非负整数，每个数不超过$$10^15$$，每次可以进行一个操作：取$$a_i$$和$$a_j$$将，$$a_i$$替换成$$a_i \oplus a_j$$，问经过若干次操作以后，$$\sum_{i=1}^na_i$$最大能是多少。

首先注意异或这个初等变换是不会改变矩阵的秩的。
高斯消元求出这个异或空间的基以后，那些不是基的都可以变成空间里的最大值。
然后每个基对应的主元，都跑去把别人的对应位置消成0，于是每个主元在基里有且仅有一个1。
用异或空间的最大值去异或每个基，那么每个主元在对应列上有且仅有1个0(除了主元最大的那个基)。
而显然在不能改变矩阵秩的前提下，这个和是最大的了。

#include 
#include 
#include 

>.<深切感受到自己蒟蒻。

 

250题意

N,M<=10^9

i=N;

j=M;

while (j<=lcm(N,M)){

while (i

ans+=j-i;

j+=M;

}

return (double)ans/(lcm(N,M)/M);(平均数)

、

然后发现其实每次j-i都是gcd(N,M)的倍数，设g=gcd(N,M)，然后j-i刚好是0,g,2*g,3*g,…,(lcm(N,M)/M-1)*g

、

lcm(N,M)/M=N/g

于是ans=(N/g)*(N/g-1)/2 * g  / (N/g)

然后最终代码是

int gcd(int x,int y){return y?gcd(y,x%y):x;}

double Starport::getExpectedTime(int N, int M) {

long long g=gcd(N,M);

long long t=N/g;

return g*(t*(t-1)/2)/(double)(t);

}

 

 

550

弄完以后交FST了….

题目大意就是给定一组字典，再给出一个字符串，让你用手机T9的方式最少要多少次按键把字符串打出来。

对我来说很考验coding啊>.<...

思路不太难，就模拟每次弄一个字典里字符的前缀。然后由于是类似栈的形式，只能从后面删和插入，所以可以F[i]表示前i个弄好最少多少次按键，然后弄个邻接矩阵mat[i][j]表示两两状态间转移最少需要多少步.

最后来个floyd就OK…

个中细节和处理技巧多多= =，请自行体会。。。

2Y。

 

被屠什么的，无所谓的。

唉，跌rating了。

250是个很骗人的题目。。。我一开始很迅速地反应到结果只能是2,1,-1。。。然后构造的方法也YY了一下。写完过掉样例以后，突然觉得好像不太靠谱，有点忐忑。然后又跑去换了个dp。最后折腾到只有130+分了。其实很显然本身就是对的啊。。。

500这种求期望的题见到就挂啊。

总是喜欢求和然后除以总方案数这种YY方式。太弱了。我YY的时候甚至觉得每个排列不是等可能的(由于第二个条件)。

然而排列和后面的选取是分步进行的。所以每个排列是等可能的。

于是可以通过枚举边，然后算对应概率，最后加起来的方式求期望值。

各路大神齐集，题目难到奇葩。

ACRush滑铁卢500和1000都挂了……

CLJ神犇爆-25……

还有两target是0的，红色爆0一堆……

‍

然后我一进去我的房间，就看到一个熟悉的ID：felix-halim，然后还有个人拼命YM它、YY着到底是谁，突然想起是建这个网站的人：

http://felix-halim.net/uva/hunting.php?id=29277

UVA帝啊T_T(上面是AekdyCoin的号)

不过后来他爆0了。我们房子唯一一个红的也爆0了……

最后本房一共7个人有分，其中有一个是叉人得的分。

其余都是只pass了250pt……

由于我巨慢的手速和思考速度，T_T，我的250只有122.66分了，最后在DIV1里刚刚好200名。

于是rating就涨回去了，终于从Blue Boy变回Yellow Boy了！！！上次由于插件事件爆0那rating跌得叫一个惨啊……

哎，我太蒟蒻了。

给定一个凸多边形包围住另一个凸多边形，外面的凸多边形上的每个点都向离自己的最远的在外凸多边形上的点连一条线。然后问，随意取一个在外凸多边形上的点，有多少的概率能取到对应线段与内多边形相交的点。

然后规模是TC的老规矩：50

然后算法就是暴力T_T。但是我暴力好像都写得很长。

第一步：

枚举每条外多边形上的边Point[i]->Point[i+1]，然后再枚举Point[j]和Point[k]，然后搞Point[j]->Point[k]的中垂线(这个有模板T_T)，这个中垂线跑回来和Point[i]->Point[i+1]求交点(没交点就算了)。然后将这些交点按到Point[i]的距离排个序，去重。然后对于这个交点序列，每个点到下一个点形成了线段，然后就找一个到线段离两个端点最远的Point[t]，然后这个线段对应的最远点就是Point[t]了。

第二步：

枚举外多边形上的点Point[i]，然后枚举内多边形上的点，找到一左一右两个交点L和R(可以加多一层循环判是不是所有点都在它左边或者右边)，然后向量Point[i]->L和向量Point[i]->R所夹的位置，就是能够穿过内多边形所对应的位置。然后枚举第一步求的交点序列，如果相邻交点间线段对应的最远点是Point[i]，那么就用Point[i]->L和Point[i]->R这两个直线向它求交点，然后分情况讨论一下(我这里好像显然写长了)。

 

T_T，幸好调对第一个样例以后就Y了，不然得Debug个半死。

【CODE】

const double eps=1e-9;

    int sign(double x){
        if (x<-eps) return -1;
        if (x> eps) return1;
        return0;
    }

    int m,n;
    struct TPoint{
        double x,y;
        TPoint operator + (TPoint oth){
            TPoint ret;
            ret.x=x+oth.x;
            ret.y=y+oth.y;
            return ret;
        }
        TPoint operator – (TPoint oth){
            TPoint ret;
            ret.x=x-oth.x;
            ret.y=y-oth.y;
            return ret;
        }
        TPoint operator * (double oth){
            TPoint ret;
            ret.x=x*oth;
            ret.y=y*oth;
            return ret;
        }
        booloperator != (TPoint oth){
            return (sign(x-oth.x)!=0 || sign(y-oth.y)!=0);
        }
        booloperator == (TPoint oth){
            return sign(x-oth.x)==0 && sign(y-oth.y)==0;
        }
        doubleoperator ^ (TPoint oth){
            return x*oth.y-y*oth.x;
        }
    }Site[55],Dep[55];
   
struct TLine{
    double a,b,c;
};

TPoint Rot90(TPoint A){
    TPoint ret;
    ret.x=-A.y;
    ret.y=A.x;
    return ret;
}
   
TLine Get_Line(TPoint A,TPoint B){
    TLine ret;
    ret.a=A.y-B.y;
    ret.b=B.x-A.x;
    ret.c=B.y*A.x-B.x*A.y;
    return ret;
}

TPoint jiao(TLine A,TLine B){
    TPoint ret;
    ret.x=(A.b*B.c-A.c*B.b)/(A.a*B.b-B.a*A.b);
    ret.y=(A.c*B.a-A.a*B.c)/(A.a*B.b-B.a*A.b);
    return ret;
}

double dis(TPoint A,TPoint B){
    return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}

    pair        pair        ret.second=false;
        TLine L2=Get_Line(A,B);
        if (sign(L.a*L2.b-L2.a*L.b)==0) return ret;
        else{
            ret.first=jiao(L,L2);
            if (sign(min(A.x,B.x)-ret.first.x)<=0 && sign(ret.first.x-max(A.x,B.x))<=0
            &&  sign(min(A.y,B.y)-ret.first.y)<=0 && sign(ret.first.y-max(A.y,B.y))<=0){
                if (ret.first==A || ret.first==B) return ret;
                ret.second=true;
                return ret;
            }
        }
        return ret;
    }
   
    vector     vector     vector     int tttt;
   
    bool cmp(TPoint A,TPoint B){
        return dis(A,Site[tttt])    }
   
    void Div_part(){
        int i,j,k,p;
        for (i=0;i            Cut[i].clear();
            Cut[i].push_back(Site[i]);
            Cut[i].push_back(Site[(i+1)%m]);
            for (j=0;j              for (k=j+1;k                  TPoint mid=(Site[j]+Site[k])*0.5;
                  TPoint dir=Rot90(Site[j]-Site[k]);
                  pair                  if (cross.second) Cut[i].push_back(cross.first);
              }
            tttt=i;
            sort(Cut[i].begin(),Cut[i].end(),cmp);
            TV.clear();
            for (j=0;j              if (j==0 || Cut[i][j]!=Cut[i][j-1]) TV.push_back(Cut[i][j]);
            Cut[i]=TV;
            best[i].clear();
            for (p=0;p                int now=0;
                for (j=1;j                  if ( sign( dis(Site[j],TV[p]) – dis(Site[now],TV[p]) )>=0 && sign( dis(Site[j],TV[p+1]) – dis(Site[now],TV[p+1]) )>=0 )
                    now=j;
                best[i].push_back(now);
            }
        }
    }
   
    double ans;
   
    void Rush(){
        int i,j,k,L,R;
        for (i=0;i            for (j=0;j                bool check=true;
                for (k=0;k                  if ( sign( (Dep[j]-Site[i])^(Dep[k]-Site[i]) ) > 0 )  check=false;
                if (check) { L=j; break; }
            }
            for (j=0;j                bool check=true;
                for (k=0;k                  if ( sign( (Dep[j]-Site[i])^(Dep[k]-Site[i]) ) < 0 ) check=false;
                if (check) {R=j; break;}
            }
            for (j=0;j              for (k=0;k                if (best[j][k]==i){
                    pair                    pair                    TPoint Lp=Cut[j][k];
                    TPoint Rp=Cut[j][k+1];
                    if (crossL.second){
                      if (crossR.second)
                          ans+=dis(crossL.first,crossR.first);
                      else{
                          if (sign( (Dep[L]-Site[i])^(Lp-Site[i]) )<=0 && sign( (Dep[R]-Site[i])^(Lp-Site[i]) )>=0 )
                              ans+=dis(Lp,crossL.first);
                          else
                              ans+=dis(Rp,crossL.first);
                      }
                    }
                    else{
                      if (crossR.second){
                          if (sign( (Dep[L]-Site[i])^(Lp-Site[i]) )<=0 && sign( (Dep[R]-Site[i])^(Lp-Site[i]) )>=0 )
                              ans+=dis(Lp,crossR.first);
                          else
                              ans+=dis(Rp,crossR.first);
                      }
                      else{
                          if (sign( (Dep[L]-Site[i])^(Lp-Site[i]) )<=0 && sign( (Dep[R]-Site[i])^(Lp-Site[i]) )>=0
                          &&  sign( (Dep[L]-Site[i])^(Rp-Site[i]) )<=0 && sign( (Dep[R]-Site[i])^(Rp-Site[i]) )>=0)
                              ans+=dis(Lp,Rp);
                      }
                    }
                }
        }
    }
class Deposit {
public:
    double successProbability(vector         m=siteX.size();
        n=depositX.size();
        for (int i=0;i            Site[i].x=siteX[i];
            Site[i].y=siteY[i];
        }
        for (int i=0;i            Dep[i].x=depositX[i];
            Dep[i].y=depositY[i];
        }
        double Sum=0;
        for (int i=0;i        ans=0;
        Div_part();
        Rush();
        return ans/Sum;
    }
};