2022-11-4总结

owo

Description

有两组玩家进行游戏，第一组玩家有 $n$ 个人，第二组玩家有 $m$ 个人，两组之间玩家两两会进行比赛，一共进行 $n*m$ 场比赛。

第一组玩家能力值为 $a_1,a_2,\cdots,a_n$, 第二组玩家能力值为 $b_1,b_2,\cdots,b_m$ ，其中能力值为 $1$ 到 $2$ 之间的浮点数，两个能力值为 $a$ 和 $b$ 的玩家进行比赛的时候，能力值为 $a$ 的玩家获胜概率为 $a/(a+b)$。

请求出所有比赛结束后，第一组每个玩家获胜场次的期望。

Input

第一行两个整数 $n, m$。

接下来一行包含 $n$ 个实数 $a_1, a_2, \cdots, a_n$ 。

最后一行包含 $m$ 个实数 $b_1, b_2, \cdots, b_m$。

输入的实数小数位数不超过 $8$ 位。

Output

输出 $n$ 行，每行一个实数表示每个玩家获胜场次的期望，要求误差在 $10^3$ 一下。

Hint

$n,m \le 10^6$

Solution

因为答案精度仅需 $10^3$ ，我们可以发挥人类智慧，将每个输入乘以 $10^4$，然后舍弃剩余小数位，这样所有的输入就变成值域在 $10^4$ 以内的整数了，然后用 $O(值域^2)$ 做法草过去就行。

#include <bits/stdc++.h>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("owo.in", "r", stdin);
        freopen("owo.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

typedef double db;

const int N = 1e6+10;
const int A = 2e4+10;

int n, m;
int a[N], b[N];
int t[A]; db sum[A];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        db x; cin >> x;
        a[i] = round(x*1e4);
    }
    for(int i = 1; i <= m; i++)
    {
        db x; cin >> x;
        b[i] = round(x*1e4), t[b[i]]++;
    }
    for(int i = 1e4; i <= 2e4; i++)
        for(int j = 1e4; j <= 2e4; j++)
            sum[i] += (db)i/(i+j)*t[j];
    for(int i = 1; i <= n; i++)
        printf("%.18lf\n", sum[a[i]]);
}


/*
3 2
1.0 2.0 1.5
1.0 2.0
*/

qaq

Description

有个无穷大的 $k$ 维空间，一开始在 $(0,0,\cdots,0)$ ，每次等概率地在 $2k$ 个方向中随机选一个方向走一步。

求走 $n$ 步之后能经过的不同位置的个数的期望，输出期望乘上 $(2k)^n$ 后对 $mod$ 取模的结果。

Input

一行三个正整数 $n, k, mod$

Output

一行一个整数表示答案。

Hint

$n \le 2000, k \le 10, mod \le 10^9+7$

Solution

$f_i$ 表示 $i$ 步之后第一次经过这个格子的方案。

$g_i$ 表示 $i$ 步之后停在这个格子的方案。

$h_i$ 表示从一个位置出发到原点的方案。

有 $f_i = g_i - \sum\limits _{j+k=i} f_j*h_k$

考虑 $h_i$ 与哪个格子没有关系，式子是一个 $g \rightarrow f$ 的线性变换。

对所有格子求和，有 $dp_i = (2k)^i - \sum\limits _{j+k=i} dp_j*h_k$ 。

用组合数暴力求卷积即可。

考虑求 $h_i$，发现每一维相互独立，直接背包就行。

#include <bits/stdc++.h>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("qaq.in", "r", stdin);
        freopen("qaq.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;


typedef long long ll;
const int N = 2005;
#define P p


int n, k, p;
ll C[N][N], pw[N];
ll f[N], g[N], h[N];

void prework(int n);

int main()
{
    cin >> n >> k >> p;
    prework(n);
    
    f[0] = 1; int m = n/2;
    for(int d = 1; d <= k; d++)
    {
        memcpy(g, f, sizeof(g));
        memset(f, 0, sizeof(f));
        for(int i = 0; i <= m; i++)
            for(int j = 0; i+j <= m; j++)
                (f[i+j] += g[i] * C[(i+j)*2][j*2]%P * C[j*2][j]%P) %= P;
    }
    
    for(int i = 0; i <= m; i++)
    {
        h[i] = f[i];
        for(int j = 1; j < i; j++)
        {
            h[i] -= h[j]*f[i-j]%P;
            h[i] = (h[i]%P+P)%P;
        }
    }
    
    ll ans = (n+1)*pw[n]%P;
    for(int i = 1; i <= m; i++)
    {
        ans -= h[i] * pw[n-i*2]%P * (n-i*2+1)%P;
        ans = (ans%P+P)%P;
    }
    
    cout << ans << "\n";
}


void prework(int n)
{
    C[0][0] = pw[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        pw[i] = pw[i-1]*2*k%P;
        C[i][0] = 1;
        for(int j = 1; j <= i; j++)
            C[i][j] = (C[i-1][j-1]+C[i-1][j])%P;
    }
    
}

tvt

Description

给一棵树，边带权，$q$ 次询问，每次询问 Alice 在 $t1$ 时刻从 $x1$ 出发走到 $y1$, Bob 在 $t2$ 时刻从 $x2$ 出发走到 $y2$ ，速度相同，问两人是否在某一时刻出现在同一条边上(不包括顶点)。

Input

第一行两个整数 $n, q$。

接下来 $n-1$ 行，每行三个整数 $x, y, w$ ，代表树上一条边。

接下来 $q$ 行，每行六个整数 $x1, y1, t1, x2, y2, t2$。

Output

输出 $q$ 行，每行为 YES 或 NO, 表示两个人是否在某一时刻同时出现在一条边上。

Hint

$n,q \le 10^5$

Solution

先求出路径交，然后分情况讨论。

如果两个人同向，那么比较路径交上最长边和时间差即可。

如果两个人相向，那么计算出相遇点，然后倍增或树剖判断相遇点是否恰好为一个顶点即可。

#include <bits/stdc++.h>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("tvt.in", "r", stdin);
        freopen("tvt.out", "w", stdout);
    }
};
// Rhine_Lab Ptilopsis_w;

typedef long long ll;
const int N = 1e5+10;

namespace ST {
    int mx[N][20];
    void init();
    int query(int l, int r);
}
namespace HLD {
    int fa[N], dep[N], siz[N];
    int big[N], top[N]; ll dis[N];
    int dfn[N], rk[N], dft;
    
    void dfs1(int x, int dad);
    void dfs2(int x, int tp);
    int lca(int x, int y);
    ll dist(int x, int y);
    int maxc(int x, int y);
    bool check(int x, ll w);
    pair<int,int> path(int a, int b, int c, int d);
}
using namespace HLD;

struct edge { int to, cost; };

int n, q;
vector<edge> ver[N];

signed main()
{
    cin >> n >> q;
    for(int i = 1; i < n; i++)
    {
        int a, b, w; cin >> a >> b >> w;
        ver[a].push_back({b, w});
        ver[b].push_back({a, w});
    }
    HLD::dfs1(1, 0);
    HLD::dfs2(1, 1);
    ST::init(); dis[0] = -1e18;
    for(int i = 1; i <= q; i++)
    {
        int u1, v1, t1, u2, v2, t2;
        cin >> u1 >> v1 >> t1 >> u2 >> v2 >> t2;
        
        auto p = HLD::path(u1, v1, u2, v2);
        int f = lca(p.first, p.second);
        
        if(p.first == -1) { cout << "NO\n"; continue; }
        
        ll d1 = t1+HLD::dist(u1, p.first);
        ll d2 = t1+HLD::dist(u1, p.second);
        ll d3 = t2+HLD::dist(u2, p.first);
        ll d4 = t2+HLD::dist(u2, p.second);
        if((d1 <= d2) != (d3 <= d4))
        {
            if((d1 <= d3 and d2 >= d4) or (d1 >= d3 and d2 <= d4))
            {
                ll len = dist(p.first,p.second)+min(d3,d4)-min(d1,d2);
                if(len%2 == 1)
                    cout << "YES\n";
                else
                {
                    len /= 2; int st;
                    if(d1 <= d2)
                    {
                        if(len <= dist(p.first, f))
                            st = p.first;
                        else
                            st = p.second, len = dist(p.first, p.second)-len;
                    }
                    else
                    {
                        if(len <= dist(p.second, f))
                            st = p.second;
                        else
                            st = p.first, len = dist(p.first, p.second)-len;
                    }
                    
                    cout << (HLD::check(st, len)?"NO\n":"YES\n");
                }
            }
            else
                cout << "NO\n";
        }
        else
        {
            if(abs(min(d1,d2)-min(d3,d4)) < HLD::maxc(p.first, p.second))
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
}

namespace HLD {
    void dfs1(int x, int dad)
    {
        siz[x] = 1;
        fa[x] = dad;
        dep[x] = dep[dad]+1;
        for(auto i : ver[x])
        {
            if(i.to == dad) continue;
            dis[i.to] = dis[x]+i.cost;
            dfs1(i.to, x); siz[x] += siz[i.to];
            if(siz[i.to] > siz[big[x]]) big[x] = i.to;
        }
    }
    void dfs2(int x, int tp)
    {
        top[x] = tp;
        dfn[x] = ++dft; rk[dft] = x;
        
        if(big[x]) dfs2(big[x], tp);
        for(auto i : ver[x])
            if(i.to != big[x] and i.to != fa[x])
                dfs2(i.to, i.to);
        
        for(auto i : ver[x])
            ST::mx[dfn[i.to]][0] = i.cost;
    }
    int lca(int x, int y)
    {
        while(top[x] != top[y])
        {
            if(dep[top[x]] < dep[top[y]]) swap(x, y);
            x = fa[top[x]];
        }
        return dep[x] < dep[y] ? x : y;
    }
    ll dist(int x, int y)
    {
        return dis[x]+dis[y]-2*dis[lca(x,y)];
    }
    
    int maxc(int x, int y)
    {
        int ans = 0;
        while(top[x] != top[y])
        {
            if(dep[top[x]] < dep[top[y]]) swap(x, y);
            ans = max(ans, ST::query(dfn[top[x]], dfn[x]));
            x = fa[top[x]];
        }
        if(dep[x] > dep[y]) swap(x, y);
        if(x != y) ans = max(ans, ST::query(dfn[x]+1, dfn[y]));
        return ans;
    }
    
    pair<int,int> path(int a, int b, int c, int d)
    {
        int p[] = {lca(a,c), lca(a,d), lca(b,c), lca(b,d)};
        sort(p, p+4, [&](int a, int b){
            return dep[a] > dep[b];
        });
        if(p[0] != p[1])
            return {p[0], p[1]};
        else
            return {-1, -1};
    }
    bool check(int x, ll w)
    {
        while(dis[x]-dis[fa[top[x]]] <= w)
        {
            w -= dis[x]-dis[fa[top[x]]];
            x = fa[top[x]];
        }
        int l = dfn[top[x]], r = dfn[x];
        while(l < r)
        {
            int mid = (l+r)>>1;
            if(dis[x]-dis[rk[mid]] < w)
                l = mid+1;
            else
                r = mid;
        }
        return dis[x]-dis[rk[l]] == w;
    }

}

namespace ST {
    void init()
    {
        for(int k = 1; k < 20; k++)
            for(int i = 1; i+(1<<k)-1 <= n; i++)
                mx[i][k] = max(mx[i][k-1], mx[i+(1<<(k-1))][k-1]);
    }
    int query(int l, int r)
    {
        int k = log2(r-l+1);
        return max(mx[l][k], mx[r-(1<<k)+1][k]);
    }
}

/*
3 1
1 2 1
2 3 1
1 3 1 3 1 1
NO

4 1
1 2 2
2 3 1
3 4 1
1 4 1 4 1 1
NO

6 1
3 2 1
2 1 1
1 4 2
4 5 2
5 6 2
3 6 1 6 3 1
NO
*/