A

易发现 $n \text{ mod }4=0$,时符合规律,具体证明就是一定要有两条边平行于 $x$ 轴,两条边平行于 $y$ 轴。

B

连续的一段 $11111000000$ 记为一个区间,可以为 $0$ 为 $1$

那么只要把所有的区间标记为类似 $1111110$ 即可,即可剩下一个 $0$

然后根据这个打一下表。

C

发现把 $1$ 剔除之后,只会贡献 $2(m-w)$ 个数。

自然地,要使这 $2(m-w)$ 个数尽可能大,就有贪心先选大 $w_i$ 的,通过这个踢掉一些小的。

D

可以发现 $level ~i+1$ 是由一个 $level ~i$ 以及 两个 $level ~i-1$ 构成的。

如果从底下选,不难发现这样选有最优性,就相当于 $c_{i+1}=c_i+2*c_{i-1}$ ,因为顶部可能也会构成一个,也就是子树的顶部都没有被标记的情况下会 $+1$ 。

E

记 $s_i$ 表示最多需要多少个 $i$ 类型。

如果 $s_i\le w_i$ ,就可以把含有 $i$ 类型的人放在末尾,尽可能少地选数,即不会吃两个。

然后把这些人踢掉,因为他们已然合法。

反复进行该操作,如果出现 $\forall i,s_i> w_i ~or ~s_i=0$ ,就不合法,因为总存在最后一个人没有东西吃。(如果存在东西吃,则不可能出现 $\forall i,s_i> w_i$ ,因为其他人会把 $i$ 类型吃完,不可能剩下)

const int N=2e5+5;
int w[N],s[N],q[N<<5],X[N],Y[N],ans[N],len;bool v[N],vs[N];
vector<int>c[N];
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i<=m;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        c[x].push_back(i);
        c[y].push_back(i);
        X[i]=x,Y[i]=y;
        ++s[x];++s[y];    
    }
    int l=1,r=0;
    for(int i=1;i<=n;i++)if(s[i]<=w[i])q[++r]=i,vs[i]=1;
    for(int t=1;t<=n;t++)
    {
        if(l>r){puts("DEAD");return 0;}
        int x=q[l++];
        for(vector<int>::iterator it=c[x].begin();it!=c[x].end();)
        {
            if(v[*it])it=c[x].erase(it);
            else 
            {
                int i=*it;
                ans[++len]=i;
                v[i]=1;s[x]--;
                if(X[i]==x)
                {
                    s[Y[i]]--;
                    if(s[Y[i]]<=w[Y[i]]&&!vs[Y[i]])
                    {
                        vs[Y[i]]=1;q[++r]=Y[i];
                    }
                }
                else
                {
                    s[X[i]]--;
                    if(s[X[i]]<=w[X[i]]&&!vs[X[i]])
                    {
                        vs[X[i]]=1,q[++r]=X[i];
                    }
                }
                ++it;
            }
        }
    }
    puts("ALIVE");
    for(int i=len;i;i--)printf("%d ",ans[i]);
    return 0;
}

F

首先先明确一下定义。

$w_i$ 为 $1$ 时,表示先手存在必胜状态,为 $0$ 时,不存在必胜状态。

$l_i$ 为 $1$ 时,表示先手存在必败(执行最神必的操作)状态,为 $0$ 时,就算执行最神必的操作,不存在必败状态。

如果 $w_i=l_i$ ,即当前这局同时存在先手必胜与必败态,或者同时不存在。

不妨来思考一个问题,

假如存在先手必胜与必败态,那么是不是意味着先手可以控制当前局面呢?

然后又冒出一个问题,是不是意味着先手可以控制整个局面呢?

稍微来思考一下第二个问题,假设后续局面没有先手必败态,也没有先手必胜态,那么意味着后手控制着游戏局面,此时只要让当前先手成为后手,即可决定整个游戏局面。

假设存在先手必败态,不存在先手必胜态,仅需让当前先手成为后手即可,因为先手只有先手必败态,其他状态均由后手决定,仅需让后手令先手必胜即可。

其他情况类似的。

于是我们可以得到 $w_i=l_i $ 时可以跳出循环,如果不是,继续执行,注意交换先手后手的顺序。

const int N=2e6+5;
bool Win(ll s,ll e)
{
    if(e&1)return !(s&1);
    if(s>e/2)
    {
        if(s&1)return 1;
        else return 0;
    }
    if(s>e/4)return 1;
    return Win(s,e/4); 
}
bool Lose(ll s,ll e)
{
    if(s>e/2)return 1;
    return Win(s,e/2);
}
int main()
{
    int n;scanf("%d",&n);
    bool sec=0;int win,lose;
    for(int i=1;i<=n;i++)
    {
         ll s,e;
        scanf("%lld%lld",&s,&e);
        win=Win(s,e),lose=Lose(s,e);
        win^=sec,lose^=sec;
        sec=win;if(win==lose)break;
    }
    printf("%d %d\n",win,lose);
    return 0;
}