首页 > 其他分享 >9.12 div.1

9.12 div.1

时间：2023-09-14 13:44:57浏览次数：41  
标签：typedef int 9.12 long -- solve div.1 define

Educational Codeforces Round 100 (Rated for Div. 2)

Educational Codeforces Round 101 (Rated for Div. 2)

Educational Codeforces Round 102 (Rated for Div. 2)

B - Find The Array

思路：相邻的数要有一方能整除另一方，那么一方为1的话一定可以，按奇偶位置将数分为两部分，求出a的两部分中的数的和，和大的那部分对应的b为1，另一部分为a，可以发现为1的部分带来的贡献一定是小于等于S的

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
const int N=1e4+5;
void solve(){
    int n;cin>>n;
    vector<int>a(n+1);
    int s1=0,s2=0;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        if(i%2)s1+=a[i];
        else s2+=a[i];
    }
    if(s1>s2){
        for(int i=1;i<=n;++i){
            if(i%2)cout<<a[i]<<' ';
            else cout<<1<<' ';
        }
    }else{
        for(int i=1;i<=n;++i){
            if(i%2)cout<<1<<' ';
            else cout<<a[i]<<' ';
        }
    }cout<<'\n';
}
signed main(){
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

C - Busy Robot

思路：模拟每一操作，对于忽略的操作，判断是否在上一操作完成和下一操作开始之前到达

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n;cin>>n;
    vector<int>t(n+5),x(n+5);
    for(int i=0;i<n;++i)cin>>t[i]>>x[i];
    t[n]=1e10;
    int st=0,ed=0,las=0,ans=0,ne=0;
    for(int i=0;i<n;++i){
        if(t[i]>=ne){
            ne=t[i]+abs(x[i]-ed);
            st=ed,ed=x[i];
            las=i;
            if(ne<=t[i+1])ans++;
        }else{
            if(st>=ed){
                int r=st-t[i]+t[las];
                int l=max(ed,st-t[i+1]+t[las]);
                if(x[i]>=l&&x[i]<=r)ans++;
            }else{
                int l=st+t[i]-t[las];
                int r=min(ed,st+t[i+1]-t[las]);
                if(x[i]>=l&&x[i]<=r)ans++;
            }
        }
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

D - Pairs

思路：由于a已定，那么每对中都有一个数已确定，只剩下n个数可匹配，若匹配的数大于ai，则是在x里，否则在n-x里；直接考虑极限，求x的最小值时，匹配的数向上取（从小的开始），求x的最大值时，匹配的数向下取（从大的开始）

 

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
const int N=1e4+5;
void solve(){
    int n;cin>>n;
    vector<int>st(2*n+1);
    for(int i=1,x;i<=n;++i){
        cin>>x;st[x]=1;
    }
    int c=0,l=0,r=n;
    for(int i=1;i<=2*n;++i){
        if(st[i]){
            if(c)c--;
            else l++;
        }else c++;
    }
    c=0;
    for(int i=2*n;i>=1;--i){
        if(st[i]){
            if(c)c--;
            else r--;
        }else c++;
    }
    cout<<r-l+1<<'\n';
}
signed main(){
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

C - Building a Fence

思路：由于第一个和第n个已确定位置，那么从第一个位置开始，维护放的围栏底部的范围l~r，满足与前一个位置的范围距离和与当前地板的距离不超过k-1

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n,k;cin>>n>>k;
    vector<int>a(n+1);
    for(int i=1;i<=n;++i)cin>>a[i];
    int l=a[1],r=a[1];
    for(int i=2;i<=n;++i){
        l=max(a[i],l-k+1);
        r=min(a[i]+k-1,r+k-1);
        if(l>r){
            cout<<"NO\n";return ;
        }
    }
    if(a[n]>=l&&a[n]<=r){
        cout<<"YES\n";
    }else cout<<"NO\n";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

D - Ceil Divisions

思路：非1非2非n的数都可以由n变为1，但将n变为1最少需要18次，所以考虑用一个数a消n，令a=2x，n=ay，且n-4+x+y<=n+5，即x+y<=9；可以看出当a为8时满足

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n;cin>>n;
    vector<PII>ans;
    if(n<=8){
        for(int i=3;i<n;++i){
            ans.push_back({i,n});
        }
        int t=n;
        while(t>1){
            ans.push_back({n,2});
            t=(t+1)/2;
        }
    }else{
        for(int i=3;i<n;++i){
            if(i==8)continue;
            ans.push_back({i,n});
        }
        int t=n;
        while(t>1){
            ans.push_back({n,8});
            t=(t+7)/8;
        }
        for(int i=0;i<3;++i)ans.push_back({8,2});
    }
    cout<<ans.size()<<'\n';
    for(auto v:ans){
        cout<<v.first<<' '<<v.second<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

C - No More Inversions

思路：对于一个这样的回文串1 2 ...k... 2 1，任选两个不同的数x和y（x<y），有两种出现的情况x y y x 和 x y x，逆序数分别为1和2，并且仅当y为k时逆序数为1，那么总的逆序数为2C（k-1，2）+（k-1）=（k-1）2；

可以发现a和b的第k-（n-k）到第n个数形成了回文串，且一半的数都不同，则存在的逆序数是一样的；影响b的逆序数的只有第1到第k-（n-k）-1个数，而a中的这些数对逆序数没有贡献，则p中的前k-（n-k）-1个数与a一样；由于要字典序最大，将b中的第k-（n-k）到第n个数的前半段和后半段翻转即可

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1e4+5;
void solve(){
    int n,k;cin>>n>>k;
    for(int i=1;i<2*k-n;++i)cout<<i<<' ';
    for(int i=k;i>=2*k-n;--i)cout<<i<<' ';cout<<'\n';
}
signed main(){
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

D - Program

思路：若删去一段[l，r]，对于原来段中r后表示的数需要减去[l，r]的贡献，且求一段操作中存在的数的种数，相当于这一段数的max-min+1个，那么维护前后缀最大、最小值，以及前缀和即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n,m;cin>>n>>m;
    string s;cin>>s;
    s.insert(s.begin(),' ');
    vector<int>sum(n+5),lma(n+5),lmi(n+5),rma(n+5),rmi(n+5);

    for(int i=1;i<=n;++i){
        if(s[i]=='-')sum[i]=sum[i-1]-1;
        else sum[i]=sum[i-1]+1;
        lmi[i]=min(lmi[i-1],sum[i]);
        lma[i]=max(lma[i-1],sum[i]);
    }
    rmi[n]=rma[n]=sum[n];
    for(int i=n-1;i>=1;--i){
        rmi[i]=min(rmi[i+1],sum[i]);
        rma[i]=max(rma[i+1],sum[i]);
    }
    int l,r;
    while(m--){
        cin>>l>>r;
        int c=sum[r]-sum[l-1];
        int mi=0,ma=0;
        if(l!=1)mi=min(lmi[l-1],mi),ma=max(ma,lma[l-1]);
        if(r!=n)mi=min(rmi[r+1]-c,mi),ma=max(ma,rma[r+1]-c);
        cout<<ma-mi+1<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

标签：typedef,int,9.12,long,--,solve,div.1,define
From： https://www.cnblogs.com/bible-/p/17700524.html

相关文章

  • 2023.9.12
    今天没有学习新知识，从新看了看c语言的知识，我认为有一个好的基础对未来的学习更有帮助，我先看了看c的编辑编译连接运行，和java是有区别的，java是用的类，这些都没什么，我在学习数据类型时看了看原反补码，主要是数据存储是按照二进制存储的，然后存的是它的反码，最开头有个控制正负的1和0，浮点......
  • 9.12 每日总结
    今天满课，上午上了大型数据库应用技术，下午上了.net和软件开发案例分析；从中学到了一些知识，不过这周刚刚正式开课大家都刚刚退补选完成，第一节课的内容相对都不是那么多，但是依然很有价值；晚上抽出时间看了看springboot的相关知识，我决定花费一到两周的时间学习springboot的知识；今天的......
  • 9.12
    今天数据结构深入学了顺序和链表，发现我之前的链表一直少着一个头节点。晚上学了学新媒体用户分析，学会了几种调查方法。比如诱导性调查：你是否认为世界应该阻止日本排放核污水。先不论答案，你脑海中已经形成了日本污染全世界的印象。事实如此。我们确实应该抵制。......
  • 9.13补9.12没保存。。。
     HTML(HyperTextMarkupLanguage):超文本标记语言超文本:超越了文本的限制，比普通文本更强大。除了文字信息，还可以定义图片、音频、视频等内容标记语言:由标签构成的语言 HTML标签都是预定义好的。例如:使用<a>展示超链接，使用<img>展示图片，<video>展示视频HTML代码直接在......
  • 9.12
    今天上午学习数据结构顺序表中基本操作的实现晚上学习关于枚举类型的方法publicclassfile{privateenumMyEnum{ONE,TWO,THREE;}publicstaticvoidmain(String[]args){for(MyEnumvalue:MyEnum.values()){System.out.pr......
  • 9.12日
    一、今天上午学了数据结构的链表部分，还有马克思主义哲学的物质世界，客观世界和主观世界，有点抽象。二、然后下午对前两天的codeforces比赛进行了收官总结，这里留一个链接，我写的博客整理的赛题。有想看的可以参考一下。https://blog.csdn.net/weixin_73550568/article/details/13283......
  • 9.12
    今天读完了一章的程序员修炼之道，第一章是注重实效的哲学，暂时感觉这本书主要让程序员注意实际，考虑目光放长远，写的代码增改的时候易于操作，能够有效的参与到团队合作，但是有些不足之处会让读者感觉不适，考虑自身的问题没错但是过多的寻找自身问题会导致精神内耗，有些地方的话有点举例不......
  • 每日总结|9.12-上帝保佑我
    今天做五了件事1、英语精听，好多生词2、刷题，看到100p啦3、hadoop的hbase学习4、改错题5、阅读---------------------------------------------闲闫碎语对于读写流程还是不太明白，刷写，内存和磁盘的读取，显示。split等等。还是不太懂。 ......
  • 9.12 周二总结
    第一节课，数据结构，学会了线性表的顺序表示和实现，学到了elemtype是为了描述统一而自定的，可以是实际需要的任何类型下午英语，学了新的课文，听了一些听力，记住了一些新单词学会了双指针算法。左右指针和快慢指针。晚上做了一下数据结构老师让看的一道题给定一个整数数组 nums 和一......
  • 9.12日总结
    今日上的数据结构课，复习了链表的基础，学习了双指针，并且联系了一道题；马原课学了有关哲学的问题，认识了唯物辩证法，以及形而上学，相关的哲学问题；明天没课学习二分查找和前缀和算法。并且写开学考试的题，联系二分和前缀和的题。......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99