AtCoder Beginner Contest 247 C D E题解

https://atcoder.jp/contests/abc247/tasks/abc247_c

递归即可解决：

#include
#include
#include
#include
#include
#include<string>
#include
#include
#include<set>
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 200005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair
#define eps 1e-5
#define pll pair
#define lson 2*x
#define rson 2*x+1

long long  qupower(int a, int b) {
    long long  ans = 1;
    while (b) {
        if (b & 1)ans = ans * a;
        b >>= 1;
        a = a * a;
    }
    return ans;
}

inline int read() {
    int an = 0, x = 1; char c = getchar();
    while (c > '9' || c < '0') {
        if (c == '-') {
            x = -1; 
        }
        c = getchar();
    }
    while (c >= '0'&&c <= '9') {
        an = an * 10 + c - '0'; c = getchar();
    }
    return an * x;
}

const int N = 65540;
int a[N];

void sol(int x){
    if(x==1){printf("1 ");return;}
    sol(x-1);
    printf("%d ",x);
    sol(x-1);
}

int main(){
    //ios::sync_with_stdio(false);
    int n; n = read();
    sol(n);
}

https://atcoder.jp/contests/abc247/tasks/abc247_d

不能用queue来模拟，复杂度过不去。我们只需要记录每一段的位置（前缀和维护），以及该段的value。

#include
#include
#include
#include
#include
#include<string>
#include
#include
#include<set>
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 200005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair
#define eps 1e-5
#define pll pair
#define lson 2*x
#define rson 2*x+1

long long  qupower(int a, int b) {
    long long  ans = 1;
    while (b) {
        if (b & 1)ans = ans * a;
        b >>= 1;
        a = a * a;
    }
    return ans;
}

inline int read() {
    int an = 0, x = 1; char c = getchar();
    while (c > '9' || c < '0') {
        if (c == '-') {
            x = -1; 
        }
        c = getchar();
    }
    while (c >= '0'&&c <= '9') {
        an = an * 10 + c - '0'; c = getchar();
    }
    return an * x;
}

int Q;
//queue q;
ll ans = 0;
const int N = 2e5+5;
ll v[N],pos[N];
ll cnt=1;
ll cur_p = 1;
ll real_p = 0;


int main(){
    //ios::sync_with_stdio(false);
    Q = read();
    while(Q--){
        int q; q = read();
        if(q==1){
            ll x,c; scanf("%lld %lld", &x,&c);
            pos[cnt] = pos[cnt-1]+c;
            v[cnt] = x;
            cnt+=1;
        }
        else{
            ll c; scanf("%lld", &c);
            ll next_p = real_p+c;
            //cout<<"next pos:"<
            ans=0;
            for(;cur_p){
                if(pos[cur_p]<=next_p){
                    ans+= ll(v[cur_p]*(pos[cur_p]-real_p));
                    real_p = pos[cur_p];
                }
                else{
                    ans+= ll(v[cur_p]*(next_p-real_p));
                    real_p = next_p;
                    break;
                }

            }
            
            //cout<
            printf("%lld\n", ans);
        }
    }
}

https://atcoder.jp/contests/abc247/tasks/abc247_e

给定一个序列，以及两个数 X,Y. 问有多少子序列（连续的）满足：该序列的最小值为Y，最大值为X。

注意到的一点是：如果有一个数字不满足条件，即 a>X or a

我们使用双指针 L,R. 开始的时候移动右指针 R。当找到最小值和最大值时，即可break来统计数量。具体来说，如果区间 [ L, W ]满足条件，那么区间 [ L, i ]，W< i < R都满足条件。最后移动左指针。

#include
#include
#include
#include
#include
#include<string>
#include
#include
#include<set>
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 200005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair
#define eps 1e-5
#define pll pair
#define lson 2*x
#define rson 2*x+1

long long  qupower(int a, int b) {
    long long  ans = 1;
    while (b) {
        if (b & 1)ans = ans * a;
        b >>= 1;
        a = a * a;
    }
    return ans;
}

inline int read() {
    int an = 0, x = 1; char c = getchar();
    while (c > '9' || c < '0') {
        if (c == '-') {
            x = -1; 
        }
        c = getchar();
    }
    while (c >= '0'&&c <= '9') {
        an = an * 10 + c - '0'; c = getchar();
    }
    return an * x;
}

const int N = 2e5 + 5;
int a[N];
int X,Y;
int n;
ll res=0;

ll cal(vector<int> &vec){
    ll ans=0;
    int l = 0, r = vec.size()-1;
    int lp=l,rp=l;
    int cnt_max=0, cnt_min = 0;
    //int len = r-l+1;
    while(lp<=r){
        while(rp<=r && (cnt_max==0 || cnt_min==0)){
            if(vec[rp]==X)cnt_max+=1;
            if(vec[rp]==Y)cnt_min+=1;
            rp+=1;
        }
        if(cnt_max>0 && cnt_min>0){
            ans = ans+ll(r-rp+2);
        }
        if(vec[lp]==X)cnt_max-=1;
        if(vec[lp]==Y)cnt_min-=1;
        lp+=1;
    }
    return ans;
}

void sol(){
    int i=0;
    int st=0,ed=0;
    while(i<n){
        // split to subproblem
        vector<int> vec;
        while(i=Y){vec.push_back(a[i]);i+=1;}
        if(vec.size()>0){
            res+= cal(vec);
        }
        else i+=1;
        
    }
}


int main(){
    //ios::sync_with_stdio(false);
    n = read();
    X = read(); Y = read();
    for(int i=0;i read();
    sol();
    printf("%lld\n", res);
}

Atcode 算法

AtCoder Beginner Contest 247 C D E题解

相关

标签