T1 最长不下降子序列

数据范围$1e18$很不妙，但模数$d$只有$150$，考虑从这里突破。

计算的式子是个二次函数，结果只与上一个值有关，而模$d$情况下值最多只有$150$个，就证明序列会出现循环。

发现每个循环节的贡献之可能是$1$或$2$（考场没考虑到贡献$2$的情况直接爆$0$），并且贡献为$2$的情况（$1$个相等，$1$个大于）最多只有循环节长度$len$个。

那么就可以把贡献为$1$的循环节拎出来不计算，树装数组计算剩余的序列，最后加和即可。

$code:$

 1 #include<bits/stdc++.h>

 2 #define int long long

 3 using namespace std;

 4 int t,n,a,b,c,d,cc[200],tmp,ans,len,pre[200],st;

 5 inline int lowbit(int x){ return x&(-x); }

 6 inline int read(){

 7     int x=0,f=1; char ch=getchar();

 8     while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

 9     while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

10     return x*f;

11 }

12 inline void write(int x){

13     char ch[20]; int len=0;

14     if(x<0) x=~x+1, putchar('-');

15     do{

16         ch[len++]=x%10+(1<<5)+(1<<4);

17         x/=10;

18     }while(x);

19     for(int i=len-1;i>=0;--i) putchar(ch[i]);

20 }

21 inline void insert(int x,int pos){

22     while(pos<=150){

23         cc[pos]=max(cc[pos],x);

24         pos+=lowbit(pos);

25     }

26 }

27 inline int query(int pos){

28     int res=0;

29     while(pos){

30         res=max(res,cc[pos]);

31         pos-=lowbit(pos);

32     }

33     return res;

34 }

35 signed main(){

36     n=read(); t=read(); a=read(); b=read(); c=read(); d=read();

37     if(n>1000000){

38     tmp=t; pre[t]=1; tmp%=d;

39         for(int i=2;i<=n;i++){

40             tmp=(tmp*tmp*a%d+tmp*b%d+c)%d;

41             if(pre[tmp]){ len=i-pre[tmp]; st=pre[tmp]-1; break; }

42             pre[tmp]=i;

43         }

44         ans=(n-st)/len-150;

45         n=st+len*150+(n-st)%len;

46     }

47     tmp=t; insert(1,tmp+1); tmp%=d;

48     for(int i=2;i<=n;i++){

49         tmp=(tmp*tmp*a%d+tmp*b%d+c)%d;

50         insert(query(tmp+1)+1,tmp+1);

51     }

52     ans+=query(150);

53     write(ans); putchar('\n');

54     return 0;

55 }

T2 完全背包问题

无思路，考场狗了个记搜。

正解分类讨论。当最小的$v$大于等于$l$时最多选$c$个，最大体积为$c*v_{max}$可以直接$DP$。

定义$f_{i,j,k}$为选到第$i$个，最多选$j$个，体积为$k$的方案是否合法。有：

$f_{k,i,j}=f_{k-1,i,j}$ $or$ $f_{k,i-1,j-v_k}$

当最小的$v$（定义为$v_0$）小于$l$时，如果存在体积为$W$的方案，那么一定存在体积为$W+v_0$的方案。直接那么只考虑体积在模$v_0$意义下的合法方案中最小的体积，询问时进行比较即可。

考虑$DP$，意义同上。有：

$f_{k,i,j}=\begin{cases}
min\left ( f_{k-1,i,j},f_{k,i-1,(j-v_k)mod(v_0)}+v_k \right ), &v_k\geq l\\min\left ( f_{k-1,i,j},f_{k,i,(j-v_k)mod(v_0)}+v_k \right ),&v_k<l
\end{cases}$

注意到$DP$状态转移是个环，就用最短路转移。建出一个点数为$v_0+1$的有向图，原点$S$向每个节点$j$连边，边权为$f_{k-1,i,j}$;每个节点$j$向节点$(j+v_k)mod(v_0)$连边，边权为$v_k$。原点与节点$j$的距离即为$f_{k,i,j}$。

注意这样跑最短路算出的$f_{k,i,j}$是正好选了$i$个体积大于等于$l$的物品的最小方案体积，最后要进行覆盖，使它符合定义。

$code:$

 1 #include<bits/stdc++.h>

 2 #define int long long

 3 using namespace std;

 4 int n,m,v[55],l,c,w,f[55][31][10005];

 5 int head[20005],to[400005],nex[400005],ew[400005],num;

 6 bitset<300005>fl[31][31];

 7 inline int read(){

 8     int x=0,f=1; char ch=getchar();

 9     while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

10     while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

11     return x*f;

12 }

13 inline void write(int x){

14     char ch[20]; int len=0;

15     if(x<0) x=~x+1, putchar('-');

16     do{

17         ch[len++]=x%10+(1<<5)+(1<<4);

18         x/=10;

19     }while(x);

20     for(int i=len-1;i>=0;--i) putchar(ch[i]);

21 }

22 void spfa(int k,int i){

23     bool vis[10005]={0};

24     queue<int>q;

25     q.push(v[1]); vis[v[1]]=1; f[k][i][v[1]]=0;

26     while(!q.empty()){

27         int x=q.front();

28         for(int j=head[x];j;j=nex[j]){

29             int vv=to[j];

30             if(f[k][i][vv]<=f[k][i][x]+ew[j]) continue;

31             f[k][i][vv]=f[k][i][x]+ew[j];

32             if(vis[vv]) continue;

33             vis[vv]=1; q.push(vv);

34         }

35         vis[x]=0; q.pop();

36     }

37 }

38 inline void add(int a,int b,int d){

39     to[++num]=b; nex[num]=head[a]; head[a]=num; ew[num]=d;

40 }

41 void s_l_e(){

42     fl[0][0][0]=1;

43     for(int i=1;i<=n;i++)  for(int j=0;j<=c;j++)

44         for(int k=1;k<c*v[n];k++)

45             if(k>=v[i]) fl[i][j][k]=fl[i-1][j][k]|fl[i][j-1][k-v[i]];

46             else fl[i][j][k]=f[i-1][j][k];

47     while(m--){

48         w=read();

49         bool flag=0;

50         if(w>c*v[n]){ puts("No"); continue; }

51         puts(fl[n][c][w]?"Yes":"No");

52     }

53 }

54 void _o_v_(){

55     for(int i=0;i<=n;i++) for(int j=0;j<=c;j++)

56         for(int k=0;k<=v[1];k++) f[i][j][k]=3e18;

57     f[0][0][0]=0;

58     for(int k=1;k<=n;k++)

59         if(v[k]>=l){

60             for(int i=0;i<=c;i++)

61                 for(int j=0;j<v[1];j++)

62                     if(!i) f[k][i][j]=f[k-1][i][j];

63                     else f[k][i][j]=min(f[k-1][i][j],f[k][i-1][(j-v[k]%v[1]+v[1])%v[1]]+v[k]);

64         }

65         else

66             for(int i=0;i<=c;i++){

67                 memset(head,0,sizeof(head)); num=0;

68                 for(int j=0;j<v[1];j++)

69                     add(j,(j+v[k])%v[1],v[k]), add(v[1],j,f[k-1][i][j]);

70                 spfa(k,i);

71             }

72     for(int i=1;i<=c;i++)

73         for(int j=0;j<v[1];j++)

74             f[n][i][j]=min(f[n][i][j],f[n][i-1][j]);

75     while(m--){

76         w=read();

77         puts(w>=f[n][c][w%v[1]]?"Yes":"No");

78     }

79 }

80 signed main(){

81 //    freopen("bag0.in","r",stdin);

82 //    freopen("out","w",stdout);

83     n=read(); m=read();

84     for(int i=1;i<=n;i++) v[i]=read();

85     sort(v+1,v+n+1);

86     l=read(); c=read();

87     if(v[1]>=l) s_l_e();

88     else        _o_v_();

89     return 0;

90 }

T3 最近公共祖先

树剖，每次染色时跳父亲，修改路径上每个点除了链上子树其他子树中所有点的最大值，遇到已修改过的点就停，避免重复修改，可以保证每个点只被修改一次。

查询时单点查询即可。

$code:$

  1 #include<bits/stdc++.h>

  2 #define ld rt<<1

  3 #define rd (rt<<1)|1

  4 using namespace std;

  5 const int NN=1e5+5;

  6 int n,m,num,to[NN<<1],nex[NN<<1],head[NN],w[NN],op;

  7 int dep[NN],siz[NN],son[NN],top[NN],fa[NN],dfn[NN],id[NN],cnt;

  8 char opt[10];

  9 bool vis[NN];

 10 inline int read(){

 11     int x=0,f=1; char ch=getchar();

 12     while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

 13     while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

 14     return x*f;

 15 }

 16 inline void write(int x){

 17     char ch[20]; int len=0;

 18     if(x<0) x=~x+1, putchar('-');

 19     do{

 20         ch[len++]=x%10+(1<<5)+(1<<4);

 21         x/=10;

 22     }while(x);

 23     for(int i=len-1;i>=0;--i) putchar(ch[i]);

 24 }

 25 inline void add(int a,int b){

 26     to[++num]=b; nex[num]=head[a]; head[a]=num;

 27     to[++num]=a; nex[num]=head[b]; head[b]=num;

 28 }

 29 void dfs1(int f,int s){

 30     fa[s]=f; dep[s]=dep[f]+1; siz[s]=1;

 31     for(int i=head[s];i;i=nex[i]){

 32         int v=to[i];

 33         if(v==f) continue;

 34         dfs1(s,v);

 35         siz[s]+=siz[v];

 36         if(siz[v]>siz[son[s]]) son[s]=v;

 37     }

 38 }

 39 void dfs2(int t,int s){

 40     top[s]=t; dfn[s]=++cnt; id[cnt]=s;

 41     if(!son[s]) return;

 42     dfs2(t,son[s]);

 43     for(int i=head[s];i;i=nex[i]){

 44         int v=to[i];

 45         if(v!=fa[s]&&v!=son[s]) dfs2(v,v);

 46     }

 47 }

 48 struct segment_tree{

 49     int l[NN<<2],r[NN<<2],mx[NN<<2],laz[NN<<2];

 50     void pushup(int rt){

 51         if(l[rt]==r[rt]) return;

 52         mx[rt]=max(mx[ld],mx[rd]);

 53     }

 54     void pushdown(int rt){

 55         if(!laz[rt]||l[rt]==r[rt]) return;

 56         mx[ld]=max(laz[rt],mx[ld]); mx[rd]=max(laz[rt],mx[rd]);

 57         laz[ld]=max(laz[ld],laz[rt]); laz[rd]=max(laz[rd],laz[rt]);

 58         laz[rt]=0;

 59     }

 60     void build(int rt,int opl,int opr){

 61         l[rt]=opl; r[rt]=opr; mx[rt]=-1;

 62         if(opl==opr) return;

 63         int mid=opl+opr>>1;

 64         build(ld,opl,mid);

 65         build(rd,mid+1,opr);

 66     }

 67     void update(int rt,int opl,int opr,int val){

 68         if(l[rt]>=opl&&r[rt]<=opr){

 69             mx[rt]=max(mx[rt],val);

 70             laz[rt]=max(laz[rt],val);

 71             return;

 72         }

 73         pushdown(rt);

 74         int mid=l[rt]+r[rt]>>1;

 75         if(opl<=mid) update(ld,opl,opr,val);

 76         if(opr>mid) update(rd,opl,opr,val);

 77         pushup(rt);

 78     }

 79     int query(int rt,int pos){

 80         if(l[rt]==r[rt]) return mx[rt];

 81         pushdown(rt);

 82         int mid=l[rt]+r[rt]>>1,ans=-1;

 83         if(pos<=mid) return query(ld,pos);

 84         else return query(rd,pos);

 85     }

 86 }s;

 87 void UPD(int x){

 88     s.update(1,dfn[x],dfn[x]+siz[x]-1,w[x]);

 89     while(fa[x]!=0&&!vis[x]){

 90         vis[x]=1;

 91         s.update(1,dfn[fa[x]],dfn[x]-1,w[fa[x]]);

 92         s.update(1,dfn[x]+siz[x],dfn[fa[x]]+siz[fa[x]]-1,w[fa[x]]);

 93         x=fa[x];

 94     }

 95 }

 96 signed main(){

 97     n=read(); m=read();

 98     for(int i=1;i<=n;i++) w[i]=read();

 99     for(int i=1;i<n;i++) add(read(),read());

100     dfs1(0,1); dfs2(1,1); s.build(1,1,n);

101     while(m--){

102         scanf("%s",opt); op=read();

103         if(opt[0]=='M') UPD(op);

104         else write(s.query(1,dfn[op])), putchar('\n');

105     }

106     return 0;

107 }

巴特西

2021.8.3考试总结[NOIP模拟29]

T1 最长不下降子序列

T2 完全背包问题

T3 最近公共祖先

最新文章

热门文章