首页 > 编程语言 >2024“钉耙编程”中国大学生算法设计超级联赛（2）

2024“钉耙编程”中国大学生算法设计超级联赛（2）

时间：2024-07-29 21:29:50浏览次数：8  
标签：钉耙 int void 编程 dfs 2024 ++ while now

女神的睿智


void solve() {
    string s;
    cin >> s;
    int a = 0, b = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == s[0]) a++;
        if (s[i] == s[4]) b++;
    }
    if (s[0] == s[4]) cout << s[0] << '\n';
    else if (a > b) cout << s[0] << '\n';
    else if (a < b) cout << s[4] << '\n';
    else cout << "N\n";
}

URL划分

思路：

找出每个子结构中A=B的形式，且A和B非空

void solve() {
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == ':' && s[i + 1] == '/' && s[i + 2] == '/') {
            cout << '\n';
            int t = i + 3;
            while (s[t] != '/') cout << s[t ++];
            cout << '\n';
            string a, b;
            bool ok = false;
            for (int j = t + 1; j < s.size(); ++j) {
                if (s[j] == '/') {
                    if (!a.empty() && !b.empty()) {
                        cout << a << '=' << b << '\n';
                    }
                    a.clear(), b.clear();
                    ok = false;
                    continue;
                }
                if (s[j] == '=') {
                    ok = true;
                    continue;
                }
                if (ok) b.push_back(s[j]);
                else a.push_back(s[j]);
            }
            return ;
        }
        cout << s[i];
    }
}

传奇勇士小凯

思路：

首先要知道期望次数为E（x）= 1 / p

对于所有的概率就可以知道每个点的期望次数为15 / pi

并且pi的范围为1到15，为了方便计算可以考虑通分，将分母都转化为为1到15的最小公倍数，这样只用计算分子，最后的答案再分子分母同时通分即可

知道了每个点的期望次数，用dijkstra的方法维护最长路即可

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e5 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};




void solve() {
    int n;
    cin >> n;

    vector<vector<int> > ve(n + 1);
    int lx = 1;
    for (int i = 2; i <= 15; ++i) {
        lx = lcm(lx, i);
    }
    vector<int> h(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        ve[u].push_back(v), ve[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
        h[i] = lx / h[i] * 15;
    }
    priority_queue<PII> q;
    vector<int> st(n + 1), dis(n + 1, 0);
    q.push({h[1], 1});
    dis[1] = h[1];
    while (q.size()) {
        auto [d, u] = q.top();
        q.pop();
        if (st[u]) continue;
        st[u] = 1;
        for (auto v:ve[u]) {
            if (!st[v] && dis[v] < dis[u] + h[v]) {
                dis[v] = dis[u] + h[v];
                q.push({dis[v], v});
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = max(ans, dis[i]);

    int d = gcd(lx, ans);
    cout << ans / d << '/' << lx / d << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

鸡爪

思路：

一个鸡爪包含一个点加三条边，需要答案的字典序最小，说明要尽可能选择小的点

有n条边，说明最多有n/3个鸡爪，那么一定会消耗n/3个点，贪心的想就是前n/3个点，编号小的点连的边一定是更优的，现在考虑怎么让编号大的点变得更优，那么就是让最大的点去连最小的3个点

可以发现对于前3个点来说，小于自己的点不足3个，并且4~n/3中的点都已经连了1~3，说明前3个点中需要在大于n/3的点中在选点，那就从n/3 + 1开始选即可

若n%3不为0，说明还多余了一些边，那么用1去连其他点一定是字典序最小的

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e6 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};


void solve() {
    int n;
    cin >> n;
    int m = n / 3;
    set<PII> se;
    int now = 2;
    for (int i = m; i >= 1; --i) {
        int t = 3;
        now = 1;
        while (t > 0 && now < i) {
            se.insert({min(i, now), max(i, now)});
            t --, now ++, n --;
        }
        now = m + 1;
        while (t > 0) {
            se.insert({min(i, now), max(i, now)});
            t --, now ++, n --;
        }
    }
    while (n > 0) {
        se.insert({1, now ++});
        n --;
    }
    for (auto [x, y]:se) {
        cout << x << ' ' << y << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

在 A 里面找有 C 的 B

思路：

kmp+ac自动机

判断c是否在b‘中用kmp，判断b是否在a中用ac自动机

直接用板子就行

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e6 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18, maxn = 5e5 + 5;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int trie[maxn][26]; //字典树
int flag[maxn];  //记录该单词在树中的位置
int fail[maxn];     //失败时的回溯指针
int tot = 0;
int vis[maxn];  //记录该点是否访问过

void insertWords(string s, int id){
    int root = 0;
    for(int i=0;i<s.size();i++){
        int next = s[i] - 'a';
        if(!trie[root][next])
            trie[root][next] = ++tot;
        root = trie[root][next];
    }

    flag[id] = root;
}
void getFail(){
    queue <int>q;
    for(int i=0;i<26;i++){      //将第二层所有出现了的字母扔进队列
        if(trie[0][i]){
            fail[trie[0][i]] = 0;
            q.push(trie[0][i]);
        }
    }

//fail[now]    ->当前节点now的失败指针指向的地方
//    trie[now][i] -> 下一个字母为i+'a'的节点的下标为trie[now][i]
    while(!q.empty()){
        int now = q.front();
        q.pop();

        for(int i=0;i<26;i++){      //查询26个字母
            if(trie[now][i]){
                //如果有这个子节点为字母i+'a',则
//让这个节点的失败指针指向(((他父亲节点)的失败指针所指向的那个节点)的下一个节点)
                //有点绕,为了方便理解特意加了括号

                fail[trie[now][i]] = trie[fail[now]][i];
                q.push(trie[now][i]);
            }
            else//否则就让当前节点的这个子节点
                //指向当前节点fail指针的这个子节点
                trie[now][i] = trie[fail[now]][i];
        }
    }
}
void query(string s){
    int now = 0;
    for(int i=0;i<s.size();i++){    //遍历文本串
        now = trie[now][s[i]-'a'];  //从s[i]点开始寻找
        for(int j=now;j && !vis[j];j=fail[j]){
            //一直向下寻找,直到匹配失败(失败指针指向根或者当前节点已找过).
            vis[j] = 1;   //将遍历国后的节点标记,防止重复计算
        }
    }
}

vector<int> ne;
void init(string pattern) {
    int m = pattern.size();
    ne = vector<int> (m, 0);
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = ne[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        ne[i] = j;
    }
}
//是否匹配
bool kmp(string text, string pattern) {
    int n = text.size(), m = pattern.size();
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = ne[j - 1];
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == m) {
            return true;
        }
    }
    return false;
}

void solve() {
    tot = 0;
    memset(fail, 0, sizeof(fail));
    memset(flag, 0, sizeof(flag));
    memset(vis, 0, sizeof(vis));
    memset(trie, 0, sizeof(trie));

    int n;
    cin >> n;
    string A, C;
    cin >> A >> C;
    init(C);
    string b1, b2;
    for (int i = 1; i <= n; ++i) {
        flag[i] = -1;
        cin >> b1 >> b2;
        if (kmp(b2, C)) {
            insertWords(b1, i);
        }
    }
    getFail();
    query(A);
    for (int i = 1; i <= n; ++i) {
        if (flag[i] != -1 && vis[flag[i]]) {
            cout << i << ' ';
        }
    }
    cout << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

成长，生命，幸福

思路：

手画下图可以发现答案路径上的点经过操作后新生成的点都属于答案路径

一个度为x的点，操作m次后新生成的点有（x - 1） * （2m - 1） + 1

知道了每个点的贡献后就可以dp求最大直径

但是会取模，所以没有办法直接判断

可以发现式子（x - 1） * （2m - 1） + 1 中的（2m - 1）是定值，那么维护（x - 1） 和 1即可

这里对m小于20的情况直接用式子的值做dp，其他情况就维护（x - 1） 和 1做dp

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e6 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int ksm(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % Mod;
        b >>= 1;
        a = a * a % Mod;
    }
    return res;
}
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > ve(n + 1);
    vector<int> in(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        ve[u].push_back(v), ve[v].push_back(u);
        in[u] ++, in[v] ++;
    }
    if (m < 20) {
        vector<int> f(n + 1);
        int ans = 0;
        auto dfs = [&] (int u, int fa, auto dfs) -> void {
            for (auto v:ve[u]) {
                if (v == fa) continue;
                dfs(v, u, dfs);
                ans = max(ans, f[u] + f[v] + (in[u] - 1) * (ksm(2, m) - 1) + 1);
                f[u] = max(f[u], f[v]);
            }
            f[u] += (in[u] - 1) * (ksm(2, m) - 1) + 1;
        };
        dfs(1, 0, dfs);
        cout << ans << '\n';
    } else {
        PII ans;
        vector<PII> f(n + 1);
        auto dfs = [&] (int u, int fa, auto dfs) -> void {
            for (auto v:ve[u]) {
                if (v == fa) continue;
                dfs(v, u, dfs);
                ans = max(ans, {f[u].first + f[v].first + in[u] - 1, f[u].second + f[v].second + 1});
                f[u] = max(f[u], f[v]);
            }
            f[u].first += in[u] - 1;
            f[u].second ++;
        };
        dfs(1, 0, dfs);
        cout << (ans.first * ((ksm(2, m) - 1 + Mod) % Mod) % Mod + ans.second) % Mod << '\n';
    }

}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

 

标签：钉耙,int,void,编程,dfs,2024,++,while,now
From： https://www.cnblogs.com/bible-/p/18325890

相关文章

  • .NET周刊【7月第4期 2024-07-28】
    国内文章.NET高性能缓冲队列实现BufferQueuehttps://mp.weixin.qq.com/s/fUhJpyPqwcmb3whuV3CDygBufferQueue是一个用.NET编写的高性能的缓冲队列实现，支持多线程并发操作。项目地址：https://github.com/eventhorizon-cli/BufferQueue项目是从mocha项目中独立出来的一......
  • 2024华为OD机试真题- 亲子游戏Python-C卷D卷-200分
    2024华为OD机试题库-(C卷+D卷)-(JAVA、Python、C++)题目描述宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上......
  • 【专题】2024家·生活智能家居趋势报告合集PDF分享（附原数据表）
    原文链接： https://tecdat.cn/?p=37146近二十载间，中国消费市场见证了从产品创新到渠道创新的双重飞跃，无论是耐用消费品还是快速消费品，均在线上线下平台绽放出前所未有的丰富选择，多数行业已转型为以消费者为核心导向的买方市场格局。阅读原文，获取专题报告合集全文，解锁文末218份智......
  • JavaSE基础编程十题
    写在前面昨天说了一下Java中的数据类型、运算符、选择语句、循环语句部分的基础知识，今天写的编程题就是来检验这部分的成果，来看看你能写出来几题。答案也是仅供参考，如果有更好的解法欢迎在下面留言！题目展示1.输入自己的名字，年龄和性别，分别用不同的变量接收，并将输入的信息做输出......
  • 02 Go语言开发REST API接口_20240728 课程笔记
    概述如果您没有Golang的基础，应该学习如下前置课程。Golang零基础入门Golang面向对象编程GoWeb基础基础不好的同学每节课的代码最好配合视频进行阅读和学习，如果基础比较扎实，则阅读本教程巩固一下相关知识点即可，遇到不会的知识点再看视频。视频课程最近发现越来越多的......
  • C++提高编程—2、STL—基础知识以及Vector容器的数据插入和遍历
    2.1STL的诞生2.2STL的基本概念2.3STL的六大组件2.4STL中容器、算法、迭代器2.5容器算法迭代器初识2.5.1vector存放内置数据类型#include<iostream>usingnamespacestd;#include<vector>#include<algorithm>//标志算法头文件//vector容器存放内置......
  • 2024.7.29 test
    A给出\(n,m\)，你要求对于所有长度为\(n\)的非负整数序列\(A,B\)中，满足\(\sumA_i=\sumB_i=m\)，求\((\sum|A_i-B_i|)^2\)的总和。\(n\le500,m\le10^5\)。首先我们发现\(\sum(A_i-B_i)=0\)，所以\(\sum|A_i-B_i|=2\sum_{A_i<B_i}B_i-A_i\)。我们把序列分为两部分，一......
  • Python 教程（六）：函数式编程
    目录专栏列表前言函数定义参数返回值示例函数类型普通函数空函数匿名函数（Lambda函数）嵌套函数函数装饰器高阶函数函数参数位置参数默认参数可变位置参数可变关键字参数函数属性和方法`__name__``__doc__``func.__dict__``func.__defaults__``func.__annotations__`函......
  • 2024夏中山集训第1周
    【NOIP模拟一】20240729比赛有点唐，C没开ll挂50，D挂了一点部分分。C注意到答案是s除以区间gcd。裴蜀定理推广D像这样建图，跑全源最短路。在这张图上有\(1\to2\to3\to4\to5\)和\(7\to8\to9\to3\to10\to11\)两条路径。把路径上的点看作车上的点，每个点本身看作......
  • 2024年必备技能：小红书笔记评论自动采集，零基础也能学会的方法
    摘要：面对信息爆炸的2024年，小红书作为热门社交平台，其笔记评论成为市场洞察的金矿。本文将手把手教你，即便编程零基础，也能轻松学会利用Python自动化采集小红书笔记评论，解锁营销新策略，提升个人竞争力。一、引言：为什么选择小红书数据采集？在小红书这片内容营销的热土上，笔记评论蕴......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99