首页 > 其他分享 >ZSTU2023校赛

ZSTU2023校赛

时间：2023-04-04 23:13:39浏览次数：33  
标签：const ZSTU2023 int cin ans 校赛 节点 mod

篠塚真佑実的树

给定\(n\)个节点的树，其中\(m\)个节点存在传送门，当飞船经过存在传送门的节点的时候，可以选择无消耗地传送至其他存在传送门的节点，现在有\(q\)次询问，每次询问给出起点\(st\)和终点\(ed\)，若每艘飞船在飞行中最多只能进行一次传送，请你输出每次询问从起点到终点的最短路径长度

\(1<=m<=n<=2e5,1<=q<=2e5\)

题解：树上倍增 + \(LCA\) + 最短路

我们可以将情况分为两类：

  1. 不进行传送：那么我们只要利用树上倍增求出起点和终点的\(lca\)即可，然后维护点到根节点距离即可快速求出起点和终点之间的最短距离
  2. 进行1次传送：我们可以把所有存在传送门的节点看成一个源点（有点类似缩点），然后利用\(dij\)求出其他点到传送门的最短距离\(dis\)，那么利用一次传送后起点和终点之间的最短距离为：\(dis[st]+dis[ed]\)

我们对于这两种情况取\(min\)即可

#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;

int n, m;
vector<pii> g[N];
int a[N];
int fa[N][22], dep[N];
int dis[N];
int dis1[N];
int vis[N];
int st[N];

void dfs(int u, int par, int w)
{
    dep[u] = dep[par] + 1;
    fa[u][0] = par;
    dis[u] = dis[par] + w;
    for (int i = 1; i <= 20; ++i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (auto &[v, w] : g[u])
    {
        if (v == par)
            continue;
        dfs(v, u, w);
    }
}

int lca(int u, int v)
{
    if (dep[u] < dep[v])
        swap(u, v);
    for (int i = 20; i >= 0; i--)
    {
        if (dep[fa[u][i]] >= dep[v])
            u = fa[u][i];
    }
    if (u == v)
        return u;
    for (int i = 20; i >= 0; i--)
    {
        if (fa[u][i] != fa[v][i])
        {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

void dij()
{
    for (int i = 1; i <= n; ++i)
        dis1[i] = INF, vis[i] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    for (int i = 1; i <= m; ++i)
    {
        int v = a[i];
        dis1[v] = 0;
        q.push({dis1[v], v});
    }
    while (q.size())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto [v, w] : g[u])
        {
            if (dis1[v] > dis1[u] + w)
            {
                dis1[v] = dis1[u] + w;
                q.push({dis1[v], v});
            }
        }
    }
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        cin >> a[i];
    for (int i = 1, u, v, w; i < n; ++i)
    {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dij();
    dfs(1, 0, 0);
    int q;
    cin >> q;
    while (q--)
    {
        int s, ed;
        cin >> s >> ed;
        int ans = INF;
        int rt = lca(s, ed);
        ans = min(ans, dis[s] + dis[ed] - 2 * dis[rt]);
        int d = dis1[s] + dis1[ed];
        ans = min(ans, d);
        cout << ans << endl;
    }
}
signed main(void)
{
    Zeoy;
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

树上Minmax

给定一棵树，其包含 \(n\) 个结点和 \(n − 1\) 条边，每条边连接两个结点，且任意两个结点间有且仅有一条简单路径互相可达，每个点存在点权\(a_i\)
每次操作可以断一条边，随后选择分裂出的两棵树中的一棵树删除，请最小化操作次数使得最后剩下的树的点权和最大。

\(1<=n<=4*10^5\)

\(-10^9<=a_i<=10^9\)

题解：树形\(dp\)

不妨令根为\(1\)，我们维护每个节点子树中的最大点权和以及得到该最大点权和所需的最小操作次数，对于任意节点\(u\)来说，存在\(3\)种情况：

  1. 子树\(v\)中的最大点权和\(<0\),显然我们要维护的是\(u\)子树内最大的点权和，所以如果我们不断开\(u\)和\(v\)之间的边，那么最大点权和会变小，所以我们贪心的将其断开，操作次数加\(1\)
  2. 子树\(v\)的最大点权和\(>0\)，那么我们贪心的将其收入囊中，我们不选择断开，所以\(u\)节点需要加上\(v\)节点的最大点权和以及将\(v\)节点变成最大点权和的操作次数
  3. 子树\(v\)的最大点权和\(=0\)，显然对于\(u\)的最大点权和来说我要不要都行，但是我们需要最小化操作次数，所以如果我们删去\(u\)和\(v\)之间的边，操作次数加\(1\)，如果说子树\(v\)中的最小操作次数\(<1\),我们可以选择不删除这条边，否则我们为了维护最小操作次数选择删除\(u\)和\(v\)之间的边

那么最大我们遍历所有节点子树中最大的点权和，如果节点\(u\)中存在最大点权和，但是\(u\)不是根节点，我们需要断开其和根节点的一条边，使其成为连通块；如果\(u\)本身就是根节点，那么不受影响

状态表示：\(f[u][0/1]\)：\(0\)代表\(u\)节点子树中的最大点权和，1代表最小操作次数

状态转移：按照上面分析的情况转移即可

if (f[v][0] < 0)
   f[u][1]++;
else if (f[v][0] > 0)
{
   f[u][0] += f[v][0];
   f[u][1] += f[v][1];
}
else if (f[v][0] == 0)
{
   if (f[v][1] < 1)
   {
       f[u][0] += f[v][0];
   	f[u][1] += f[v][1];
   }
   else
       f[u][1]++;
}

状态初始：\(f[u][0] = a_u,f[u][1] = 0\)

#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 4e5 + 10, M = 4e5 + 10;

int n;
int a[N];
int f[N][2];
vector<int> g[N];

void dfs(int u, int par)
{
    f[u][0] = a[u];
    f[u][1] = 0;
    for (auto v : g[u])
    {
        if (v == par)
            continue;
        dfs(v, u);
        if (f[v][0] < 0)
            f[u][1]++;
        else if (f[v][0] > 0)
        {
            f[u][0] += f[v][0];
            f[u][1] += f[v][1];
        }
        else if (f[v][0] == 0)
        {
            if (f[v][1] > 1)
                f[u][1]++;
            else
            {
                f[u][0] += f[v][0];
                f[u][1] += f[v][1];
            }
        }
    }
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1, u, v; i < n; ++i)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    int maxx = -INF;
    for (int i = 1; i <= n; ++i)
    {
        maxx = max(f[i][0], maxx);
    }
    int cnt = INF;
    for (int i = 1; i <= n; ++i)
    {
        if (f[i][0] == maxx)
        {
            if (i != 1)
                cnt = min(cnt, f[i][1] + 1);
            else
                cnt = min(cnt, f[i][1]);
        }
    }
    cout << maxx << " " << cnt << endl;
}
signed main(void)
{
    Zeoy;
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

树上MinmaxⅡ

给定一棵根为 \(1\) 的树，其包含 \(n\) 个结点和 \(n − 1\) 条边，每条边连接两个结点，且任意两个结点间有且仅有一条简单路径互相可达。在这里，我们认为当 \(n=1\) 时，根节点也是叶节点。
我们定义一个子节点都是叶节点且子树都被打上标记的节点为 “枝” ，被标记的叶节点都是 “花” 。在任何时刻你都可以选择一个 “枝” ，把它的所有子节点，也即 “花” 折下来。操作过后，会删除选定的 “枝” 和它的 “花” 间的连边， 选定的 “枝” 会变成新的 “花” 。
在每个时间点你都可以选取一个没有被标记过的节点来打上标记，最开始没有节点被标记。
你的目标是将树变为一枝 “花” 并最小化任何时间点树上被标记点数量的最大值，并求出该最小化后的最大值

题解：树形\(dp\) + 贪心 \(O(nlogn)\)

首先如果要将任意节点\(u\)变为花节点，我们必须将其所有子节点\(v\)变为花节点，即叶子节点，然后将\(u\)节点打上标记后\(u\)就变成了枝节点，然后我们就可以将花节点\(v\)折下使得\(u\)变为花节点；我们发现我们在将\(u\)的子节点\(v\)变为花的过程中，假设\(u\)有\(k\)个子节点，我们不妨先将子节点\(v_1\)变为花，那么在将\(v_2\)变为花的时候\(v_1\)一直处于标记状态，对于\(v_3\)来说，将其变为花的时候，\(v_1,v_2\)处于标记状态，令\(f[u]\)为将\(u\)节点变为花的所需的被标记点的数量，那么我们可以得到规律：将\(v_i\)变为花的时刻树上被标记的节点数位\(f[v_i]+i-1\),那儿我们是要最小化树上任意时刻被标记点的最大值，我们只需贪心地先将最大的子树变为花，然后次大.....最后选择最小的子树变为花即可，对于贪心我们只需对子节点的\(dp\)值进行排序即可

注意最后将\(u\)的所有子节点变为花后，我们还需要标记\(u\)，那么此时场上被标记的节点数为\(sz[u]+1\)，\(sz[u]\)代表\(u\)的子节点数

状态表示：\(f[u]\):将\(u\)节点变为花的所需的被标记点的最大数量

状态属性：\(MAX\)

状态转移：

\[f[u] = max(f[v_1],f[v_2]+1...f[v_i]+i-1,sz[u]+1)\\ f[v_1]>=f[v_2]>=...f[v_i] \]

状态初始：\(f[u] = 1\)

答案呈现：遍历\(f[u]\)后找到最大值即可

#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 4e5 + 10, M = 4e5 + 10;

int n;
int f[N];
vector<int> g[N];

void dfs(int u, int par)
{
    f[u] = 1;
    vector<int> a;
    for (auto v : g[u])
    {
        if (v == par)
            continue;
        dfs(v, u);
        a.push_back(f[v]);
    }
    sort(all(a), greater<int>());
    for (int i = 0; i < a.size(); ++i)
        f[u] = max(f[u], a[i] + i);
    f[u] = max(f[u], (long long)(a.size() + 1));
    a.clear();
}

void solve()
{
    cin >> n;
    for (int i = 1, u, v; i < n; ++i)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    int ans = -INF;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, f[i]);
    cout << ans << endl;
}
signed main(void)
{
    Zeoy;
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

千里朱音的数

\[(\sum_{p_1\times p_2\times p_3<=k,1<=p_1,p_2,p_3<=n,p_1,p_2,p_3∈N^+} p_1\times p_2\times p_3)\ mod \ 998244353\\ 1<=n,k<=10^9 \]

题解：思维 + 数论 ： 还是蛮有套路的，多学学

不妨我们令\(p_1<=p_2<=p_3\)

此时我们发现\(p_1\)的上限为\(min(\sqrt[3]{k},n)\),即\(p_1\)的范围\([1,min(\sqrt[3]{k},n)]\)那么\(p_2\)的上限为\(min(\sqrt{\frac{k}{p_1}},n)\)，即\(p_2\)的范围为\([p_1,min(\sqrt{\frac{k}{p_1}},n)]\)，那么对于\(p_3\)来说上限为\(min(\frac{k}{p_1p_2},n)\),即\(p_3\)范围为\([p_2,min(\frac{k}{p_1p_2},n)]\)

我们打表后发现可以利用求和公式快速算出\(p_3\)的贡献:\(p_1*p_2*\sum p_3\)，所以我们只需要枚举\(p_1,p_2\)即可，时间复杂度为\(O(k^{\frac{2}{3}})\)

但是我们只枚举了\(p_1<=p_2<=p_3\)，实际上少计算了答案，我们考虑以下三种情况：

  1. 若\(p_1=p_2=p_3\),此时我们没有少算答案，不需要多加
  2. 若\(p_1<=p_2=p_3\ or\ p_1=p_2<=p_3\),对于这两种情况我们需要对贡献乘以\(C_3^1\)
  3. 若\(p_1<p_2<p_3\),对于这种情况我们需要对贡献乘\(A_3^3\)


#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;

int n, k;

void solve()
{
    cin >> n >> k;
    int ans = 0;
    for (int p1 = 1; p1 <= min((int)cbrt(k), n); ++p1)
    {
        for (int p2 = p1; p2 <= min((int)sqrt(1.0 * k / p1), n); ++p2)
        {
            int L = p2;
            int R = min((int)(1.0 * k / (p1 * p2)), n);
            if (R >= L)
            {
                if (p1 == p2)
                {
                    ans = (ans % mod + ((p1 % mod) * (p2 % mod) * (p2 % mod)) % mod) % mod;
                    if (R >= L + 1)
                        ans = (ans % mod + ((p1 % mod) * (p2 % mod) * (((L + 1 + R) * (R - L) / 2) % mod) * 3) % mod) % mod;
                }
                else if (p1 < p2)
                {
                    ans = (ans % mod + ((p1 % mod) * (p2 % mod) * (p2 % mod) * 3) % mod) % mod;
                    if (R >= L + 1)
                        ans = (ans % mod + ((p1 % mod) * (p2 % mod) * (((L + 1 + R) * (R - L) / 2) % mod) * 6) % mod) % mod;
                }
            }
        }
    }
    cout << ans << endl;
}
signed main(void)
{
    Zeoy;
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

标签：const,ZSTU2023,int,cin,ans,校赛,节点,mod
From： https://www.cnblogs.com/Zeoy-kkk/p/17288224.html

相关文章

  • 2019杭电多校赛第一场Vacation
    Vacation题意：n辆车排队过路口，每辆车给定最大车速、车长、车头到路口的距离，求最后一辆车的最短通过时间分析：确定每辆车通过路口需要的总路程sum[i],然后分情况讨论：......
  • 记第一次正式参加程序设计竞赛（程序设计天梯赛校赛）的感觉（随便写写）
    背景2021年冬天到2022年春天开始在学校的相关课程下接触计算机，了解到算法竞赛的一些东西，2022年春天也参加了一次，虽然那次是线上赛，而且没什么准备，到了比赛的时候只会做一些......
  • 【比赛记录】校赛
    \(\textcolor{orange}{义中常规赛20230319}\)\(\textcolor{green}{time:2023.3.19}\)\(\textcolor{red}{Performance:180/252(实际分数/期望分数)}\)\(\textcolor{purp......
  • 2018年东北农业大学春季校赛（周赛训练）
    题解报告题解顺序不是原来比赛的题目顺序题目意思可以去原题了解基本的一些理解和问题都在注释中题目一：wyh的矩阵//思维题，找规律，考虑中点的性质。#include<cstd......
  • 【HDU6867】Tree 2020多校赛9（树形DP，贪心，爆搜）
    problemTreeTimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):126AcceptedSubmission(s):65ProblemDescript......
  • 中国计量大学第六届个人校赛题解
    中国计量大学第六届个人校赛题解这里是一篇关于中国计量大学第六届个人校赛的题解。顺便写一点校赛的经历和想法，稍微给这次参与校赛组织的经历留下一点回忆C题配图的候......
  • 大学生程序设计创新实践基地2022年冬季校赛（NPU ACM Winter Contest）
    大学生程序设计创新实践基地2022年冬季校赛（NPUACMWinterContest）总述总体考察对于板子的熟练变换，以及考察离谱地使用python和对getchar()以及EOF的基础掌握程度。B，D，E......
  • 蓝桥杯校赛题目以及解析
    题目一输入一个字符串，求它包含多少个单词。单词间以一个或者多个空格分开。第一个单词前，最后一个单词后也可能有0到多个空格。比如："abc   xyz"包含两个单词，"ab  c......
  • 合肥学院校赛热身赛题解
    A.codeforces直接读入输入即可#include<bits/stdc++.h>intmain(){strings;cin>>s;cout<<"https://codeforces.com/profile/"<<s;return0;}......
  • 2022 zafu校赛题解
    A煎饼哥哥好鲨题读入时，分别统计四种不同提交结果，最后按题目要求输出即可。代码链接B富哥磊神暴力枚举三种纸币的数量，统计合法付款方式的数量即可。注意优化暴力枚举......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99