本文共 2882 字，大约阅读时间需要 9 分钟。

比赛概况

掉了一万年的分终于升了一次了。。

但是最终不仅手速不够快，也没有AK 大概做题顺序A—->B—–>C（开黑的）——>F——>D——>hack 然后把房间里面的人都快要看完了，都没有hack出来。。 E没弄出来

题解

A，B，C就先不说了。。大家自己去看代码。。

说些我比赛时会做的F题。。话说A了这个就直接rank10了，贼爽 为什么E题在F后面，因为E题太长了QAQ。。

F

题意：给你n个数，问你有多少个子串，满足这个子串所有元素的或值大于这个子串的最大值

题解：我们考虑枚举最大值为某个数的时候答案的贡献。用一个单调栈不难搞出每个数是最大值的区间。。然后我们在弄出对于一个数，他或哪一个数可以使他变大，分别取左边和右边最近的两个，这个按位弄，正着和倒着分别扫一次就能出来了。于是就变成了一个简单的计数问题了。不懂的还可以看代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;typedef long long LL;const LL N=200005;LL n;LL a[N];LL L[N],R[N];LL l[N],r[N]; LL sta[N],top;LL vis[35];//这一位没有的是在哪里 void prepare (){    LL top=0;    for (LL u=1;u<=n;u++)    {        while (top!=0&&a[sta[top]]
       
        >=1;        }    }    for (LL u=1;u<=34;u++) vis[u]=n+1;    for (LL u=n;u>=1;u--)    {        r[u]=n+1;        LL x=a[u];        for (LL i=1;i<=34;i++)//第几位         {            LL o=(x&1);            if (o==0)//他这一位是0            {                r[u]=min(r[u],vis[i]);            }            else                vis[i]=u;            x>>=1;        }    }}void solve (){    LL ans=0;    for (LL u=1;u<=n;u++)//以这一位为最大值的答案     {        if (L[u]<=l[u])        {            if (R[u]>=r[u])                ans=ans+(u-L[u]+1)*(R[u]-u+1)-(r[u]-u)*(u-l[u]);            else ans=ans+(l[u]-L[u]+1)*(R[u]-u+1);        }        else    if (R[u]>=r[u])            ans=ans+(R[u]-r[u]+1)*(u-L[u]+1);    }    printf("%I64d\n",ans);}int main(){    scanf("%I64d",&n);    for (LL u=1;u<=n;u++)   scanf("%I64d",&a[u]);    prepare();    solve();    return 0;}
       
      
     
    
   

E

题意：给你n个串，然后你现在有一种操作：将一个数打上$'$，我们定义，

a′<b′<....z′<a<b<....z

$a'<b'<....z'<a<b<....z$。然后你只要对一个2打上了$'$，所有的2都要变。问是否有一种方案可以使得变化后的串字典序大小满足给定的顺序。

题解（yang老师的做法）：我们可以对于相邻的两个进行处理。找到第一位不一样的，那么他们的决策点肯定在这里，定义在上面的这一位为a，下一位为b

那么有两种情况: a$<$b，那么说明他们已经有序了，那么如果b变，那么a肯定要变，于是b向a连边 a > <script type="math/tex" id="MathJax-Element-5">></script>b一开始是无序的，那么说明a一定要变，b不能变，于是打上两个标记。。 最后我们就可以得到一张图。。一个DAG。。然后我们就把一定要变的标记传递下去。看看是否会遇到一个不能变的标记，如果有就不合法，否则，就合法 CODE:

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N=100005;int n,m;int len[N];vector
         
           s[N],e[N];int fl[N];//这个点是什么int d[N];bool vis[N];int main(){ memset(fl,-1,sizeof(fl)); scanf("%d%d",&n,&m); for (int u=1;u<=n;u++) { scanf("%d",&len[u]); for (int i=1;i<=len[u];i++) { int x; scanf("%d",&x); s[u].push_back(x); } if (u==1) continue; int o=min(len[u-1],len[u]); int i; for (i=0;i
          
           s[u][i])//我比你大 { if (fl[s[u-1][i]]==0) { printf("No\n");return 0;} fl[s[u-1][i]]=1; if (fl[s[u][i]]==1) { printf("No\n");return 0;} fl[s[u][i]]=0; break; } else if (s[u-1][i]
           
            len[u]) { printf("No\n"); return 0; } } } queue
            
              q; for (int u=1;u<=m;u++) if (d[u]==0) q.push(u); for (int u=1;u<=m;u++) { if (fl[u]==1)//这个必须要改 vis[u]=true; else vis[u]=false; } while (!q.empty()) { int x=q.front();q.pop(); int SZ=e[x].size(); for (int u=0;u