首页 > 其他分享 >2023冲刺国赛模拟 6.0

2023冲刺国赛模拟 6.0

时间：2023-05-22 14:59:20浏览次数：50  
标签：include int siz max1 pos 国赛 6.0 2023 now

T1 染色

我们按照深度分别进行考虑，设当前考虑的深度为 \(x\) ，考虑一种暴力的做法是设 \(f_u\) 表示将 \(u\) 节点内所有深度为 \(x\) 的点全部涂黑的最小代价，显然有转移 \(f_u=\min(\sum f_v,a_{x-deep_u})\) ，正解考虑将深度为 \(x\) 的点取出来建立虚树，容易发现一个点代表原树一条链，因此这个点可以选择的方案对应 \(a\) 数组上一段连续的区间，用 ST 表维护区间最小值即可。

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

const int max1 = 1e5;

int n, a[max1 + 5];
vector <int> edge[max1 + 5];

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

vector <int> point[max1 + 5];
int tmp[max1 * 2 + 5], len;
int s[max1 + 5], stop;
vector <int> new_edge[max1 + 5];

long long f[max1 + 5], ans;

void Find_Heavy_Edge ( int now, int fa, int depth )
{
    father[now] = fa, deep[now] = depth, siz[now] = 1, son[now] = 0;
    int max_siz = 0;
    for ( auto v : edge[now] )
    {
        if ( v == fa )
            continue;
        Find_Heavy_Edge(v, now, depth + 1);
        if ( max_siz < siz[v] )
            max_siz = siz[v], son[now] = v;
        siz[now] += siz[v];
    }
    return;
}

void Connect_Heavy_Edge ( int now, int ancestor )
{
    top[now] = ancestor;
    dfn[now] = ++dfs_clock;
    rk[dfs_clock] = now;
    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;
}

struct ST_List
{
    int list[max1 + 5][18];
    
    void Build ()
    {
        for ( int i = 1; i <= n; i ++ )
            list[i][0] = a[i];
        for ( int k = 1; ( 1 << k ) <= n; k ++ )
            for ( int i = 1; i + ( 1 << k ) - 1 <= n; i ++ )
                list[i][k] = min(list[i][k - 1], list[i + ( 1 << k - 1 )][k - 1]);
        return;
    }

    int Query ( int L, int R )
    {
        return min(list[L][__lg(R - L + 1)], list[R - ( 1 << __lg(R - L + 1) ) + 1][__lg(R - L + 1)]);
    }
}ST;

bool Cmp ( const int &x, const int &y )
{
    return dfn[x] < dfn[y];
}

void DP ( int now, int pre, int target )
{
    f[now] = ST.Query(target - deep[now] + 1, target - pre);
    
    if ( !new_edge[now].empty() )
    {
        long long sum = 0;
        for ( auto v : new_edge[now] )
        {
            DP(v, deep[now], target);
            sum += f[v];
        }
        f[now] = min(f[now], sum);
    }
    return;
}

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

    scanf("%d", &n);
    for ( int i = 1; i <= n; i ++ )
        scanf("%d", &a[i]);

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

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

    for ( int i = 1; i <= n; i ++ )
        point[deep[i]].push_back(i);

    ST.Build();

    ans = 0;

    for ( int i = 0; i <= n - 1; i ++ )
    {
        if ( point[i].empty() )
            continue;
        
        sort(point[i].begin(), point[i].end(), Cmp);
        len = 0;
        int cnt = point[i].size() - 1;
        for ( int k = 0; k <= cnt; k ++ )
            tmp[++len] = dfn[point[i][k]];
        for ( int k = 0; k <= cnt - 1; k ++ )
            tmp[++len] = dfn[Get_Lca(point[i][k], point[i][k + 1])];
        tmp[++len] = 1;
        
        sort(tmp + 1, tmp + 1 + len);
        len = unique(tmp + 1, tmp + 1 + len) - ( tmp + 1 );

        for ( int k = 1; k <= len; k ++ )
        {
            tmp[k] = rk[tmp[k]];
            new_edge[tmp[k]].clear();
        }
        
        stop = 0;
        for ( int k = 1; k <= len; k ++ )
        {
            while ( stop && Get_Lca(s[stop], tmp[k]) != s[stop] )
                --stop;
            if ( stop )
                new_edge[s[stop]].push_back(tmp[k]);
            s[++stop] = tmp[k];
        }

        DP(1, -1, i);

        ans += f[1];
    }

    printf("%lld\n", ans);

    return 0;
}

T2 技能

2023冲刺清北营10 T3 。

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

const int max1 = 1000, lim = 200;
const int inf = 0x3f3f3f3f;

int n, a[max1 + 5][3];
int now, f[2][max1 + 5][max1 + 5][3];

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

    scanf("%d", &n);
    for ( int i = 1; i <= n; i ++ )
        for ( int k = 0; k < 3; k ++ )
            scanf("%d", &a[i][k]);
    
    now = 0;
    for ( int i = 0; i <= n; i ++ )
        for ( int j = 0; j <= n; j ++ )
            for ( int k = 0; k < 3; k ++ )
                f[now][i][j][k] = -inf;

    f[now][1][1][0] = f[now][1][1][1] = f[now][1][1][2] = 0;

    for ( int i = 1; i <= n; i ++ )
    {
        now ^= 1;
        for ( int j = max(1, i - lim); j <= i + 1; j ++ )
            for ( int k = max(1, i - lim); k <= i + 1; k ++ )
                for ( int w = 0; w < 3; w ++ )
                    f[now][j][k][w] = -inf;
        
        for ( int j = max(1, i - lim - 1); j <= i; j ++ )
        {
            for ( int k = max(1, i - lim - 1); k <= i; k ++ )
            {
                int x, y, z;

                if ( f[now ^ 1][j][k][0] != -inf )
                {
                    x = 1;
                    y = i - j;
                    z = i - k;
                    
                    f[now][j + ( j == i )][k + ( k == i )][0] = max(f[now][j + ( j == i )][k + ( k == i )][0], f[now ^ 1][j][k][0] + a[i][0] - y - z);
                    f[now][i - 1][k + ( k == i )][1] = max(f[now][i - 1][k + ( k == i )][1], f[now ^ 1][j][k][0] + a[i][1] - x - z);
                    f[now][i - 1][j + ( j == i )][2] = max(f[now][i - 1][j + ( j == i )][2], f[now ^ 1][j][k][0] + a[i][2] - x - y);
                }

                if ( f[now ^ 1][j][k][1] != -inf )
                {
                    x = i - j;
                    y = 1;
                    z = i - k;
                    
                    f[now][i - 1][k + ( k == i )][0] = max(f[now][i - 1][k + ( k == i )][0], f[now ^ 1][j][k][1] + a[i][0] - y - z);
                    f[now][j + ( j == i )][k + ( k == i )][1] = max(f[now][j + ( j == i )][k + ( k == i )][1], f[now ^ 1][j][k][1] + a[i][1] - x - z);
                    f[now][j + ( j == i )][i - 1][2] = max(f[now][j + ( j == i )][i - 1][2], f[now ^ 1][j][k][1] + a[i][2] - x - y);
                }

                if ( f[now ^ 1][j][k][2] != -inf )
                {
                    x = i - j;
                    y = i - k;
                    z = 1;
                    
                    f[now][k + ( k == i )][i - 1][0] = max(f[now][k + ( k == i )][i - 1][0], f[now ^ 1][j][k][2] + a[i][0] - y - z);
                    f[now][j + ( j == i )][i - 1][1] = max(f[now][j + ( j == i )][i - 1][1], f[now ^ 1][j][k][2] + a[i][1] - x - z);
                    f[now][j + ( j == i )][k + ( k == i )][2] = max(f[now][j + ( j == i )][k + ( k == i )][2], f[now ^ 1][j][k][2] + a[i][2] - x - y);
                }
            }
        }
    }

    int ans = -inf;
    for ( int i = max(1, n - lim); i <= n + 1; i ++ )
        for ( int j = max(1, n - lim); j <= n + 1; j ++ )
            for ( int w = 0; w < 3; w ++ )
                ans = max(ans, f[now][i][j][w]);
    printf("%d\n", ans);

    return 0;
}

T3 重排

设球的总数为 \(n\) ，操作次数为 \(k\) ，求解的位置为 \(pos\) 。

可以得到一个结论：如果存在一次操作选择了前 \(i\) 个球，那么这 \(i\) 个球对应的概率完全相同。

设 \(M=\max(l_i)\) ，其中 \(l_i\) 为第 \(i\) 次选择的前缀长度，我们大致分两种情况考虑：

如果 \(M<pos\) ，显然这个球位置不变，贡献为 \(P(M)\times pos\) ；

如果 \(M\ge pos\) ，那么第 \(pos\) 个球的活动范围为 \([1,M]\) ，并且前 \(M\) 个球的概率相同，贡献为 \(P(M)\times\tfrac{M+1}{2}\) 。

枚举 \(M\) 计算即可。

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

int n, pos, k;
double ans;

double Quick_Power ( double base, int p )
{
    double res = 1.0;
    while ( p )
    {
        if ( p & 1 )
            res = res * base;
        p >>= 1;
        base = base * base;
    }
    return res;
}

double P ( int x )
{
    return Quick_Power(1.0 * ( x - 1 ) / n, k);
}
int main ()
{
    freopen("arrange.in", "r", stdin);
    freopen("arrange.out", "w", stdout);
    scanf("%d%d%d", &n, &pos, &k);
    ans = P(pos) * pos;
    for ( int i = pos; i <= n; i ++ )
        ans += ( P(i + 1) - P(i) ) * ( i + 1 ) * 0.5;
    printf("%.15lf\n", ans);
    return 0;
}

标签：include,int,siz,max1,pos,国赛,6.0,2023,now
From： https://www.cnblogs.com/KafuuChinocpp/p/17420571.html

相关文章

  • 2023冲刺国赛模拟6
    A.染色发现一条链的话等同于对一个区间取\(min\)长剖，记录取\(min\)的次数和推到的位置，使用\(st\)表辅助处理每次合并将取\(min\)推到较短长度code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefp......
  • irq中断相关(2023.5.22)
    //irq29:nobodycared(trybootingwiththe"irqpoll"option) //aer_irqthreaded   aer_isrDIsablingIRQ#105 https://blog.csdn.net/Guet_Kite/article/details/106689126note_interrupt（）{if(unlikely(desc->irqs_unhandled>99900)){ ......
  • 冲刺国赛模拟 6
    长剖调不出来喜提垫底！评价：同比赛编号。牛子老师给出三道原题题号：qoj5418、5146、2303。染色简单长剖，为啥没有调出来呢？不懂。首先按深度考虑，设\(dp_{x,i}\)为在\(x\)把子树深度\(i\)染完的最小代价，转移显然\[dp_{x,i}=\min(\sum_{v}dp_{v,i-1},a_i)\]这玩意和深度有关......
  • Mac版PDF编辑器-Acrobat Pro DC 2023
    AcrobatProDC2023(pdf编辑器)是一款能让用户轻松创建和编辑多种pdf格式的实用工具，并且能够同时使用各种方法编辑大量pdf文件。AcrobatProDC是Mac上运行速度最快、处理能力最强、功能最丰富的工具之一。AcrobatProDC包括强大的图像编辑工具，可让您轻松编辑图片和视频，而......
  • APIO2023 线下又寄
    前情提要：因为\(\text{CSP-S}\)没挂分所以是线下\(\text{Day0}\)下午三点多到的，从高铁站到华山饭店路上跟一中、学军的一路，本来华二和我们差不多一起到的，但不知道为啥他们先走了，不过在车上都不敢跟\(\text{qiuly}\)他们讲话，实在太社恐了/ll然后就是报道，报完道，开幕式也没啥......
  • LeetCode 周赛 346（2023/05/21）仅 68 人 AK 的最短路问题
    本文已收录到AndroidFamily，技术和职场问题，请关注公众号[彭旭锐]提问。LeetCode单周赛第345场·体验一题多解的算法之美单周赛345概览T1.删除子串后的字符串最小长度（Easy）标签：栈T2.字典序最小回文串（Medium）标签：贪心、双指针T3.求一个整数的惩罚数（Medium）标签......
  • 2023语言与智能技术竞赛开辟“双赛道”：寻找“全民测评官”，探索AI多模态能力
    开年以来，人工智能大语言模型（LLM）掀起新一轮全球科技竞赛，全球科技巨头打响“百模大战”。当大语言模型正深刻改变人类生产生活方式时，该如何进一步释放其潜能，成为业界关注的问题，也成为了2023语言与智能技术竞赛命题的起点。5月17日，2023语言与智能技术竞赛正式启动，该大赛由中国计算机学......
  • 2023江西省赛赛后总结
    大一acmer的第二场线下赛（第一场是天梯赛。去年省赛是线上赛，结果我还因为时间冲突没有去，最后只有我的两个队友去了），比赛前一天晚上睡不着，早上坐车去比赛的时候就一直很困，比赛开始后却立马精神了。最后只过了四题，拿了个三等奖，我好菜啊。。。。。。别人都是fake，只有我是真菜。。。......
  • APIO2023游记
    没报名APIO。Day\(1\)是5.20。Day\(-2\)今天上午怎么有模拟赛。大为震撼。不过徐老师和我们说这场我们可以鸽掉。于是就鸽子了。就看了眼T2，会了。听zak说这是不归之人与望眼欲穿的人们。应徐教练要求，上午我讲课，大概讲了一下【数据删除】，还拿了松松松的【数据删除】做......
  • 6月西安 | 2023年易智瑞遥感应用培训班报名开启
    传递遥感技术助力遥感应用2023年易智瑞遥感应用培训班—6月西安站 主办单位易智瑞信息技术有限公司培训简介遥感应用培训班自2009年启动以来，已经举办了14年。已先后在20多个城市举办了120多场培训，共有7000多名学员参加。每年培训班内容都会根据学......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99