Codeforces Round 976 (Div. 2)（A，B，C，D，E）并查集，区间合并，概率dp

🕗 发布于 2024-10-03 22:35 算法 c++ 数据结构 动态规划

比赛链接

https://codeforces.com/contest/2020

A题

思路

按照 $2$ 的整次幂从大到小枚举。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, k;
int qmi(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1) res = res * a;
b >>= 1;
a = a * a;
}
return res;
}
void solve()
{
cin >> n >> k;
if (k == 1)
{
cout << n << endl;
return;
}
int ans = 0;
for (int i = 30; i >= 0; i--)
{
int op = qmi(k, i);
if (op <= n && op > 0)
{
ans += (n / op);
n = n - (n / op) * op;
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}

B题

思路

灯泡最后为开或关，与开关灯的操作次数有关。

每次开关灯的条件是包含因数 $i$ ，因此最后开着的灯的操作次数为偶数。

因为，只有平方数有奇数个因数，所以 $[1, n]$ 排除所有平方数的个数即为 $k$ 。

因此我们可以直接二分查找答案求解。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int k;
int func(int x)
{
return x - (int)(sqrtl(x));
}
void solve()
{
cin >> k;
int low = 1, high = 2e18;
while (low < high)
{
int mid = low + high >> 1;
if (func(mid) >= k)
{
high = mid;
}
else low = mid + 1;
}
cout << high << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}

C题

思路

所以可以从高位到低位贪心地确定 $a$ 的该位取什么值，然后分类讨论即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int b, c, d;
void solve()
{
cin >> b >> c >> d;
int ans = 0;
bool ok = true;
for (int j = 61; j >= 0; j--)
{
int bitb = (b >> j) & 1;
int bitc = (c >> j) & 1;
int bitd = (d >> j) & 1;
if (bitd == 1)
{
if (bitb == 1 && bitc == 1)continue;
if (bitb == 1 && bitc == 0)continue;
if (bitb == 0 && bitc == 1) {ok = false; continue;}
if (bitb == 0 && bitc == 0)ans += (1ll << j);
}
else
{
if (bitb == 1 && bitc == 1) {ans += (1ll << j); continue;}
if (bitb == 1 && bitc == 0) {ok = false; continue;}
if (bitb == 0 && bitc == 1) {ans += (1ll << j); continue;}
if (bitb == 0 && bitc == 0)continue;
}
}
if (!ok)
{
cout << -1 << endl;
}
else
{
cout << ans << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}

D题

思路

我们发现 $d$ 的大小只有 $10$ 。

我们可以将每一组 $a, d, k$ 视作一个区间。我们可以按照 $d$ 和 $\% d$ 依次对每一个区间进行分组。

之后，我们按照分好的每个小组依次进行区间合并。

对于合并后的区间，我们使用并查集进行暴力缩点，最后统计连通块的数量即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, m;
struct DSU {
std::vector<int> f, siz;

DSU() {}
DSU(int n) {
init(n);
}

void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}

int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}

bool same(int x, int y) {
return find(x) == find(y);
}

bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}

int size(int x) {
return siz[find(x)];
}
};
vector<pair<int, int>> merge(vector<pair<int, int>>&segs)
{
vector<pair<int, int>>res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
{
if (ed < seg.first)
{
if (ed != -2e9) res.push_back({st, ed});
st = seg.first;
ed = seg.second;
}
else ed = max(ed, seg.second);
}
if (st != 2e9) res.push_back({st, ed});
return res;
}
void solve()
{
cin >> n >> m;
DSU dsu(n + 1);
map<int, map<int, vector<pair<int, int>>>>mp1;
map<int, set<int>>mp2;
for (int i = 1, a, d, k; i <= m; i++)
{
cin >> a >> d >> k;
if (!mp1.count(d))
{
mp1[d][a % d].push_back({a, a + k * d});
mp2[d].insert(a % d);
}
else
{
if (mp2[d].count(a % d))
{
mp1[d][a % d].push_back({a, a + k * d});
}
else
{
mp1[d][a % d].push_back({a, a + k * d});
mp2[d].insert(a % d);
}
}
}
for (auto mpp : mp1)
{
int d = mpp.first;
for (auto val : mpp.second)
{

vector<pair<int, int>>op = merge(val.second);
for (pair<int, int> & pii : op)
{
int a = pii.first;
int high = pii.second;
for (int i = a + d; i <= high; i += d)
{
dsu.merge(i - d, i);
}
}

}
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (dsu.find(i) == i) ans++;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}

E题

思路

概率 $d p$

我们发现 $a_{i}$ 最大为 $1023$ ，也就是 $2^{10}-1$ 。

我们令 $dp_{i,j}$ 表示前 $i$ 个数，最终值为 $j$ 时的概率，状态转移方程为：

$\oplus a[i]] \times \frac{p[i]}{1e4} + dp[i-1][j] \times (1-\frac{p[i]}{1e4})$

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n;
int a[N], p[N];

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 MLong {
    i64 x;
    constexpr MLong() : x{} {}
    constexpr MLong(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_;
    }
    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr i64 val() const {
        return x;
    }
    explicit constexpr operator i64() const {
        return x;
    }
    constexpr MLong operator-() const {
        MLong res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MLong inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MLong &operator*=(MLong rhs) & {
        x = mul(x, rhs.x, getMod());
        return *this;
    }
    constexpr MLong &operator+=(MLong rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MLong &operator-=(MLong rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MLong &operator/=(MLong rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MLong operator*(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MLong operator+(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MLong operator-(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MLong operator/(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
        i64 v;
        is >> v;
        a = MLong(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MLong lhs, MLong rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MLong lhs, MLong rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;

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

    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * 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();
    }
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 1000000007;
using Z = MInt<P>;

void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
cin >> p[i];
}
int m = 1ll << 10;
const Z inv1e4 = Z(10000).inv();
vector<Z>dp(m);
dp[0] = 1;
for (int i = 1; i <= n; i++)
{
vector<Z>f(m);
for (int j = 0; j < m; j++)
{
f[j ^ a[i]] += dp[j] * p[i] * inv1e4;
f[j] += dp[j] * (Z(1ll) - p[i] * inv1e4);
}
dp.swap(f);
}

Z ans = 0;
for (int i = 0; i < m; i++)
{
ans += Z(1) * i * i * dp[i];
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}

原文地址：https://blog.csdn.net/weixin_74754298/article/details/142684362

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：TCP/UDP初识
下一篇：基于springboot的数据库原理教学案例案例库管理系统

ubuntu * 表达的应用
在使用 ln -s 软连接、cp -r， rm -r等操作指令时，一般都是对整个文件夹操作，但是有些时候只想复制文件夹中的文件，而不是整个文件夹，就需要*表达来进行筛选了。例如，将/home/no1/
阅读更多2024-10-05
mysql学习教程，从入门到精通，SQL 创建视图(CREATE VIEW 语句)（34）
在 SQL 中，`CREATE VIEW` 语句用于创建一个视图（View），视图是一种虚拟表，它基于 SQL 查询的结果集。视图并不存储实际数据，而是存储定义视图的查询。当您查询视图时，数据库会动态
阅读更多2024-10-05
KNN算法
机器学习是区别于明确编程,它通过算法训练数据学习内容,最终得到可靠的模型.今天先介绍其中一种模型训练算法KNN.
阅读更多2024-10-05
C++教程一口气讲完！（万字讲解）(￣y▽￣)╭ Ohohoho... 下
使用#define预处理器。使用const关键字。C++ 中的函数定义的一般形式如下：在 C++ 中，函数由一个函数头和一个函数主体组成。一个函数可以返回一个值。是函数返回的值的数据类型。有些函数执行
阅读更多2024-10-05
PowerShell脚本在自动化Windows开发工作流程中的应用
PowerShell是微软开发的一款基于任务的自动化和配置管理框架，它运行在.NETFramework之上，提供了丰富的命令行界面和脚本编写能力。与传统的CMD或Bash相比，PowerShell支持
阅读更多2024-10-05
C初阶（八）选择结构（分支结构）--if、else、switch
👉在本博文中，将有对 if 、else、switch使用场景的举例，还有关键字 case 、break的使用。
阅读更多2024-10-05
基于ScriptableObject设计游戏数据表
本文将针对运行时的只读数据表的应用进行探索，并且结合自定义的本地持久化存储方式使得基于ScriptableObject开发的数据表能够在运行时进行读写。
阅读更多2024-10-05
CentOS 替换 yum源经验分享
CentOS 替换 yum源经验分享
阅读更多2024-10-05
Stable Diffusion绘画 | 插件-Deforum：动态视频生成（中篇）
本篇文章重点讲解参数最多的关键帧模块。
阅读更多2024-10-05
函数的概念
函数是一组语句的集合，这些语句在某个条件下被执行。定义函数时，可以指定输入参数，并可以返回结果。
阅读更多2024-10-05

Codeforces Round 976 (Div. 2)（A，B，C，D，E）并查集，区间合并，概率dp

比赛链接

A题

思路

代码

B题

思路

代码

C题

思路

代码

D题

思路

代码

E题

思路

代码

相关文章