526互联

2023冲刺国赛模拟 15.1

发布时间 2023-06-10 22:24:24作者: KafuuChinocpp

T1 计数

首先考虑计数有标号可重叠的方案数，容易发现此时 \(x,y\) 两维独立，因此考虑其中 \(1\) 维，设 \(f_{i,j}\) 表示此时考虑到第 \(i\) 对左右边界 \((x_{i,1},x_{i,2})\) ，离散化后的 \(x\) 坐标形成了 \(j\) 个点时的方案数，容易发现此时数轴上存在 \(j\) 个点，以及 \(j+1\) 个空白段，转移考虑 \(x_{i+1,1}\) 和 \(x_{i+1,2}\) 的位置，容易发现存在以下三种转移：

  1. \(x_{i+1,1}\) 和 \(x_{i+1,2}\) 均位于空白段内：

\[f_{i,j}\times (\binom{j+1}{2}+j+1)\to f_{i+1,j+2} \]

  1. \(x_{i+1,1}\) 和 \(x_{i+1,2}\) 一个位于原先点上，一个位于空白段内：

\[f_{i,j}\times j\times (j+1)\to f_{i+1,j+1} \]

  1. \(x_{i+1,1}\) 和 \(x_{i+1,2}\) 均位于原有点上：

\[f_{i,j}\times \binom{j}{2}\to f_{i+1,j} \]

\(i\) 个矩形的方案数显然为 \((\sum_j f_{i,j})^2\) 。

考虑计算题目要求的答案，即 \(n\) 个矩形无标号，不可重叠的方案数，设答案为 \(ans(n)\) ，设有标号，可重叠方案数为 \(g(n)\) ，设一个长度为 \(n\) 的序列，总共有 \(i\) 种元素，要求每个元素至少出现一次的合法序列的数量为 \(h(n,i)\) ，容易发现这样的等量关系：

\[g(n)=\sum_{i=1}^{n}ans(i)h(n,i) \]

直接 \(O(n^2)\) 递推即可。

code 
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int max1 = 5000;
const int mod = 1e9 + 7;

int n;

int g[2][max1 * 2 + 5], h[2][max1 + 5], now;
int f[max1 + 5];

int Binom ( int x )
{
    return ( 1LL * x * ( x - 1 ) >> 1 ) % mod;
}

int Calc ( int x )
{
    return ( 1LL * ( x + 1 ) * x >> 1 ) % mod;
}

void Add ( int &x, int y )
{
    x += y;
    if ( x >= mod )
        x -= mod;
    return;
}

int Quick_Power ( int base, int p )
{
    int res = 1;
    while ( p )
    {
        if ( p & 1 )
            res = 1LL * res * base % mod;
        p >>= 1;
        base = 1LL * base * base % mod;
    }
    return res;
}

int main ()
{
    freopen("count.in", "r", stdin);
    freopen("count.out", "w", stdout);

    scanf("%d", &n);

    now = 0; g[now][0] = 1; h[now][0] = 1;
    for ( int i = 1; i <= n; i ++ )
    {
        now ^= 1;
        memset(g[now], 0, sizeof(int) * ( i + i + 1 ));
        memset(h[now], 0, sizeof(int) * ( i + 1 ));

        for ( int j = 0; j <= i + i - 2; j ++ )
        {
            g[now][j + 2] = ( g[now][j + 2] + 1LL * g[now ^ 1][j] * ( Binom(j + 1) + j + 1 ) ) % mod;
            g[now][j + 1] = ( g[now][j + 1] + 2LL * g[now ^ 1][j] * Calc(j) ) % mod;
            g[now][j] = ( g[now][j] + 1LL * g[now ^ 1][j] * Binom(j) ) % mod;
        }

        for ( int j = 0; j <= i - 1; j ++ )
        {
            h[now][j + 1] = ( h[now][j + 1] + 1LL * h[now ^ 1][j] * ( j + 1 ) ) % mod;
            h[now][j] = ( h[now][j] + 1LL * h[now ^ 1][j] * j ) % mod;
        }

        int sum = 0;
        for ( int j = 0; j <= i + i; j ++ )
            Add(sum, g[now][j]);
        sum = 1LL * sum * sum % mod;

        for ( int j = 1; j <= i - 1; j ++ )
            Add(sum, mod - 1LL * f[j] * h[now][j] % mod);

        f[i] = 1LL * sum * Quick_Power(h[now][i], mod - 2) % mod;
    }

    printf("%d\n", f[n]);

    return 0;
}

T2 AKEE的大砍刀

将原问题抽象，将含有公共边的三角形连边，容易发现形成树形结构，那么在原多边形上切一刀相当于断裂树上一条边，因此考虑维护每个小朋友吃的蛋糕所构成的虚树，对于每条边维护边权表示有多少虚树覆盖了这条边，此时我们的操作为树上一条链边权全局加，查询最小值以及最小值个数，很容易使用树剖 + 线段树维护，当然，由于笔者是废物，脑子经常断路，所以写了树剖套分块，具体而言对于每条重链分块即可，复杂度为 \(O(n\sqrt n)\) 。

code 
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
using namespace std;

const int max1 = 1e5;
const int inf = 0x3f3f3f3f;

int n, q, color[max1 + 5];
map < pair <int, int>, int > Map;
vector <int> edge[max1 + 5];

int siz[max1 + 5], deep[max1 + 5], father[max1 + 5], son[max1 + 5];
int top[max1 + 5], dfn[max1 + 5], rk[max1 + 5], dfs_clock;

set <int> point[max1 + 5];
int ans;

struct Part
{
    int total, len, block;
    vector <int> st, ed, bel;
    vector <int> val, tag, Min, cnt;

    void Build ()
    {
        len = sqrt(total), block = total / len;

        st.resize(total + 1), ed.resize(total + 1), bel.resize(total + 1);

        st[0] = ed[0] = 0;
        for ( int i = 1; i <= block; i ++ )
        {
            st[i] = ed[i - 1] + 1;
            ed[i] = i * len;
        }
        ed[block] = total;

        for ( int i = 1; i <= block; i ++ )
            for ( int j = st[i]; j <= ed[i]; j ++ )
                bel[j] = i;

        val.resize(total + 1);
        tag.resize(total + 1);
        Min.resize(total + 1);
        cnt.resize(total + 1);

        for ( int i = 1; i <= total; i ++ )
            val[i] = 0;
        
        for ( int i = 1; i <= block; i ++ )
        {
            tag[i] = Min[i] = 0;
            cnt[i] = ed[i] - st[i] + 1;
            ans += cnt[i];
        }
        return;
    }

    void Update ( int L, int R, int k )
    {
        if ( bel[L] == bel[R] )
        {
            int B = bel[L], BL = st[B], BR = ed[B];

            if ( !( tag[B] + Min[B] ) )
                ans -= cnt[B];

            for ( int i = BL; i <= BR; i ++ )
                val[i] += tag[B];
            for ( int i = L; i <= R; i ++ )
                val[i] += k;
            
            tag[B] = 0;
            Min[B] = inf;
            for ( int i = BL; i <= BR; i ++ )
                Min[B] = min(Min[B], val[i]);
            cnt[B] = 0;
            for ( int i = BL; i <= BR; i ++ )
                cnt[B] += val[i] == Min[B];
            
            if ( !Min[B] )
                ans += cnt[B];
        }
        else
        {
            Update(L, ed[bel[L]], k);
            Update(st[bel[R]], R, k);

            for ( int i = bel[L] + 1; i <= bel[R] - 1; i ++ )
            {
                if ( !( tag[i] + Min[i] ) )
                    ans -= cnt[i];
                
                tag[i] += k;
                
                if ( !( tag[i] + Min[i] ) )
                    ans += cnt[i];
            }
        }
        return;
    }

}part[max1 + 5];

void Find_Heavy_Edge ( int now, int fa, int depth )
{
    siz[now] = 1, deep[now] = depth, father[now] = fa, son[now] = 0;

    int max_siz = 0;

    for ( auto v : edge[now] )
    {
        if ( v == fa )
            continue;

        Find_Heavy_Edge(v, now, depth + 1);
        siz[now] += siz[v];
        if ( siz[v] > max_siz )
            max_siz = siz[v], son[now] = v;
    }
    return;
}

void Connect_Heavy_Edge ( int now, int ancestor )
{
    top[now] = ancestor;
    dfn[now] = ++dfs_clock;
    rk[dfs_clock] = now;
    ++part[top[now]].total;

    if ( son[now] )
        Connect_Heavy_Edge(son[now], ancestor);

    for ( auto v : edge[now] )
    {
        if ( v == father[now] || v == son[now] )
            continue;

        Connect_Heavy_Edge(v, v);
    }
    return;
}

int Get_Lca ( int u, int v )
{
    while ( top[u] != top[v] )
    {
        if ( deep[top[u]] < deep[top[v]] )
            swap(u, v);

        u = father[top[u]];
    }

    if ( deep[u] > deep[v] )
        swap(u, v);
    return u;
}

void Update ( int u, int v, int k )
{
    while ( top[u] != top[v] )
    {
        if ( deep[top[u]] < deep[top[v]] )
            swap(u, v);

        part[top[u]].Update(1, deep[u] - deep[top[u]] + 1, k);
        u = father[top[u]];
    }

    if ( deep[u] > deep[v] )
        swap(u, v);
    
    if ( u != v )
        part[top[u]].Update(deep[u] - deep[top[u]] + 2, deep[v] - deep[top[u]] + 1, k);
    
    return;
}

void Insert ( int x )
{
    int c = color[x];

    if ( !point[c].empty() )
    {
        int p = rk[*point[c].begin()], q = rk[*--point[c].end()], lca = Get_Lca(p, q);

        if ( dfn[x] >= dfn[lca] && dfn[x] <= dfn[lca] + siz[lca] - 1 )
        {
            p = rk[*--point[c].upper_bound(dfn[x])];
            lca = Get_Lca(p, x);

            if ( *--point[c].end() > dfn[x] )
            {
                p = rk[*point[c].upper_bound(dfn[x])];
                q = Get_Lca(p, x);

                if ( deep[q] > deep[lca] )
                    lca = q;
            }
        }

        Update(x, lca, 1);
    }

    point[c].insert(dfn[x]);

    return;
}

void Delete ( int x )
{
    int c = color[x];

    point[c].erase(point[c].find(dfn[x]));

    if ( !point[c].empty() )
    {
        int p = rk[*point[c].begin()], q = rk[*--point[c].end()], lca = Get_Lca(p, q);

        if ( dfn[x] >= dfn[lca] && dfn[x] <= dfn[lca] + siz[lca] - 1 )
        {
            p = rk[*--point[c].upper_bound(dfn[x])];
            lca = Get_Lca(p, x);

            if ( *--point[c].end() > dfn[x] )
            {
                p = rk[*point[c].upper_bound(dfn[x])];
                q = Get_Lca(p, x);

                if ( deep[q] > deep[lca] )
                    lca = q;
            }
        }

        Update(x, lca, -1);
    }

    return;
}

int main ()
{
    freopen("akee.in", "r", stdin);
    freopen("akee.out", "w", stdout);

    int tmp[3];
    scanf("%d", &n); n -= 2;
    for ( int i = 1; i <= n; i ++ )
    {
        scanf("%d%d%d%d", &tmp[0], &tmp[1], &tmp[2], &color[i]);

        sort(tmp, tmp + 3);

        for ( int j = 0; j < 3; j ++ )
        {
            for ( int k = j + 1; k < 3; k ++ )
            {
                if ( Map.find(make_pair(tmp[j], tmp[k])) != Map.end() )
                {
                    int v = Map[make_pair(tmp[j], tmp[k])];
                    edge[i].push_back(v); edge[v].push_back(i);
                }
                else
                    Map[make_pair(tmp[j], tmp[k])] = i;
            }
        }
    }

    for ( int i = 1; i <= n; i ++ )
        part[i].total = 0;

    Find_Heavy_Edge(1, 0, 0);
    Connect_Heavy_Edge(1, 1);

    for ( int i = 1; i <= n; i ++ )
        if ( i == top[i] )
            part[i].Build();

    for ( int i = 1; i <= n; i ++ )
        Insert(i);
    
    printf("%d\n", ans - 1);
    scanf("%d", &q);

    int x, p;
    while ( q -- )
    {
        scanf("%d%d", &x, &p);
        Delete(x);
        color[x] = p;
        Insert(x);
        printf("%d\n", ans - 1);
    }

    return 0;
}

T3 普及题

设第 \(i\) 个特殊点的临域集合为 \(S_i\) ，设 \(S=\cup S_i\) ，那么我们需要求解 \(|S|\) ，考虑构造一个长度为 \(\sum |S_i|\) 的序列 \(x\) ，对于每个集合 \(S_i\) ，设 \(a\) 为 \(S_i\) 中一个元素，设 \(a\) 在所有集合中的出现次数为 \(r\) ，那么 \(\tfrac{1}{r}\) 位于序列 \(x\) 中，容易发现 \(\sum x_i\) 就是我们需要求解的答案。

由于 \(x\) 序列的长度很容易计算，因此考虑求解 \(E(x_i)\) ，一种经典做法是随机取出 \(x\) 序列中一个数，然后求解所有数的平均值。

首先考虑随机的过程，选定当前数属于的集合（假设当前随机次数确定，可以直接计算当前集合内期望取出的数的个数），然后等概率随机集合内一个与当前集合对应点存在连边的点，由于可以确定当前集合的大小，可以随机排名后，通过字典序按位依次确定，设随机次数为 \(N\) ，此时复杂度为 \(O(Nk)\) 。

考虑求解当前随机点所对应的 \(r\) ，直接暴力的复杂度为 \(O(Tk)\) ，总复杂度为 \(O(NTk^2)\) ，然而题解表示 \(N\) 的大小需要为 \(O(k^2\epsilon^2)\) ，即使时限为 \(20s\) 也无法通过，考虑优化这个过程，预处理数组 \(f_{i,j,w}\) 表示在 \(i\) 这一维（一个点总共有 \(k\) 维），原图上 \(j\) 点与第 \(w\) 个特殊点的第 \(i\) 维是否存在连边，由于数组值只存在 \(0/1\) 状态，因此可以压位处理，考虑当前随机点与哪些特殊点存在连边，容易直接得到当前随机点的每一维与特殊点在这一维上的连边情况，但是由于这个矩阵是竖着压位存储的，但是我们需要的信息（当前随机点与特殊点每一维上边的个数）需要这个矩阵横着压位存储才能使用 __builtin_popcount 快速计算，因此考虑对原矩阵进行转置。

考虑一种转置的方法，假设当前矩阵的行列相等并且均为 \(2\) 的整数幂，可以考虑分治，将原矩阵行列分成均等的四份，对四个小矩阵分别转置，之后交换左下角与右上角的矩阵，容易发现次数的矩阵就是转置矩阵，复杂度为 \(O(n^2\log n)\) ，由于矩阵每一位只存在 \(0/1\) 状态，因此这个过程可以使用神奇的二进制技巧实现，复杂度可以做到 \(O(\tfrac{n^2\log n}{w})\) ，可以通过本题。

code 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <random>
#include <bitset>
#include <iostream>
using namespace std;

const int max1 = 32, max2 = 1000;
const int seed = 1204;
mt19937 rnd((unsigned long long)&seed);

double Sdouble ( double L, double R )
{
    return uniform_real_distribution <double> (L, R) (rnd);
}

int n, m, k, s, T;
vector <int> edge[max2 + 5], rev_edge[max2 + 5];
bitset <max2 + 5> connect[max2 + 5];
int point[max1 + 5][max1 + 5];
unsigned int is_edge[max1 + 5][max2 + 5];
unsigned int tmp[max1 + 5], matrix[max1 + 5];

double f[max1 + 5][max1 + 5], sum[max1 + 5], total, ans;

int sp[max1 + 5], cnt;

int main ()
{
    freopen("tech.in", "r", stdin);
    freopen("tech.out", "w", stdout);

    scanf("%d%d%d%d%d", &n, &m, &k, &s, &T);

    for ( int i = 1, u, v; i <= m; i ++ )
    {
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);

        connect[u][v] = connect[v][u] = 1;
    }

    for ( int i = 1; i <= T; i ++ )
        for ( int j = 1; j <= k; j ++ )
            scanf("%d", &point[i][j]);
    
    for ( int i = 1; i <= n; i ++ )
    {
        sort(edge[i].begin(), edge[i].end());
        edge[i].erase(unique(edge[i].begin(), edge[i].end()), edge[i].end());
        int pre = 0;
        for ( auto v : edge[i] )
        {
            for ( int j = pre + 1; j <= v - 1; j ++ )
                rev_edge[i].push_back(j);
            pre = v;
        }

        for ( int j = pre + 1; j <= n; j ++ )
            rev_edge[i].push_back(j);
    }

    for ( int i = 1; i <= T; i ++ )
    {
        for ( int j = 1; j <= k; j ++ )
        {
            for ( auto v : edge[point[i][j]] )
            {
                is_edge[j][v] |= 1u << i - 1;
            }
        }
    }
    
    for ( int i = 1; i <= T; i ++ )
    {
        memset(f, 0, sizeof(f));
        f[0][0] = 1.0;
        for ( int j = 1; j <= k; j ++ )
        {
            for ( int w = 0; w <= s; w ++ )
            {
                f[j][w] += f[j - 1][w] * rev_edge[point[i][j]].size();
                f[j][w + 1] += f[j - 1][w] * edge[point[i][j]].size();
            }
        }
        sum[i] = f[k][s];
        total += sum[i];
    }

    if ( total < 1 )
    {
        printf("0\n");
        return 0;
    } 

    for ( int i = 1; i <= T; i ++ )
    {
        int p = k * k * 10000 * sum[i] / total;

        memset(f, 0, sizeof(f));
        f[0][0] = 1.0;
        for ( int j = 1; j <= k; j ++ )
        {
            for ( int w = 0; w <= s; w ++ )
            {
                f[j][w] += f[j - 1][w] * rev_edge[point[i][j]].size();
                f[j][w + 1] += f[j - 1][w] * edge[point[i][j]].size();
            }
        }

        while ( p -- )
        {
            double val = floor(Sdouble(1.0, sum[i] + 0.99999));
            int now = s;

            bool flag = false;

            for ( int j = k; j >= 1; j -- )
            {
                if ( f[j - 1][now] * rev_edge[point[i][j]].size() >= val )
                {
                    sp[j] = rev_edge[point[i][j]][(int)( ( val - 1 ) / f[j - 1][now] )];
                    val -= (int)( ( val - 1 ) / f[j - 1][now] ) * f[j - 1][now];
                }
                else
                {
                    if ( !now )
                        { flag = true; break; }
                    
                    val -= f[j - 1][now] * rev_edge[point[i][j]].size();
                    sp[j] = edge[point[i][j]][(int)( ( val - 1 ) / f[j - 1][now - 1] )];
                    val -= (int)( ( val - 1 ) / f[j - 1][now - 1] ) * f[j - 1][now - 1];
                    --now;
                }
            }

            if ( flag )
                continue;

            for ( int j = 1; j <= 32; j ++ )
                matrix[j - 1] = is_edge[j][sp[j]];
            
            for ( int bit = 0; bit < 5; bit ++ )
            {
                for ( int j = 0; j < 32; j ++ )
                    tmp[j] = matrix[j];
                
                unsigned int x = 0, y = 0;
                for ( int j = 0; j < 32; j ++ )
                {
                    if ( j >> bit & 1 )
                        x |= 1u << j;
                    else
                        y |= 1u << j;
                }

                for ( int j = 0; j < 32; j += 1 << bit + 1 )
                {
                    for ( int w = 0; w < 1 << bit; w ++ )
                    {
                        matrix[j + w] = ( ( tmp[j + w] & y ) | ( tmp[j + ( 1 << bit ) + w] & y ) << ( 1 << bit ) );
                        matrix[j + ( 1 << bit ) + w] = ( ( tmp[j + w] & x ) >> ( 1 << bit ) | ( tmp[j + ( 1 << bit ) + w] & x ) );
                    }
                }
            }

            int match = 0;
            for ( int j = 0; j < 32; j ++ )
                match += __builtin_popcount(matrix[j]) == s;
            if ( match )
            {
                ans += 1.0 / match;
                ++cnt;
            }
        }
    }

    ans = ans * total / cnt;
    printf("%.8lf\n", ans);

    return 0;
}