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

2023冲刺国赛模拟 2.1

时间:2023-05-17 17:22:50浏览次数:66  
标签:seq int mid 国赛 树边 edge 2023 2.1 now

2023冲刺国赛模拟 2.1

T1 树

首先考虑初始节点只有 \(1\) 个的情况,很容易使用 dp 解决,设 \(f_i\) 表示初始节点为 \(i\) ,占领以 \(i\) 为根的子树所需要的最小回合数量,只需要优先占领回合多的子树即可。

当初始节点为 \(2\) 个时,容易发现 \(u,v\) 路径上存在一条边,满足最优方案下 \(u,v\) 的士兵均不会跨过这条边,因此可以枚举这条边并对边两侧的子树分别 dp ,容易发现 \(u,v\) 两侧的 dp 值随着边位置的单调移动具有单调性,因此可以二分两侧 dp 值最接近的位置,这个位置取到最优方案。

直接做复杂度为 \(O(n\log^2 n)\) ,考虑进行优化,容易发现每次进行 dp 进行了许多重复的计算,因此考虑断掉链上所有边预处理每个地方的 dp 值,二分 check 时只需要连接链即可,此时我们相当于在原先节点下连接一棵子树,设当前连接的子树的贡献为 \(res\) ,此时我们需要将 \(res\) 插入到对应节点的子树序列中,我们设原先这个节点 \(i\) 取到最大 dp 值的位置为 \(pos\) ,如果 \(res\) 可以插入到 \(pos\) 之前,显然会产生 \(f_i+1\) 的贡献,否则产生 \(f_i\) 的贡献,同时考虑到 \(res\) 插入到序列开头贡献为 \(res+1\) ,对这几种贡献取 \(\max\) 即可,复杂度为 \(O(n\log n)\) 。

code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iostream>
using namespace std;
const int max1 = 5e5, B = 30;
const int inf = 0x3f3f3f3f;

int n, a, b;
struct Node
    { int next, v; } edge[max1 * 2 + 5];
int head[max1 + 5], total;
int father[max1 + 5], seq[max1 + 5], len;
bool vis[max1 + 5];

int f[max1 + 5], maxpos[max1 + 5], ans;
vector <int> tmp;

void Add ( int u, int v )
{
    edge[++total].v = v;
    edge[total].next = head[u];
    head[u] = total;
    return;
}

void Dfs ( int now, int fa, int pre_edge )
{
    father[now] = fa;
    for ( int i = head[now]; i; i = edge[i].next )
    {
        int v = edge[i].v;
        if ( v == fa )
            continue;
        Dfs(v, now, i);
    }
    return;
}

void Redfs ( int now, int fa )
{
    for ( int i = head[now]; i; i = edge[i].next )
    {
        int v = edge[i].v;
        if ( v == fa || vis[v] )
            continue;
        Redfs(v, now);
    }

    tmp.clear();
    for ( int i = head[now]; i; i = edge[i].next )
    {
        int v = edge[i].v;
        if ( v == fa || vis[v] )
            continue;
        tmp.push_back(f[v]);
    }
    sort(tmp.begin(), tmp.end());
    reverse(tmp.begin(), tmp.end());

    f[now] = 0; maxpos[now] = -1;
    
    int siz = tmp.size();
    for ( int i = 0; i < siz; i ++ )
    {
        if ( f[now] <= i + 1 + tmp[i] )
        {
            f[now] = i + 1 + tmp[i];
            maxpos[now] = tmp[i];
        }
    }
    return;
}

bool Check ( int mid )
{
    int A = f[seq[mid + 1]], B = f[seq[mid]];
    for ( int i = mid + 2; i <= len; i ++ )
        A = max(f[seq[i]] + ( A >= maxpos[seq[i]] ), A + 1);

    for ( int i = mid - 1; i >= 1; i -- )
        B = max(f[seq[i]] + ( B >= maxpos[seq[i]] ), B + 1);
    return A < B;
}

int Query ( int mid )
{
    int A = f[seq[mid + 1]], B = f[seq[mid]];
    for ( int i = mid + 2; i <= len; i ++ )
        A = max(f[seq[i]] + ( A >= maxpos[seq[i]] ), A + 1);

    for ( int i = mid - 1; i >= 1; i -- )
        B = max(f[seq[i]] + ( B >= maxpos[seq[i]] ), B + 1);
    return max(A, B);
}

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

    scanf("%d%d%d", &n, &a, &b); total = 1;
    for ( int i = 2, u, v; i <= n; i ++ )
    {
        scanf("%d%d", &u, &v);
        Add(u, v), Add(v, u);
    }

    Dfs(a, 0, 0);

    int now = b;
    while ( now )
    {
        seq[++len] = now;
        vis[now] = true;
        now = father[now];
    }

    for ( int i = 1; i <= len; i ++ )
        Redfs(seq[i], 0);

    int L = 1, R = len - 1, pos = len - 1;
    while ( L <= R )
    {
        int mid = L + R >> 1;
        if ( Check(mid) )
            pos = mid, R = mid - 1;
        else
            L = mid + 1;
    }

    ans = Query(pos);
    if ( pos > 1 )
        ans = min(ans, Query(pos - 1));

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

    return 0;
}

T2 最小生成树

假设当前我们已经知道所有树边权值的相对大小关系,考虑统计非树边产生的贡献。

有一个经典结论:非树边连接端点 \(u,v\) 满足非树边权值大于 \(u,v\) 对应最小生成树的路径上边权最大值。

从边权较小的边向较大的边连边,可以得到拓扑关系图,去掉不必要的边后发现树边构成一条链,链上每个节点连接一些非树边,此时我们的目的是统计拓扑序的方案数,设每个节点下连接的非树边个数为 \(w_i\) ,考虑按照 \(w_i\) 个非树边, \(1\) 个树边的顺序依次插入到拓扑序中。

设当前加入的边的总数为 \(n\) ,树边有 \(b\) 个,方案数为 \(c\) 个,所有方案的树边位置和为 \(s\) 。

考虑加入一条树边,由于只能插入到序列开头,因此变化为:

\[(n,b,c,s)\to (n+1,b+1,c,s+c(b+1)) \]

考虑加入一条非树边,变化为:

\[(n,b,c,s)\to (n+1,b,c(n+1),s(n+2)) \]

简单解释一下 \(s\to s(n+2)\) ,首先一个基础的方案数的贡献为 \(s(n+1)\) ,之后树边所在的位置 \(A\) ,容易发现存在 \(A\) 种方案满足这个树边的位置 \(+1\) ,不难发现这部分的贡献和为 \(s\) 。

考虑加入 \(w_i\) 条非树边,变化为:

\[(n,b,c,s)\to (n+w_i,b,(n+w_i)^{\underline{w_i}}) \]

标签:seq,int,mid,国赛,树边,edge,2023,2.1,now
From: https://www.cnblogs.com/KafuuChinocpp/p/17409408.html

相关文章

  • 冲刺国赛模拟 5
    今天上午给我整不会了,开着空调结果冻的要死,这还是外边三十多度的情况下。结果一上午两眼发黑打题,心态相当爆炸。题目名称好像是qlr洛谷主页。今晚九点简单题。为啥赛时没人做。在每个位置有意义的走法显然只有两种:用\(2\)步走到相邻一格,或者用\(1\)步走到头。那每个点最......
  • Jan 2023-Prioritizing Samples in Reinforcement Learning with Reducible Loss
    1Introduction本文建议根据样本的可学习性进行抽样,而不是从经验回放中随机抽样。如果有可能减少代理对该样本的损失,则认为该样本是可学习的。我们将可以减少样本损失的数量称为其可减少损失(ReLo)。这与Schaul等人[2016]的vanilla优先级不同,后者只是对具有高损失的样本给予高优......
  • 合合信息亮相CCIG2023:多位大咖共话智能文档未来,文档图像内容安全还面临哪些技术难题?
    ​ 近日,中国图象图形大会(CCIG2023)(简称“大会”)在苏州圆满落幕。本届大会以“图象图形·向未来”为主题,由中国科学技术协会指导,中国图象图形学学会主办,苏州科技大学承办,特邀谭铁牛院士、赵沁平院士、吴一戎院士等百余位国内外知名学者,来自代表企业的技术专家,共话图像图形学术研......
  • SSO2.0 6-20230516
                 ......
  • 全注解springMVC实例20230517
     1、pom<dependencies><dependency><groupId>org.springframework</groupId><artifactId>spring-webmvc</artifactId><version>4.3.13.RELEASE</version></dependency><dependency&g......
  • Boris FX Silhouette 2023 for MAC 影视后期Roto抠像Paint视效合成独立版软件/Adobe插
    业界领先的rotoscoping和painttool,包含了主要的合成功能。Silhouette2023提供400多个VFX节点,包括BorisFXSapphire、MochaPro和ParticleIllusion。十五年来,Silhouette一直是好莱坞大片不可或缺的一部分,最近在《Dune》、《Spiderman:NoWayHome》、《FreeGuy》和《Th......
  • 2023.5.17——软件工程日报
    所花时间(包括上课):6h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习。我了解到的知识点:1.了解了一些数据库的知识;2.了解了一些python的知识;3.了解了一些英语知识;5.了解了一些Javaweb的知识;4.了解了一些数学建模的知识;6.了解了一些计算机网络的知识;......
  • 【2023-05-16】贴心大宝
    20:00不要去猜测别人的心里在想什么,琢磨别人的心思的人从来都不是幸福的人。每个人都应该关注自己内心的所思所想,如果连这一点都做不到,那是很可悲可叹的。                                      ......
  • 【2023-05-15】适应探索
    20:00从事单调工作的人之所以比无所事事的人幸福,就是因为工作为他们提供了消磨时间的快乐与施展哪怕是微小包袱的快乐。                                                ......
  • 2023年05月10日错题分析
    1.  2.  3.   4.  ......