标签存档：Codeforces

A

直接模拟即可。10^6

 

B

【题目大意】

m*n的方格(m,n<=4*10^4)，有一些格子坏掉了(数目<=10^3)。然后以

for (int i=1;i<=m;i++)

  for (int j=1;j<=n;j++)

的顺序填好的格子，依次填上Carrots  Kiwis  Grapes.

然后有<=10^3个询问，问第i行第j列的格子是什么。waste表示坏格子。

【算法】

(i,j)->(i-1)*n+j

然后根据排序二分。得出<=自己的坏掉的格子的数目。

 

C

【题目大意】

给定一个10^5的串，然后给出10个小串，他们的长度都<=10。然后问你大串满足不包含小串的最长连续子串是多少。

【算法】

令C[i]表示以大串第i位为结尾和小串匹配时的最短小串长度。如果没有小串和大串在以i为结尾的地方匹配，那么C[i]=oo。

然后就i递增地扫描，然后记now为当前以i为结尾的最长匹配长度。如果now>=C[i],那么now=C[i]-1。记录过程中最大的now与位置即可。

【时间复杂度】

10^7 —暴力

10^6 —KMP

10^5 —自动机

 

D

【题目大意】

1..n个格子，有黑白，一开始全白。其中有k个不相同的key_blocks。然后有m种操作。每种操作为L[i]，表示可以选择一段长度为L[i]连续格子翻转。

问最少多少步使得所有key_blocks变黑，其他格子全白。

【算法】

看了解题报告、

这个模型的转换确实挺巧妙的。

令b[i]=a[i]^a[i-1]。其中a[i]就是原格子的黑白状态。那么b[i]=0表示a[i]==a[i-1]。否则不等。

添加a[0]=0。那么用b可以完整表示出a。(要添加a[n+1]=0,b[n+1]=a[n]^a[n+1]，key_blocks如果前后没有，就要1变2了)

然后翻转连续的一段，就会只更改b的两个值x和x+L[i]，1<=x<=n+1。这样模型就很适合反映情况了。

更改两个b的值表示两个点有边，那么问题变成我们选择一些边，使得key_blocks对应的点度为奇数，其它点度为偶数。

因此答案必然可以分割为若干条简单路径，每条简单路径的起始点和结束点都是key_blocks，而且每个key_blocks会被覆盖1次且仅1次。于是可以bfs算出各个key_blocks间的最短距离。然后SCDP取得最优解。

 

可见把模型转化成合适的形式是很重要的。

【时间复杂度】

mnk + 2^(2k) * k

 

这场之后rating达到新高1922。= =，希望接下来一场多人点的把我带红。

 

这两天缺席了一场TC，一场CF、据说这两场都很好涨rating？555555555555555

 

【A. Heroes】

就是一个DFS枚举，然后模拟。

最坏时间3^7 * 7^2

 

【B. Falling Anvils】

【题目大意】

给定一个方程。然后p的范围是[0,a]，q的范围是[-b,b]。

p,q在各自区间上等概率分布。

问这个方程有解的概率。

【算法分析】

就是求p-4q>=0的概率。

然后把p看成x，q看成y。然后画出对应的平面图形分类讨论一下即可。高中数学课本的例题阿

代码就这样

        if (fabs(b)<1e-9) ret=1;

        else

        if (a

            ret=(2*b+a/4)/(4*b);

        }

        else{

            ret=1-b/a;

        }

注意b=0的情况。被坑了一次。

 

 

【C. Beavermuncher-0xFF】

【题目大意】

给定一棵有根树，每个点上有w[i]只鱼(其实题目是海狸= =)，一开始你在根上。你每走一条边x->y，那么y上要少一条鱼。如果y上没鱼，那么不能走边x->y。现在要求你结束时依然需要站在根处，问你最多能干掉多少条鱼(即最多能走多少步)。

n<=10^5

【算法分析】

首先很容易发现我们可以把走出去的路线分解为很多圈圈，每个圈圈只包含两个点。

于是我们可通过点来划分路径。

考虑一棵以p为根的子树

我们可以以p为分界点把路径分隔开。

那么p下面怎么走和上面无关，只要剩下一条鱼在p上，就足够把p这个子树拼接到fa上。

我们考虑p上的鱼消失的两种方式。

A、从儿子走回来

B、从fa走下来

如果能选A，我们肯定尽量选A。因为如果选了B，那么必须要走回fa那儿去，那么就要同时消耗fa上鱼的数目，这就会影响以后的决策，使得后面取得的鱼变少。

于是这个贪心算法就很显然了。令F[i]表示以i为根，绕一圈回到i最多能吃到多少鱼。(如果i不为根，那么要求最后i上剩的鱼>=1，否则>=0)。

然后每次将自己的儿子按F[i]排个序。然后拼接就好了。

如果拼接完还有在i上的鱼多出来，那么就找个儿子卡能不能抵消。最后输出F[i]即可。

附代码

#include

#include

#include

#include

#include

using namespace std;

const int N=100005;

const int oo=0x80000000;

int n,S;

int w[N];

int fa[N];

int Q[N];

long long F[N];

vector

 

void bfs(){

    int head=0,tail=1;

    Q[1]=S;

    fa[S]=0;

    while (head!=tail){

        head++;

        int x=Q[head];

        int L=G[x].size();

        for (int i=0;i

            int y=G[x][i];

            if (fa[x]!=y){

                fa[y]=x;

                Q[++tail]=y;

            }

        }

    }

}

 

bool cmp(int i,int j){

    return F[i]>F[j];

}

 

void solve(){

    for (int i=1;i<=n;i++) F[i]=oo;

    for (int j=n;j>=1;j–){

        int low_limit= (j==1) ? 0 : 1;

        int x=Q[j];

        int L=G[x].size();

        F[x]=0;

        sort(G[x].begin(),G[x].end(),cmp);

        for (int i=0;i

            int y=G[x][i];

            if (fa[x]!=y){

                if (w[x]>low_limit && w[y]>0){

                    F[x]+=F[y]+2;

                    w[x]–;

                    w[y]–;

                }

            }

        }

        for (int i=0;i

            int y=G[x][i];

            if (fa[x]!=y){

                if (w[x]>low_limit && w[y]>0){

                    int delta=min(w[x]-low_limit,w[y]);

                    F[x]+=delta*2;

                    w[x]-=delta;

                    w[y]-=delta;

                }

            }

        }

    }

    cout << F[S] << endl;

}

 

int main(){

    freopen("input.txt","r",stdin);

    scanf("%d",&n);

    for (int i=1;i<=n;i++) scanf("%d",&w[i]);

    for (int x,y,i=1;i

        scanf("%d%d",&x,&y);

        G[x].push_back(y);

        G[y].push_back(x);

    }

    scanf("%d",&S);

    bfs();

    solve();

}

 

【D. Domino Carpet】

【题目大意】

经过一些人肉转换以后，题目变成了m*n个格子，这些格子有3种类型。

1、只允许被2*1的方块覆盖的。

2、只允许被1*2的方块覆盖的。

3、允许被1*2或2*1的方块覆盖的。

然后用2*1或者1*2的格子去完美覆盖这些格子。问有多少种方案。

n,m<=250

还有一个重要条件，假如放了一块1*2的方块占在(i,j)和(i,j+1)，那么就不能存在其它的1*2方块放在(k,j-1)(k,j)或(k,j+1)(k,j+2)。

【算法分析】

由于那个重要条件，我们可以一列一列地dp转移。

要么直接整列竖的2*1方块。要么就是存在1*2方块的两列。

第一种很好算直接F[j+1]+=F[j]。

第二种可以在里面套一个dp。G[i][0]表示到达第i行，还没有放过1*2的方块，这时候的方案数。G[i][1]就是放过2*1的方块的方案数了。

然后F[j+2]+=G[m][1]*F[j]。

 

【E. Martian Food】

= =，算了10页草稿纸发现算不出来。唉，太弱小了。不会捉。

 

 

、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

比赛时前3题都是迅速反应出算法，但是第3题写的时候，头脑有点混，悲剧写挂了。今天重打一遍不到10分钟就1Y了

然后就前两题那个沙茶分数排到了DIV I 150+。居然还涨rating了

纪念第一套自己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();
}