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

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

时间：2024-07-25 21:32:50浏览次数：7  
标签：钉耙 i64 begin return int 编程 2024 矩形 MInt

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

循环位移

HDU - 7433

思路

字符串哈希，将 A 串拼接两遍记为 AA，然后对其哈希一下，用 map/set 记录哈希值，因为 \(|A|\le|B|\)，所以只要检查 B 中长度为 \(|A|\) 的子串哈希值是否存在 AA 中即可。

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

struct Hash {
    using u64 = unsigned long long;
    u64 base = 13331;
    vector<u64> pow, hash;
    Hash(string &s) {
        s = " " + s;
        int N = s.size();
        pow.resize(N + 1), hash.resize(N + 1);
        pow[0] = 1, hash[0] = 0;
        for (int i = 1; i < s.size(); i ++) {
            pow[i] = pow[i - 1] * base;
            hash[i] = hash[i - 1] * base + s[i];
        }
    }

    u64 get(int l, int r) {
        return hash[r] - hash[l - 1] * pow[r - l + 1];
    }

    //拼接两个子串
    u64 link(int l1, int r1, int l2, int r2) {
        return get(l1, r1) * pow[r2 - l2 + 1] + get(l2, r2);
    }

    bool same(int l1, int r1, int l2, int r2) {
        return get(l1, r1) == get(l2, r2);
    }

};

void solve() {

    string a, b;
    cin >> a >> b;

    int k = a.size();

    a = a + a;

    Hash HashA(a), HashB(b);

    set<i64> s;
    for (int i = 0; i + k - 1 < a.size(); i ++) {
        s.insert(HashA.get(i, i + k - 1));
    }

    i64 ans = 0;
    for (int i = 0; i + k - 1 < b.size(); i ++) {
        if (s.count(HashB.get(i, i + k - 1)))
            ans ++;
    }

    cout << ans << '\n';

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

星星

HDU - 7434

思路

考虑分组背包。

设 \(dp_i\) 表示体积为 i 的星星所需的最小代价。

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

void solve() {

    int n, k;
    cin >> n >> k;

    vector<array<i64, 5>> A(n + 1);
    for (int i = 1; i <= n; i ++)
        cin >> A[i][1] >> A[i][2] >> A[i][3] >> A[i][4];


    vector<i64> dp(k + 1, INT_MAX);

    dp[0] = 0;
    for (int i = 1; i <= n; i ++) {
        for (int v = k; v >= 0; v --) {
            for (int j = min(v, 4); j >= 0; j --) {
                dp[v] = min(dp[v], dp[v - j] + A[i][j]);
            }
        }
    }

    cout << dp[k] << '\n';

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

思路

代码

思路

代码

思路

代码

思路

代码

并

HDU - 7444

思路

点数较少，但坐标很大，考虑离散。

求 k 个矩形面积并集的期望，看到面积并，想到扫描线，但是扫描线只能扫描全部扫，无法单独扫某些矩形，考虑将问题转化。

一个矩形会对 \(H\times W\) 个格子产生贡献，则可以计算 n 个矩形对哪些格子产生贡献，这一步可以用一阶差分二维前缀和计算，假设把 k 个矩形的贡献集中一点，是不是就变成了这个点中 k 个矩形对其产生的期望了呢，现考虑扩展到矩形，要计算 k 个矩形的，就是把这 k 个矩形对点的贡献又统计起来，但这样统计又要在计算的时候去 n 方遍历，诶，之前不是离散了坐标吗，离散后的两个点之间构成的矩形面积就是对当前所覆盖的点产生的总贡献，那我们就可以直接计算当前点被覆盖的次数加上这个矩形的贡献，这样就把所有 k 个矩形产生的贡献集中在一个点被覆盖了 k 次的贡献中了。

设 \(g_i\) 表示被 i 个矩形覆盖的区域的面积之和，考虑枚举选出 k 个矩形，再枚举被覆盖了 i 次的区域，当 \(n-i<k\) 的时候，则说明这个区域至少会被 k 个矩形中的一个所覆盖，那么其产生的贡献就是 \(g_i\)，当 \(n-i≥k\) 的时候，不会算，题解是考虑取补集，即考虑这些区域不被 k 个矩形中任意一个覆盖的概率，即 \(\sum_{j=1}^n\Big(1-\frac{C_{n-i}^k}{C_n^k} \Big)\times g_i\)

代码

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

//------取模机------//
using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
    T res {1};
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
} // 快速幂

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
} // 取模乘

template<i64 P>
struct MInt {
    i64 x;
    constexpr MInt() : x {0} {}
    constexpr MInt(i64 x) : x {norm(x % getMod())} {}

    static i64 Mod;
    constexpr static i64 getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(i64 Mod_) {
        Mod = Mod_;
    }//只有P<=0, setMod才生效
    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr i64 val() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        if (getMod() < (1ULL << 31)) {
            x = x * rhs.x % int(getMod());
        } else {
            x = mul(x, rhs.x, getMod());
        }
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
    friend constexpr bool operator<(MInt lhs, MInt rhs) {
        return lhs.val() < rhs.val();
    }
};

template<>
i64 MInt<0>::Mod = 998244353; //只有P<=0, Mod才生效

constexpr int P = 998244353; //在这设置要用的模数
using Z = MInt<P>;
//------取模机------//

//----计算组合数----//
struct Comb {
    int n;
    std::vector<Z> _fac; //阶乘
    std::vector<Z> _invfac; //阶乘的逆元
    std::vector<Z> _inv; //数字的逆元

    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }

    void init(int m) {
        m = std::min<i64>(m, Z::getMod() - 1);
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);

        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }

    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z C(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
    Z A(int n, int m) {
        if (n < m || m < 0 ) return 0;
        return fac(n) * invfac(m);
    }
} comb;
//----计算组合数----//

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<pair<int, int>> loc1, loc2;
    vector<i64> x, y;
    for (int i = 0; i < n; i ++) {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        loc1.emplace_back(x1, y1);
        loc2.emplace_back(x2, y2);
        x.push_back(x1), x.push_back(x2);
        y.push_back(y1), y.push_back(y2);
    }

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    int len1 = unique(x.begin(), x.end()) - x.begin();
    int len2 = unique(y.begin(), y.end()) - y.begin();
    x.resize(len1);
    y.resize(len2);

    vector f(len1 + 1, vector<int>(len2 + 1));
    for (int i = 0; i < n; i ++) {
        auto &[lx, ly] = loc1[i];
        auto &[rx, ry] = loc2[i];

        lx = lower_bound(x.begin(), x.end(), lx) - x.begin() + 1;
        rx = lower_bound(x.begin(), x.end(), rx) - x.begin() + 1;
        ly = lower_bound(y.begin(), y.end(), ly) - y.begin() + 1;
        ry = lower_bound(y.begin(), y.end(), ry) - y.begin() + 1;

        f[lx][ly] ++ , f[lx][ry] --, f[rx][ly] --, f[rx][ry] ++;
    }

    for (int i = 1; i <= len1; i ++)
        for (int j = 1; j <= len2; j ++)
            f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];

    vector<Z> num(n + 1);
    for (int i = 1; i <= len1; i ++)
        for (int j = 1; j <= len2; j ++)
            num[f[i][j]] += Z(x[i] - x[i - 1]) * (y[j] - y[j - 1]);

    for (int k = 1; k <= n; k ++) {
        Z ans = 0;
        for (int i = 0; i <= n; i ++) {
            ans += (comb.C(n, k) - comb.C(n - i, k)) * num[i];
        }
        ans /= comb.C(n, k);
        cout << ans << '\n';
    }

    return 0;
}

标签：钉耙,i64,begin,return,int,编程,2024,矩形,MInt
From： https://www.cnblogs.com/Kescholar/p/18324143

相关文章

  • 自定义IPython启动：打造个性化的交互式编程环境
    自定义IPython启动：打造个性化的交互式编程环境IPython，一个强大的交互式Python解释器，提供了丰富的定制选项，允许用户根据个人或团队的需求定制其行为和外观。设置自定义的启动命令是IPython定制功能的一部分，它可以让你在启动IPython时自动执行一系列操作，如导入模块、设置变量......
  • 2024牛客暑期多校训练营4
    Preface最赤石的一集，上来先认为D是个煞笔贪心提交了该题的第一发代码并喜提WA后面下机后祁神把L扔给我告诉我就是个煞笔线段树板，结果我写完过不去样例发现题意假了值得一提的是最后发现这两题是这场过的人最少的两题，直接开局给我干的道心破碎之后A题写不来带权并查集样......
  • 2024暑假集训测试11
    前言比赛链接。这次好多外校的参加\(60\)多个人，反正至少没怎么挂分。确切的说赛时我只能冲T1、T2，T3可撤销或可持久化并查集都不会，赛后现学的，T4更抽象，可惜T2打假了。T3最后五分钟才开始看，没想直接打暴力了。但是T3数据太水了，加了捆绑还是水，赛后安排了重测。T1Pe......
  • 河南萌新联赛2024第（二）场：南阳理工学院
    A-国际旅行Ⅰ因为保证联通，所以直接排序就好了#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingvi=vector<int>;i32main(){ intn,m,q; cin>>n>>m>>q; via(n); for(int&i:a)cin>>i; sort(a......
  • Kotlin协程：现代并发编程的艺术
    引言随着软件系统变得越来越复杂，处理异步操作的需求也随之增加。传统的多线程模型虽然有效，但在某些情况下会导致过多的资源消耗和复杂的控制流。Kotlin协程提供了一种优雅的方式来管理这些异步任务，并且极大地简化了代码结构。协程简介协程是一种轻量级的线程，允许程序在执行过......
  • 【专题】2024年云计算白皮书报告合集PDF分享（附原数据表）
    原文链接：https://tecdat.cn/?p=371122023年全球云计算市场显著增长，预计将持续繁荣至2027年突破万亿美元，中国市场同样保持强劲势头，预计也将大幅跃升。国内云计算经过十余年发展，虽取得显著进展，但在资源布局、服务质量和技术融合等方面仍需深化提升。阅读原文，获取专题报告合集全文，解......
  • 平邑2024高算（补题）
    Day1risk题目描述解法考虑最后的集结，不妨考虑找出所有集结过程中可能经过的边，不难发现是一棵树，所以答案就是最小生成树。代码点击查看代码structnode{ intu,v,w;}e[3000001];intn,m;intfa[3000001];intfind(intx){ returnx==fa[x]?fa[x]:fa[x]=find(......
  • 2024 暑假友谊赛-热身2
    TreeDestruction-洛谷|计算机科学教育新生态(luogu.com.cn)思路:树的直径。定理：在一棵树上，从任意节点y开始进行一次DFS，到达的距离其最远的节点z必为直径的一端。第一次dfs1(),从任意一个点,到达的最远的点必然是直径两端的其中一个。再从找到的端点开始dfs1(),......
  • NOIP2024/7/25模拟赛
    T4题意：答案对\(2^{16}\)取模。分析：根节点\(1\)选到\(1\)的概率为\(\frac{1}{n}\)，然后随便把剩下的\(n-1\)分配给它的所有子树，记\(1\)的其中一个儿子为\(y\)，那么\(y\)选到它所被分配到的数中最小值的概率为\(\frac{1}{siz_{y}}\)，然后\(y\)再继续分配给它的子......
  • 河南萌新联赛2024第（二）场：南阳理工学院
    1.D-A*BBBB原题链接：https://ac.nowcoder.com/acm/contest/87255/D根据乘法的原理，且b的每一位都相同，最终答案则是错位相加得出的结果，于是我们将a翻转，从个位开始计算，如果当前位置小于a.size就往前累加，但如果大于或等于b.size就从头开始一个一个的减（这个过程可以通过纸上手写乘法计......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99