Codeforces Round 962 (Div. 3) ABCDEF（思路+代码）

🕗 发布于 2024-08-01 23:51 c++ 算法 数据结构 二分前缀和

题目链接https://codeforc es.com/contest/1996

A. Legs

题意

一只鸡有两条腿，一只牛有四条腿，一共有 $n$ ( $n$ 是偶数)条腿，问最少多少只动物。

思路

全是牛的时候动物数量最多，所以 $\lceil \frac{n}{4} \rceil$

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n;
    cin>>n;
    cout<<(n+3)/4<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

B. Scale

题意

有一个01数组，请你缩小k倍，然后输出它。

例如：

缩小完变为

01
10

思路

循环输出，每次跳k格即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
char mp[1005][1005];
void solve(){
    int n,k;
    cin>>n>>k;
    rep(i,1,n){
        rep(j,1,n) cin>>mp[i][j];
    }
    for(int i =1;i<=n;i+=k){
        for(int j = 1;j<=n;j+=k){
            cout<<mp[i][j];
        }
        puts("");
    }
}
signed main(){
    // IO;
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

C. Sort

题意

给你两个字符串 $a, b$ , 进行 $q$ 次询问，每次询问 $l, r$ 。对于每次询问，你可以进行一些次数操作，每次可以使得一个字符变为任意另一个字符，问最少多少次操作，能够使得 $sor t e d (a [l .. r]) = sor t e d (b [l .. r])$

注意：每次询问的修改操作不影响之后的询问。

思路

因为我们会对这两个子串进行排序操作，所以我们就只需要考虑子串中每个字符出现的次数即可。

我们定义两个子串的差异度为 $\sum_{ch = a}^z |cnta[ch]-cntb[ch]|$ ,即每种字符在两个子串中数量的差的总和。

我们每次操作可以将一个字符变为另一个字符，因此会使得二者的差异度减少2 。

所以我们总共的操作次数就是差异度除以2。即 $\frac{\sum_{ch = a}^z |cnta[ch]-cntb[ch]|}{2}$

于是我们需要解决的问题变为：如何更快地求出某一子串中所含有的字符数量： 前缀和 ，使用一个sum[N][26] 数组来记录每个字符出现的次数。于是对于某一子串 $a [l .. r]$ ，字符 $c h$ , 出现的次数为sum[r][ch-'a'] - sum[l-1][ch-'a']

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int cnt1[200005][27];
int cnt2[200005][27];
void solve(){
    int n,q;
    cin>>n>>q;
    string a,b;
    cin>>a>>b; a = ' ' + a; b = ' ' + b;
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<26;j++){
            cnt1[i][j] = cnt1[i-1][j] + (a[i] == 'a' + j);
            cnt2[i][j] = cnt2[i-1][j] + (b[i] == 'a' + j);
        }
    }
    while(q--){
        int l, r;
        cin>>l>>r;
        int ans = 0;
        for(int j = 0;j<26;j++){
            ans += abs((cnt1[r][j] - cnt1[l-1][j])-(cnt2[r][j] - cnt2[l-1][j]));
        }
        cout<<ans/2<<'\n';
    }
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

D. Fun

题意

给定两个数 $n, x$ , 求满足 $a+b+c\le x , ab + ac + bc \le n$ 的三元组 $(a, b, c)$ 的个数。 $1\le n ,x \le 10^6$

注意：三元组是有序的，即 $(1, 1, 2), (2, 1, 1)$ 视为不同的三元组

思路

如果暴力枚举，我们需要三重循环分别枚举 $a, b, c$ ，他们的取值为 $1\le a,b,c \le x-2$ ,此时的复杂度为 $O(x^3)$ ，显然是不行的。考虑根据两个条件节时，我们枚举最外层变量为a，即在a确定之后：

根据条件1：一定有 $\le x - a - c \le x - a - 1$ ，于是b只需要枚举到 $x - a - 1$ 即可。
根据条件2：一定有 $a * b < n$ , 即b最大为 $\lfloor \frac{n}{a} \rfloor$

二者取min，得到b的最大值。可以得出，此时枚举a和b的复杂度大概为 $n l nn$ , 那么我们需要 $O (1)$ 求出c的取值范围，在确定完 $a, b$ 的值后，可以得出$ 1\le c \le min(x - a -b,\frac{ n - ab}{a+b})$ , 而对于每个c，都会对答案贡献1，因此在确定完a和b后，我们直接令答案加上$ min(x - a -b,\frac{ n - ab}{a+b})$ 即可。总体时间复杂度即为枚举a和b的复杂度 $O (n l nn)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n,x;
    cin>>n>>x;
    int ans =0;
    rep(a,1,x){
        rep(b,1,x){
            if(a+b>=x) break;
            if(a*b>=n) break;
            int nn = n - a * b;
            int c1 = (n-a*b) / (a+b);
            int c2 = x - a - b;
            ans += min(c1,c2);
        }
    }
    cout<<ans<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

E. Decode

题意

给一个01串S，求对于每一对 $(1\le l\le r\le n)$ ,计算 $,(l\le x\le y \le r)$ 这样的整数对的个数，要求 $S [x .. y]$ 中0 和1的数量相同。

思路

我们考虑逆向思维，找出每一个满足 $f_0(S[x..y]) = f_1(S[x..y])$ 的 $(x, y)$ 对，计算每个对的贡献（即为在多少个子串 $S [l .. r]$ 中），将其加和即可。如果我们确定一个 $(x, y)$ 那么很容易算出，它的贡献为 $x * (n - y + 1)$ 。

那么如何确定这些 $(x, y)$ 对呢，我们考虑前缀和，将字符0的贡献为-1，字符1的贡献为1 ，那么 $f_0(S[x..y]) = f_1(S[x..y])$ 就等价于 $s u m [y] = s u m [x - 1]$ , 我们边枚举y边对这么一个sum数组进行桶计数。于是 $c n t [s u m [y]]$ 即表示在y之前，有多少个 $x$ 满足 $s u m [x - 1] = s u m [y]$ ,但是我们记录数量是不够的，我们还要考虑x的位置，即对于每个y，贡献为 $x_1*(n-y+1) + x_2*(n-y+1)+...+x_k*(n-y+1) = (x_1+x_2+...+x_k)*(n-y+1)$ ，于是我们的桶数组每次应该令 $c n t [s u m [x]] + = i + 1$ ，即记录为每个满足条件的 $x$ 的和。（注意每次加到 $c n t$ 数组中的是 $i + 1$ ,不是 $i$ ,因为 $i = x - 1$ ）

注意 $s u m [x]$ 可能是负数，我们进行桶计数是要进行偏移 $n$ 处理
注意对答案加和的过程中取模

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
const int mod = 1e9+7;
void solve(){
    string str;
    cin>>str;
    int n = str.size();str = ' ' + str; // 将字符串变为下标从1开始
    vector<int> cnt(2 * n + 5); // 开2*n大小的桶，因为sum[i]的取值为[-n,n]
    vector<int> sum(n+5);
    cnt[0+n] = 1;
    int ans = 0;
    for(int i = 1;i <= n;i++){
        int y = i;
        sum[y] = sum[y-1];
        if(str[y] == '0') sum[y]--;
        else sum[y] ++;
        ans = (ans + cnt[sum[y]+n] * (n-y+1)%mod)%mod;
        cnt[sum[y] + n] += i+1; // 这里要加一，因为我们存的是sum[x-1],那么对于
    }
    cout<<ans<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

F. Bomb

题意

给两个长度为 $n$ 的数组 $a, b$ , 你至多进行 $k(1\le k \le 10^9)$ 次操作，每次操作如下：
选择一个数 $i$ , 获得 $a [i]$ 枚金币，并令 $a [i] = ma x (0, a [i] - b [i])$

问最多能获得多少金币

思路

我们先考虑 $O (k)$ 的朴素解法：每次选择一个最大的 $a [i]$ ,选择完后使用堆（优先队列）更新最大值，重复选择k次即可。

但是上述代码会导致超时（因为k太大了），我们考虑二分搜索：

我们设 $f (x)$ 表示令所有的 $a [i]$ 都减至 $a [i] < x$ ，所需要的操作次数。显而易见， $f (x)$ 是单调递减的。因此满足二分性。

我们找到这样一个 $l$ , 使得 $\le k$ , 这样我们先令所有的 $a [i]$ 都减至小于 $l$ ,此时相比k，会多进行 $f (l) - k$ 次操作，因此会导致多获得一些金币，这里每次操作会使我们额外获得 $l$ 的贡献，令最终的金币数量减去 $(f (l) - k) * l$ 即为最终答案。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int n,k;
int a[200005];
int b[200005];
bool check(int x){
    int sum = 0;
    for(int i = 1;i<=n;i++){
        if(a[i]>=x){
            sum += (a[i]-x)/b[i] + 1;
        }
    }
    return sum <= k;
}
void solve(){
    cin>>n>>k;
    rep(i,1,n) cin>>a[i];
    rep(i,1,n) cin>>b[i];
    int l =0; int r =1e9+5;
    while(l<r){
        int mid = (l+r+1)>>1;
        if(check(mid)){
            r = mid-1;
        }else{
            l = mid;
        }
    }
    int ans = 0;
    int s = 0;
    for(int i = 1;i<=n;i++){
        if(a[i]>=l){
            int m = (a[i] - l)/b[i] + 1;
            ans += (a[i] + a[i]-(m-1)*b[i])*m/2;
            s += m;   
        }
    }
    ans -= 1LL * l * (s - k);
    cout<<ans<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

原文地址：https://blog.csdn.net/qq_66608435/article/details/140856880

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

上一篇：linux进程脚本开机自启动异常，手动执行正常问题分析
下一篇：架构师软考-每日两道单选题1

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20