期望得分：100+30+100=230

实际得分：60+30+100=190

排序去重

固定右端点，左端点单调不减

考场上用了二分，没去重，60

#include
      
       #include
       
        #include
        
         using namespace std;#define N 100001void read(int &x){    x=0;char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}struct node{    int a,b;    bool operator < (node q) const    {        if(a!=q.a) return a
         
          n) last++;        mx=max(mx,l-last+1);    }    printf("%d\n",n-mx);}
         
        
       
      

 

记录所有子集的最后出现位置

对于每个ai，枚举ai的子集，若最后出现位置<i-bi,ans++

枚举子集复杂度：

for(int s=1;s<(1<<n);s++)

　　for(int i=s;i;i=(i-1)&s)

这两个循环的复杂度为3^n

因为对于n个二进制位，要么属于s不属于i，要么属于s属于i，要么不属于s

#include
      
       #include
       
        #define N 100001using namespace std;void read(int &x){    x=0;  char c=getchar();    while(!isdigit(c))  c=getchar();     while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}int pos[N];int main(){    freopen("test.in","r",stdin);    freopen("test.out","w",stdout);    int n,a,b,ans;    read(n);    for(int i=1;i<=n;i++)    {        ans=0;        read(a); read(b);        for(int j=a;j;j=(j-1)&a)        {            if(pos[j]
       
      

 

套路，tarjan+拓扑排序/单源最短路

#include
      
       #include
       
        #include
        
         #include
         
          #define N 500001using namespace std;int n,m,S;int val[N];int front[N],to[N],nxt[N],tot,from[N];int dfn[N],low[N],st[N],top;bool ins[N];int id[N],cnt,sum[N];int nxt2[N],front2[N],to2[N],tot2;int q[N];int in[N],dp[N];void read(int &x){    x=0;char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void add(int u,int v){    if(u==v) return;    for(int i=front[u];i;i=nxt[i])        if(to[i]==v) continue;    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u;}void init(){    read(n);read(m);    int u,v;    for(int i=1;i<=m;i++) { read(u); read(v); add(u,v); }    for(int i=1;i<=n;i++) read(val[i]);    read(S);}void tarjan(int x){    dfn[x]=low[x]=++tot;    st[++top]=x; ins[x]=true;    for(int i=front[x];i;i=nxt[i])        if(!dfn[to[i]]) tarjan(to[i]),low[x]=min(low[x],low[to[i]]);        else if(ins[to[i]]) low[x]=min(low[x],dfn[to[i]]);    if(low[x]==dfn[x])    {        id[x]=++cnt; sum[cnt]+=val[x];        while(top && st[top]!=x)  { id[st[top]]=cnt; sum[cnt]+=val[st[top]]; ins[st[top--]]=false; }        ins[st[top--]]=false;    }}void add2(int u,int v){    to2[++tot2]=v; nxt2[tot2]=front2[u]; front2[u]=tot2;  in[v]++;}void rebuild(){    for(int i=1;i<=m;i++)        if(id[from[i]]!=id[to[i]]) add2(id[from[i]],id[to[i]]);}void pre(){    memset(ins,false,sizeof(ins));    int h=0,t=1;    q[++h]=id[S]; ins[id[S]]=true;    int now;     while(h<=t)    {        now=q[h++];        for(int i=front2[now];i;i=nxt2[i])            if(!ins[to2[i]]) ins[to2[i]]=true,q[++t]=to2[i];    }    for(int i=1;i<=cnt;i++)        if(!ins[i])            for(int j=front2[i];j;j=nxt2[j]) in[to2[j]]--;    }void topsort(){    st[top=1]=id[S]; dp[id[S]]=sum[id[S]];    int now;    while(top)    {        now=st[top--];        for(int i=front2[now];i;i=nxt2[i])         {            dp[to2[i]]=max(dp[to2[i]],dp[now]+sum[to2[i]]);            in[to2[i]]--;            if(!in[to2[i]]) st[++top]=to2[i];        }    }}void answer(){    int ans=0,k,x;    read(k);    for(int i=1;i<=k;i++)    {        read(x);        ans=max(ans,dp[id[x]]);    }    printf("%d\n",ans);}int main(){    freopen("save.in","r",stdin);    freopen("save.out","w",stdout);    init();    tot=0;    for(int i=1;i<=n;i++)         if(!dfn[i]) top=0,tarjan(i);    rebuild();    pre();    topsort();    answer();}