北京建站,宁夏建设主管部门网站,六安论坛,wordpress简约红主题A
Yet Another Promotion
题意#xff1a;要买n千克物品#xff0c;第一天的价格为a#xff0c;第二天的价格为b。第一天有促销活动#xff0c;每买m千克物品#xff0c;可以额外获得1千克物品。问最少花费多少可以获得至少n千克的物品。
思路#xff1a;分类讨论要买n千克物品第一天的价格为a第二天的价格为b。第一天有促销活动每买m千克物品可以额外获得1千克物品。问最少花费多少可以获得至少n千克的物品。
思路分类讨论当ab时肯定全在第一天买掉。当ab时又可能第二天的价格特别低因此全在第二天买或者第一天的平均价格比较低先尽可能用第一天去买没凑齐的用第二天买
#include bits/stdc.h
#define lowbit(x) x (-x)
#define ios cin.sync_with_stdio(false)
#define PII pairint, 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 pairint,int
typedef long long ll;
const int N1e610;
const int inf0x3f3f3f3f;using namespace std;
int x,y;
void solve()
{cinxy;vectorintans;int tx;while(ty) ans.push_back(t--);while(yx) ans.push_back(y);coutans.size()\n;for(int i0;ians.size();i)coutans[i] \n[ians.size()-1];
}
signed main()
{//ios;int _t1;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 pairint,int
typedef long long ll;
const int N1e610;
const int inf0x3f3f3f3f;using namespace std;
int n;
int a[N];
void solve()
{cinn;for(int i1;in;i) cina[i];int mi1,man;int l1,rn;while(lr){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(lr) coutl r\n;else cout-1\n;
}
signed main()
{//ios;int _t1;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区间mexi时此时区间不含i
当mex1时我们找到1在a和b中出现的位置记为L和R那么左右端点可以在[1,L) 和LR和R,n]中选。若区间长度为x那么对答案的贡献就是x*(x1)/2
当mex1时我们找到mex在a和b中出现的位置记为papb接下来分情况讨论即可。①pa L R pb时左端点可以在(pa,L]中选右端点可以在[R,pb)中选。②papbLR ③LRpapb ④LpaR || LpbR
注意当mexn1时此时l1rn也是满足的。
#include bits/stdc.h
#define lowbit(x) x(-x)
#define ios cin.sync_with_stdio(false)
#define PII pairint,int
#define int long long
typedef long long ll;
const int N1e610;
const int inf0x3f3f3f3f;using namespace std;
int n;
int a[N],b[N];
int posa[N],posb[N];
void solve()
{cinn;for(int i1;in;i) cina[i],posa[a[i]]i;for(int i1;in;i) cinb[i],posb[b[i]]i;ll ans0;int Lposa[1],Rposb[1];if(LR) swap(L,R);ans(L-1)*(L)/2(n-R)*(n-R1)/2max(0ll,(R-L-1)*(R-L)/2);for(int mex2;mexn;mex){int paposa[mex],pbposb[mex];if(papb) swap(pa,pb);if((paLpaR)||(pbLpbR)) {}else if(LpapbR) //pa L R pb{ans(L-pa)*(pb-R);}else if(pbL) //pa pb L R{ans(L-pb)*(n-R1);}else if(paR) //L R pa pb{ans(L)*(pa-R);}Lmin(L,pa);Rmax(R,pb);}coutans1\n;
}
signed main()
{//ios;int _t1;// cin_t;while(_t--) solve();system(pause);return 0;
}
