首页 > 编程语言 > 详细

Acwing 枚举、模拟与排序 打卡

时间:2021-05-22 23:36:40      阅读:21      评论:0      收藏:0      [点我收藏+]

1210. 连号区间数

https://www.acwing.com/problem/content/1212/

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int a[N];
int n;
int ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        int maxv=0;
        int minv=0x3f3f3f3f;
        for(int j=i;j<=n;j++){
            maxv=max(maxv,a[j]);
            minv=min(minv,a[j]);
            if(j-i==maxv-minv){
                ans++;
            }
        }
    }
    cout<<ans<<endl;
  return 0;
}
//  freopen("testdata.in", "r", stdin);

1236. 递增三元组

https://www.acwing.com/problem/content/1238/

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int a[N],b[N],c[N];
int n;
LL res;
int fun1(int x){
    int l=0,r=n-1;//二分查找最后一个小于b[i]的下标
    while(l<r){
        int mid=(l+r+1)>>1;
        if(a[mid]<x){
            l=mid;
        }
        else r=mid-1;
    }
    if(a[l]>=x) l=-1;
    return l;
}
int fun2(int x){
    int l=0,r=n-1;//二分查找第一个大于b[i]的下标
    while(l<r){
        int mid=(l+r)>>1;
        if(c[mid]<=x){
            l=mid+1;
        }
        else r=mid;
    }
    if(c[l]<=x) l=n;
    return l;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<n;i++) cin>>c[i];
    sort(c,c+n);
    for(int i=0;i<n;i++){
        int x=fun1(b[i]);
        int y=fun2(b[i]);
        res+=(LL)(x+1)*(n-y);
    }
    cout<<res<<endl;
  return 0;
}
//  freopen("testdata.in", "r", stdin);

1245. 特别数的和

https://www.acwing.com/problem/content/1247/

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long LL;
int n;
LL ans;
int fun(string s){
    if(s.find("2")!=s.npos) return 1;
    if(s.find("0")!=s.npos) return 1;
    if(s.find("1")!=s.npos) return 1;
    if(s.find("9")!=s.npos) return 1;
    return 0;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        string s=to_string(i);
        if(fun(s)){
            ans+=i;
        }
    }
    cout<<ans<<endl;
  return 0;
}
//  freopen("testdata.in", "r", stdin);

1204. 错误票据

https://www.acwing.com/problem/content/1206/

#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
int a[N];

int main()
{
    int cnt;
    cin >> cnt;
    string line;

    getline(cin, line); // 忽略掉第一行的回车
    while (cnt -- )
    {
        getline(cin, line);
        stringstream ssin(line);

        while (ssin >> a[n]) n ++ ;
    }

    sort(a, a + n);

    int res1, res2;
    for (int i = 1; i < n; i ++ )
        if (a[i] == a[i - 1]) res2 = a[i];  // 重号
        else if (a[i] >= a[i - 1] + 2) res1 = a[i] - 1; // 断号

    cout << res1 << ‘ ‘ << res2 << endl;

    return 0;
}

1219. 移动距离

https://www.acwing.com/problem/content/1221/

#include <bits/stdc++.h>

using namespace std;

int main(){
    int w, m, n;
    cin >> w >> m >> n;
    m --, n --;//序号减1,便于利用公式求行号和列号

    int x1 = m / w, x2 = n / w;//行号
    int y1 = m % w, y2 = n % w;//求列号
    if(x1 & 1) y1 = w - 1 - y1;//特判,是否为奇数行
    if(x2 & 1) y2 = w - 1 - y2;

    //曼哈顿顿距离
    cout << abs(x1 - x2) +abs(y1 - y2) << endl;
    return 0;
}

Acwing 枚举、模拟与排序 打卡

原文:https://www.cnblogs.com/OfflineBoy/p/14799982.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!