总的来说这套题还是很不错的，让我对主席树有了更深的了解
A：水题，模拟即可
#include<bits/stdc++.h> #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 pii pair<int,int> using namespace std; const double g=10.0,eps=1e-12; const int N=200+10,maxn=200000+10,inf=0x3f3f3f3f; int a[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; int p1=1,p2=2; for(int i=0;i<n;i++)cin>>a[i]; for(int i=0;i<n;i++) { if(a[i]!=p1&&a[i]!=p2) { cout<<"NO"<<endl; return 0; } else { if(a[i]==p2)swap(p1,p2); if(p1==1) { if(p2==2)p2=3; else p2=2; } else if(p1==2) { if(p2==1)p2=3; else p2=1; } else if(p1==3) { if(p2==1)p2=2; else p2=1; } } } cout<<"YES"<<endl; return 0; } /******************** ********************/
B：给一个数n，找最大的n的余数是特定数，特定数是二进制前面k+1个1后面k个0的数，公式给出了，直接算出来然后从大到小遍历
这题没给公式的话可能还可以做做，不过也不难推，但是给了公式就相当水了
#include<bits/stdc++.h> #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 pii pair<int,int> using namespace std; const double g=10.0,eps=1e-12; const int N=200+10,maxn=200000+10,inf=0x3f3f3f3f; int a[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); for(int i=1;i<=10;i++) a[i]=((1<<i)-1)*(1<<(i-1)); int n; cin>>n; for(int i=10;i>=1;i--) { if(n%a[i]==0) { cout<<a[i]<<endl; return 0; } } return 0; } /******************** ********************/
C：找每个连通图里点权值最小相加即可，简单dfs
#include<bits/stdc++.h> #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 pii pair<int,int> using namespace std; const double g=10.0,eps=1e-12; const int N=100000+10,maxn=200000+10,inf=0x3f3f3f3f; vector<int>v[N]; bool vis[N]; ll c[N],cnt; void dfs(int u) { vis[u]=1; cnt=min(cnt,c[u]); for(int i=0;i<v[u].size();i++) { if(!vis[v[u][i]]) { dfs(v[u][i]); } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n>>m; for(int i=1;i<=n;i++)cin>>c[i]; for(int i=0;i<m;i++) { int a,b; cin>>a>>b; v[a].pb(b); v[b].pb(a); } ll ans=0; for(int i=1;i<=n;i++) { if(!vis[i]) { cnt=1e18; dfs(i); ans+=cnt; } } cout<<ans<<endl; return 0; } /******************** ********************/
D：题意：刚开始账户里余额为0，余额不能超过k，每天早上你可以存钱，晚上有交易，可能增减，如果晚上交易为0，那么就需要查询账户，此时的账户余额不能为负数，问最少需要几天存钱，不行输出-1
题解：先求一遍前缀和，然后对前缀和求一遍后缀最大值，然后从前往后扫，每次查询到余额为负的时候就根据后缀最大值来判断，然后加上最大能加的钱数，不能就输出-1
#include<bits/stdc++.h> #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 pii pair<int,int> using namespace std; const double g=10.0,eps=1e-12; const int N=100000+10,maxn=200000+10,inf=0x3f3f3f3f; ll a[N],sum[N],maxx[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n;ll d; cin>>n>>d; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++) { sum[i]=sum[i-1]+a[i]; if(sum[i]>d) { cout<<-1<<endl; return 0; } } maxx[n+1]=-1e18; for(int i=n;i>=1;i--)maxx[i]=max(maxx[i+1],sum[i]); ll cnt=0,ans=0; for(int i=1;i<=n;i++) { if(a[i]==0&&sum[i]+cnt<0) { ll x=max(d-maxx[i]-cnt,(ll)0); // cout<<i<<"++++"<<x<<" "<<cnt<<" "<<maxx[i]<<" "<<d-maxx[i]-cnt<<endl; cnt+=x; /* if(sum[i]+cnt>d) { cout<<-1<<endl; return 0; }*/ ans++; if(a[i]==0&&sum[i]+cnt<0) { // cout<<i<<" "<<sum[i]+cnt<<endl; cout<<-1<<endl; return 0; } } else if(sum[i]+cnt>d) { cout<<-1<<endl; return 0; } } cout<<ans<<endl; return 0; } /******************** 3 4 -5 3 0 3 5 -5 -5 0 ********************/
E：题意：给你x，y要求y个数相乘等于x的情况数
题解：组合数，求出x的所有质因数的个数a，然后每次乘上C(y-1+a,y-1)，,因为是隔板法，相当于y个盒子中放a个小球，有y-1个隔板，y-1+a个地方放y-1个隔板，所有情况就是C(y-1+a,y-1)，没有放的地方就放上1，最后考虑有负数的情况，因为C(n,2)+C(n,4)+...=2^(n-1)乘上这个就好了
#include<bits/stdc++.h> #define fi first #define se second #define ll long long #define mp make_pair #define pb push_back #define mod 1000000007 #define pii pair<int,int> #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 using namespace std; const int g=10.0,eps=1e-9; const int N=2000000+10,maxn=5000000+10,inf=0x3f3f3f3f; ll fac[N]; ll quick(ll a,ll b) { ll ans=1; while(b) { if(b&1)ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } int main() { /*ios::sync_with_stdio(false); cin.tie(0);*/ fac[0]=1; for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod; int q; scanf("%d",&q); while(q--) { ll x,y,ans=1; scanf("%lld%lld",&x,&y); for(ll i=2;i*i<=x;i++) { if(x%i==0) { ll cnt=0; while(x%i==0)cnt++,x/=i; // cout<<cnt<<endl; ll inv=quick(fac[y-1]*fac[cnt]%mod,mod-2); ans=ans*fac[y-1+cnt]%mod*inv%mod; } } if(x!=1) { ll cnt=1; ans=ans*y%mod; } printf("%lld\n",ans*quick(2,y-1)%mod); } return 0; } /******************* C(y-1+x,y-1)*2^(y-1)%mod; (y-1+x)! (y-1)!(x)! *******************/
F：给你一棵树，每个节点有一个权值，q个查询每次查询x的子树中与x距离不超过k的权值最小的那个节点，强制在线
题解：主席树维护，先dfs序建树，然后按照树节点深度从小到大来插入每个点，最后查询的时候找1到d【x】+k的那颗主席树，然后查询l【x】到r【x】的最小值就是答案了
总结：主席树一般就是用来维护从1到x(x<=n)的所有区间的，可以方便的维护某一区间的权值，本质来说还是一颗线段树，主要是通过rt来访问是哪颗主席树
#include<bits/stdc++.h> #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 pii pair<int,int> using namespace std; const double g=10.0,eps=1e-12; const int N=100000+10,maxn=200000+10,inf=0x3f3f3f3f; int a[N],d[N],l[N],r[N],num; int maxd,pos[N],res; int rt[N*20],ls[N*20],rs[N*20],value[N*20],tot; vector<int>v[N]; void dfs(int u,int c,int f) { ++num; l[u]=num; d[u]=c; maxd=max(maxd,c); for(int i=0;i<v[u].size();i++) { int x=v[u][i]; if(x==f)continue; dfs(x,c+1,u); } r[u]=num; } void build(int &o,int l,int r) { o=++tot; value[o]=1e9+10; if(l==r)return ; int m=(l+r)>>1; build(ls[o],l,m); build(rs[o],m+1,r); } void update(int &o,int l,int r,int last,int p,int va) { o=++tot; ls[o]=ls[last]; rs[o]=rs[last]; if(l==r) { value[o]=va; return ; } int m=(l+r)>>1; if(p<=m)update(ls[o],l,m,ls[last],p,va); else update(rs[o],m+1,r,rs[last],p,va); value[o]=min(value[ls[o]],value[rs[o]]); } int query(int o,int l,int r,int L,int R) { if(L<=l&&r<=R)return value[o]; int ans=1e9+10; int m=(l+r)>>1; if(L<=m)ans=min(ans,query(ls[o],l,m,L,R)); if(R>m) ans=min(ans,query(rs[o],m+1,r,L,R)); return ans; } void bfs(int n,int root) { queue<int>q; q.push(root); res=1; while(!q.empty()) { int u=q.front(); q.pop(); // cout<<u<<endl; pos[d[u]]=res;//对应深度在哪颗主席树中 update(rt[res],1,n,rt[res-1],l[u],a[u]); res++; for(int i=0;i<v[u].size();i++) { int x=v[u][i]; if(d[x]==d[u]+1)q.push(x); } } } void print(int o,int l,int r) { cout<<l<<" "<<r<<" "<<value[o]<<endl; if(l==r)return ; int m=(l+r)>>1; print(ls[o],l,m); print(rs[o],m+1,r); } int main() { /*ios::sync_with_stdio(false); cin.tie(0);*/ int n,root; scanf("%d%d",&n,&root); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); v[a].pb(b); v[b].pb(a); } num=tot=0; dfs(root,1,-1); /* for(int i=1;i<=n;i++) cout<<l[i]<<" "<<r[i]<<" "<<d[i]<<endl;*/ build(rt[0],1,n); // print(rt[0],1,n); bfs(n,root); /* for(int i=1;i<=n;i++) printf("%d\n",pos[i]);*/ int q,last=0; scanf("%d",&q); while(q--) { int x,k; scanf("%d%d",&x,&k); x=((x+last)%n)+1,k=(k+last)%n; k=k+d[x];k=min(k,maxd); last=query(rt[pos[k]],1,n,l[x],r[x]); printf("%d\n",last); } return 0; } /******************** 5 2 1 3 2 3 5 2 3 5 1 3 4 4 1 2 1 2 2 3 ********************/