目录

• ABC266 – E,F Solutions
  • E – Throwing the Die
    • Problem Statement
    • Solution
    • Implementation
  • F – Well-defined Path Queries on a Namori
    • Problem Statement
    • Solution
    • Implementation

ABC266 – E,F Solutions

E – Throwing the Die

Problem Statement

Let us play a game using a die. The game consists of at most /(N/) turns, each of which goes as follows.

• Throw a /(6/)-sided die that shows /(1,/ldots,6/) with equal probability, and let /(X/) be the number shown (each throw is independent of the others).
• If it is the /(N/)-th turn now, your score is /(X/), and the game ends.
• Otherwise, choose whether to continue or end the game.
  • If you end the game, your score is /(X/), and there is no more turn.

Find the expected value of your score when you play the game to maximize this expected value.

Constraints

• /(1≤N≤100/)

Solution

一句话题意：投骰子，投出1~6的概率相等，不满意可以重投，最多投n次，期望投出点数是多少？

先考虑 /(N=2/)，每次骰子期望投出 /(3.5/) 的分数，于是第一次投出 /(1/text ~3/) 的时候就可以重投。同理，对于更普遍的情况，当第 /(i/) 次投出的结果小于 /(i+1/text ~N/) 计算得到期望时，就可以考虑重投。

Implementation

此处 f[n] 是倒序的。

n=rd();
f[1]=3.50;
jk(i,2,n)jk(j,1,6)f[i]+=std::max((double)j,f[i-1])/6.0;
printf("%.7lf/n",f[n]);

F – Well-defined Path Queries on a Namori

Problem Statement

You are given a connected simple undirected graph /(G/) with /(N/) vertices numbered /(1/) to /(N/) and /(N/) edges. The /(i/)-th edge connects Vertex /(u_i/) and Vertex /(v_i/) bidirectionally.

Answer the following /(Q/) queries.

• Determine whether there is a unique simple path from Vertex /(x_i/) to Vertex /(y_i/) (a simple path is a path without repetition of vertices).

Constraints

• /(3≤N≤2×10^5/)
• /(G/) is a connected simple undirected graph with /(N/) vertices and /(N/) edges.
• 1 /leq Q /leq 2 /times 10^5

Solution

N点N边，一眼基环树，先tarjan找到环。不难发现两点仅存在一条路径时，它们在环上节点的同一颗（向环外的）子树内，于是直接dfs就好了，下面是样例2的示意图：

Implementation

void ta(int u,int f){
    st[++s]=u;is[u]=1;
    fn[u]=lo[u]=++T;
    for(int i=h[u];i;i=e[i].n){
        int v=e[i].v;
        if(v==f)continue;
        if(!fn[v]){
            ta(v,u);
            lo[u]=std::min(lo[u],lo[v]);
        }else lo[u]=std::min(lo[u],fn[v]);
    }
    Z[lo[u]]++;
}

void df(int u,int f,int b){
    B[u]=b;
    for(int i=h[u];i;i=e[i].n){
        int v=e[i].v;
        if(v!=f&&(u!=b||lo[v]!=o)&&!B[v])df(v,u,b);
    }
}

// puts(B[rd()]^B[rd()]?"No":"Yes");