Codeforces Round 852 (Div. 2)

A

Yet Another Promotion

题意：要买n千克物品，第一天的价格为a，第二天的价格为b。第一天有促销活动，每买m千克物品，可以额外获得1千克物品。问最少花费多少可以获得至少n千克的物品。

思路：分类讨论，当a<=b时，肯定全在第一天买掉。当a>b时，又可能第二天的价格特别低，因此全在第二天买；或者第一天的平均价格比较低，先尽可能用第一天去买，没凑齐的用第二天买

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define ios cin.sync_with_stdio(false)
#define PII pair<int, int>
typedef long long ll;
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;using namespace std;
ll a, b, n, m;
void solve()
{cin >> a >> b >> n >> m;if (a <= b)cout << a * (n - n / (m + 1)) << '\n';else{cout << min(n * b, n / (m + 1) * a * m + (n - n / (m + 1) * (m + 1)) * b) << '\n';}
}
signed main()
{// ios;int _t = 1;cin >> _t;while (_t--)solve();system("pause");return 0;
}

B

Fedya and Array

题意：环形数组，定义ai为局部最大值时满足ai大于左右两边的元素；局部最小值同理。现给你局部最大值的总和x，局部最小值的总和y，构造环形数组且要满足数组相邻元素差值等于1.

思路：构造一个v型的即可，从x减到y，再从y加到x-1

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios cin.sync_with_stdio(false)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int x,y;
void solve()
{cin>>x>>y;vector<int>ans;int t=x;while(t>y) ans.push_back(t--);while(y<x) ans.push_back(y++);cout<<ans.size()<<'\n';for(int i=0;i<ans.size();i++)cout<<ans[i]<<" \n"[i==ans.size()-1];
}
signed main()
{//ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

C

Dora and Search

题意：给定长度为n的排列，求l,r，满足 a[l] != min(a[l~r]),  a[l] != max(a[l~r]) , a[r] != min(a[l~r]), a[r] != max(a[l~r])

思路：从两端将数组剥开，当两端是极值时，就向内部移动。直到移到两端都不是极值即可。

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios cin.sync_with_stdio(false)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
int a[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int mi=1,ma=n;int l=1,r=n;while(l<r){if(a[l]==mi) mi++,l++;else if(a[l]==ma) ma--,l++;else if(a[r]==mi) mi++,r--;else if(a[r]==ma) ma--,r--;else break;}if(l<r) cout<<l<<' '<<r<<'\n';else cout<<-1<<'\n';
}
signed main()
{//ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

D

Moscow Gorillas

题意：给定两个长度为n的排列a和排列b，问有多少对l,r满足mex(a[l~r])=mex(b[l~r])

mex为数组中没出现的最小正整数。

思路：枚举mex，区间mex=i时，此时区间不含i

当mex=1时，我们找到1在a和b中出现的位置，记为L和R，那么左右端点可以在[1,L) 和（L，R）和（R,n]中选。若区间长度为x，那么对答案的贡献就是x*(x+1)/2

当mex>1时，我们找到mex在a和b中出现的位置记为pa，pb；接下来分情况讨论即可。①pa <L <R< pb时，左端点可以在(pa,L]中选，右端点可以在[R,pb)中选。②pa<pb<L<R ③L<R<pa<pb ④L<pa<R || L<pb<R

注意当mex=n+1时，此时l=1，r=n也是满足的。

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios cin.sync_with_stdio(false)
#define PII pair<int,int>
#define int long long
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
int a[N],b[N];
int posa[N],posb[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i],posa[a[i]]=i;for(int i=1;i<=n;i++) cin>>b[i],posb[b[i]]=i;ll ans=0;int L=posa[1],R=posb[1];if(L>R) swap(L,R);ans+=(L-1)*(L)/2+(n-R)*(n-R+1)/2+max(0ll,(R-L-1)*(R-L)/2);for(int mex=2;mex<=n;mex++){int pa=posa[mex],pb=posb[mex];if(pa>pb) swap(pa,pb);if((pa>=L&&pa<=R)||(pb>=L&&pb<=R)) {}else if(L>pa&&pb>R) //pa L R pb{ans+=(L-pa)*(pb-R);}else if(pb<L) //pa pb L R{ans+=(L-pb)*(n-R+1);}else if(pa>R) //L R pa pb{ans+=(L)*(pa-R);}L=min(L,pa);R=max(R,pb);}cout<<ans+1<<'\n';
}
signed main()
{//ios;int _t=1;// cin>>_t;while(_t--) solve();system("pause");return 0;
}