题解 | #憧憬#

憧憬

https://ac.nowcoder.com/acm/contest/11216/A

憧憬

题目描述：

给出n个向量，以及一个目标向量，问能否通过n个向量中两个向量相加来构造出一个与目标向量平行的向量

思路：

签到题

枚举+判断

n个向量两两组合得到所有的向量，然后挨个与目标向量进行判断即可

判断向量(a, b) // (c, d)的条件是：a * d = b * c

坑点：

一个向量不可以同时使用

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 100000000
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

#define MAX 300000 + 50
int tt;
int n, m, k;
int a, b, c, d;
int xx, yy;
struct ran{
    int x, y;
}tr[MAX];

bool judge(int x, int y){
    if(x * yy == y * xx)return true;
    return false;
}

void work(){
    cin>>n;
    for(int i = 1; i <= n; ++i){
        cin>>a>>b>>c>>d;
        tr[i].x = c - a;
        tr[i].y = d - b;
    }
    cin>>a>>b>>c>>d;
    xx = c - a;
    yy = d - b;
    for(int i = 1; i <= n; ++i){
        for(int j = i + 1; j <= n; ++j){
            if(judge(tr[i].x + tr[j].x, tr[i].y + tr[j].y)){
                cout<<"YES\n";
                return;
            }
        }
    }
    cout<<"NO\n";
}

int main(){
    io;
//    cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

欢欣

题目描述：

找到第一个QAQ字符串的位置

思路：

签到题

find函数直接找就行

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 100000000
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

#define MAX 300000 + 50
int tt;
int n, m, k;
int a, b, c, d;
int xx, yy;
struct ran{
    int x, y;
}tr[MAX];

bool judge(int x, int y){
    if(x * yy == y * xx)return true;
    return false;
}

void work(){
    string s;
    cin>>s;
    cout<<s.find("QAQ") + 1<<endl;
}

int main(){
    io;
//    cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

奋发

题目描述：

给出两个非降序列a, b

两个变量A，B，初始为0

  • 如果 A = an && B = bn，就结束
  • 否则，如果∃t,at=A,bt>B\exists{t},a_t = A, b_t>B，则给B+1
  • 否则，如果∃t,bt=B,at>A，\exists{t},b_t = B,a_t>A，则将A+1
  • 否则，任选一个A或B进行+1操作、

每次操作完了以后，如果A=B，就让ans+1

问ans最大为多少

思路：

思维+模拟

我们考虑对于每一对的a和b，假设c = max(a, b), C = min(A, B)，如果C<c，此时1、2、3都是不满足的，只要操作4可以执行，那我们就可以最大化ans了，方法是先让A和B中小的那个到达大的的那个的水平，这样使得ans+1，再就每次都A+1，B+1的来进行操作，直到有个数先到达了min(a, b)，此时就会根据条件2或3使得另一个变量达到max(a, b)，这样一次下来ans += max(0, max(a, b) - min(A, B) + (A != B))

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 100000000
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

#define MAX 300000 + 50
int tt;
int n, m, k;
int a, b;
int A, B;
int ans;

void work(){
    cin>>n;--n;
    cin>>A;cin>>B;
    ans = min(A, B);
    for(int i = 1; i <= n; ++i){
        cin>>a>>b;
        ans += max(0, min(a, b) - max(A, B) + (A != B));
        A = a;B = b;
    }
    cout<<ans<<endl;
}

int main(){
    io;
//    cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

绝望

题目描述：

n个数，两种操作

  • 1 l r x, 将 l 到 r 的数都乘以 i^x^，并且输出 l 到 r 中素数的个数
  • 2 l r 输出 l 到 r 中素数的个数

思路：

势能线段树

咋一看会觉得每次操作1都乘了个数，会使得整个区间都变成合数，但其实不然，因为会有特殊的情况

  • 如果 i = 1, 那不管怎么乘，他的数值都不会变

  • 如果a[i] 是1，且 i 是素数，且 x 是1，那乘完以后就变成了素数

  • 如果x是0，则不会发生改变

  • 其他情况都是会变成合数的

总的来看，一个数最多修改两次就会变成合数

所以我们使用势能线段树

sum[] 表示区间的素数的个数

one表示这个区间有没有1

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 100000000
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

#define MAX 500000 + 50
int tt;
int n, m, k;
int op, l, r, c;
int tot;
int prime[500005];
bool vis[500005];

void init(){
    vis[1] = 1;
    for(int i = 2; i <= 500005; ++i){
        if(!vis[i])prime[++tot] = i;
        for(int j = 1; j <= tot && i * prime[j] <= 500005; ++j){
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0)break;
        }
    }
}

int tr[4 * MAX];
int sum[4 * MAX];
int one[4 * MAX];

inline void pushup(int p){
    sum[p] = sum[ls] + sum[rs];
    one[p] = one[ls] | one[rs];
}

void built(int p, int l, int r){
    if(l == r){
        one[p] = (tr[l] == 1);
        sum[p] = (!vis[tr[l]]);
        return;
    }
    int mid = (l + r) / 2;
    built(ls, l, mid);
    built(rs, mid + 1, r);
    pushup(p);
}

void update(int p, int l, int r, int s, int t, int c){
    if(sum[p] == 0 && one[p] == 0)return;//区间内全是合数
    if(l == r){
        if(l == 1)return;//如果i=1，就不用管惹
        if(c == 1 && !vis[l] && one[p]){//1变成一个素数
            sum[p] = 1;
            one[p] = 0;
            return;
        }
        sum[p] = one[p] = 0;//其他情况都变成了合数
        return;
    }
    int mid = (l + r) / 2;
    if(mid >= s)update(ls, l, mid, s, t, c);
    if(mid < t)update(rs, mid + 1, r, s, t, c);
    pushup(p);
}

int getsum(int p, int l, int r, int s, int t){
    if(s <= l && r <= t)return sum[p];
    int sum = 0;
    int mid = (l + r) / 2;
    if(mid >= s)sum += getsum(ls, l, mid, s, t);
    if(mid < t)sum += getsum(rs, mid + 1, r, s, t);
    return sum;
}

void work(){
    init();
    cin>>n>>m;
    for(int i = 1; i <= n; ++i){
        cin>>tr[i];
    }
    built(1, 1, n);
    for(int i = 1; i <= m; ++i){
        cin>>op;
        if(op == 1){
            cin>>l>>r>>c;
            if(c)update(1, 1, n, l, r, c);//c不是0的时候更新
            cout<<getsum(1, 1, n, l, r)<<endl;
        }
        else{
            cin>>l>>r;
            cout<<getsum(1, 1, n, l, r)<<endl;
        }
    }
}

int main(){
    io;
//    cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

迷惘

题目描述：

将一个十进制数转换成二进制后进行一次翻转，去掉前导0，在变成十进制数，求和

思路：

签到题，模拟就可以

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 100000000
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

#define MAX 300000 + 50
int tt;
int n, m, k;
ll ans = 0;

string int_to_string(int n){
    string s = "";
    while (n) {
        s += n % 2 + '0';
        n /= 2;
    }
    return s;
}

int string_to_int(string s){
    int ans = 0;
    for(int i = 0; i < s.size(); ++i){
        ans += (int)pow(2, i) * (s[i] - '0');
    }
    return ans;
}

void work(){
    cin>>n;
    for(int i = 1; i <= n; ++i){
        cin>>m;
        string s = int_to_string(m);
        int len = (int)s.size();
        string ss = "";
//        cout<<s<<endl;
        bool k = 0;
        for(int i = 0; i < len; ++i){
            if(s[i] == '1'){
                k = 1;
                ss += s[i];
            }
            else{
                if(k)ss += s[i];
                else continue;
            }
        }
        reverse(ss.begin(), ss.end());
        ans += string_to_int(ss);
    }
    cout<<ans<<endl;
}

int main(){
    io;
//    cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

冷静

题目描述：

q次询问，每次给出n和k，问 1 ~ n 中有多少数可以表示为大于等于 K 的质数的乘积（一个数可以乘多次）。

思路：

树状数组+离线查询

每次询问显然是问1到n中最小质因子中大于等于k的数量

这样就有一个树状数组+离线查询的方法

根据n从小到大的排序

每次查询之前都把小与等于他的数都插到树上去，再输出ans即可

坑点：

1这个点很特殊需要特殊考虑

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 100000000
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

#define MAX 3000000 + 50
int tt;
int n, q, k;
int tot;
int prime[3000005];
bool vis[3000050];
int p[MAX];

void SHAI(){
    for(int i = 2; i <= MAX; ++i){
        if(!vis[i]){
            p[i] = i;
            prime[++tot] = i;
        }
        for(int j = 1; j <= tot && prime[j] * i <= MAX; ++j){
            p[prime[j] * i] = prime[j];
            vis[prime[j] * i] = 1;
            if(i % prime[j] == 0)break;
        }
    }
}

struct ran{
    int n, k, id;
}tr[MAX];

bool cmp(ran a, ran b){
    return a.n < b.n;
}

int tree[MAX];
inline void insert(int i){
    for(;i <= MAX; i += lowbit(i))++tree[i];
}
inline int getans(int i){
    int ans = 0;
    for(;i > 0; i -= lowbit(i))ans += tree[i];
    return ans;
}

int ans[MAX];

void work(){
    SHAI();
    p[1]=1;
    cin>>q;
    for(int i = 1; i <= q; ++i){
        cin>>tr[i].n>>tr[i].k;
        tr[i].id = i;
    }
    sort(tr + 1, tr + 1 + q, cmp);
    int l = 1;
    for(int i = 1; i <= q; ++i){
        while (l < tr[i].n) {
            insert(p[++l]);//从2开始插数字
        }
        ans[tr[i].id] = tr[i].n - 1 - getans(tr[i].k - 1);//减1是减的数字1的情况
    }
    for(int i = 1; i <= q; ++i)cout<<ans[i]<<endl;
}

int main(){
    io;
//    cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

终别

题目描述：

n个怪兽，每个怪兽都有一个血量，你的每一次斩击都可以伤害连续的三个位置的怪兽，怪兽死后位置不变，你还有一次使用魔法的机会，会直接杀死任意的两个相邻怪兽，问杀死所有的怪兽需要的最少斩击数是多少

思路：

贪心+前缀和优化

如果去掉这个魔法，那就是一个贪心的过程

加上了这么的一个魔法，那我们就在这个的基础上去枚举魔法的施法地方，这样就会将怪兽分成了两部分，这就是两部分的贪心，但如果这么做就是O(n^2^)的复杂度，肯定接受不了，那我们就可以通过前缀和和后缀和来优化每次前半部分与后半部分的贪心，这样就可以惹

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 100000000
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

#define MAX 3000000 + 50
int tt;
int n, q, k;
int tot;
ll tr[MAX], ar[MAX];
ll pre[MAX];
ll suf[MAX];

void work(){
    cin>>n;
    for(int i = 1; i <= n; ++i){
        cin>>tr[i];
        ar[i] = tr[i];
    }
    for(int i = 1; i <= n; ++i){
        ll sh = max(0ll, tr[i]);
        tr[i] -= sh;tr[i + 1] -= sh;tr[i + 2] -= sh;
        pre[i] = pre[i - 1] + sh;
    }
    for(int i = n; i >= 3; --i){
        ll sh = max(0ll, ar[i]);
        ar[i] -= sh;ar[i - 1] -= sh;ar[i - 2] -= sh;
        suf[i] = sh + suf[i + 1];
    }
    ll minx = 0x3f3f3f3f3f3f3f3f;
    for(int i = 2; i <= n; ++i){
        minx = min(minx, pre[i - 2] + suf[i + 1]);
    }
    cout<<minx<<endl;
}

int main(){
//    io;
//    cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}
全部评论

相关推荐

11-23 11:33
华南理工大学 Java
点赞 评论 收藏
分享
11-19 17:35
华南师范大学 Web前端
点赞 评论 收藏
分享
11-08 13:58
门头沟学院 Java
鼠鼠我啊终于有 offer 了！！
喜大普奔
程序员小白条：竟然是蓝桥杯人才doge,还要花钱申领的offer，这么好的公司哪里去找
点赞 评论 收藏
分享
11-06 13:27
哈尔滨工业大学（威海） C++
点赞 评论 收藏
分享
11-19 12:12
北京理工大学 管理培训生
点赞 评论 收藏
分享
6 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
302519次浏览 2684人参与
# 如果不工作真的会快乐吗 #
59429次浏览 519人参与
# 百度开奖 #
163513次浏览 980人参与
# 地方国企笔面经互助 #
3859次浏览 10人参与
# 美团求职进展汇总 #
1327916次浏览 12451人参与
# 选完offer后，你后悔学本专业吗 #
20102次浏览 144人参与
# 阿里云管培生offer #
17732次浏览 296人参与
# 正在实习的你，几点下班 #
52091次浏览 391人参与
# 国央企薪资爆料 #
8568次浏览 69人参与
# 如何一边实习一边秋招 #
992375次浏览 12640人参与
# 提前批简历挂麻了怎么办 #
146535次浏览 1948人参与
# 学历or实习经历，哪个更重要 #
51222次浏览 402人参与
# 海康威视求职进展汇总 #
398983次浏览 3406人参与
# 米哈游求职进展汇总 #
176031次浏览 1458人参与
# 求职遇到的搞笑事件 #
70883次浏览 577人参与
# 投递实习岗位前的准备 #
1179589次浏览 18397人参与
# 面试体验感最好的是哪家？ #
85134次浏览 846人参与
# 实习生应该准时下班吗 #
167474次浏览 1159人参与
# 得物求职进展汇总 #
66331次浏览 682人参与
# 网申一定要掌握的小技巧 #
5339次浏览 53人参与
# 招聘要求与实际实习内容不符怎么办 #
10304次浏览 273人参与
# 0offer是寒冬太冷还是我太菜 #
898728次浏览 8014人参与
牛客网
牛客企业服务