首页 > 其他分享 >AtCoder Beginner Contest 370 A-F题解

AtCoder Beginner Contest 370 A-F题解

时间：2024-09-08 13:03:26浏览次数：13  
标签：__ AtCoder typedef int 题解 cin long 370 define

A

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll  P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
    return rand()%r+l;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int __=1;
//    cin >> __;
    while(__--){
        int a,b;
        cin >> a >> b;
        if(a^b){
            if(a==1) cout << "Yes\n";
            else cout << "No" << '\n';
        }
        else cout << "Invalid\n";
    }
    system("color 04");
    return 0;
}

B

问从s变到t，每次可以变s中的一个字母，找到一个字典序最小的方案，首先可以从左到右枚举变哪一个，我们想要字典序最小，每次要变，\(si>ti\),如果没找到,则变\(si<ti\)。时间复杂度\(O(N^2)\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll  P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
    return rand()%r+l;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int __=1;
//    cin >> __;
    while(__--){
        string s,t;
        cin >> s >> t;
        vector<string> ans;
        while(s!=t){
            bool ok=0;
            fors(i,0,s.size()-1){
                if(s[i]>t[i]){
                    s[i]=t[i];
                    ok=1;
                    break;
                }
            }
            if(!ok){
                forr(i,0,s.size()-1){
                    if(s[i]<t[i]){
                        s[i]=t[i];
                        break;
                    }
                }
            }
            ans.push_back(s);
        }
        cout << ans.size() << '\n';
        if(ans.size()) fors(i,0,ans.size()-1) cout << ans[i] << '\n';
    }
    system("color 04");
    return 0;
}

C

模拟

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll  P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
    return rand()%r+l;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int __=1;
//    cin >> __;
    while(__--){
        int n;
        cin >> n;
        vector<vector<int>> a(n+1,vector<int>(n+1));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                cin >> a[i][j];
                a[j][i]=a[i][j];
            }
        }
        int ans=1;
        for(int i=1;i<=n;i++) ans=a[ans][i];
        cout << ans << '\n';
    }
    system("color 04");
    return 0;
}

D

二分查找,如果(x,y)这个格子存在直接删除，否则需要找到第x行大于y的第一个元素，小于y的第一个元素，第y列大于x的第一个元素，小于x的第一个元素，可以用set实现,时间复杂度\(O(Q*log)\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=1e9+7,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll  P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
    return rand()%r+l;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int __=1;
//    cin >> __;
    while(__--){
        int n,m,q;
        cin >> n >> m >> q;
        vector<set<int>> a(n+1),b(m+1);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                a[i].insert(j);
                b[j].insert(i);
            }
        }
        int ans=n*m;
        while(q--){
            int x,y;
            cin >> x >> y;
            if(a[x].count(y)){
                ans--;
                a[x].erase(y);
                b[y].erase(x);
            }
            else{
                auto it=a[x].lower_bound(y);
                if(it!=a[x].begin()){
                    int p=*prev(it);
                    ans--;
                    a[x].erase(p);
                    b[p].erase(x);
                }
                if(it!=a[x].end()){
                    int p=*it;
                    ans--;
                    a[x].erase(p);
                    b[p].erase(x);
                }
                it=b[y].lower_bound(x);
                if(it!=b[y].begin()){
                    int p=*prev(it);
                    ans--;
                    a[p].erase(y);
                    b[y].erase(p);
                }
                if(it!=b[y].end()){
                    int p=*it;
                    ans--;
                    a[p].erase(y);
                    b[y].erase(p);
                }
            }
        }
        cout << ans << '\n';
    }
    system("color 04");
    return 0;
}

E

dp f(i)表示以i结尾的合法的划分方案，如果不考虑k，\(f_i+=\sum_{j=1}^{i-1}f_j\,\,\,\),可以用一个变量记录前缀和。现在考虑k，需要再减去一个等于k的方案数，维护一个dpj [j+1,i]和等于k的方案数，前缀和si-sj=k,sj=si-k,sj是一个固定值，用一个map维护就可以。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=998244353,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll  P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
    return rand()%r+l;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int __=1;
//    cin >> __;
    while(__--){
        int n,k;
        cin >> n >> k;
        vector<int> a(n+1),pre(n+1),f(n+1);
        map<int,int> mp;
        fors(i,1,n) cin >> a[i],pre[i]=pre[i-1]+a[i];
        mp[0]=1;
        f[0]=1;
        int sum=1;
        fors(i,1,n){
            f[i]=(sum-mp[pre[i]-k]+mod)%mod;
            mp[pre[i]]=(mp[pre[i]]+f[i])%mod;
            sum=(sum+f[i])%mod;
        }
        cout << f[n] << '\n';
    }
    system("color 04");
    return 0;
}

F

看到最小值最大，不难想到二分，主要是check函数怎么写，如果说是链的情况很简单直接贪心分段每段的长度>=x,看是否能分成k段,现我们可以开俩倍长度的数组进行破环成链,我们可以先放几块板子，满足各段区间和大于等于x，俩个板子的位置为i和j，如果板子i移动到j位置，则j会移动到下一个板子所在的位置。就会得到一个图论问题，i->j连一条边，j到下一个板子连一条边。可以用到倍增预处理出来，g(i,j)，表示从i开始走\(2^j\)步到达的板子位置，最后我们只需要看最后一块板子是不是小于等于i+n。时间复杂度\(O（n*log*log）\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
#define int long long
typedef tuple<int,int,int> tp;
#define x first
#define y second
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
constexpr int N=200010,mod=998244353,inf=1e18;
constexpr double pi=3.1415926535897932384626,eps=1e-5;
const ll  P=rnd()%mod;
#define all(a) a.begin(),a.end()
#define get_count(x) __builtin_popcount(x)
#define fors(i,a,b) for(int i=a;i<=b;i++)
#define forr(i,a,b) for(int i=b;i>=a;i--)
#define pb(x) push_back(x)
int dx[]={0,1,0,-1,1,1,-1,-1,0};
int dy[]={1,0,-1,1,1,-1,-1,1,0};
int random(int l,int r){
    return rand()%r+l;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int __=1;
//    cin >> __;
    while(__--){
        int k,n;
        cin >> n >> k;
        vector<int> a(2*n+1),pre(2*n+1);
        fors(i,1,n) cin >> a[i],a[i+n]=a[i];
        fors(i,1,2*n) pre[i]=pre[i-1]+a[i];
        auto check=[&](int x)->int{
            vector<vector<int>> f(2*n+2,vector<int>(20,2*n+1));
            for(int i=1,j=1;i<=2*n;i++){
                while(j<=2*n&&pre[j]-pre[i-1]<x) j++;
                if(j<=2*n) f[i][0]=j+1;
                else f[i][0]=j;
            }
            fors(j,1,19){
                fors(i,1,2*n){
                    f[i][j]=f[f[i][j-1]][j-1];
                }
            }
            int cnt=0;
            fors(i,1,n){
                int cur=i;
                forr(j,0,19){
                    if(k>>j&1){
                        cur=f[cur][j];
                        if(cur>i+n) break;
                    }
                }
                if(cur<=i+n) cnt++;
            }
            return cnt;
        };
        int l=1,r=1e10;
        while(l<r){
            int mid=l+r+1>>1;
            if(check(mid)) l=mid;
            else r=mid-1;
        }
        cout << l << ' ' << n-check(l) << '\n';
    }
    system("color 04");
    return 0;
}

标签：__,AtCoder,typedef,int,题解,cin,long,370,define
From： https://www.cnblogs.com/stability/p/18402774

相关文章

  • 配置PHP的Session存储到Mysql / Redis / memcache 以及使用opcache以及apc缓存清除工
    一、配置PHP的Session存储到Mysql,Redis以及memcache等        PHP的会话默认是以文件的形式存在的，可以通过简单的配置到将Session存储到NoSQL中，即提高了访问速度，又能很好地实现会话共享！1.默认配置:session.save_handler=filessession.save_path=/tmp/2.配......
  • 【洛谷 P1996】约瑟夫问题 题解（队列+模拟+循环）
    约瑟夫问题题目描述个人围成一圈，从第一个人开始报数,数到的人出列，再由下一个人重新从开始报数，数到的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰名小朋友，而该题是全部出圈。输入......
  • 【题解】CF1955E
    CF1955E翻译思路代码翻译原题链接CF1955E思路  由于每次操作区间长度是定值，所以我们可以说，如果最前面的数已经是1了，那它再也不会被进入操作。因为如果把它变回0，那想再变成1只能以它为起点再操作一次，前后两次操作抵消。  所以思路很简单，直接......
  • Leetcode 第 409 场周赛题解
    Leetcode第409场周赛题解Leetcode第409场周赛题解题目1：3242.设计相邻元素求和服务思路代码复杂度分析题目2：3243.新增道路查询后的最短距离I思路代码复杂度分析题目3：3244.新增道路查询后的最短距离II思路代码复杂度分析题目4：3245.交替组III思路代码复杂度......
  • 题解：AT_abc370_c [ABC370C] Word Ladder
    说句闲话并不会有更好的阅读体验。这题是一个比较奇葩的贪心、构造。也可以认为是一个数据结构略有难度的练习题。理论部分?>注：使用\(N\)表示字符串长度。一句段话题意：三个字符串\(S\)、\(T\)、\(X\)，其中\(S\)和\(T\)仅包含小写字母且等长，\(X\)为空。每一个操作可以......
  • CF2002D2 DFS Checker (Hard Version) 题解
    https://codeforces.com/problemset/problem/2002/D2考虑找一个容易维护的必要条件，再证明充分性。最容易想到的是每个子树对应一个区间，子树根位于左端点sol1相邻的结点\(p_{i-1},p_i\)有两种情况：\(fa[p_i]=p_{i-1}\)；叶子\(p_{i-1}\)在子树\(fa[p_i]\)中，回溯到\(fa[......
  • AtCoder Beginner Contest 370 补题记录（A~F）
    Asignedmain(){intl,r;cin>>l>>r;if(!(l==1&&r==1||l!=1&&r!=1)){if(l==1)cout<<"Yes\n";elsecout<<"No\n";}elsecout<<"Invalid\n";}Bsig......
  • AtCoder Beginner Contest 370
    A-RaiseBothHands(abc370A)题目大意给出Snuke举的左右手情况，如果只举左手，输出Yes，如果只举右手，输出No，否则输出Invalid。解题思路逐一判断即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with......
  • abc370 A-E题解 (AtCoder Beginner Contest 370)
     A这类简单题，看清楚：OutputPrint Yes, No,or Invalid accordingtotheinstructionsintheproblemstatement. B Cstd，这样写（0->n-1，n-1->0），可以少写一个vector1#include<bits/stdc++.h>2usingnamespacestd;34intmain(){5strings,......
  • 题解：Toyota Programming Contest 2024#9（AtCoder Beginner Contest 370）
    总体情况这次手速够快：ABCin10min，ABCDEin30min。A-RaiseBothHands思路分类讨论很简单的。注意一定要判断\(0,0\)这种情况。Code//Problem:A-RaiseBothHands//Contest:AtCoder-ToyotaProgrammingContest2024#9（AtCoderBeginnerContest370）//URL:......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99