IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> Educational Codeforces Round 120 (Rated for Div. 2)简训 -> 正文阅读

[数据结构与算法]Educational Codeforces Round 120 (Rated for Div. 2)简训

导语

日常

涉及的知识点

思维,二分,贪心

链接: Educational Codeforces Round 120 (Rated for Div. 2)

题目

A Construct a Rectangle

题目大意:给出三个的木条(长度为整数),现在需要挑选一根木条进行切割,保证得到的四根木条能够组成矩形,对于给定的木条判断是否能通过一次切割组成矩形

思路:判断是否存在一个能分成其余两条之和,或者判断是否有两条相等且另一条能一分为二

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >>t;
    while(t--) {
        int a[4];
        for(int i=1; i<=3; i++)cin >>a[i];
        sort(a+1,a+4);//排序便于判断能否加起来等于
        if(a[1]+a[2]==a[3]||(a[2]==a[3]&&a[1]%2==0)||(a[1]==a[2]&&a[3]%2==0))
            cout <<"yes\n";
        else
            cout <<"no\n";
    }
    return 0;
}

B Berland Music

题目大意:略

思路:分别收集喜爱与不喜爱的原价值,然后排序按照题设条件重新赋值即可

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int t,n,a[maxn],b[maxn];
bool vis[maxn];
vector<int>zero,one;
signed main() {
//    ios::sync_with_stdio(false);
//    cin.tie(0);
    cin >>t;
    while(t--) {
        cin >>n;
        for(int i=1; i<=n; i++)cin >>a[i];
        one.clear();
        zero.clear();
        for(int i=1; i<=n; i++) {
            int x;
            scanf("%1lld",&x);
            if(x)one.push_back(a[i]);//分别统计喜爱与不喜爱的价值
            else zero.push_back(a[i]);
        }
        int ans=n;
        sort(one.begin(),one.end());//重新排序
        int len=one.size();
        for(int i=len-1; i>=0; i--)//重新分配价值
            b[one[i]]=ans--;
        sort(zero.begin(),zero.end());
        len=zero.size();
        for(int i=len-1; i>=0; i--)
            b[zero[i]]=ans--;
        for(int i=1; i<=n; i++)
            cout <<b[a[i]]<<" ";
        cout <<endl;
    }
    return 0;
}

C Set or Decrease

题目大意:给出一共整数序列 a a a和一个整数 k k k,每一步可以选择一个下标 i i i,然后使 a i ? 1 a_i-1 ai??1,或者选择两个下标 i , j i,j i,j使得 a i = a j a_i=a_j ai?=aj?,求出能使得 ∑ i = 1 n a i ≤ k \sum_{i=1}^n a_i\le k i=1n?ai?k的最小操作次数

思路:贪心的来想,肯定是对最小值-1,多次-1之后让大值赋值为最小值即可,暴力尝试对几个大值赋值,然后二分获得给最小值-1的次数

代码

#include <bits/stdc++.h>
#define int long long
const int inf=0x3f3f3f3f;
using namespace std;
const int maxn=2e5+5;
int t,a[maxn],k,n,pre[maxn];
bool Judge(int len,int x) {
    int sum=pre[n-len]-a[1]+x*(len+1);
    return sum<=k;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    while(t--) {
        cin >>n>>k;
        for(int i=1; i<=n; i++)cin >>a[i];//记录数据
        sort(a+1,a+1+n);//排序
        for(int i=1; i<=n; i++)pre[i]=pre[i-1]+a[i];
        //前缀和
        int res=2*inf,ans=0;
        for(int i=0; i<=n-1; i++) {//i为最大的i个数被赋值为a[1]
            int l=-inf,r=inf;
            while(l<r) {
                int mid=l+r+1>>1;
                if(Judge(i,mid))//mid为对a[1]进行几次-1
                    l=mid;
                else
                    r=mid-1;
            }
            res=min(res,max(0ll,a[1]-l)+i);
            //a[1]-l为对a[1]减了几次,为负值代表不用减就能满足
        }
        cout <<res<<endl;
    }
    return 0;
}

D Shuffle

题目大意:给出一个01串,定义一个操作:选择串中的一个严格有k个1的子串然后重新排列再放回去,现在只能进行一次这个操作,求出最后能构造出多少种字符串

思路:由于长串的排列组合的结果包括短串的结果(例如1100和110,前者必然包括了后者的排列结果),所以枚举每种尽可能长的包括k个1的子串,并且去重,那么,如何去重呢?
如图,两个相邻的极长子串(假设k=2)在计算排列组合时,圈起来的地方是重复的,分别计算两个极长子串的排列数然后减去重复数即可,但是重复的部分只能插k-1个1,因为两个子串有一个1是公用的
在这里插入图片描述

代码

#include <bits/stdc++.h>
#define int long long
const int inf=0x3f3f3f3f;
using namespace std;
const int maxn=5e3+5;
const int mod=998244353;
int c[maxn][maxn],t;
vector<int>pos;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i=0; i<maxn; i++) {//预处理组合数的值
        c[i][0]=1;
        for(int j=1; j<=i; j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    }
    int n,k,res=0;
    cin >>n>>k;
    string s;
    cin >>s;
    pos.push_back(0);//塞一个0方便下标从1开始
    for(int i=0; i<n; i++)
        if(s[i]=='1')pos.push_back(i+1);//把1的下标塞进去,默认从1开始
    pos.push_back(n+1);//多塞一个作为结尾,方便统计
    int len=pos.size();
    for(int i=k; i<len-1; i++) {//以长度为k开始取
        res=(res+c[pos[i+1]-pos[i-k]-1][k])%mod;
        //pos[i+1]-pos[i-k]-1为极长串的长度
        if(i>k)res=(res-c[pos[i]-pos[i-k]-1][k-1]+mod)%mod;
        //去重,由于有一个1是公用的,所以是k-1
    }
    if(k==0||len-2<k)cout <<1<<endl;//特判
    else cout <<res<<endl;
    return 0;
}

参考文献

  1. C. Set or Decrease—二分+贪心
  2. Educational Codeforces Round 120 (Rated for Div. 2) D. Shuffle(组合数学+巧妙去重)
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-03-22 20:49:54  更:2022-03-22 20:52:19 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年1日历 -2025/1/9 2:05:23-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码