憧憬
题目描述：
给出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 = a
n&& B = bn，就结束- 否则，如果，则给B+1
- 否则，如果则将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;
}
京公网安备 11010502036488号