526互联

Codeforces Round 863 (Div. 3)（4.5）

发布时间 2023-04-06 00:26:12作者: bible_w

Codeforces Round 863 (Div. 3)

A - Insert Digit

思路：插到第一个小于它的位置前

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int t,n;
string s,d;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>d>>s;
        char a=d[0];
        bool ok=false;
        for(int i=0;i<s.size();++i){
            if(s[i]<a){
                s.insert(i,d);
                ok=true;
                break;
            }
        }
        if(!ok)s+=d;
        cout<<s<<'\n';
    }
    return 0;
}
View Code

 

B - Conveyor Belts

思路：求出起始点的层数差。把两点都对应到左上角的四分之一方块中，层数为坐标x,y取最小（代码非此做法^_^）

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int t,n;
int a,b,c,d;
int p(int x){
    int s;
    if(x<=n)s=n-x+1;
    else s=x%n;
    if(s==0)s=n;
    return s;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>a>>b>>c>>d;
        n/=2;
        int dy1,dy2,dx1,dx2;
        dy1=p(b),dy2=p(d);
        dx1=p(a),dx2=p(c);
        int ans=abs(max(dx1,dy1)-max(dx2,dy2));
        cout<<ans<<'\n';
    }
    return 0;
}
View Code

 

C - Restore the Array

思路：取最边上的和每相邻两个数的最小的数

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=2e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int t,n;
int a[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        vector<int>ans;
        for(int i=0;i<n-1;++i)cin>>a[i];
        ans.push_back(a[0]);
        for(int i=1;i<n-1;++i){
            ans.push_back(min(a[i],a[i-1]));
        }
        ans.push_back(a[n-2]);
        for(auto x:ans)cout<<x<<' ';
        if(t!=0)cout<<'\n';
    }
    return 0;
}
View Code

 

D - Umka and a Long Flight

思路：倒着判断，每次涂的正方形的边为h，由于两边涂的方法对称，将点都对应到左边，去涂右边，若点在涂的正方形内，则不可能；

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=2e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int t,fi[50];
bool check(int n,int x,int y){
    if(n==0)return true;
    if(y>fi[n-1])y=fi[n+1]-y+1;
    if(y>fi[n-1])return false;
    return check(n-1,y,x);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    fi[0]=fi[1]=1;
    for(int i=2;i<=45;++i)fi[i]=fi[i-1]+fi[i-2];
    int n,x,y;
    while(t--){
        cin>>n>>x>>y;
        if(check(n,x,y))cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}
View Code

 

E - Living Sequence

思路：去除出现4的数，可将十进制转换为九进制，九进制由0,1,2,3,5,6,7,8,9表示

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=2e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int t;
ll k;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>k;
        string s="";
        while(k){
            ll x=k%9;
            s+='0'+(x<4?x:x+1);
            k/=9;
        }
        reverse(s.begin(),s.end());
        cout<<s;
        if(t)cout<<'\n';
    }
    return 0;
}
View Code