2023 ICPC 网络赛 第一场 部分题解 （待完善）

2023-09-18 17:35:26

D Transitivity

题解:

根据题意可以推出结论: 如果存在连通块,那么这个连通块要满足条件,必然是满连通块.

一共有两种情况

1. 存在一个连通块不是满连通块

设cnt表示连通块的节点个数, num表示连通块边的个数

一个连通块的贡献 = cnt*(cnt-1)/2 - num;

那么最终答案 =  连通块贡献之和

2.所有连通块都是满连通块

因为我们至少需要添加一条边，所以此时等价于我们需要把两个连通块合并.

假设连通块A有x个节点,连通块B有y个节点,那么我们需要添加 x*y条边 才能满足条件.

所以即找到 最小和次小的连通块即可,答案 = x*y

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define endl '\n'
#define bit(x) (1ll << x)
using namespace std;
const int N = 1e6 + 5;
const int inf = 1e16;
vector<int> g[N];
int sz[N];//连通块大小
int cnt[N];//边的数量
int vis[N];
void solve()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1; i<=m; i++)
    {
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int Min1 = inf;//最小值
    int Min2 = inf;//次小
    auto dfs = [&](auto self, int u, int fa,int root)-> void
    {
        vis[u] = 1;
        sz[u] = 1;
          cnt[root]+=g[u].size();
        for(auto v: g[u])
        {
           
            if(vis[v])
            {
                continue;
            }

            self(self,v,u,root);
            sz[u]+=sz[v];
        }
    };
    auto cal = [&](int now, int sum)//计算贡献
    {
        return sum*(sum-1)/2 - now;
    };
    int ans = 0;
    int f = 0;
    for(int i = 1; i<=n; i++)
    {
        if(vis[i])
        {
            continue;
        }
        dfs(dfs,i,-1,i);
        cnt[i]/=2;
        int val = cal(cnt[i],sz[i]);//连通块的贡献
        if(val != 0)
        {
            ans+=val;
            f = 1;
        }
        else
        {
            if(sz[i] < Min1)
            {
                Min2 = Min1;
                Min1 = sz[i];
            }
            else if(sz[i] <=Min2)
            {
                Min2 = sz[i];
            }
        }
    }
    if(f)
    {
        cout << ans << endl;
    }
    else
    {
        cout << Min1*Min2 << endl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

A Qualifiers Ranking Rules

题解： 

按照题意模拟即可

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define endl '\n'
#define bit(x) (1ll << x)
using namespace std;
const int N = 1e6 + 5;
const int inf = 1e16;
struct node
{
    string s; // 学校名称
    int rank; // 比赛名次
    int t;
    node(string x, int y, int _t)
    {
        s = x;
        rank = y;
        t = _t;
    }
};
int cmp(node a, node b)
{
    if (a.rank == b.rank)
    {
        return a.t < b.t;
    }
    return a.rank < b.rank;
}
void solve()
{
    int n, t;
    cin >> n >> t;
    map<string, int> vis;
    vector<node> pos1;
    int cnt = 1;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        if (vis.count(s))
        {
            continue;
        }
        pos1.push_back({s, cnt, 1});
        vis[s] = 1;
        cnt++;
    }
    cnt = 1;
    vis.clear();
    for (int i = 1; i <= t; i++)
    {
        string s;
        cin >> s;
        if (vis.count(s))
        {
            continue;
        }
        pos1.push_back({s, cnt, 2});
        cnt++;
        vis[s] = 1;
    }
    vis.clear();
    sort(pos1.begin(), pos1.end(), cmp);
    
    for (int i = 0; i < pos1.size(); i++)
    {
        if (vis.count(pos1[i].s))
        {
            continue;
        }
        cout << pos1[i].s << endl;
        vis[pos1[i].s] = 1;
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

L KaChang!

题解： 找到最大的数Max,输出  max(2ll,(int)ceil(1.0*Max/k)) 即可

void solve()
{
    int n,k;
    cin >> n >> k;
    int Max = 0;
    for(int i = 1; i<=n; i++)
    {
        int x;
        cin >> x;
        Max = max(Max,x);
    }
    cout << max(2ll,(int)ceil(1.0*Max/k)) << endl;;
}

I Pa?sWorD

题解:

设dp[i][S][ch] 表示只看前i个字母,且当前字符的出现状态为S,且最后一个字母是ch的方案数

(下面这些事伪代码,看不懂的可以直接看代码,有详细注释)

1.当前是 大写字母
dp[i][S| bit(2)][ch1] += dp[i-1][S][ch2];//其中ch2 != ch1  即上一层所有字符的方案数 - 上一层ch1的方案数

1.当前是 小写字母

(1)大写字母
dp[i][S| bit(2)][ch1] += dp[i-1][S][ch2];//其中ch2 != ch1  即上一层所有字符的方案数 - ch1的方案数


(2)填小写字母
dp[i][S| bit(1)][ch1] += dp[i-1][S][ch2];//其中ch2 != ch1  即上一层所有字符的方案数 - ch1的方案数

1.当前是 数字
dp[i][S| bit(0)][ch1] += dp[i-1][S][ch2];//其中ch2 != ch1  即上一层所有字符的方案数 - ch1的方案数


1.当前是 问号
枚举当前字符ch1,  t表示当前字母是谁
dp[i][S| bit(t)][ch1] += dp[i-1][S][ch1];//其中ch2 != ch1  即上一层所有字符的方案数 - ch1的方案数

AC代码:  

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define endl '\n'
#define bit(x) (1ll << x)
using namespace std;
const int N = 1e6 + 5;
const int inf = 1e16;
const int MOD = 998244353;
int add(int x, int y)
{
    x += y;
    while (x >= MOD)
        x -= MOD;
    while (x < 0)
        x += MOD;
    return x;
}

int sub(int x, int y)
{
    return add(x, MOD - y);
}

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
    int z = 1;
    while (y > 0)
    {
        if (y % 2 == 1)
            z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}

int inv(int x)
{
    return binpow(x, MOD - 2);
}

int divide(int x, int y)
{
    return mul(x, inv(y));
}


int my_hash(char ch)//对字符进行哈希
{
    if (ch >= 'a' && ch <= 'z')
    {
        return ch - 'a' + 10;
    }
    else if (ch >= 'A' && ch <= 'Z')
    {
        return ch - 'A' + 36;
    }
    else
    {
        return ch - '0';
    }
}
int pos(int ch)//当前字符在二进制中的位置
{
    if (ch >= 10 && ch <= 35) // 小写表示第1位
    {
        return 1;
    }
    else if (ch >= 36 && ch <= 61) // 大写表示第2位
    {
        return 2;
    }
    else // 数字表示第0位
    {
        return 0;
    }
}

int dp[2][10][70]; // 当前状态为S且最后一个字符是 ch 的方案数
int last[10];      // 状态为S时 所有的字符方案数之和
void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;

    //初始化部分
    int S = 0;
    int now;
    int ch; // 当前填入的字符编号
    if (s[1] == '?')
    {
        for (ch = 0; ch <= 61; ch++) // 当前填入ch
        {
            now = S | bit(pos(ch)); // 填入s[i]后,当前的二进制状态
            dp[1][now][ch] = 1;
        }
    }
    else
    {
        now = S | bit(pos(my_hash(s[1]))); // 填入s[i]后,当前的二进制状态
        ch = my_hash(s[1]);
        dp[1][now][ch] = 1; // 加上全部的
        if (s[1] >= 'a' && s[1] <= 'z')//如果是小写字母,还可以是大写字母
        {
            now = S | bit(pos(my_hash(s[1]) + 26)); // 填入s[i]后,当前的二进制状态
            ch = my_hash(s[1]) + 26;                // 填大写字母
            dp[1][now][ch] = 1;                     // 加上全部的
        }
    }


    for (int i = 2; i <= n; i++)
    {
        for (int S = 0; S < 8; S++)//
        {
            int sum = 0;
            for (int ch = 0; ch <= 61; ch++)
            {
                dp[0][S][ch] = dp[1][S][ch]; // 滚动数组
                dp[1][S][ch] = 0;            // 进行初始化
                sum = add(sum, dp[0][S][ch]);//表示上一层状态为S的所有字符的方案数
            }
            last[S] = sum; // 表示上一层状态为S的所有字符的方案数
        }

        for (int S = 0; S < 8; S++) // 枚举上一层的状态
        {
            int now;//表示填入字符后的状态
            int ch; // 当前填入的字符编号
            if (s[i] == '?')
            {
                for (ch = 0; ch <= 61; ch++) // 当前填入ch
                {
                    now = S | bit(pos(ch));                             // 填入s[i]后,当前的二进制状态
                    dp[1][now][ch] = add(dp[1][now][ch], last[S]);      // 加上全部的
                    dp[1][now][ch] = sub(dp[1][now][ch], dp[0][S][ch]); // 相邻不能相同，减去
                }
            }
            else
            {
                now = S | bit(pos(my_hash(s[i]))); // 填入s[i]后,当前的二进制状态
                ch = my_hash(s[i]);
                dp[1][now][ch] = add(dp[1][now][ch], last[S]);      // 加上全部的
                dp[1][now][ch] = sub(dp[1][now][ch], dp[0][S][ch]); // 相邻不能相同，减去

                if (s[i] >= 'a' && s[i] <= 'z') // 填入大写的
                {
                    now = S | bit(pos(my_hash(s[i]) + 26)); // 填入s[i]后,当前的二进制状态
                    ch = my_hash(s[i]) + 26;
                    dp[1][now][ch] = add(dp[1][now][ch], last[S]);      // 加上全部的
                    dp[1][now][ch] = sub(dp[1][now][ch], dp[0][S][ch]); // 相邻不能相同，减去
                }
            }
        }
    }
    int ans = 0;
    for (int ch = 0; ch <= 61; ch++)
    {
        ans = add(ans, dp[1][7][ch]);
    }
    cout << ans << endl;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

更多推荐

【跟小嘉学 Rust 编程】三十一、Rust的日志与追踪

系列文章目录【跟小嘉学Rust编程】一、Rust编程基础【跟小嘉学Rust编程】二、Rust包管理工具使用【跟小嘉学Rust编程】三、Rust的基本程序概念【跟小嘉学Rust编程】四、理解Rust的所有权概念【跟小嘉学Rust编程】五、使用结构体关联结构化数据【跟小嘉学Rust编程】六、枚举和模式匹配【跟小嘉学Rust

肖sir__mysql之存储__012

mysql之存储一、存储1、什么是存储过程定义：存储过程就是实现某个特定功能的sql语句的集合，编译后的存储过程会保存在数据库中，通过存储过程的名称可以反复的调用执行。2、存储过程的优点?(1)存储创建后，可以反复的调用，和使用，不需要重新写复杂的sal语句（2）创建、修改存储过程不会对数据有任何影响（3）存储过程可以

CFCA证书 申请 流程（二）

关于CFCA证书的介绍，可参考上一篇文章：CFCA证书申请流程（一）_身价五毛的博客-CSDN博客CFCA测试证书申请流程测试证书主要用于在测试环境对所需功能进行验证，例如HTTPS访问等。首先，向CFCA的支持邮箱（support@cfca.com.cn）发送邮件，描述申请证书的类型和参数，具体包括：此邮件是自动回复

轻量云服务器租用好在哪

从技术上讲，轻量级云服务器是特化了某一配置的高性价比云服务器的结合。下面，我们将了解轻量级云服务器有什么优势，使用物理服务器搭建网站，您需要租用整个服务器，这成本会变得非常昂贵。这对于一些比较简单的使用需求而言，例如搭建一个单页网站或者一个做个代理的话其实用整台服务器不仅性能溢出而且价格很贵对于初学者来说，使用轻量级云

灾备系统中虚拟机的有代理备份与无代理备份之间的差异

虚拟机的有代理备份是在虚拟机内部安装备份代理程序，然后把虚拟机当作物理机一样来进行备份任务。借助虚拟机系统中内置的程序来进行备份的，就像在正常系统中备份那样，借助备份和还原（Windows7）功能对系统进行备份。但是这种方法操作起来比较麻烦，而且也没有办法进行批量化操作，比如有大量的虚拟机，都需要备份它们的数据，那么就

前后台分离开发 YAPI平台 前端工程化之Vue-cli

目录YAPI介绍前端工程化之Vue-cli前端工程化简介前端工程化入门——Vue-cli环境准备Vue项目简介创建Vue项目vue项目目录结构介绍vue项目运行方法Vue项目开发流程前后台混合开发这种开发模式有如下缺点：沟通成本高：后台人员发现前端有问题，需要找前端人员修改，前端修改成功，再交给后台人员使用分工不明确：

nginx反向代理vue项目

文章目录前言一、创建站点1.添加站点2.添加ssl证书二、反向代理vue项目1.添加反向代理2.更改vue项目配置3.修改反向代理配置前言项目描述：前端vue项目、后端Java项目、首页WordPress项目客户要求：使用宝塔进行部署需求描述：客户只有一个SSL单域名DV证书要求首页部署wordpress项目作为官网，

大话数据结构 2 算法

算法：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作算法的五个基本特性：输入、输出、有穷性、确定性、可行性1.输入输出：算法具有0个或多个输入，算法至少有1个或多个输出。2.有穷性:指算法在执行有限的步骤后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成

JUC相关面试题

👏作者简介：大家好，我是爱发博客的嗯哼，爱好Java的小菜鸟🔥如果感觉博主的文章还不错的话，请👍三连支持👍一下博主哦📝社区论坛：希望大家能加入社区共同进步🧑‍💼个人博客：智慧笔记📕系列专栏：面试宝典本文引自黑马程序员Java面试宝典JUC基础薄弱的可以先看JUC详解文章目录面试官：聊一下并行和并发有什么

干货：数据仓库基础知识（全）

1、什么是数据仓库？权威定义：数据仓库是一个面向主题的、集成的、相对稳定的、反映历史变化的数据集合，用于支持管理决策。1）数据仓库是用于支持决策、面向分析型数据处理；2）对多个异构的数据源有效集成，集成后按照主题进行重组，并包含历史数据，而且存放在数据仓库中的数据一般不再修改。面对大数据的多样性，在存储和处理这些大数据

【算法】单调栈

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。推荐:kuan的首页,持续学习,不断总结,共同进步,活到老学到老导航檀越剑指大厂系列:全面总结java核心技术点,如集合,jvm,并发编程redis,kaf

热文推荐
  1. 2023！6招玩转 Appium 自动化测试

    Appium是个什么鬼Appium是一个移动端的自动化框架，可用于测试原生应用，移动网页应用和混合型应用，且是跨平台的。可用于IOS和Android以及firefox的操作系统。原生的应用是指用android或ios的sdk编写的应用，移动网页应用是指网页应用，类似于ios中safari应用或者Chrome应用或者类浏

  2. 【react】使用useEffect操作dom

    简言在学习react时，需要了一个需要在useEffect里操作dom的用法。一般不推荐这么干，如果是函数组件在一渲染已挂载后立即需要操作dom绑定事件等可以参考下面解决方法。描述官网交错运动示例这个示例中，usePointerPosition()Hook追踪当前指针位置。尝试移动光标或你的手指到预览区域上方，可以看到

  3. 【二叉搜索树】将二叉搜索树变平衡-力扣 1382 题

    💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。推荐:kuan的首页,持续学习,不断总结,共同进步,活到老学到老导航檀越剑指大厂系列:全面总结java核心技术点,如集合,jvm,并发编程redis,kaf

  4. AG35学习笔记（一）：debug串口抓取模组log、debug串口测试AT指令、echo命令通过串口发送16进制数据

    目录一、概述二、抓取模组log2.1硬件接口2.2用户登录2.3相关指令三、测试AT指令3.1查看端口3.2进入模式四、串口发16进制echo使用一、概述二、抓取模组log在之前记录了通过USB，使用移远工具Qwinlog来抓取log（3.3抓取模组log）。现在记录下使用debug串口抓取模组log。2.1硬件接口根

  5. MES管理系统在生产中的应用及智能工厂的构建思路

    在当今制造业中，随着信息化技术和智能化的不断发展，MES生产管理系统已成为工厂生产的核心组成部分。MES管理系统不仅能够提高生产效率，还可以优化生产流程，提升产品质量。本文将详细介绍MES管理系统在工厂生产中的应用以及构建智能工厂的思路。一、MES系统在工厂生产中的应用1、生产计划管理MES系统在生产计划管理中起到了关

  6. chat-gpt笔记：参数temperature与top_p

    temperature官方文档temperaturenumberornullOptionalDefaultsto1Whatsamplingtemperaturetouse,between0and2.Highervalueslike0.8willmaketheoutputmorerandom,whilelowervalu

  7. python中的NaN在质量控制中怎么处理？

    一、数据中的缺省值气象数据中经常存在缺省值，比如未入库的站点数据、比如海温格点实况数据中的陆地区域。这些缺省值往往被赋予NaN（NotaNumber，非数）。NaN是计算机科学中数值数据类型的一类值，表示未定义或不可表示的值。这些NaN值一般需要在计算时被去除掉，以免影响计算结果。那么，该怎么去除呢？二、NaN的定义和

  8. 27 WEB漏洞-XSS跨站之代码及httponly绕过

    目录HttpOnly安全过滤测试HttpOnly安全过滤绕过思路演示案例：Xsslabs关卡代码过滤绕过测试HttpOnly安全过滤测试防止xss攻击，指的是攻击手法，并不是能防止XSS漏洞，httponly阻止的仅仅只是cookiehttponly在相关的脚本都是支持的，我们根据自己网站的脚本环境，有相当的开启方法h

  9. 【错误记录】Python 中使用 PySpark 数据计算报错 ( SparkException: Python worker failed to connect back. )

    文章目录一、报错信息二、问题分析三、解决方案错误原因:没有为PySpark配置Python解释器,将下面的代码卸载Python数据分析代码的最前面即可;#为PySpark配置Python解释器importosos.environ['PYSPARK_PYTHON']="Y:/002_WorkSpace/PycharmPr