t3：
题意
给你一棵树，然后每次两种操作：1.给一个节点染色 ； 2. 查询一个节点与任意已染色节点 lca 的权值的最大值
分析
考虑一个节点被染色后的影响：令它的所有祖先节点（包括自身）的所有除去更新节点上来的整棵子树的所有节点更新。
那么考虑dfs序会使某节点的子树节点连成一片，所以不更新某棵子树就可以轻易做到
然后考虑用线段树维护，复杂度就是 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();11for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;12for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;13 } inline int cread(){ char c=getchar();14while(!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'){18if(C>1<<20) Ot();if(x<0)sr[++C]='-',x=-x;19for(;z[++Z]=x%10+48,x/=10;);20for(;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){25e[++pat]=(Edge){v,head[u]},head[u]=pat;26e[++pat]=(Edge){u,head[v]},head[v]=pat;27 }28 #define v e[i].to29 void dfs(int u){ dfn[u]=++cnt,siz[u]=1;30for(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 v34 struct segT{ int mx[M<<2];35#define ls k<<136#define rs k<<1|137#define mid (l+r>>1)38#define lson ls,l,mid39#define rson rs,mid+1,r40inline void clear(){memset(mx,-1,sizeof(mx));}41void 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}46int 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}50inline 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}53inline int query(int x){ return query(1,1,n,dfn[x]); }54 }t;55 bool B[M];56 inline void modify(int x){57for(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(){63freopen("lca.in","r",stdin);64freopen("lca.out","w",stdout);65n=read(),m=read();66for(int i=1;i<=n;++i) v[i]=read();67for(int i=1,a,b;i<n;++i)68 a=read(),b=read(),add(a,b);69dfs(1),t.clear();70for(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 均给出，求这个序列的最长不下降子序列
分析
一眼看出这玩意儿有循环节。
但是这个序列前面的一部分与最后的一部分要特殊考虑，后面一部分倒还好说，前面一部分根本就与循环节是无关的。
所以我们考虑前后两部分特殊处理，然后中间的部分利用循环节做掉。
做法有两种：
一个是列出转移式然后矩阵加速解，复杂度 $D^3 \log n$一个是考虑贪心构造，观察出每个数字必然至少出现一次的特点（当然是 n 足够大的时候），将中间的每个循环中的数字能利用就利用上，然后对于 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(){13for(int i=2;i<=n;++i) a[i]=get(a[i-1]);14for(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}18for(int i=0;i<=D;++i) cmax(ans,MX[i]);19printf("%lld\n",ans);20 }21 struct Matrix{ ll a[N][N];22inline void mem(){ memset(a,-1,sizeof(a)); }23ll* operator [](const int x){return a[x];}24Matrix 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;32for(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(){37freopen("lis.in","r",stdin);38freopen("lis.out","w",stdout);39cin>>n>>a[1]>>A>>B>>C>>D,pos[a[1]]=1;40if(n<=1e6) return solv_pre(),0;41for(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];44for(int i=2;i<=m<<1;++i) b[i]=get(b[i-1]);45for(int i=2;i<=n-ed;++i) c[i]=get(c[i-1]);46I.mem(),G.mem(); for(int i=1;i<=m;++i) I[i][i]=0;47for(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]);49for(int i=1;i<=D;++i) cmax(lf[i],lf[i-1]);50memset(f,0,sizeof(f));51for(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]);53for(int i=D-1;i>=0;--i) cmax(rf[i],rf[i+1]);54for(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);59for(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);61return 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{ 9int t[maxd];10void clear(){ memset(t,0,sizeof(t)); }11void insert(int x,int v){12 for(int i=++x;i<maxd;i+=i&-i)13 t[i]=max(t[i],v);14}15int 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(){23scanf("%d%d%d%d%d",a+1,&A,&B,&C,&D);24bit.clear(),bit.insert(a[1],1); int ans=1;25for(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}30printf("%d\n",ans);31 }32 33 void init(){34scanf("%d%d%d%d%d",a+1,&A,&B,&C,&D);35memset(pos,-1,sizeof(pos)),pos[a[1]]=1;36for(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}41ed=n-(n-st+1)%m;42for(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;44b[1]=a[st];45for(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;47st+=m*m,ed-=m*m; assert(st<ed);48 }49 50 int lf[maxd],rf[maxd],f[maxn];51 void solve(){52memset(lf,0,sizeof(lf));53memset(f,0,sizeof(f)),bit.clear();54for(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}59for(int i=1;i<maxd;++i)60 lf[i]=max(lf[i],lf[i-1]);61memset(f,0,sizeof(f)),bit.clear();62for(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}67for(int i=maxd-2;i>=0;--i)68 rf[i]=max(rf[i],rf[i+1]);69int64 ans=0;70for(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}74printf("%lld\n",ans);75 }76 77 int main(){78freopen("lis.in","r",stdin);79freopen("lis.out","w",stdout);80scanf("%lld",&n);81if(n<=50000)82 brute_force();83else init(),solve();84return 0;85 }
t2：
题意
给你 n 件物品来放完全背包，体积小于 L 的无限放， 大于等于 L 的物品总共最多放 C 件，然后给出多组询问，你需要判断是否能用这些物品在满足条件的情况下放满 W 大小的背包
分析
回到了被跳楼机支配的恐惧...
首先令最小的物品体积为 V ，那么这个物品是可以无限放的，所以我们只需要记录要达到在模 V 下的体积会放到的最小体积，然后判断的时候看 询问值模 V 后是否大于等于这个值就好了（因为多出来的体积可以用 V 补）
设计状态 $f[i][j][k]$ 为前 i 个物品中加入了 j 次体积不小于 L 的物品，且总体积模 V 为 k 的最小总体积 （我就觉得是跳楼机了）
然后刚刚我说的显然有错啊，最小物品的体积不见得就可以无限放，那么如果最小体积物品也 ≥ L ，那么最多放 C 件，直接暴力跑就能出解了，状态也比较简单，就是考虑放不超过 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();10for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;11for(;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(){17for(int j=0;j<=c;++j) for(int k=0;k<V;++k) f[j][k]=1e18; f[0][0]=0;18for(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;26for(int j=0;j<=c;++j) for(int k=0;k<V;++k) cmin(g[k],f[j][k]);27for(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';30return Ot();31 }32 int main(){33freopen("bag.in","r",stdin);34freopen("bag.out","w",stdout);35n=read(),m=read();36for(int i=1;i<=n;++i) v[i]=read(); sort(v+1,v+1+n);37return V=v[1],V0=read(),c=read(),preset(),0;38 }
如果觉得《NOIP模拟赛10 题解》对你有帮助，请点赞、收藏，并留下你的观点哦！
