首页 > 其他分享 >[CSP-S 2022 T1] 假期计划

[CSP-S 2022 T1] 假期计划

时间:2023-09-22 18:36:41浏览次数:41  
标签:int LL d% top3 long T1 2022 include CSP

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std; 
typedef long long LL;
const int N = 2505;
vector<int> G[N];
int dis[N], top3[N][3];
bool vis[N], ok[N][N];
LL s[N];
int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 2; i <= n; i++) scanf("%lld", &s[i]); // 注意景点分数的数据范围
    for (int i = 0; i < m; i++) {
        int x, y; scanf("%d%d", &x, &y);
        G[x].push_back(y); G[y].push_back(x);
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        while (!q.empty()) q.pop();
        for (int j = 1; j <= n; j++) {
            dis[j] = -1; vis[j] = false;
        }
        q.push(i); vis[i] = true; dis[i] = 0; 
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            for (int to : G[cur]) {
                if (!vis[to]) {
                    vis[to] = true;
                    dis[to] = dis[cur] + 1;
                    if (dis[to] <= k + 1) {
                        q.push(to); ok[i][to] = true;
                    }
                }
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= n; j++) {
            // ok[i][i] 必定是 false,不列入讨论范围
            if (ok[1][j] && ok[i][j]) { 
                if (s[j] > s[top3[i][0]]) {
                    top3[i][2] = top3[i][1];
                    top3[i][1] = top3[i][0];
                    top3[i][0] = j;
                } else if (s[j] > s[top3[i][1]]) {
                    top3[i][2] = top3[i][1];
                    top3[i][1] = j;
                } else if (s[j] > s[top3[i][2]]) {
                    top3[i][2] = j;
                }
            }
        }
    }
    LL ans = 0;
    for (int b = 2; b <= n; b++) {
        for (int c = 2; c <= n; c++) {
            if (b == c || !ok[b][c]) continue;
            for (int i = 0; i < 3; i++) {
                int a = top3[b][i];
                if (a == 0) break;
                if (a == b || a == c) continue;
                for (int j = 0; j < 3; j++) {
                    int d = top3[c][j];
                    if (d == 0) break;
                    if (d == a || d == b || d == c) continue;
                    ans = max(ans, s[a] + s[b] + s[c] + s[d]);   
                }
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

标签:int,LL,d%,top3,long,T1,2022,include,CSP
From: https://www.cnblogs.com/ronchen/p/17723103.html

相关文章

  • 春秋云镜 - CVE-2022-28060
    VictorCMSv1.0/includes/login.php存在sql注入找到页面的登录框,看介绍应该是post类型的表单注入。上sqlmap用原本的梭发现ctf的那个表是空的,换用--file-read参数从目标中读取文件拿到flag。root@Locklytemp/tmp»sqlmap-rsql.txt--file-read"/flag"--batch......
  • 春秋云镜 - CVE-2022-28512
    FantasticBlog(CMS)是一个绝对出色的博客/文章网络内容管理系统。它使您可以轻松地管理您的网站或博客,它为您提供了广泛的功能来定制您的博客以满足您的需求。它具有强大的功能,您无需接触任何代码即可启动并运行您的博客。该CMS的/single.php路径下,id参数存在一个SQL注入漏洞......
  • 2021-2022 ICPC Northwestern European Regional Programming Contest (NWERC 2021)
    A.AccessDenied先问若干次,问出长度,然后再一位一位的问即可。#include<bits/stdc++.h>usingnamespacestd;intinput(){strings;getline(cin,s);if(s=="ACCESSGRANTED")exit(0);intt=0;for(autoi:s){if(i&g......
  • [CSP-J 2021] 插入排序
    题目描述插入排序是一种非常常见且简单的排序算法。小Z是一名大一的新生,今天H老师刚刚在上课的时候讲了插入排序算法。假设比较两个元素的时间为\(\mathcalO(1)\),则插入排序可以以\(\mathcalO(n^2)\)的时间复杂度完成长度为\(n\)的数组的排序。不妨假设这\(n\)个数......
  • 主打低功耗物联网国产替代,纵行科技ZT1826芯片以速率和灵敏度出圈​
    在低功耗物联网领域,国产替代的趋势越演越烈。9月20日,纵行科技在“IOTE2023深圳·物联网通信技术与应用高峰论坛”发表了“自主原创AdvancedM-FSK®调制技术助力国产替代和泛在物联”的演讲,并推出了ZT1826芯片,以“更低功耗、更低成本、更高性能”为差异化优势,想在低功耗物联网赛道......
  • Couchdb-权限绕过--命令执行--(CVE-2017-12635)&&(CVE-2017-12636)--H2database命令执
    Couchdb-权限绕过--命令执行--(CVE-2017-12635)&&(CVE-2017-12636)--H2database命令执行--(CVE-2022-23221)环境概述采用Vulfocus靶场环境进行复现,搭建操作和文章参考具体搭建教程参考vulfocus不能同步的解决方法/vulfocus同步失败。CouchdbCVE-2017-12635权限绕过漏洞概述A......
  • 上新!100%国产物料认证,米尔入门级国产核心板全志T113-i方案
    自米尔国产全志T113系列的核心板发布以来,这款高性价比、低成本、入门级、高性能的国产核心板咨询不断,配套的开发板已经成交量数百套,深受工程师们的青睐,为了集齐T113全系列的产品,这次米尔发布了基于全志T113-i处理器的核心板和开发板,让广大工程师有了更多的选择。接下来看看这款T113......
  • 上新!100%国产物料认证,米尔入门级国产核心板全志T113-i方案
    自米尔国产全志T113系列的核心板发布以来,这款高性价比、低成本、入门级、高性能的国产核心板咨询不断,配套的开发板已经成交量数百套,深受工程师们的青睐,为了集齐T113全系列的产品,这次米尔发布了基于全志T113-i处理器的核心板和开发板,让广大工程师有了更多的选择。接下来看看这款T11......
  • VS2022代码格式化
    升级到vs2022后发现之前常用代码格式化插件FormatdocumentonSave不怎么好用了,经常会ctrl+s后代码并没有格式化, 这让我很不爽,查阅资料后发现vs2022内置了代码格式化功能,具体操作如下图所示: 这样既可以了。这个配置文件也是可以修改的,比如我只想要保存时格式化代码而......
  • 春秋云镜 - CVE-2022-32991
    靶标介绍:该CMS的welcome.php中存在SQL注入攻击。访问页面,先注册,使用邮箱加密码登录。bp抓包,后台挂上sqlipy然后去测welcome.php,常用的语句都没成功但过一会就有了结果,注入点在eid这个参数,看payload是bool盲注。直接sqlmap一把梭,脱裤。sqlmap-rsql.txt--dbs--batch......