T1

看到了有向无环图，很容易让人想到拓扑。

设 \(f_i\) 表示经过节点 \(i\) 路径，这条路径上的关键点个数的最大值。

如果有一个点满足 \(f_i=k\)，那么答案就是 \(Yes\)，否则就是 \(No\)，这个显然。

转移就是从所有能到达 \(i\) 的节点转移，取 \(\max\)。这个可以通过拓扑实现。

复杂度为 \(\Theta(\sum m)\)。

Code

#include <iostream>
#include <cstdio>
#include <queue>

const int N=1e6+10;

using namespace std;

inline int read() {
    int f=1, x=0;
    char ch=getchar();
    while(ch>'9' || ch<'0') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return f*x;
}

inline void write(bool x) {
    if(x) cout<<"Yes";
    else cout<<"No";
    putchar('\n');
}

int T;
int n, m, k, cnt_edge;
struct edge {
    int next, to;
}e[N<<1];
int head[N], in[N];
int vis[N], val[N];

void add_edge(int u,int v) {
    e[++cnt_edge].to=v;
    e[cnt_edge].next=head[u];
    head[u]=cnt_edge;
    in[v]++;
}

inline void init() {
    for(int i=1;i<=n;i++) {
        head[i]=in[i]=0;
        vis[i]=val[i]=0;
    }
    for(int i=1;i<=cnt_edge;i++) {
        e[i].to=e[i].next=0;
    }
    n=cnt_edge=0;
}

queue <int> q;

void topu() {

    for(int i=1;i<=n;i++) {
        if(!in[i]) q.push(i);
    }

    while(!q.empty()) {
        int now=q.front(); q.pop();
        vis[now]+=val[now];
        for(int i=head[now];i;i=e[i].next) {
            int v=e[i].to;
            vis[v]=max(vis[v], vis[now]);
            in[v]--;
            if(!in[v]) q.push(v);
        }
    }

    bool flag=0;
    for(int i=1;i<=n;i++) {
        if(vis[i]==k) {
            flag=1;
            break;
        } 
    }
    write(flag);
}

int main() {

    T=read();
    while(T--) {
        init();

        n=read(), m=read();
        for(int i=1;i<=m;i++) {
            int u=read(), v=read();
            add_edge(u, v);
        }
        k=read();
        for(int i=1;i<=k;i++) {
            int x=read();
            val[x]=1;
        }
        topu();
    }
 
    return 0;
}

T2

Part1

区间修改不考虑，考虑差分，原序列为 \(a_i\)，设 \(b_i=a_i \oplus a_{i-1}\)，那么易证当且仅当所有的 \(b_i\) 都为零时，所有的 \(a_i\) 也等于零。对 \(a_i\) 的区间修改，在差分数组上就是单点修改。一次修改一个值或者两个值。

Part2

我们把 \(n\) 个数看成 \(n\) 个点，两个数的修改看成两个点之间的连边，一个点的修改看成自环。那么最终的答案就是总边数，我们想让边数最小。

我们选 \(x\) 个点组成一个连通块，考虑最优策略下要连多少条边，发现上界为 \(x\)（即 \(x\) 个自环），下界为 \(x-1\)，组成了一棵树，考虑什么情况下可以达到下界。有结论：

当且仅当连通块内的点一开始的异或和为 \(0\) 时，才可以达到下界。

必要性：因为进行了 \(x-1\) 次操作，那么每次操作必然是修改两个，总的异或和不变，要想通过修改使其都变成 \(0\)，那么这几个数一开始的异或和必然为 \(0\)。

充分性：如果异或和为 \(0\)，那么可以把这几个点穿成一条链，每次把链头通过异或自己的方式把自己变为 \(0\)，这样最后一个数就变成了这几个数的异或和，为 \(0\)。

那么我们就是想让这样的连通块最多，设其为 \(x\)，答案就是 \(n-x\)。

Part3

现在问题变成了：给定一个序列，把其划分成若干个子序列，最大化异或和为 \(0\) 的个数。可以状压解决，每次转移枚举子集。用到了一个枚举子集的技巧。

复杂度证明

考虑每个状态被枚举了几次。

设当前状态集合为 \(T\)，那么被枚举的次数就是 \(2^{n-|T|}\)

由此可得总的次数为：

\[\sum_{i=0}^{n}\dbinom{n}{i}2^{n-i} \]

根据二项式反演即为：\(3^n\)。

复杂度为 \(\Theta(3^n)\)。

Code

#include <iostream>
#include <cstdio>

#define int long long

const int N=18;
const int M=(1<<N)+10;

using namespace std;

inline int read() {
    int f=1, x=0;
    char ch=getchar();
    while(ch>'9' || ch<'0') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return f*x;
}

inline void write(int x) {
    cout<<x; putchar('\n');
}

int n, ans;
int a[N], b[N], dp[M];
bool f[M];

signed main() {

    n=read();
    for(int i=1;i<=n;i++) {
        a[i]=read(); b[i]=a[i]^a[i-1];
    }
    
    for(int s=0;s<(1<<n);s++) {
        int sum=0;
        for(int i=1;i<=n;i++) {
            if(s & (1<<(i-1))) sum^=b[i];
        }
        if(!sum) f[s]=1;
    }

    for(int s=1;s<(1<<n);s++) {
        for(int t=s;t;t=(t-1)&s) {
            if(f[t]) {
                dp[s]=max(dp[s], dp[s^t]+1);
            }
        }
    }
    
    write(n-dp[(1<<n)-1]);
 
    return 0;
}