首页 > 其他分享 >2024 湖南省赛(HNCPC 2024)

2024 湖南省赛(HNCPC 2024)

时间:2024-11-10 21:46:19浏览次数:3  
标签:i64 return int cin 2024 using mint 湖南省 HNCPC

C - easy math

\[\Pi a_i \le 2024^b\\ \log_2 (\Pi 2^{k_i}) \le \log_2(2024^b)\\ \sum k_i\le b\log_2 2024 \]

因此答案就是\(b = \frac{\sum k_i}{\log_2 2024}\)

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;

#define int i64

using pii = pair<int,int>;
using vi = vector<int>;

 
i32 main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;

    int sum = 0;
    for(int i = 0, x; i < n; i ++) {
    	cin >> x;
    	sum += log2(x);
    }

    cout << ceil(sum / log2(2024));
    return 0;
}

E - 拼接串

考虑值域只有\(18\),因此我们可以用\(f[i]\)表示状态\(i\)对应的最长区间。其中\(i\)是一个\(18\)位二进制整数

我们可以先用双指针统计出每个\(l\)对应的合法区间的最大右端点\(r\)。并且更新\(f\)。

然后我们可以在做一次dp,状态为\(g[i]\)表示\(i\)的子集对应的最场区间。

此时答案就可以表示为\(\max(g[i]+g[(2^{18} - 1) \oplus i])\)。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;

#define int i64

using pii = pair<int,int>;
using vi = vector<int>;

 
i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;

    vi a(n + 1);
    for(int i = 1; i <= n; i ++) 
        cin >> a[i], a[i] = (1 << (a[i] - 1));

    int N = (1 << 18) - 1;
    
    vi f(N + 1);
    for(int l = 1, r = 0, t = 0; l <= n; l ++) {
        while(r + 1<= n and (t & a[r + 1]) == 0)
            r ++, t |= a[r];
        f[t] = max(f[t], r - l + 1);
        t ^= a[l]; 
    }

    for(int i = 0; i < N; i ++) {
        for(int j = 1; j <= N; j <<= 1){
            if((i & j) == 0)
                f[i | j] = max(f[i | j], f[i]);
        }
    }

    int res = 0;
    for(int i = 0; i <= N; i ++)
        res = max(res, f[i] + f[N ^ i]);
    cout << res;
    return 0;
}

H. 经文

\(f[i][j][l]\)表示前\(i\)位,且已经匹配了\(j\)个完整的串,当前串匹配到了\(l\)的方案数。然后我们可以枚举下一位放什么,这里面如果失配,下一位不一定需要从头开始匹配,我们可以用\(kmp\)的前缀数组进行计算下一位可能匹配到哪一位。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;

#define int i64

using pii = pair<int,int>;
using vi = vector<int>;

vector<int> prefix_function(const string &s) {
    vector<int> pi(s.size());
    for (int i = 2, j = 0; i < s.size(); i++) {
        while (j > 0 && s[i] != s[j + 1]) j = pi[j];
        if (s[i] == s[j + 1]) j++;
        pi[i] = j;
    }
    return pi;
}
const int mod = 998244353;
 
struct mint {
    int x;

    mint(int x = 0) : x(x) {}

    int val() {
        return x = (x % mod + mod) % mod;
    }

    mint &operator=(int o) { return x = o, *this; }

    mint &operator+=(mint o) { return (x += o.x) >= mod && (x -= mod), *this; }

    mint &operator-=(mint o) { return (x -= o.x) < 0 && (x += mod), *this; }

    mint &operator*=(mint o) { return x = (i64) x * o.x % mod, *this; }

    mint &operator^=(int b) {
        mint w = *this;
        mint ret(1);
        for (; b; b >>= 1, w *= w) if (b & 1) ret *= w;
        return x = ret.x, *this;
    }

    mint &operator/=(mint o) { return *this *= (o ^= (mod - 2)); }

    friend mint operator+(mint a, mint b) { return a += b; }

    friend mint operator-(mint a, mint b) { return a -= b; }

    friend mint operator*(mint a, mint b) { return a *= b; }

    friend mint operator/(mint a, mint b) { return a /= b; }

    friend mint operator^(mint a, int b) { return a ^= b; }
};

i32 main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;
    int m = s.size();
    s = " " + s;

    auto pi = prefix_function(s);

    vector f(n + 1, vector(k + 2, vector<mint>(m + 1)));
    f[0][0][0] = 1;
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j <= k; j ++) {
            for(int l = 0; l < m; l ++){
                for(char c = 'a'; c <= 'z'; c ++) { // 枚举 i+1 位放什么字母
                    bool ok = false;// 有没有匹配成功过
                    for(int pre = l; ok == false; pre = pi[pre]) {
                        if(s[pre + 1] == c) { // 匹配
                            if(pre == m - 1){
                                f[i + 1][j + 1][0] += f[i][j][l];
                            } else {
                                f[i + 1][j][pre + 1] += f[i][j][l];
                            }
                            ok = true;
                        }
                        if(pre == 0) break;
                    }
                    if(ok) continue;
                    f[i + 1][j][0] += f[i][j][l];
                }
            }
        }
    }
    mint res = 0;
    for(int i = 0; i < m; i ++)
        res += f[n][k][i];
    cout << res.val();
    return 0;
}

I - 数据检索系统

按照题目模拟

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;

#define int i64

using pii = pair<int,int>;
using vi = vector<int>;

 
i32 main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
    int mod, k, n, q;
    cin >> mod >> k >> n >> q;

    vi vis(mod);
    for(int x; n; n --) {
        cin >> x;
        for(int i = 1, y = 1; i <= k; i ++) {
            y = y * x % mod;
            vis[y] |= 1;
        }
    }

    for(int x, f; q; q --) {
        cin >> x, f = 1;
        for(int i = 1, y = 1; i <= k; i ++) {
            y = y * x % mod;
            f &= vis[y];
        }
        cout << f << " ";
    }
    return 0;
}

J - Beautiful Sequence

对于数组\(a[i]\)我们记\(A\)表示数字\(a[i]\)出现在了下标\(A[a[i]]\)的位置。对于\(b\)有类似的\(B\)

对于题目的要求,可以转换为对于值域\([l,r]\),如果值域内的数都选就是 beautifu 序列。

很容想到一个性质,对于值域\([l,r]\)的子序列,如果\(a,b\)相同,则一定满足值域\([l,r-1]\)的子序列\(a,b\)也一定相同。

因此我们可以用双指针求出对于每一个\(l\)符合条件的最大的\(r\)。

现在我们考虑如何快速判断出值域\([l,r]\)的子序列在\(a,b\)出现的顺序相同。此时应满足

\[\forall x,y \in [l, r], (A[x] > A[y]) = (B[x] > B[y]) \]

我们如果暴力的判断实际是\(O(N^2)\)的,加上双指针的复杂度,肯定无法通过。

我们可以考虑,如何在已知\([l,r - 1]\)满足的情况下,判断\([l,r]\)是否满足?

我们可以用两个std::set<int>分别维护\(A[l,r-1],B[l,r-1]\)。 当我们插入\(A[r],B[r]\),可以在set中找到前后的第一个数字,并判断是否相等,这样的复杂度是\(O(\log N)\)。所以总体复杂度就是\(O(N\log N)\)。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;

#define int i64

using pii = pair<int,int>;
using vi = vector<int>;

const int inf = LLONG_MAX / 2;


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int n, m;
    cin >> n;

    vi a(n + 1), b(n + 1), A(n + 1), B(n + 1);

    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        A[a[i]] = i;
    }

    for(int i = 1; i <= n; i ++) {
        cin >> b[i];
        B[b[i]] = i;
    }

    int res = 0;
    set<int> pa , pb;
    for(int l = 1, r = 0; l <= n; l ++ ){
        
        auto check = [&](int i) -> bool {
            int x = A[i], y = B[i];

            auto rx = pa.upper_bound(x), ry = pb.upper_bound(y);

            if((rx == pa.end()) != (ry == pb.end())) return false;
            

            if(rx != pa.end()) {
                if(a[*rx] != b[*ry]) return false;
            }

            if((rx == pa.begin()) != (ry == pb.begin())) return false;

            if(rx == pa.begin()) return true;

            auto lx = prev(rx), ly = prev(ry);

            if(a[*lx] != b[*ly]) return false;

            return true;
        };

        while(r + 1 <= n and check(r + 1)){
            r ++;
            pa.insert(A[r]), pb.insert(B[r]);
        }
        
        res += r - l + 1;

        pa.erase(A[l]), pb.erase(B[l]);
    }

    cout << res;

}

K - 渡劫

我们可以建立分层图,这样的话一次免费的机会就是层与层之间的单向边。然后建立一个超级终点,然后从每一个点到超级终端的单向边权就是点权。

然后就是要求所有点到终点的最短路,实际上我们从终点反向建边求单源最短路。

答案就是最短路的最大值。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;

#define int i64

using pii = pair<int,int>;
using vi = vector<int>;

const int inf = LLONG_MAX / 2;


i32 main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;

    int N = 2 * n;

    vector<vector<pii>> e(N + 1);
    for(int u, v, w; m; m --) {
        cin >> u >> v >> w;
        e[u].emplace_back(v, w);
        e[v].emplace_back(u, w);
        e[u].emplace_back(v + n, 0);
        e[v].emplace_back(u + n, 0);
        e[u + n].emplace_back(v + n, w);
        e[v + n].emplace_back(u + n, w);
    }

    for(int i = 1, x; i <= n; i ++) {
        cin >> x;
        e[0].emplace_back(i, x);
        e[0].emplace_back(i + n, x);
    }

    vi dis(N + 1, inf), vis(N + 1);
    dis[0] = 0;

    priority_queue<pii,vector<pii>, greater<>> heap;
    heap.emplace(0, 0);
    while(not heap.empty()) {
        auto [d, u] = heap.top();
        heap.pop();

        if(vis[u]) continue;
        vis[u] = 1;
        for(auto [v, w] : e[u]) {
            if(vis[v] or dis[v] <= d + w) continue;
            dis[v] = d + w;
            heap.emplace(dis[v], v);
        }
    }
    
    int res = -1;
    for(int i = 1; i <= n; i ++)
        res = max(res, min(dis[i], dis[i + n]));
    cout << res;
	return 0;
}

标签:i64,return,int,cin,2024,using,mint,湖南省,HNCPC
From: https://www.cnblogs.com/PHarr/p/18538584

相关文章

  • 2024年(2025届)四非电子通信保研推免经历(北邮、西电、西工大、天大等)
    前言写下这篇博客的原因在于自己保研期间刷了很多很多的经验贴,保研过程中充满了大量的信息差,一路走来听了很多学长学姐讲述了自己的经历,感觉收获颇丰。所以希望能将自己的经历也分享下去,如果以后的学弟学妹能获得一点点帮助,那就再好不过了。一、保研黑话rk:绩点/均分/综测的......
  • 多校A层冲刺NOIP2024模拟赛20
    多校A层冲刺NOIP2024模拟赛20昨天晚上打ABC了,所以今天才发。T1星际联邦直接上菠萝(Borůvka)算法就行了,当然还可以用线段树优化prim算法,但是没打过只是口胡:就是维护当前的连通块,但一个点$i$加入连通块时,后面那些点就可以有$a_j-a_i$的贡献,前面的点可以有$a_i-......
  • 2024-2025-1 学号20241306 《计算机基础与程序设计》第7周学习总结
    2024-2025-1学号20241306《计算机基础与程序设计》第7周学习总结作业信息这个作业属于哪个课程<班级的链接>2024-2025-1-计算机基础与程序设计这个作业要求在哪里<作业要求的链接>(如2024-2025-1计算机基础与程序设计第一周作业)这个作业的目标了解学习数组与链......
  • CSP-J/S 2024游记
    年代久远,有些内容记不太清了。初赛Day-n~0做做了n遍的模拟卷。(明年再也不做了)Day1面到了一桶人。zyf和ikun在跟lzt的同学打听lzt的一些秘密。zyf'sbrother在玩自动伞,非常善。他试图把伞发射到楼上去,但后来伞虚了。J和S都和zqy一个考场。JT1错了,真抽象。(......
  • 2024.11.10 鲜花
    Triple扩展像神一样呐愛のネタバレ「別れ」っぽいな人生のネタバレ「死ぬ」っぽいななにそれ意味深でかっこいいじゃんそれっぽい単語集で踊ってんだ失敬とぅとぅるとぅとぅとぅる“風”とぅとぅるとぅとぅとぅる“風”とぅとぅるとぅとぅとぅる“風......
  • 2024-2025-1 20241406刘书含《计算机基础与程序设计》第七周学习总结
    作业信息作业课程 2024-2025-1-计算机基础与程序设计作业要求 2024-2025-1计算机基础与程序设计第七周作业作业目标 数组与链表,基于数组和基于链表实现数据结构,无序表与有序表,树,图,子程序与参数作业正文 2024-2025-120241328《计算机基础与程序设计》第七周学习总结教材学习......
  • 2024-2025-1 20241408陈烨南《计算机基础与程序设计》第七周学习总结
    这个作业属于哪个课程2024-2025-1-计算机基础与程序设计)这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK07这个作业的目标数组与链表、基于数组和基于链表实现数据结构、无序表与有序表、树、图、子程序与参数作业正文本博客链接教......
  • NOIP2024(欢乐)加赛3
    NOIP2024(欢乐)加赛3\(T1\)CF2033BSakurakoandWater\(100pts\)枚举主对角线取\(\max\)即可。点击查看代码lla[510][510];intmain(){ llt,n,ans=0,maxx,i,j,k,h; cin>>t; for(h=1;h<=t;h++) { cin>>n; ans=0; for(i=1;i<=n;i++) { for(......
  • 20222402 2024-2025-1《网络与系统攻防技术》实验四实验报告
    一、实验内容本周学习内容计算机病毒(Virus):通过感染文件(可执行文件、数据文件、电子邮件等)或磁盘引导扇区进行传播,一般需要宿主程序被执行或人为交互才能运行蠕虫(Worm):一般为不需要宿主的单独文件,通过网络传播,自动复制通常无需人为交互便可感染传播恶意移动代码(Malicio......
  • 20222409 2024-2025-1 《网络与系统攻防技术》实验四实验报告
    1.实验内容1.1本周学习内容本周学习了恶意代码分析的基本方法,静态分析和动态分析的核心概念。静态分析主要通过代码结构和API调用等特征来识别恶意行为,动态分析则使用沙箱等环境运行代码,观察其行为。通过实验学习了IDAPro和ProcessMonitor等工具的基本操作。1.2实践内容......