526互联

2023冲刺国赛模拟 9.1

发布时间 2023-05-31 19:37:47作者: KafuuChinocpp

T1 哈密顿路

容易发现一条哈密顿回路一定会经过节点 \(1\) ，因此考虑从节点 \(1\) 进行 dp ，设 \(f_{S,i}\) 表示是否存在方案在 \(i\) 节点结束，经过点集为 \(S\) ，统计答案是需要枚举在 \(1\) 之前经过的点集简单进行合并即可。由于 dp 值只有 \(0/1\) ，压位后转移总复杂度为 \(O(n2^n)\) 。

code 
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 24, max2 = 1 << 24;
#define lowbit(now) ( now & -now )
int n;
char edge[max1 + 5][max1 + 5];
int f[max2 + 5], g[max2 + 5];

int ans[max1 + 5];

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

    scanf("%d", &n);
    for ( int i = 1; i <= n; i ++ )
    {
        scanf("%s", edge[i] + 1);
        for ( int j = 1; j <= n; j ++ )
            if ( edge[i][j] == '1' )
                f[1 << i - 1] |= 1 << j - 1;
    }

    for ( int s = 1; s < 1 << n; s ++ )
        f[s] = f[s ^ lowbit(s)] | f[lowbit(s)];

    g[1] = 1;
    for ( int s = 1; s < 1 << n; s ++ )
    {
        if ( !g[s] )
            continue;
        for ( int i = 1; i <= n; i ++ )
            if ( !( s >> i - 1 & 1 ) && ( f[g[s]] >> i - 1 & 1 ) )
                g[s | 1 << i - 1] |= 1 << i - 1;
    }

    for ( int s = 0; s < 1 << n; s ++ )
        for ( int i = 1; i <= n; i ++ )
            if ( g[s] >> i - 1 & 1 )
                ans[i] |= g[( ( 1 << n ) - 1 ) ^ s ^ 1];

    for ( int i = 1; i <= n; i ++ )
    {
        for ( int j = 1; j <= n; j ++ )
        {
            if ( i == j )
                putchar('0');
            else
                putchar('0' + ( ans[i] >> j - 1 & 1 ));
        }
        putchar('\n');
    }

    return 0;
}

T2 统一省选

考虑将每个关卡写成函数的形式：

\[\begin{aligned} f(x)&= \begin{cases} -\infty & x\le a_i\\ x-a_i & x>a_i \end{cases} \\ g(x)&= \begin{cases} -\infty & x<a_i\\ a_i & x\ge a_i \end{cases} \\ h(x)&= \begin{cases} a_i & x\le a_i\\ x & x>a_i \end{cases} \end{aligned} \]

容易发现这些操作可以归纳为函数：

\[f(x)= \begin{cases} -\infty & x\le A\\ Y & A<x\le B\\ x-B+Y & x > B \end{cases} \]

发现上述函数合并后形式不变，使用线段树维护即可。

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

const int max1 = 1e6;
const long long inf = 1e14;

int n, q;
long long H0;

struct Option
{
    int type;
    long long val;
}opt[max1 + 5];

struct Data
{
    long long A, B, Y;

    Data () {}
    Data ( long long __A, long long __B, long long __Y )
        { A = __A, B = __B, Y = __Y; }
};

Data Merge ( const Data &L, const Data &R )
{
    Data res;

    if ( R.B <= L.Y )
    {
        res.A = L.A;
        res.B = L.B;
        res.Y = L.Y - R.B + R.Y;
    }
    else if ( R.A < L.Y && R.B > L.Y )
    {
        res.A = L.A;
        res.B = L.B + R.B - L.Y;
        res.Y = R.Y;
    }
    else
    {
        res.A = R.A + L.B - L.Y;
        res.B = R.B + L.B - L.Y;
        res.Y = R.Y;
    }

    return res;
}

long long Query ( long long x, const Data &D )
{
    if ( x <= D.A )
        return -inf;
    else if ( x > D.B )
        return x - D.B + D.Y;
    return D.Y;
}

struct Segment_Tree
{
    #define lson(now) ( now << 1 )
    #define rson(now) ( now << 1 | 1 )

    Data tree[max1 * 4 + 5];

    void Insert ( int now, int pos )
    {
        if ( opt[pos].type == 1 )
        {
            tree[now].A = opt[pos].val;
            tree[now].B = opt[pos].val;
            tree[now].Y = 0;
        }
        else if ( opt[pos].type == 2 )
        {
            tree[now].A = opt[pos].val - 1;
            tree[now].B = inf;
            tree[now].Y = opt[pos].val;
        }
        else
        {
            tree[now].A = 0;
            tree[now].B = opt[pos].val;
            tree[now].Y = opt[pos].val;
        }
        return;
    }

    void Build ( int now, int L, int R )
    {
        if ( L == R )
            return Insert(now, L);

        int mid = L + R >> 1;
        Build(lson(now), L, mid);
        Build(rson(now), mid + 1, R);

        tree[now] = Merge(tree[lson(now)], tree[rson(now)]);
        return;
    }

    void Insert ( int now, int L, int R, int pos )
    {
        if ( L == R )
            return Insert(now, pos);

        int mid = L + R >> 1;
        if ( pos <= mid )
            Insert(lson(now), L, mid, pos);
        else
            Insert(rson(now), mid + 1, R, pos);

        tree[now] = Merge(tree[lson(now)], tree[rson(now)]);
        return;
    }

    Data tmp;

    int Query ( int now, int L, int R, int pos )
    {
        if ( L >= pos )
        {
            Data sum = Merge(tmp, tree[now]);

            int mid = L + R >> 1;
            if ( ::Query(H0, sum) <= 0 )
            {
                if ( L == R )
                    return L;

                int res = Query(lson(now), L, mid, pos);
                if ( res == -1 )
                    res = Query(rson(now), mid + 1, R, pos);
                return res;
            }

            tmp = sum;
            return -1;
        }

        int mid = L + R >> 1, res = -1;
        if ( pos <= mid )
            res = Query(lson(now), L, mid, pos);
        if ( res == -1 )
            res = Query(rson(now), mid + 1, R, pos);
        return res;
    }
}Tree;

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

    scanf("%d%d%lld", &n, &q, &H0);
    for ( int i = 1; i <= n; i ++ )
        scanf("%d%lld", &opt[i].type, &opt[i].val);
    Tree.Build(1, 1, n);

    int op, x, ans;
    while ( q -- )
    {
        scanf("%d", &op);
        if ( op == 1 )
        {
            scanf("%d", &x);
            scanf("%d%lld", &opt[x].type, &opt[x].val);
            Tree.Insert(1, 1, n, x);
        }
        else
        {
            scanf("%d", &x); Tree.tmp.A = Tree.tmp.B = Tree.tmp.Y = 0;
            ans = Tree.Query(1, 1, n, x);

            if ( ans == x )
                printf("-1\n");
            else if ( ans == -1 )
                printf("%d\n", n);
            else
                printf("%d\n", ans - 1);
        }
    }
    return 0;
}

T3 并行计算

根据某些奇怪的证明可以知道操作次数下界为 \(\min(\lceil\log n\rceil,0.4n)+O(1)\) 。

可以大力手玩得到 \(6\) 次消去 \(15\) 个数，以及 \(4\) 次消去 \(10\) 个数的构造，对于 \(n\) 的大部分使用上述构造，其余的使用 \(3\) 次 \(7\) 个数， \(2\) 次 \(3\) 个数， \(1\) 次 \(1\) 个数简单补全即可。

由于数据点较少但本题特殊情况较多，代码可能在一些情况上存在漏洞。

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

struct Answer
{
    int a, b, c;

    Answer () {}
    Answer ( int __a, int __b, int __c )
        { a = __a, b = __b, c = __c; }
};

vector <Answer> ans;

void Make_16_6 ( int s )
{
    ans.push_back(Answer(s + 1, s + 2, s + 2));
    ans.push_back(Answer(s + 3, s + 4, s + 4));
    ans.push_back(Answer(s + 5, s + 6, s + 6));
    ans.push_back(Answer(s + 8, s + 9, s + 9));
    
    ans.push_back(Answer(s + 2, s + 3, s + 3));
    ans.push_back(Answer(s + 2, s + 4, s + 4));
    ans.push_back(Answer(s + 6, s + 7, s + 7));
    ans.push_back(Answer(s + 10, s + 11, s + 11));

    ans.push_back(Answer(s + 4, s + 5, s + 5));
    ans.push_back(Answer(s + 4, s + 6, s + 6));
    ans.push_back(Answer(s + 4, s + 7, s + 7));
    ans.push_back(Answer(s + 13, s + 14, s + 14));

    ans.push_back(Answer(s + 7, s + 8, s + 8));
    ans.push_back(Answer(s + 7, s + 9, s + 9));
    ans.push_back(Answer(s + 11, s + 12, s + 12));
    ans.push_back(Answer(s + 14, s + 15, s + 15));

    ans.push_back(Answer(s + 9, s + 10, s + 10));
    ans.push_back(Answer(s + 9, s + 11, s + 11));
    ans.push_back(Answer(s + 9, s + 12, s + 12));
    ans.push_back(Answer(s + 15, s + 16, s + 16));

    ans.push_back(Answer(s + 12, s + 13, s + 13));
    ans.push_back(Answer(s + 12, s + 14, s + 14));
    ans.push_back(Answer(s + 12, s + 15, s + 15));
    ans.push_back(Answer(s + 12, s + 16, s + 16));
    return;
}

void Make_11_4 ( int s )
{
    ans.push_back(Answer(s + 1, s + 2, s + 2));
    ans.push_back(Answer(s + 3, s + 4, s + 4));
    ans.push_back(Answer(s + 5, s + 6, s + 6));
    ans.push_back(Answer(s + 8, s + 9, s + 9));

    ans.push_back(Answer(s + 2, s + 3, s + 3));
    ans.push_back(Answer(s + 2, s + 4, s + 4));
    ans.push_back(Answer(s + 6, s + 7, s + 7));
    ans.push_back(Answer(s + 9, s + 10, s + 10));

    ans.push_back(Answer(s + 4, s + 5, s + 5));
    ans.push_back(Answer(s + 4, s + 6, s + 6));
    ans.push_back(Answer(s + 4, s + 7, s + 7));
    ans.push_back(Answer(s + 10, s + 11, s + 11));

    ans.push_back(Answer(s + 7, s + 8, s + 8));
    ans.push_back(Answer(s + 7, s + 9, s + 9));
    ans.push_back(Answer(s + 7, s + 10, s + 10));
    ans.push_back(Answer(s + 7, s + 11, s + 11));
    return;
}

void Make_8_3 ( int s )
{
    ans.push_back(Answer(s + 1, s + 2, s + 2));
    ans.push_back(Answer(s + 3, s + 4, s + 4));
    ans.push_back(Answer(s + 5, s + 6, s + 6));
    ans.push_back(Answer(s + 7, s + 8, s + 8));
    
    ans.push_back(Answer(s + 2, s + 3, s + 3));
    ans.push_back(Answer(s + 2, s + 4, s + 4));
    ans.push_back(Answer(s + 6, s + 7, s + 7));
    ans.push_back(Answer(s + 6, s + 8, s + 8));

    ans.push_back(Answer(s + 4, s + 5, s + 5));
    ans.push_back(Answer(s + 4, s + 6, s + 6));
    ans.push_back(Answer(s + 4, s + 7, s + 7));
    ans.push_back(Answer(s + 4, s + 8, s + 8));
    return;
}

void Make_4_2 ( int s )
{
    ans.push_back(Answer(s + 1, s + 2, s + 2));
    ans.push_back(Answer(s + 3, s + 4, s + 4));
    ans.push_back(Answer(2000, 2000, 2000));
    ans.push_back(Answer(2000, 2000, 2000));

    ans.push_back(Answer(s + 2, s + 3, s + 3));
    ans.push_back(Answer(s + 2, s + 4, s + 4));
    ans.push_back(Answer(2000, 2000, 2000));
    ans.push_back(Answer(2000, 2000, 2000));
    return;
}

void Make_2_1 ( int s )
{
    ans.push_back(Answer(s + 1, s + 2, s + 2));
    ans.push_back(Answer(2000, 2000, 2000));
    ans.push_back(Answer(2000, 2000, 2000));
    ans.push_back(Answer(2000, 2000, 2000));
    return;
}

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

    int n, s; scanf("%d", &n);
    for ( s = 0; s + 16 <= n; s += 15 )
        Make_16_6(s);

    if ( n - s == 1 )
        ;
    else if ( n - s == 2 )
        Make_2_1(s);
    else if ( n - s == 3 )
        Make_4_2(s);
    else if ( n - s == 4 )
        Make_4_2(s);
    else if ( n - s == 5 )
    {
        if ( !ans.empty() )
        {
            for ( int i = 0; i < 24; i ++ )
                ans.pop_back();
            Make_11_4(s - 15);
            Make_11_4(s - 5);
        }
        else
            Make_8_3(s);
    }
    else if ( n - s == 6 )
    {
        if ( !ans.empty() )
        {
            for ( int i = 0; i < 24; i ++ )
                ans.pop_back();
            Make_11_4(s - 15);
            Make_11_4(s - 5);
        }
        else
            Make_8_3(s);
    }
    else if ( n - s == 7 )
        Make_8_3(s);
    else if ( n - s == 8 )
        Make_8_3(s);
    else if ( n - s == 9 )
        Make_11_4(s);
    else if ( n - s == 10 )
        Make_11_4(s);
    else if ( n - s == 11 )
        Make_11_4(s);
    else if ( n - s == 12 )
        Make_11_4(s), Make_2_1(s + 10);
    else if ( n - s == 13 )
        Make_11_4(s), Make_4_2(s + 10);
    else if ( n - s == 14 )
        Make_11_4(s), Make_4_2(s + 10);
    else
        Make_11_4(s), Make_8_3(s + 10);
    
    printf("%lu\n", ans.size() >> 2);

    int cnt = 0;
    for ( auto v : ans )
    {
        printf("%d %d %d ", v.c, v.a, v.b);
        ++cnt;
        if ( !( cnt & 3 ) )
            putchar('\n');
    }

    return 0;
}