Codeforces Beta Round #64 【Solution】

纪念第一套自己YY切完的CF、（其实同时也是第一套切完的CF）

‍

T_T，题意略的都是没什么技术含量纯粹为完整性的题目

 

 

A题

题意略

比赛被hack了一把。F[0]=1啊T_T。

其实就是个dp，F[i]=F[j]*2^(i-1-j) 1<=j

然后输出F[i]即可

 

 

B题

题意略

把每个sentence看成一个块，然后可以说是dp，也可以说是贪心。

F[i]表示用i段最长能覆盖到哪里，显然F[i]=F[i-1]+尽量接……

于是看什么时候能覆盖到尾巴就行了。

 

 

C题

【题意】

给定3个数Max_x Max_y w，让你求一个数对(x,y)满足这样 1<=Max_x,Max_y<=10^5 w<=10^7

for (i=1;i<=x;i++)

  for (j=1;j<=y;j++)

     if (i*j==rev(i)*rev(j)) cnt++;

最后cnt>=w，并且满足x*y最小。

输出x y或者无解输出-1

其中rev函数表示翻转。比如说rev(123217)=712321

【算法分析】

首先把式子换一下变成

 i/rev(i)=rev(j)/j

从小到大枚举i，令g=gcd(i,rev(i))，然后对i/rev(i)约分一下，再围观另外一边，显然

((i/g)*k)/((rev[i]/g)*k) = rev(j) / j……其实也就算是说j是rev(i)/g的倍数……然后就发现其实答案最多是Max_x lg Max_y级别的……然后其实可以暴力。

我们枚举x，考虑找出每个x对应的最小的y，满足1<=i<=x && 1<=j<=y内包含满足条件的数对的数目>=w。

然后x从小到大枚举，那么y必然递减，这里可以不必二分。

最终时间复杂度O(n lg n) (n=max(Max_x,Max_y))

于是有了这种代码

    int i,j,Tmp=Max_y,r;

    for (i=1;i<=Max_x;i++){

        r=rev[i]/g[i];                                                          // g[i]=gcd(i,rev[i])

        for (j=r;j<=Max_y;j+=r)

          if ((lld)(i)*j==(lld)(rev[i])*rev[j]) add(j);                 //add(i)表示将Tr[i]+1

        while (Tmp>1 && Get(Tmp-1)>=w) Tmp–;           //Get(i)表示Tr[1]+Tr[2]+Tr[3]+…+Tr[i] (于是使用树状数组维护之)

        if (Get(Tmp)>=w && (lld)(i)*Tmp

            ans=(lld)(i)*Tmp;

            ret_x=i;

            ret_y=Tmp;

        }

    }

    if (ans==INF) cout << "-1n";

    else cout << ret_x << " " << ret_y << endl;

 

 

D题

【题目大意】

一开始点集S为空，然后有Q<=10^5个询问，询问有两种类型，第一种是在点集S中插入一个点，第二种是在问，一个点是否在由点集S所构成的凸包中。

【算法分析】

其实问题就在于动态维护凸包，对于第二种询问，我们只要尝试用这个点去更新凸包，如果需要更新，那么该点在凸包外，否则在凸包内。

我们考虑把凸包上的边逆时针定向：

‍
于是他们都变成了向量，我们以atan2(x,y)给这些向量排序(其实就是极角排序)，然后再定第一条的向量的起始点为原点。然后以该原点对每个点连一条向量。

‍

这样向量划分出了很多个区域，注意因为是凸包，所以这些向量所夹的角都为(0,pi)之间。然后我们就可以通过类似二分的方法找出该删的一个向量在哪里位置，然后暴力枚举前后的向量判断能否删除(该删的向量必然是连续的)

特别地，如果新的那个点在那个>pi的区间内，那么我们只需要检测与原点相连的边即可得到该删的向量。

对于凸包中的一个向量(x1,y1)->(x2,y2)，我们判断该不该删，就是判断(x2-x1,y2-y1)^(New.x-x1,New.y-y1)是否<0， 其中^表示叉乘……

特别地叉乘等于0时要特判这个点是否在线段(x1,y1)-(x2,y2)上。

考虑动态维护一个有序序列，我们可以使用平衡树来解决。这样每个点只能被插入以及删除一次，于是是平摊lg n的。(这里不一定需要Splay)

当然几何题免不了各种恶心情况……大家可以慢慢发掘……

该题算法不难，但是实现有点恶心……属于体力题……WA了N久……

 

E题

【题目大意】

给定一棵n<=180个结点的树(树上的边长度都为1)，然后让你指定一些点作为关键点(指定一个关键点需要付出k的代价)，设点i到离自己最近的关键点的距离为dis(i)，那么这个点需要花费d[dis(i)]的代价。(d[]在数据中给出)

【算法分析】

这个题我觉得很不错，实现不麻烦，也挺考思维的。一开始看成是一般图了，后来发现是树囧、YY良久，终于切掉。

我的方法是……dp

F[i,j]表示处理到i这个点，并且离i最近的一个关键是j，这时候最小花费的费用是多少。然后从树的叶子往根推。

我们考虑处理第i个结点，那么离它最近的关键点j有3种情况

1、i要通过自己的父亲到达j

2、i通过其中一个儿子到达j

3、i=j（这种情况处理起来和第一种其实是一样的）

先设near[i][j]表示从i跑到j，走第一步跑到哪里。比如说从1->2->3->4，那么near[1][4]=2,near[4][1]=3。

再设mat[i][j]表示从i跑到j的路径长度。

注意上面提到的3种情况中有一些状态是不能通过儿子转移上来的。

Case 1:

设当前状态为F[p][j]，儿子状态是F[i][k]，那么如果near[i][k]=p，但是j!=k，那么显然没有j=k时优的……

理由如下：

i->p->……->k————————这是i到离自己最近关键点的路径

    p->……->j————————这是p到离自己最近关键点的路径

……既然p->……->j是最短的，那么显然i->p->……->j也是最短的T_T。

 

Case 2:

设当前状态为F[p][j]，儿子状态时F[i][k]，那么如果near[p][j]=i，但是j!=k，那么显然没有j=k时优的……

理由类似上面：

p->i->……->j

     i->……->k

然后你们懂的T_T

 

于是就可以转移了。你们可能觉得这不太正确……那么继续来YY。

考虑F[i,j]所包含的信息，在i为根的子树里，如果不需要通过i跑上来的点，显然在下面已经指派完成了的不用管。

如果要通过i跑上来的点，那么它们所需要的点都是j，于是，F[i,j]所包含的信息对我们推导后面的状态是一样的，于是同样是达到(i,j)这种状态，我们只需要取最优的一个就可以了，所以这个状态定义是正确的……

由于一棵树有n条边，每次转移需要n^2，所以一共要n^3

下面附上代码。

 #include 

#include #include #include #include using namespace std;
typedef long long lld;
const lld INF=(lld)(1)<<50;
int n,price;
int w[205];
lld mat[205][205];
int near[205][205];
lld F[205][205];
int belong[205];

void Floyed(){
  int i,j,k;
  for (k=1;k<=n;k++)
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
      if (mat[i][k]+mat[k][j]        mat[i][j]=mat[i][k]+mat[k][j];
}

void Make_Near(){
  int i,j,k;
  for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
    if (i!=j){
      for (k=1;k<=n;k++)
        if (mat[k][j]==mat[i][j]-1 && mat[i][k]==1) near[i][j]=k;
    }
}

void dfs(int p,int fa){//dp的转移
  int i,j,k;
  for (i=1;i<=n;i++)
    if (mat[p][i]==1 && i!=fa)
      dfs(i,p);
  for (j=1;j<=n;j++)
    if (p==j)
    F[p][j]=price;                    //price是题目中提到的k，表示建一个关键点需要的代价
    else
    F[p][j]=w[mat[p][j]];             //w是题目中的d[]数组
  for (i=1;i<=n;i++)                    //F[p][j] Get message from  F[i][k]
    if (mat[p][i]==1 && i!=fa)          //i是p的儿子
      for (j=1;j<=n;j++){
      lld Min=INF;
      for (k=1;k<=n;k++){
      if (near[i][k]==p && k!=j) continue;      //文中提到的Case 1
      if (near[p][j]==i && k!=j) continue;      //文中提到的Case 2
      if (F[i][k]        Min=F[i][k];
      }
      F[p][j]+=Min;
    }
}

void Out(int p,int j,int fa){
  belong[p]=j;
  for (int i=1;i<=n;i++)
    if (mat[p][i]==1 && i!=fa){
    lld Min=INF;
    int Mini=0;
    for (int k=1;k<=n;k++){
      if (near[i][k]==p && k!=j) continue;
      if (near[p][j]==i && k!=j) continue;
      if (F[i][k]        Min=F[i][k];
        Mini=k;
      }
    }
    Out(i,Mini,p);
    }
}

void output(){
  lld Min=INF,Mini=0;
  for (int i=1;i<=n;i++)
    if (F[1][i]      Min=F[1][i];
      Mini=i;
    }
  cout << Min << endl;
  memset(belong,0,sizeof(belong));
  Out(1,Mini,0);
  for (int i=1;i<=n;i++) cout << belong[i] << " ";
  cout << endl;
}

int main(){
  scanf("%d%d",&n,&price);
  for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
      if (i==j)
      mat[i][j]=0;
      else
      mat[i][j]=INF;
  w[0]=0;
  for (int i=1;i  for (int x,y,i=1;i    scanf("%d%d",&x,&y);
    mat[x][y]=mat[y][x]=1;
  }
  Floyed();
  Make_Near();
  dfs(1,0);
  output();
}