• 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");