題解：

1.

二分答案之后判斷

把式子移項使得x,y不關(guān)聯(lián)

#include <bits/stdc++.h> using namespace std; #define rint register int #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) const int N=3e5; int a[N],sum[N],n,m; const int INF=1e9; bool check(int x) {sum[0]=0;int mina=-INF;rep(i,1,n){if (a[i]<x) sum[i]=sum[i-1]+1; else sum[i]=sum[i-1];if (i-m+1>0) mina=max(mina,2*sum[i-m]-(i-m+1));if (2*sum[i]-i<=mina) return(1);}return(0); } int main() {freopen("1.in","r",stdin);freopen("1.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>m;rep(i,1,n) cin>>a[i];int h=0,t=INF;while (h<t){int mid=(h+t+1)>>1;if (check(mid)) h=mid; else t=mid-1;}cout<<h<<endl;return 0; }

?

2.

數(shù)位dp

考慮10個數(shù)字一共有18個

C(27,9) 算一下發(fā)現(xiàn)不大

然后就直接記憶化搜索就行了

數(shù)比較大可以用map記錄

但好像比較慢于是改了hash

然后有3個點是考細(xì)節(jié)的

后面兩個是map如果初值為0就炸了 可能之后一直為0 因為y可以是-1

另外一個是0要特殊考慮dfs(0)

#include <bits/stdc++.h> using namespace std; #define rint register int #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) #define ll long long #define mp(x,y) make_pair(x,y) ll l,n,m,f[100]; int cnt=0; const int mo=6e6+7; struct re{bool a,b;short c; ll d,ans; }hs[mo+1000]; queue<int> q; struct hash{ll find(bool a,bool b,short x,ll y){int t1=((1ll*x%mo*y%mo)%mo+mo)%mo;while (hs[t1].c&&!(hs[t1].a==a&&hs[t1].b==b&&hs[t1].c==x&&hs[t1].d==y))t1++,cnt++;if (hs[t1].c) return(hs[t1].ans);return(-1);}void insert(bool a,bool b,short x,ll y,ll ans){int t1=((1ll*x%mo*y%mo)%mo+mo)%mo;while (hs[t1].c) t1++,cnt++;hs[t1].a=a; hs[t1].b=b; hs[t1].c=x; hs[t1].d=y; hs[t1].ans=ans;q.push(t1);}void clear(){while (!q.empty()){int x=q.front(); q.pop();hs[x].c=hs[x].ans=0;}} }M; ll dfs(short x,ll y,bool z,bool kk) {cnt++;ll ans1=M.find(z,kk,x,y);if (ans1!=-1) return(ans1);if (x==l+1){if (kk==1) y=0;if (y<=m){return(1);}return(0);}ll ans=0;rep(i,0,9)if (i==0&&kk==1) ans+=dfs(x+1,1,0,1);else{if (z==1){if (i<f[x]) ans+=dfs(x+1,y*i,0,0);if (f[x]==i) ans+=dfs(x+1,y*i,1,0);} else ans+=dfs(x+1,y*i,0,0);}M.insert(z,kk,x,y,ans);return(ans); } ll js(ll x,ll y) {if (x<0) return(0);M.clear();ll tmp=x; l=0;if (x==0) l=1,f[1]=0;while (tmp) l++,f[l]=tmp%10,tmp/=10;reverse(f+1,f+l+1);m=y;return dfs(1,1,1,1); } int main() {ios::sync_with_stdio(false);ll x1,x2,y1,y2;cin>>x1>>x2>>y1>>y2;cout<<js(x2,y2)-js(x2,y1-1)-(js(x1-1,y2)-js(x1-1,y1-1))<<endl;return 0; }

?

3.

大體思路就是差分來做

剛開始傻逼的寫了直接dfs拿線段樹來維護(hù)。。

這樣顯然是有問題的。。。

并且，我的樹上二分也很傻比。。。

取了比它深度淺的二分所以既要多寫代碼又要多寫細(xì)節(jié)。。

拍完了細(xì)節(jié)才發(fā)現(xiàn)要改成線段樹合并

5min改完就a了。。

另外一種做法是主席樹+二分 二分部分和這種做法一樣

主席樹就是維護(hù)dfs序也和這個基本一樣

利用相減表示出當(dāng)前子樹

#include <bits/stdc++.h> using namespace std; #define rint register int #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) #define mid ((h+t)>>1) const int N=3e5; int head[N],l,dep[N],bz[N][20],ans[N]; vector<int> ve[N],ve3[N]; struct re{int a,b; }a[N*2]; vector<re> ve2[N]; void arr(int x,int y) {a[++l].a=head[x];a[l].b=y;head[x]=l; } void dfs(int x,int y) {bz[x][0]=y; dep[x]=dep[y]+1;for (rint u=head[x];u;u=a[u].a){rint v=a[u].b;if (v!=y) dfs(v,x);} } int lca(int x,int y) {if (dep[x]<dep[y]) swap(x,y);dep(i,19,0) if (dep[bz[x][i]]>=dep[y]) x=bz[x][i];if (x==y) return(x);dep(i,19,0) if (bz[x][i]!=bz[y][i]) x=bz[x][i],y=bz[y][i];return(bz[x][0]); } int f[N],ph[N],pt[N],num,n,m,root[N]; struct sgt{int v[N*20],ls[N*20],rs[N*20],cnt;#define updata(x) v[x]=v[ls[x]]+v[rs[x]]void change(int &x,int h,int t,int pos,int k){if (pos<=0) return;if (!x) x=++cnt;if (h==t){v[x]+=k; return;}if (pos<=mid) change(ls[x],h,mid,pos,k);else change(rs[x],mid+1,t,pos,k);updata(x);}int query(int x,int h,int t,int h1,int t1){if (h1<=h&&t<=t1) return(v[x]);int ans=0;if (h1<=mid) ans+=query(ls[x],h,mid,h1,t1);if (mid<t1) ans+=query(rs[x],mid+1,t,h1,t1);return(ans); }void find(int x,int h,int t,int h1,int t1){if (h1<=h&&t<=t1){f[++num]=x; ph[num]=h; pt[num]=t;return;}if (h1<=mid) find(ls[x],h,mid,h1,t1);if (mid<t1) find(rs[x],mid+1,t,h1,t1);}int find2(int x,int h,int t,int k){if (h==t){if (v[x]>=k) return(h);else return(h+1);} if (v[rs[x]]<k) return(find2(rs[x],mid+1,t,k));else return(find2(ls[x],h,mid,k-v[rs[x]]));}int query2(int kk,int x,int y){int k1=y-query(kk,1,n,dep[x]+1,n);num=0; find(kk,1,n,1,dep[x]);dep(i,num,1){if (v[f[i]]>=k1) k1-=v[f[i]];else return(find2(f[i],ph[i],pt[i],k1));}return(1);}int merge(int x,int y){if (!x||!y) return(x|y);v[x]+=v[y];ls[x]=merge(ls[x],ls[y]);rs[x]=merge(rs[x],rs[y]);return(x);} }S; void dfs2(int x,int y) {for (rint u=head[x];u;u=a[u].a){rint v=a[u].b;if (v!=y) dfs2(v,x),root[x]=S.merge(root[x],root[v]);}int l=(int)(ve3[x].size())-1;rep(i,0,l){S.change(root[x],1,n,dep[x],1);S.change(root[x],1,n,dep[ve3[x][i]]-1,-1);}l=(int)(ve2[x].size())-1;rep(i,0,l){int x1=ve2[x][i].a,y1=ve2[x][i].b;ans[x1]=dep[x]-S.query2(root[x],x,y1);}l=(int)(ve[x].size())-1;rep(i,0,l){S.change(root[x],1,n,dep[x]-1,1);S.change(root[x],1,n,dep[ve[x][i]],-1);} } int main() {ios::sync_with_stdio(false);cin>>n>>m;rep(i,1,n-1){int x,y;cin>>x>>y;arr(x,y); arr(y,x);}dfs(1,0);rep(i,1,19)rep(j,1,n)bz[j][i]=bz[bz[j][i-1]][i-1];rep(i,1,m){int x,y;cin>>x>>y;int k=lca(x,y);ve[k].push_back(x); ve[k].push_back(y);ve3[x].push_back(k); ve3[y].push_back(k);}int q;cin>>q;rep(i,1,q){int x,t;cin>>x>>t;ve2[x].push_back((re){i,t});}dfs2(1,0);rep(i,1,q) cout<<max(0,ans[i])<<endl;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/yinwuxiao/p/9614810.html

總結(jié)

以上是生活随笔為你收集整理的牛客网round1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。