Codeforces Round 976 (Div. 2) and Divide By Zero 9.0（A~E）

🕗 发布于 2024-10-04 08:28 算法 数据结构 c++

A - Find Minimum Operations

思路

对 $n$ 进行 $m$ 进制分解，所有位上相加就是答案（参考 $m = 2$ 时）

代码

// Problem: A. Find Minimum Operations
// Contest: Codeforces - Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
// URL: https://codeforces.com/contest/2020/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
int calc(int n , int m){
int cnt = 0;
if(m == 1){
return n;
}
while(n){
cnt += n % m;
n /= m;
}
return cnt;
}
void solve() 
{
int n , m;
cin >> n >> m;
cout << calc(n , m) << endl;
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
cin>>t;
    while(t--)
    {
    solve();
    }
    return 0;
}

B - Brightness Begins

思路

经典关灯，第 $x$ 位置的灯会被 $x$ 的所有因数操作，因此当且仅当 $x$ 为完全平方数时会被关闭，考虑二分答案，找到 $mi d$ 之前有多少个完全平方数就能算出最终有多少个灯是关着的，可以直接用 $s q r t$ 函数近似的找到最接近 $mi d$ 的完全平方数，然后左右探测一下就能找到有多少个完全平方数小于等于 $mi d$ .

代码

// Problem: B. Brightness Begins
// Contest: Codeforces - Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
// URL: https://codeforces.com/contest/2020/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
#define int long long
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
void solve() 
{
int n;
cin >> n;
int l = n , r = 2e18;
while(l < r){
int mid = (l + r) >> 1;
//[1 - mid]中有几个完全平方数
int t = sqrt(mid);
while(t * t > mid){
t--;
}
while((t + 1) * (t + 1) <= mid){
t++;
}
if(mid - t >= n){
r = mid;
}
else{
l = mid + 1;
}
}
cout << l << endl;
}            
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
cin>>t;
    while(t--)
    {
    solve();
    }
    return 0;
}

C - Bitwise Balancing

思路

拆位，对每一位进行分析， $[b, c, d]$ 在某一位上的组合只有 $8$ 种，对每种分类讨论 $a$ 的取值

代码

// Problem: C. Bitwise Balancing
// Contest: Codeforces - Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
// URL: https://codeforces.com/contest/2020/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
#define int long long
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
void solve() 
{
//如果d的这一位是0，
int b , c , d;
cin >> b >> c >> d;
int a = 0;
for(int i = 63 ; i >= 0 ; i --){
if(d >> i & 1LL){
if(c >> i & 1LL){
if(b >> i & 1LL){
continue;
}
else{
cout << -1 << endl;
return;
}
}
else{
a |= (1LL << i);
}
}
else{
if(b >> i & 1LL){
if(c >> i & 1LL){
a |= (1LL << i);
}
else{
cout << -1 << endl;
return;
}
}
else{
continue;
}
}
}
cout << a <<endl;
}            
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
cin>>t;
    while(t--)
    {
    solve();
    }
    return 0;
}

D - Connect the Dots

思路

注意到 $d$ 很小，因此如果我们只需要知道某一位置上能否跟前面 $d$ 个数相连，就能把最终的图连出来。
用数组 $c n t [i] [j]$ 来表示 $a_i$ 能否跟 $a_{i - j}$ 相连，用差分来维护 $c n t$ 数组即可。

代码

// Problem: D. Connect the Dots
// Contest: Codeforces - Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
// URL: https://codeforces.com/contest/2020/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
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)];
    }
};

void solve() 
{
//注意到D很小
int n , m;
cin >> n >> m;
int vis[n + 100][20];
int cnt[n + 100][20];
memset(vis , 0 , sizeof vis);
memset(cnt , 0 , sizeof cnt);
DSU dsu(n + 5);
for(int i = 0; i < m ; i ++){
int a , d , k;
cin >> a >> d >> k;
int l = a , r = a + k * d;
cnt[l + d][d]++;
cnt[r + d][d]--;
}
for(int i = 1 ; i <= n ; i ++){
int tot = 0;
for(int j = 1 ; j <= min(10 , i) ; j ++){
cnt[i][j] += cnt[i - j][j];
}
}
for(int i = 2 ; i <= n ; i ++){
for(int j = 1 ; j <= min(i - 1 , 10) ; j ++){
if(cnt[i][j]){
dsu.merge(i , i - j);
}
}
}
int ans = 0;
for(int i = 1 ; i <= n ; i ++){
ans += (dsu.f[i] == i);
}
cout << ans << endl;
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
cin>>t;
    while(t--)
    {
    solve();
    }
    return 0;
}

E - Expected Power

思路

观察到 $a$ 数组取值很小，考虑 $d p$ 解决问题。用 $d p [i]$ 来代表取到当前取到 $i$ 的概率，那么对于每个 $a_{i}$ ,我们枚举 $\leq x \leq 1023)$ , $\oplus a_{i}] = dp[x] * p , dp[x] = dp[x] * (1 - p)$ ，总体复杂度为 $O (1024 * N)$ 能通过此题

代码

// Problem: E. Expected Power
// Contest: Codeforces - Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
// URL: https://codeforces.com/contest/2020/problem/E
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
#define int long long
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL qpow(LL a , LL b)//快速幂
{
LL sum=1;
while(b){
if(b&1){
sum=sum*a%mod;
}
a=a*a%mod;
b>>=1;
}
return sum;
}
void solve() 
{
int t = qpow(10000 , mod - 2);
int dp[1030][2];//取到i的概率
memset(dp , 0 , sizeof dp);
dp[0][0] = 1;
int n;
cin >> n;
int a[n];
for(int i = 0 ; i < n ; i ++){
cin >> a[i];
}
for(int i = 0 ; i < n ; i ++){
int p;
cin >> p;
for(int j = 0 ; j < 1024 ; j ++){
int k = j ^ a[i];
dp[k][1] += dp[j][0] * ((p * t) % mod);
dp[k][1] %= mod;
dp[j][1] += dp[j][0] * (((10000 - p) * t) % mod);
dp[j][1] %= mod;
}
for(int j = 0 ; j < 1024 ; j++){
dp[j][0] = dp[j][1];
dp[j][1] = 0;
}
}
int ans = 0;
for(int i = 1 ; i < 1024 ; i ++){
ans += dp[i][0] * i * i;
ans %= mod;
}
cout << ans << endl;
}            
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
cin>>t;
    while(t--)
    {
    solve();
    }
    return 0;
}

原文地址：https://blog.csdn.net/weixin_61825750/article/details/142646582

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

上一篇：在Linux中创建检查点并还原的工具——criu
下一篇：1G，2G，3G，4G，5G各代通信技术的关键技术，联系和区别

眼儿媚·秋雨绵绵窗暗暗
回忆彼时，恰是此时的仲秋季节，笔者的身体状况、精神面貌和心态都很糟糕，加上环境的十分冷清寂寞，就难免影响到老病之身，度日如年。
阅读更多2024-10-07
分享国产32位单片机的电机控制方案
由于其运算速度快，支持硬件压栈和硬件除法器，集成多个高级和通用定时器，内置多路高速双ADC和模拟运放，使其在电机控制应用领域有着较好的性能优势。•支持永磁同步电机(PMSM)、无刷直流电机(BLDC)
阅读更多2024-10-07
Linux 线程同步
介绍线程同步的概念和相关的接口操作
阅读更多2024-10-07
windows C++-创建基于代理的应用程序（上）
本文介绍了如何创建基本的基于代理的应用程序。在这个案例中，你可以创建一个代理，从文本文件中异步读取数据。应用程序使用 Adler-32 校验和算法来计算该文件内容的校验和。
阅读更多2024-10-07
归并排序：递归、非递归实现、文件排序(归并排序实现)
归并排序：递归、非递归实现、文件排序(归并排序实现)
阅读更多2024-10-07
第二章：处理机管理：第三节：同步与互斥
【总结】
阅读更多2024-10-07
Java8 到 Java23 的新特性，都在这里了！
其实每个 Java 版本发布的新特性并不多，而且好多特性要进行多个版本的孵化和预览。虽然公司的 Java 版本肯定跟不上 Java 版本发布的节奏，但作为程序员的我们，可以关注下 Java 的新增特性
阅读更多2024-10-07
如何实现两个标签页之间的通信
【代码】如何实现两个标签页之间的通信。
阅读更多2024-10-07
如何用3个月零基础入门网络安全？_网络安全零基础怎么学习
我们知道计算机最早是在西方发明出来的，很多名词或者代码都是英文的，甚至现有的一些教程最初也是英文原版翻译过来的，而且一个漏洞被发现到翻译成中文一般需要一个星期的时间，在这个时间差上漏洞可能都修补了。”
阅读更多2024-10-07
k8s集群搭建（保姆级教程以及遇到的各种问题解决）
注意上面指定的网段不要跟自己真实的内网网段产生冲突，否则会造成机器之间无法ping通的问题。之后修改kube-flannel.yml中"Network": "10.244
阅读更多2024-10-07