D
给定一序列 $a$ ，每次操作可以使指定位置的数变成整个序列的异或和，求达到目标序列的最少次数
设初始时异或和为 $x$ ，转化为每次将 $a_i$ 变为 $x$ 并将 $a_i$ 拿在手上下一次替换
显然有解当且仅当 $a\cup \{x\} \in b$
再考虑替换的过程，最后一定要用 $b_i$ 替换掉 $a_i$ ，这启发连边 $b_i\rightarrow a_i$ ，再从 $x$ 开始遍历每一条边
如果图是一个包含 $x$ 的连通块，则一定有一条 $1$ 欧拉路径覆盖所有边
如果不连通，或 $x$ 是孤立点/不在连通块内，则答案就是 $边数+连通块数-(x不是孤立点)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| const int N=1e5+100;
int n,a[N],b[N],x;
int cnt,edge_cnt,block_cnt;
int vis[N];
map<int, int> mp;
vector<int> G[N];
void dfs(int x){
vis[x]=1;
for(int y:G[x]) if (!vis[y]) dfs(y);
}
int main(){
scanf("%d",&n);
for(rei i=1;i<=n;++i) scanf("%d",&a[i]),++mp[ a[i] ],x^=a[i];
for(rei i=1;i<=n;++i) scanf("%d",&b[i]),--mp[ b[i] ];
++mp[x];
for(auto it:mp) if(it.second<0) return puts("-1"),0;
for(auto &it:mp) it.second=++cnt;
for(rei i=1;i<=n;++i)
if(a[i]!=b[i]){
rei u=mp[ b[i] ],v=mp[ a[i] ];
G[u].push_back(v),G[v].push_back(u); ++edge_cnt;
}
for(rei i=1;i<=cnt;++i) if(G[i].size()) if(!vis[i]) ++block_cnt,dfs(i);
printf("%d\n",edge_cnt+block_cnt-(!G[ mp[x] ].empty()));
getchar(),getchar();
return 0;
}
|
E
$2\leq N\leq 400$ 只火鸡， $m$ 个人，每人指定两只火鸡2 $x,y$ ，若两只都活着，则会等概率随机吃掉一只；若只活着一只，则悲吃掉；若都死亡则不做操作。第 $1$ 个人到第 $m$ 个人依次操作，求有多少 $(i,j)$ 满足最终时刻 $i,j$ 可能都活着
考虑如何使 $i$ 存活：第 $I$ 人选中 $i,j$ 只，则必须让 $j$ 死亡 ，则在第 $1\sim I-1$ 中第 $j$ 只不能死亡
而如果选择了 $(i,j),(i,k)$ 则如果前面的人选择 $(j,k)$ ，则第 $i$ 只必死
对于第 $i$ 只，设 $S_i$ 表示为了使 $i$ 存活需要保护的鸡的编号，从后往前扫到 $(x,y)$ ：
- 初始时 $S_i=\{i\}$
- 不妨设 $x\in S_i , y\notin S_i$ ，则将 $y$ 加入 $S_i$
- 若 $x,y\in S_i$ ，则 $i$ 一定会死亡
再考虑鸡 $(i,j)$ 的存活：枚举 $i,j$ 并判断 $S_i\cap S_j$ 是否为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| const int N=2e5+100;
int n,m,ans,x[N],y[N],dead[N];
bitset<410> f[401];
int main(){
scanf("%d%d",&n,&m);
for(rei i=1;i<=m;++i) scanf("%d%d",&x[i],&y[i]);
for(rei i=1;i<=n;++i){
f[i][i]=1;
for(rei j=m;j;--j){
rei u=f[i][ x[j] ],v=f[i][ y[j] ];
u&&v ? dead[i]=1 : 0;
u ? f[i][ y[j] ]=1 : (v ? f[i][ x[j] ]=1 : 0);
}
}
for(rei i=1;i<=n;++i){
if(dead[i]) continue;
for(rei j=i+1;j<=n;++j){
if(dead[j]) continue;
ans+=!((f[i]&f[j]).count());
}
}
printf("%d\n",ans);
getchar(),getchar();
return 0;
}
|