t3：

題意

給你一棵樹，然后每次兩種操作：1.給一個節(jié)點染色 ； 2. 查詢一個節(jié)點與任意已染色節(jié)點 lca 的權(quán)值的最大值

?

?

分析

考慮一個節(jié)點被染色后的影響：令它的所有祖先節(jié)點（包括自身）的所有除去更新節(jié)點上來的整棵子樹的所有節(jié)點更新。

?

那么考慮dfs序會使某節(jié)點的子樹節(jié)點連成一片，所以不更新某棵子樹就可以輕易做到

?

然后考慮用線段樹維護，復雜度就是 n log n?

code

1 //by Judge 2 #include<bits/stdc++.h> 3 #define ll long long 4 using namespace std; 5 const int M=2e5+3; 6 #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1,*p2; 8 inline int Max(int a,int b){return a>b?a:b;} 9 inline void cmax(int& a,int b){if(a<b)a=b;} 10 inline int read(){ int x=0,f=1; char c=getchar(); 11 for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; 12 for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; 13 } inline int cread(){ char c=getchar(); 14 while(!isupper(c)) c=getchar(); return c=='M'; 15 } char sr[1<<21],z[21]; int Z,C=-1; 16 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} 17 inline void print(int x,char ch='\n'){ 18 if(C>1<<20) Ot();if(x<0)sr[++C]='-',x=-x; 19 for(;z[++Z]=x%10+48,x/=10;); 20 for(;sr[++C]=z[Z],--Z;);sr[++C]=ch; 21 } int n,m,pat,cnt,v[M]; 22 int f[M],head[M],dfn[M],siz[M]; 23 struct Edge{ int to,next; }e[M<<1]; 24 inline void add(int u,int v){ 25 e[++pat]=(Edge){v,head[u]},head[u]=pat; 26 e[++pat]=(Edge){u,head[v]},head[v]=pat; 27 } 28 #define v e[i].to 29 void dfs(int u){ dfn[u]=++cnt,siz[u]=1; 30 for(int i=head[u];i;i=e[i].next) 31 if(v^f[u]) f[v]=u,dfs(v),siz[u]+=siz[v]; 32 } 33 #undef v 34 struct segT{ int mx[M<<2]; 35 #define ls k<<1 36 #define rs k<<1|1 37 #define mid (l+r>>1) 38 #define lson ls,l,mid 39 #define rson rs,mid+1,r 40 inline void clear(){memset(mx,-1,sizeof(mx));} 41 void modify(int k,int l,int r,int L,int R,int v){ 42 if(v<mx[k]||L>r||l>R) return ; 43 if(L<=l&&r<=R) return mx[k]=v,void(); 44 modify(lson,L,R,v),modify(rson,L,R,v); 45 } 46 int query(int k,int l,int r,int x){ if(l==r) return mx[k]; 47 if(x<=mid) return Max(mx[k],query(lson,x)); 48 else return Max(mx[k],query(rson,x)); 49 } 50 inline void modify(int x,int y,int v){ if(!y) modify(1,1,n,dfn[x],dfn[x]+siz[x]-1,v); 51 else modify(1,1,n,dfn[x],dfn[y]-1,v),modify(1,1,n,dfn[y]+siz[y],dfn[x]+siz[x]-1,v); 52 } 53 inline int query(int x){ return query(1,1,n,dfn[x]); } 54 }t; 55 bool B[M]; 56 inline void modify(int x){ 57 for(int las=0;x;las=x,x=f[x]){ 58 t.modify(x,las,v[x]); 59 if(B[x]) return ; B[x]=1; 60 } 61 } 62 int main(){ 63 freopen("lca.in","r",stdin); 64 freopen("lca.out","w",stdout); 65 n=read(),m=read(); 66 for(int i=1;i<=n;++i) v[i]=read(); 67 for(int i=1,a,b;i<n;++i) 68 a=read(),b=read(),add(a,b); 69 dfs(1),t.clear(); 70 for(int op,x;m;--m){ 71 op=cread(),x=read(); 72 if(op) modify(x); 73 else print(t.query(x)); 74 } return Ot(),0; 75 }

?

t1：

題意

給你一個序列 a ，長度為 n ，首項為 t0，后面每一項 $a[i] = (A*a[i-1]*a[i-1]+B*a[i-1]+C)%D$? ， A、 B、 C、 D 均給出，求這個序列的最長不下降子序列

?

分析

一眼看出這玩意兒有循環(huán)節(jié)。

?

但是這個序列前面的一部分與最后的一部分要特殊考慮，后面一部分倒還好說，前面一部分根本就與循環(huán)節(jié)是無關(guān)的。

?

所以我們考慮前后兩部分特殊處理，然后中間的部分利用循環(huán)節(jié)做掉。

?

做法有兩種：

?

一個是列出轉(zhuǎn)移式然后矩陣加速解，復雜度? $D^3 \log n$

一個是考慮貪心構(gòu)造，觀察出每個數(shù)字必然至少出現(xiàn)一次的特點（當然是 n 足夠大的時候），將中間的每個循環(huán)中的數(shù)字能利用就利用上，然后對于 n 小一點的直接 n log n 跑一遍暴力解（n^3 也可以隨你開心啦） 復雜度 $D^2 \log D$

　　

?

code

?

$D^3 \log n$

1 //by Judge 2 #include<bits/stdc++.h> 3 #define ll long long 4 using namespace std; 5 const int M=1e6+3; 6 const int N=163; 7 int A,B,C,D,a[M],f[M]; 8 int b[M<<1],c[M],pos[M]; 9 ll n,m,st,ed,top,ans=1,MX[M]; 10 template<class T>inline void cmax(T& a,T b){if(a<b)a=b;} 11 inline int get(int x){return (A*x*x+B*x+C)%D;} 12 inline void solv_pre(){ 13 for(int i=2;i<=n;++i) a[i]=get(a[i-1]); 14 for(int i=1,k;i<=n;++i){ 15 k=upper_bound(f+1,f+1+top,a[i])-f; 16 if(k>top) ++top; f[k]=a[i],MX[a[i]]=k; 17 } 18 for(int i=0;i<=D;++i) cmax(ans,MX[i]); 19 printf("%lld\n",ans); 20 } 21 struct Matrix{ ll a[N][N]; 22 inline void mem(){ memset(a,-1,sizeof(a)); } 23 ll* operator [](const int x){return a[x];} 24 Matrix operator *(Matrix& b){ static Matrix c; 25 for(int i=1;i<=m;++i) for(int j=1;j<=m;++j) c[i][j]=-1; 26 for(int i=1;i<=m;++i) for(int k=1;k<=m;++k) 27 for(int j=1;j<=m;++j) if(a[i][k]!=-1&&b[k][j]!=-1) 28 cmax(c[i][j],a[i][k]+b[k][j]); return c; 29 } 30 }I,G; 31 Matrix qpow(Matrix x,ll p){ Matrix s=I; 32 for(ll i=p;i;i>>=1,x=x*x) 33 if(i&1) s=s*x; return s; 34 } 35 int lf[N],rf[N]; 36 int main(){ 37 freopen("lis.in","r",stdin); 38 freopen("lis.out","w",stdout); 39 cin>>n>>a[1]>>A>>B>>C>>D,pos[a[1]]=1; 40 if(n<=1e6) return solv_pre(),0; 41 for(int i=2;;pos[a[i]]=i,++i){ a[i]=get(a[i-1]); 42 if(pos[a[i]]){st=i,m=i-pos[a[i]];break;} 43 } ed=n-(n-st+1)%m,b[1]=c[1]=a[st]; 44 for(int i=2;i<=m<<1;++i) b[i]=get(b[i-1]); 45 for(int i=2;i<=n-ed;++i) c[i]=get(c[i-1]); 46 I.mem(),G.mem(); for(int i=1;i<=m;++i) I[i][i]=0; 47 for(int i=1;i<st;cmax(lf[a[i]],++f[i]),++i) 48 for(int j=1;j<i;++j) if(a[j]<=a[i]) cmax(f[i],f[j]); 49 for(int i=1;i<=D;++i) cmax(lf[i],lf[i-1]); 50 memset(f,0,sizeof(f)); 51 for(int i=n-ed;i>=1;cmax(rf[c[i]],++f[i]),--i) 52 for(int j=n-ed;j>i;--j) if(c[j]>=c[i]) cmax(f[i],f[j]); 53 for(int i=D-1;i>=0;--i) cmax(rf[i],rf[i+1]); 54 for(int i=1;i<=m;++i){ memset(f,-1,sizeof(f)),f[i]=0; 55 for(int j=i+1;j<=m<<1;++j) if(b[j]>=b[i]) 56 for(int k=i;k<j;++k) if(b[k]<=b[j]) cmax(f[j],f[k]+1); 57 for(int j=m+1;j<=m<<1;++j) G[i][j-m]=f[j]; 58 } G=qpow(G,(ed-st+1)/m-1); 59 for(int i=1;i<=m;++i) for(int j=1;j<=m;++j) 60 cmax(ans,G[i][j]+lf[b[i]]+rf[b[j]]+1); 61 return printf("%lld\n",ans),0; 62 }

?

$D^2 \log D$

本來我用的是貪心，然后掛了，就用矩陣了，這里就放 std 的代碼好了 Q.T

?

1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long int64; 4 const int maxn=50010,maxd=160; 5 int a[maxn],b[maxn],pos[maxd]; 6 int A,B,C,D,m; int64 st,ed,n; 7 8 struct Tbinary_index_tree{ 9 int t[maxd]; 10 void clear(){ memset(t,0,sizeof(t)); } 11 void insert(int x,int v){ 12 for(int i=++x;i<maxd;i+=i&-i) 13 t[i]=max(t[i],v); 14 } 15 int query(int x){ 16 int res=0; ++x; 17 for(int i=x;i;i-=i&-i) 18 res=max(res,t[i]); 19 return res; 20 } 21 }bit; 22 void brute_force(){ 23 scanf("%d%d%d%d%d",a+1,&A,&B,&C,&D); 24 bit.clear(),bit.insert(a[1],1); int ans=1; 25 for(int i=2;i<=n;++i){ 26 a[i]=(A*a[i-1]*a[i-1]+B*a[i-1]+C)%D; 27 int f=bit.query(a[i])+1; 28 bit.insert(a[i],f),ans=max(ans,f); 29 } 30 printf("%d\n",ans); 31 } 32 33 void init(){ 34 scanf("%d%d%d%d%d",a+1,&A,&B,&C,&D); 35 memset(pos,-1,sizeof(pos)),pos[a[1]]=1; 36 for(int i=2;;++i){ 37 a[i]=(A*a[i-1]*a[i-1]+B*a[i-1]+C)%D; 38 if(pos[a[i]]!=-1){ st=i,m=i-pos[a[i]]; break; } 39 pos[a[i]]=i; 40 } 41 ed=n-(n-st+1)%m; 42 for(int i=st;i<=st+m*m-1;++i) 43 a[i]=(A*a[i-1]*a[i-1]+B*a[i-1]+C)%D; 44 b[1]=a[st]; 45 for(int i=2;i<=n-ed+m*m;++i) 46 b[i]=(A*b[i-1]*b[i-1]+B*b[i-1]+C)%D; 47 st+=m*m,ed-=m*m; assert(st<ed); 48 } 49 50 int lf[maxd],rf[maxd],f[maxn]; 51 void solve(){ 52 memset(lf,0,sizeof(lf)); 53 memset(f,0,sizeof(f)),bit.clear(); 54 for(int i=1;i<st;++i){ 55 f[i]=bit.query(a[i])+1; 56 bit.insert(a[i],f[i]); 57 lf[a[i]]=max(lf[a[i]],f[i]); 58 } 59 for(int i=1;i<maxd;++i) 60 lf[i]=max(lf[i],lf[i-1]); 61 memset(f,0,sizeof(f)),bit.clear(); 62 for(int i=n-ed;i>=1;--i){ 63 f[i]=bit.query(maxd-b[i]-2)+1; 64 bit.insert(maxd-b[i]-2,f[i]); 65 rf[b[i]]=max(rf[b[i]],f[i]); 66 } 67 for(int i=maxd-2;i>=0;--i) 68 rf[i]=max(rf[i],rf[i+1]); 69 int64 ans=0; 70 for(int i=1;i<=m;++i){ 71 int v=a[st-m*m+i-1]; 72 ans=max(ans,lf[v]+(ed-st+1)/m+rf[v]); 73 } 74 printf("%lld\n",ans); 75 } 76 77 int main(){ 78 freopen("lis.in","r",stdin); 79 freopen("lis.out","w",stdout); 80 scanf("%lld",&n); 81 if(n<=50000) 82 brute_force(); 83 else init(),solve(); 84 return 0; 85 }

?

?

t2：

題意

給你 n 件物品來放完全背包，體積小于 L 的無限放， 大于等于 L 的物品總共最多放 C 件，然后給出多組詢問，你需要判斷是否能用這些物品在滿足條件的情況下放滿 W 大小的背包

?

分析

回到了被跳樓機支配的恐懼...

?

首先令最小的物品體積為 V ，那么這個物品是可以無限放的，所以我們只需要記錄要達到在模 V 下的體積會放到的最小體積，然后判斷的時候看 詢問值模 V 后是否大于等于這個值就好了（因為多出來的體積可以用 V 補）

?

設計狀態(tài) $f[i][j][k]$ 為前 i 個物品中加入了 j 次體積不小于 L 的物品，且總體積模 V 為 k 的最小總體積 （我就覺得是跳樓機了）?

?

然后剛剛我說的顯然有錯啊，最小物品的體積不見得就可以無限放，那么如果最小體積物品也 ≥ L ，那么最多放 C 件，直接暴力跑就能出解了，狀態(tài)也比較簡單，就是考慮放不超過 c 件物品能達到的體積，加上 vi 本來就小，隨便套套 bitset （不套也行）就解決了

?

code

1 //by Judge 2 #include<bits/stdc++.h> 3 #define ll long long 4 using namespace std; 5 const int MV=10011,M=53; 6 #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1,*p2; 8 inline void cmin(ll& a,ll b){if(a>b)a=b;} 9 inline ll read(){ ll x=0,f=1; char c=getchar(); 10 for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; 11 for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; 12 } char sr[1<<21],z[21]; int Z,C=-1; 13 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} 14 int n,m,v[M],V,V0,c; 15 ll f[33][MV*33],g[MV]; 16 inline void preset(){ 17 for(int j=0;j<=c;++j) for(int k=0;k<V;++k) f[j][k]=1e18; f[0][0]=0; 18 for(int i=1,t;i<=n;++i) if(v[i]>=V0){ t=v[i]%V; 19 for(int j=1;j<=c;++j) for(int k=0;k<V;++k) 20 cmin(f[j][k],f[j-1][(k+V-t)%V]+v[i]); 21 } else{ int len=V/__gcd(v[i],V); 22 for(int j=0;j<=c;++j) for(int N=V/len,d=0;d<N;++d) 23 for(int T=1;T<=2;++T) for(int k=0,las=d,now;k<=len;++k) 24 now=(las+v[i])%V,cmin(f[j][now],f[j][las]+v[i]),las=now; 25 } for(int i=0;i<V;++i) g[i]=1e18; 26 for(int j=0;j<=c;++j) for(int k=0;k<V;++k) cmin(g[k],f[j][k]); 27 for(ll x;m;--m) 28 if(x=read(),g[x%V]>x) sr[++C]='N',sr[++C]='o',sr[++C]='\n'; 29 else sr[++C]='Y',sr[++C]='e',sr[++C]='s',sr[++C]='\n'; 30 return Ot(); 31 } 32 int main(){ 33 freopen("bag.in","r",stdin); 34 freopen("bag.out","w",stdout); 35 n=read(),m=read(); 36 for(int i=1;i<=n;++i) v[i]=read(); sort(v+1,v+1+n); 37 return V=v[1],V0=read(),c=read(),preset(),0; 38 }

?

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

總結(jié)

以上是生活随笔為你收集整理的NOIP模拟赛10 题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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