NERC 2021
K. King’s Task
抄ZRC:
题意：给一个1000以内偶数个排列，两种操作，一种是前一半元素和后一半互换，一种是从1,2开始每两个互换，问给定数列转化为排序结束数列的最小步数，不行则-1.
解：显然两种操作都不能连续执行两次，否则就会抵消。因此，除了初始状态可以进行两种操作，其它到达的状态均只能进行一种操作。通过一些小数据可以发现，能到的状态数相当少，因此如果不想计算可以直接搜索到1e7次看看能不能到达。
分析1：观察小数据可以知道，123…n这个排列能到达的状态中，所有数均错位，且在每个位置上均出现一遍，因此状态数应该为排列的长度
分析2：将两次操作合在一起看效果，发现事实上进行一次操作相当于在一个大小为数字数量的置换群当中置换一次，所以得到结果。
D. Digits
WD dp
G. Guide
题意：从根节点开始走k个不同的点，问最少步数
写了个$O(n^4)$的树上背包（因为要记录答案），但其实有直接贪心的做法。
分析：如果走完k个点后一定要返回根节点，那么无论怎么走，步数都为2(k-1)，但因为不需要回到根节点，为了让步数最少，只要保证最后停下来的位置深度最大即可。然后比较显然的是如果最大深度为maxd，当k<=maxd时沿着链一直走，当k>maxd时一定能停在深度最大的点上。
B. Button Lock
题意：有d<=10个二进制位，给定n个二进制数，每次操作可以把一个位上的数从0变成1，或者把所有数清零，问要使这n个数都出现至少一次的最少操作数
分析：把这n个点取出来建个图，如果a是b的子集，就连一条a->b的边，问题就转化成用一些路径覆盖所有的点，每条路径的权值为路径中最后一个点的深度(bitcount)，问最小的路径和
可以进一步转化为一张二分图：每个点$a$拆成左右两个点$a_L,a_R$，把a->b的边连成$a_L\rightarrow b_R$，考虑某一种匹配状态，如果$a_L$不在匹配中，说明$a$是某个路径的最后一个点，对答案产生贡献，问题要求贡献和最小，或者说左边的点里在匹配中的点和最大
接着发现，将所有点根据bitcount从大到小排序之后，从大到小贪心可以保证解是最优的。从二分图的角度考虑，对于一个新加入的点，因为它的值小于等于图中其他任何点，所以用它替换掉当前匹配方案中的其他任何点，都不可能使答案更优，但如果这个点能加入到匹配中，且原来在匹配中的点仍然在，那么加入这个点一定是最优的（因为后续不会再替换掉这个点了）。
所以就从大到小把点加入进去，每加一次就在原来的图上跑一次dinic，如果产生增量，说明这个点不会产生贡献，否则这个点是某条路径的终点，会产生贡献
输出答案就是判断残量网络上$(a_L,b_R)$边的容量是否为0，为0则说明有一条$a\rightarrow b$的边，直接记录nxt[a]=b即可。对于在右边且不在任何匹配中的点$b_R$，说明有$0\rightarrow b$。
#include<bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << '\n'
using namespace std;
typedef long long LL;
typedef long long ll;
const int N = 2050 + 5;
//理论上界O(N^2*M)
//二分图最大匹配时间复杂度O(sqrt(N)*M)
struct Dinic{
struct Edge{
int to;LL v;int rev;
};
int n,s,t,dep[N],_cur[N];
bool used[N];
vector<Edge>G[N];
queue<int>L;
void init(int n_,int s_,int t_) {
n=n_,s=s_,t=t_;
for (int i=0;i<=n;i++) G[i].clear();
}
void addEdge(int x,int y,LL v) {
G[x].push_back({y,v,G[y].size()});
G[y].push_back({x,0,G[x].size()-1});
}
bool bfs() {
memset(used,0,sizeof(used));
dep[s]=1,used[s]=1;
L.push(s);
while(!L.empty()) {
int cur=L.front();
L.pop();
for (int i=0;i<G[cur].size();i++) {
Edge &e=G[cur][i];
if (!used[e.to] && e.v>0) {
dep[e.to]=dep[cur]+1;
used[e.to]=1;
L.push(e.to);
}
}
}
return used[t];
}
LL dfs(int c,LL flow) {
if (c==t ||flow==0) return flow;
LL ret=0,f;
for (int &i=_cur[c];i<G[c].size();i++) {
Edge &e=G[c][i];
if (dep[e.to]==dep[c]+1 && (f=dfs(e.to,min(flow,e.v)))>0) {
ret+=f,flow-=f,e.v-=f;
G[e.to][e.rev].v+=f;
if (!flow) break;
}
}
return ret;
}
LL go() {
LL ans=0;
while(bfs()) {
memset(_cur,0,sizeof(_cur));
ans+=dfs(s,1LL*100*INT_MAX);
}
return ans;
}
}dinic;
int d, n, a[N];
bool not_ini[N];
char s[20];
vector<int> E[N];
int nxt[N];
int getval(char *s) {
int res = 0, len = strlen(s);
for (int i = 0; i < len; i++) {
res = res * 2 + s[i] - '0';
}
return res;
}
bool contain(int x, int y) {
while(x || y) {
int dx = x & 1, dy = y & 1;
if (dx == 1 && dy == 0) return 0;
x >>= 1;
y >>= 1;
}
return 1;
}
int bitcount(int x) {
int res = 0;
while(x) {
res += x & 1;
x >>= 1;
}
return res;
}
void PRINT(int x, int y) {
int k = d - 1;
while(x || y) {
int dx = x & 1, dy = y & 1;
if (dx == 0 && dy == 1) printf("%d ", k);
k--;
x >>= 1;
y >>= 1;
}
}
int main() {
scanf("%d %d", &d, &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s);
a[i] = getval(s);
// dbg(a[i]);
}
sort(a + 1, a + 1 + n, [&](int u, int v) {
return bitcount(u) > bitcount(v);
});
for (int i = 1; i <= n - 1; i++) {
for (int j = i + 1; j <= n; j++) {
if (contain(a[j], a[i])) E[j].push_back(i);
}
}
int s = 0, t = 2 * n + 1;
dinic.init(2 * n + 1, 0, 2 * n + 1);
int ans = 0;
for (int i = 1; i <= n; i++) {
dinic.addEdge(s, i, 1);
dinic.addEdge(n + i, t, 1);
for (auto x : E[i]) dinic.addEdge(i, x + n, 1);
int now = dinic.go();
if (now == 0) ans += bitcount(a[i]) + 1;
}
ans--;
cout << ans << endl;
for (int i = 1; i <= n; i++) {
for (auto T : dinic.G[i]) {
if (T.to == 0) continue;
if (T.v == 0) {
nxt[i] = T.to - n;
not_ini[T.to - n] = 1;
}
}
}
bool first = 1;
for (int i = 1; i <= n; i++) {
if (!not_ini[i]) {
if (!first) printf("R ");
first = 0;
int j = i, prev = 0;
while(j != 0) {
PRINT(prev, a[j]);
prev = a[j];
j = nxt[j];
}
}
}
printf("\n");
return 0;
}