考的好烂啊 （悲
T1 路径
依旧签到题，依旧没写出来
一道非常简单的拓扑排序，对于每次拓扑时的拓展，记录其 \(siz\) 值表示由此节点可以到达的关键点数量，最后判断一下有没有关节点的 \(siz=k\) 就行了，代码放下面：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int T;
int n,m,k;
struct edge{int next,to;
}e[MAXN];
int head[MAXN],cnt;
void add(int a,int b){e[++cnt].to=b;e[cnt].next=head[a];head[a]=cnt;return ;
}
int rd[MAXN],q[MAXN],flag[MAXN];
int siz[MAXN],ans;
queue<int> que;
int main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;add(a,b);rd[b]++;}cin>>k;for(int i=1;i<=k;i++){cin>>q[i];flag[q[i]]=1;}for(int i=1;i<=n;i++){if(rd[i]==0) que.push(i);}while(!que.empty()){int x=que.front();que.pop();siz[x]+=flag[x];for(int i=head[x];i;i=e[i].next){int y=e[i].to;rd[y]--;siz[y]=max(siz[y],siz[x]);if(!rd[y]) que.push(y);}}for(int i=1;i<=n;i++){ans|=(siz[i]==k);siz[i]=flag[i]=rd[i]=rd[i]=head[i]=0;}cnt=0;if(ans) cout<<"Yes\n";else cout<<"No\n";ans=0;}return 0;
}
T2 异或
区间修改非常难处理，我们可以把整个序列转换为查分序列，那么区间修改也就变成了单点修改，接下来描述的所有操作也均在这个查分序列的基础上进行；
我们可以把 n 个数抽象成 n 个点，每次修改就是在双端连上一条无向边，那么一组合法解就是若干个异或和为零的联通块构成的（设其大小为 \(x\)），其下界边数就是 \(x-1\) ，上界则是 \(x\)；考虑如何取到这个下界，因为两次异或不会修改整个联通块的异或和，要满足最后的联通块异或和为0，那么最开始就要为零；
所以容易发现答案就是 \(n\) 减去异或和为0的子序列数，那么我们就要最大化异或和为0的子序列数，这个可以拿状压dp轻松做到，时间复杂度 \(o(3^n)\) ；
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n;
long long a[25],d[25];
long long yh[2000005],fg[2000005],flag[2000005];
long long dp[2000005];
void dfs(int x){if(flag[x]) return ;flag[x]=1;for(int i=1;i<=n;i++){if(!(x&1<<(i-1))){yh[(x|(1<<(i-1)))]=yh[x]^d[i];if(!yh[(x|(1<<(i-1)))]) dp[(x|(1<<(i-1)))]=1;dfs((x|(1<<(i-1))));}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];d[i]=a[i]^a[i-1];}dfs(0);for(int i=1;i<=((1<<n)-1);i++){for(int j=i;j!=0;j=(j-1)&i){dp[i]=max(dp[i],dp[j]+dp[i^j]);}}cout<<n-dp[(1<<n)-1];return 0;
}
T3 距离
正解是淀粉质+淀粉树，但是我没学；（悲
T4 花之舞
en……T3都没改，T4更是改不出来；
似乎是神奇线段树+整体二分