A:水题
//#pragma comment(linker, "/stack:200000000")//#pragma GCC optimize("Ofast,no-stack-protector")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")//#pragma GCC optimize("unroll-loops")#include #define fi first#define se second#define mp make_pair#define pb push_back#define pi acos(-1.0)#define ll long long#define mod 1000000007#define C 0.5772156649#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#define pil pair #define pii pair #define ull unsigned long long#define base 1000000000000000000#define fio ios::sync_with_stdio(false);cin.tie(0)using namespace std;const double g=10.0,eps=1e-12;const int N=100000+10,maxn=2000+10,inf=0x3f3f3f3f;int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); if(c==0) { if(a==b)puts("YES"); else puts("NO"); return 0; } if((b-a)%c==0) { if(a>=b&&c<=0)puts("YES"); else if(a<=b&&c>=0)puts("YES"); else puts("NO"); } else puts("NO"); return 0;}/****************************************/ B:sb公式题,把公式列出来枚举即可
//#pragma comment(linker, "/stack:200000000")//#pragma GCC optimize("Ofast,no-stack-protector")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")//#pragma GCC optimize("unroll-loops")#include #define fi first#define se second#define mp make_pair#define pb push_back#define pi acos(-1.0)#define ll long long#define mod 1000000007#define C 0.5772156649#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#define pil pair #define pii pair #define ull unsigned long long#define base 1000000000000000000#define fio ios::sync_with_stdio(false);cin.tie(0)using namespace std;const double g=10.0,eps=1e-12;const int N=100000+10,maxn=2000+10,inf=0x3f3f3f3f;int main(){ ll n,a,b,c,d; scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d); ll ans=n; ll te1=a+b,te2=a+c,te3=b+d,te4=c+d; ll te=max(te1,max(te2,max(te3,te4)))-min(te1,min(te2,min(te3,te4))); te=max(0ll,te);te=min(n,te); te=n-te; printf("%lld\n",ans*te); return 0;}/****************************************/ C:题意:给你n个数,每次能把一个数转移到隔壁,1和n是隔壁,要求最少几次能把每个数变成0
题解:前缀和维护一下,前缀和相同就代表这一段区间和为0,那么就可以少转移一次,map维护一下瞎搞就行了
//#pragma comment(linker, "/stack:200000000")//#pragma GCC optimize("Ofast,no-stack-protector")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")//#pragma GCC optimize("unroll-loops")#include #define fi first#define se second#define mp make_pair#define pb push_back#define pi acos(-1.0)#define ll long long#define mod 1000000007#define C 0.5772156649#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#define pil pair #define pii pair #define ull unsigned long long#define base 1000000000000000000#define fio ios::sync_with_stdio(false);cin.tie(0)using namespace std;const double g=10.0,eps=1e-12;const int N=100000+10,maxn=2000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;ll a[N],sum[N];map ma;int main(){ ll n; scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; ma[sum[i]]++; } ll ans=n-1; for(auto x:ma)ans=min(ans,n-x.se); printf("%lld\n",max(0ll,ans)); return 0;}/****************************************/ D:题意:给你n个数,依次插入到二叉搜索树里,看每个点的父亲节点价值是多少
题解:很明显不能模拟,退化成一条链 的时候复杂度O(N^2),所以我们需要用set来维护一下,当插入值是x时,前驱是l,后继是r,x要么是l的右儿子,要么是r的左儿子,,又因为l没有右儿子和r没有左儿子不能同时成立,所以找到另一个插入即可.set+upperbound即可
黑体字的证明:假设l没有右儿子而且r没有左儿子,而且l,r不能是另一个的祖先(这样不满足假设),那么l,r的公共祖先为a,那么a要么是前驱,要么是后继,所以假设不成立
//#pragma comment(linker, "/stack:200000000")//#pragma GCC optimize("Ofast,no-stack-protector")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")//#pragma GCC optimize("unroll-loops")#include #define fi first#define se second#define mp make_pair#define pb push_back#define pi acos(-1.0)#define ll long long#define mod 1000000007#define C 0.5772156649#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#define pil pair #define pii pair #define ull unsigned long long#define base 1000000000000000000#define fio ios::sync_with_stdio(false);cin.tie(0)using namespace std;const double g=10.0,eps=1e-12;const int N=100000+10,maxn=2000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;struct point{ int v; mutable bool l,r; bool operator <(const point &rhs)const{ return v s;int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&p[i].v); p[i].l=p[i].r=0; if(i!=1) { auto te=s.upper_bound(p[i]); if(te==s.end()) { te--; (*te).r=1; printf("%d ",(*te).v); } else { if((*te).l==0) { (*te).l=1; printf("%d ",(*te).v); } else { te--; (*te).r=1; printf("%d ",(*te).v); } } } s.insert(p[i]); } puts(""); return 0;}/****************************************/ E:题意:给你n个车站,从i到i+1~a[i]只需要一步,i到j的价值是最少需要走的步数μ(i,j),求每两个不相同的点的价值和
题解:dp[i]表示∑(i<j<=n)μ(i,j),因为对于路径i,j,对于i<j<=a[i],为1,否则dis[i]=dis[a[m]]+1,m是i+1到a[i]中a[m]最大的,那么转移方程dp[i]=dp[m]+(n-i)-(a[i]-m),m的i+1到a[i]的a[m]最大值,这个可以用线段树维护
仔细解释一下转移方程,dp[m]-(a[i]-m)就是要把m到a[i]的删掉,因为这个地方从dp[m]可以一步到达,而在dp[i]中也能一步到达,对于i到m的地方dp[i]一步能到达,对于a[i]+1到n的地方,我们可以从dp[m]+1步来到达,所以转移公式就是这么来的
//#pragma comment(linker, "/stack:200000000")//#pragma GCC optimize("Ofast,no-stack-protector")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")//#pragma GCC optimize("unroll-loops")#include #define fi first#define se second#define mp make_pair#define pb push_back#define pi acos(-1.0)#define ll long long#define mod 1000000007#define C 0.5772156649#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#define pil pair #define pii pair #define ull unsigned long long#define base 1000000000000000000#define fio ios::sync_with_stdio(false);cin.tie(0)using namespace std;const double g=10.0,eps=1e-12;const int N=100000+10,maxn=2000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;int a[N];pair maxx[N<<2];ll dp[N];void pushup(int rt){ if(maxx[rt<<1].fi>maxx[rt<<1|1].fi) maxx[rt]=maxx[rt<<1]; else maxx[rt]=maxx[rt<<1|1];}void build(int l,int r,int rt){ if(l==r) { maxx[rt].fi=a[l]; maxx[rt].se=l; return ; } int m=(l+r)>>1; build(ls);build(rs); pushup(rt);}pair query(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) return maxx[rt]; pair ans,te; ans.fi=0; int m=(l+r)>>1; if(L<=m) { te=query(L,R,ls); if(ans.fi =1;i--) { int te=query(i+1,a[i],1,n,1).se;// printf("%d\n",te); dp[i]=dp[te]+n-i-(a[i]-te); } ll ans=0; for(int i=1;i<=n;i++) {// printf("%d ",dp[i]); ans+=dp[i]; } printf("%lld\n",ans); return 0;}/****************************************/