noip模拟测试40

朴灿烈づ我的快乐病毒、 2023-08-17 15:43 120阅读 0赞

--------------------

**T1：队长快跑**

考虑dp，发现一维无法解决，于是二维做

$f\[i\]\[j\]$表示考虑前i个水晶，选择其中一些，且满足$min\_A=j$时最多能选的个数

然后将第一维去掉，对第二维用线段树维护，维护时讨论$A\_i$与$B\_i$的大小关系即可

复杂度为$O(nlogn)$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
      2 #include<iostream>
      3 #include<cmath>
      4 #include<cstdlib>
      5 #include<cstring>
      6 #include<algorithm>
      7 using namespace std;
      8 const int MAXN=500233,INF=0x3f3f3f3f;
      9 int n,A[MAXN],B[MAXN],book[MAXN*2],tot;
     10 struct node {
     11     int val,tag,l,r;
     12     node() {
     13         val=tag=l=r=0;
     14     }
     15 }tr[MAXN*4];
     16 void build(int p,int l,int r) {
     17     tr[p].l=l,tr[p].r=r;
     18     if(l==r) return;
     19     int mid=(l+r)>>1;
     20     build(p<<1,l,mid),build(p<<1|1,mid+1,r);
     21 }
     22 void up(int p) {
     23     tr[p].val=max(tr[p<<1].val,tr[p<<1|1].val);
     24 }
     25 void add(int p,int l,int r,int k) {
     26     if(tr[p].l==l&tr[p].r==r) {
     27         tr[p].val+=k,tr[p].tag+=k;
     28         return ;
     29     }
     30     int mid=(tr[p].l+tr[p].r)>>1;
     31     if(tr[p].tag) {
     32         add(p<<1,tr[p].l,mid,tr[p].tag);
     33         add(p<<1|1,mid+1,tr[p].r,tr[p].tag);
     34         tr[p].tag=0;
     35     }
     36     if(r<=mid) add(p<<1,l,r,k);
     37     else if(l>mid) add(p<<1|1,l,r,k);
     38     else add(p<<1,l,mid,k),add(p<<1|1,mid+1,r,k);
     39     up(p);
     40 }
     41 int query(int p,int l,int r) {
     42     if(l==tr[p].l&&r==tr[p].r) return tr[p].val;
     43     int mid=(tr[p].l+tr[p].r)>>1;
     44     if(tr[p].tag) {
     45         add(p<<1,tr[p].l,mid,tr[p].tag);
     46         add(p<<1|1,mid+1,tr[p].r,tr[p].tag);
     47         tr[p].tag=0;
     48     }
     49     if(r<=mid) return query(p<<1,l,r);
     50     else if(l>mid) return query(p<<1|1,l,r);
     51     else return max(query(p<<1,l,mid),query(p<<1|1,mid+1,r));
     52 }
     53 void modify(int p,int x,int k) {
     54     if(tr[p].l==tr[p].r) {
     55         tr[p].val=max(tr[p].val,k);
     56         return;
     57     }
     58     int mid=(tr[p].l+tr[p].r)>>1;
     59     if(tr[p].tag) {
     60         add(p<<1,tr[p].l,mid,tr[p].tag);
     61         add(p<<1|1,mid+1,tr[p].r,tr[p].tag);
     62         tr[p].tag=0;
     63     }
     64     if(x<=mid) modify(p<<1,x,k);
     65     else modify(p<<1|1,x,k);
     66     up(p);
     67 }
     68 inline int R() {
     69     int a=0;char c=getchar();
     70     while(c>'9'||c<'0')c=getchar();
     71     while(c>='0'&&c<='9')a=a*10+c-'0',c=getchar();
     72     return a;
     73 }
     74 int main() {
     75     n=R();
     76     for(int i=1;i<=n;i++) {
     77         A[i]=R(),B[i]=R();
     78         book[++tot]=A[i],book[++tot]=B[i];
     79     }
     80     sort(book+1,book+tot+1);
     81     tot=unique(book+1,book+tot+1)-book-1;
     82     for(int i=1;i<=n;i++) {
     83         A[i]=lower_bound(book+1,book+tot+1,A[i])-book;
     84         B[i]=lower_bound(book+1,book+tot+1,B[i])-book;
     85     }
     86     ++tot;
     87     build(1,1,tot);
     88     for(int i=1;i<=n;i++) {
     89         if(A[i]>B[i]) {
     90             int tmp=query(1,A[i],tot);
     91             add(1,B[i]+1,A[i],1);
     92             modify(1,A[i],tmp+1);
     93         } else {
     94             int tmp=query(1,B[i]+1,tot);
     95             modify(1,A[i],tmp+1);
     96         }
     97     }
     98     printf("%d\n",tr[1].val);
     99     return 0;
    100 }

t1 Code

--------------------

**T2：影魔**

只会离线……

对于每个节点维护一颗线段树，下标为颜色，权值为该颜色的最浅深度（子树内）

再对全局开一颗树状数组，下标为深度，权值为种类数

离线处理询问，最后遍历一边原树

当进入某节点时，查询该节点所有询问，即子树外对答案的影响

当即将离开某节点时，再次查询，将本次查询值减去上次查询值即为$answer$

对于线段树，只需要一层层向上合并即可

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<cmath>
     5 #include<cstdlib>
     6 #include<algorithm>
     7 #include<vector>
     8 using namespace std;
     9 const int MAXN=100233,MAXP=3000233;
    10 int n,m,root[MAXN],clr[MAXN],ans[MAXN];
    11 int ls[MAXP],rs[MAXP],dmi[MAXP],tot;
    12 vector<int> ver[MAXN];
    13 vector<pair<int,int> > que[MAXN];
    14 int dep[MAXN],fa[MAXN];
    15 
    16 int tr[MAXN];
    17 void add(int x,int k) {
    18     for(;x<=n;x+=x&-x) tr[x]+=k;
    19 }
    20 int ask(int x) {
    21     int ret=0;
    22     for(;x;x-=x&-x) ret+=tr[x];
    23     return ret;
    24 }
    25 
    26 void change(int &p,int l,int r,int x,int c) {
    27     if(!p) p=++tot;
    28     if(l==r) {
    29         if(dmi[p]) {
    30             if(dmi[p]>c) add(dmi[p],-1),add(c,1),dmi[p]=c;
    31         } else dmi[p]=c,add(c,1);
    32         return;
    33     }
    34     int mid=(l+r)>>1;
    35     if(x<=mid) change(ls[p],l,mid,x,c);
    36     else change(rs[p],mid+1,r,x,c);
    37 }
    38 void dfs(int u) {
    39     for(int i=0;i<(int)ver[u].size();i++) {
    40         int v=ver[u][i];
    41         dep[v]=dep[u]+1;
    42         dfs(v);
    43     }
    44 }
    45 void merge(int &p1,int p2) {
    46     if(!p1||!p2) return (void)(p1=p1+p2);
    47     if(dmi[p1]||dmi[p2]) {
    48         if(!dmi[p1]||!dmi[p2]) dmi[p1]+=dmi[p2];
    49         else add(max(dmi[p1],dmi[p2]),-1),dmi[p1]=min(dmi[p1],dmi[p2]);
    50         return;
    51     }
    52     merge(ls[p1],ls[p2]);
    53     merge(rs[p1],rs[p2]);
    54 }
    55 void get_ans(int u) {
    56     for(int i=0;i<(int)que[u].size();i++)
    57         ans[que[u][i].second]=-ask(que[u][i].first);
    58     for(int i=0;i<(int)ver[u].size();i++) {
    59         int v=ver[u][i];
    60         get_ans(v);
    61         merge(root[u],root[v]);
    62     }
    63     change(root[u],1,n,clr[u],dep[u]);
    64     for(int i=0;i<(int)que[u].size();i++)
    65         ans[que[u][i].second]+=ask(que[u][i].first);
    66 }
    67 int main() {
    68     scanf("%d%d",&n,&m);
    69     for(int i=1;i<=n;i++) scanf("%d",&clr[i]);
    70     for(int i=2;i<=n;i++) scanf("%d",&fa[i]),ver[fa[i]].push_back(i);
    71     dep[1]=1,dfs(1);
    72     for(int i=1,tu,td;i<=m;i++) {
    73         scanf("%d%d",&tu,&td);
    74         que[tu].push_back(make_pair(min(td+dep[tu],n),i));
    75     }
    76     get_ans(1);
    77     for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    78     return 0;
    79 }

t2 Code

--------------------

**T3：抛硬币**

简单dp，刚开始想复杂了（后缀数组？？？）

设计状态$f\[i\]\[j\]$表示用前i个字符，拼出长度为j的不同子序列的个数

考虑如何转移，$f\[i\]\[j\]=f\[i-1\]\[j-1\]+f\[i-1\]\[j\]-g\[string\[i\]\]\[j\]$

$g\[string\[i\]\]\[j\]=f\[i-1\]\[j-1\]$

（其中$g\[i\]\[j\]$表示以字符i结尾，长度为j的子序列个数）

即：将长度为$j-1$的串后再拼上$string\[i\]$，或直接取出长度为j的串而不使用$string\[i\]$

最后减去本质相同的串的个数

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 #include<cmath>
     4 #include<cstring>
     5 #include<algorithm>
     6 #define ll long long
     7 using namespace std;
     8 const int MAXN=3005;
     9 const ll D=998244353;
    10 int n,L;
    11 ll f[MAXN][MAXN],g[26][MAXN];
    12 char s[MAXN];
    13 int main() {
    14     scanf("%s%d",s+1,&L);
    15     n=strlen(s+1);
    16     for(int i=0;i<=n;i++) f[i][0]=1;
    17     for(int i=1;i<=n;i++) {
    18         for(int j=1;j<=L;j++) {
    19             f[i][j]=(f[i-1][j-1]+f[i-1][j]-g[s[i]-'a'][j])%D;
    20             g[s[i]-'a'][j]=f[i-1][j-1];
    21         }
    22     }
    23     printf("%lld\n",(f[n][L]%D+D)%D);
    24     return 0;
    25 }

t3 Code

--------------------

转载于:https://www.cnblogs.com/Gkeng/p/11509140.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230810/6756d81608f74e05813c29546eaa57b0.png