Public Round #1

传送门

【PR #1】删数

• 题意:写的很清楚了，略
• 思路：
  首先转化为差分数组，两个连续数相同，删掉，乘二放进去。
  发现能互相转化的两个数，符号，值\(/lowbit\)都一样。
  把能相互转化的数归为一类，处理出每个的lowbit，能除\(2\)的次数。
  \(f_i\)表示前\(i\)个最终的数的数量。
  枚举第\(i\)最后为\(2^j\)，想要知道多少到\(i\)可以变为\(2^j\)。
  考虑到两个\(2^j\)凑出\(2^{j+1}\)这个可以倍增处理已知右端点\(i\)，合并后值为\(2^j\)的左端点\(L_{i,j}\)
  \(g_{i,j}=g_{{g_{i,j-1}\ \ -1},\ j-1}\)
• 调很久的原因：
  1.没有考虑\(b_i=0\)是随便合并成一个\(0\)，单独处理，方案\(+1\)即可。
  2.数组下标为负数（一些点能过，一些不能过）
• code:

#include
using namespace std;
const int N=3e5+5;
const int M=31;
int a[N],b[N],R[N],L[N][M],f[N];
int main() {
//	freopen("ex_data2.in","r",stdin);
	int T,n;
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i=l)f[i]=min(f[L[i][j]-1]+1,f[i]);
				}
			}
		}
		for(int i=0;i<=n;i++)for(int j=0;j<=30;j++)L[i][j]=0;
		printf("%d\n",f[n]+1);
	}
	return 0;
}

T2 【PR #1】守卫

• 题意:图，求生成树森林，满足每个连通块有且只能包含一个士兵。每个士兵都有能选的点集。
• 思路：
  有三种思路，可以去看题解，我的是第二种，最好想的一种，不过跑的不快。
  可以想到先求最小生成树森林。连通块不够就从大到小删边。
  判断一条边能否删：跑连通块与士兵的匹配就好了。
  每一次都跑吗?\(O(n^4)\)的耶。（好像有的人也跑过了很多点的）
  其实次删边，从一个连通块变为两个连通块。那只用在新的一个连通块处跑增广路（\(O(n^3)->O(n^2)\)）
  当然方便处理我dfs*2分别标记了一下两个连通块中的点。
  首先以上操作默认当前每个连通块都应该匹配了一个士兵的。
  若删边前的连通块本身匹配的士兵为\(p\),看\(p\)在两个连通块中的哪个，更改一下匹配关系，且另一个就是新连通块。
  这里的g_fa()就用来找连通块在二分图匹配上代表的节点编号。如果找到增广路了，就删这条边，改一下\(fa\)（随便改一个该连通块里面的节点即可，这里就改边\(x,y\)就好）
  总复杂度\(O(n^3)\)，匹配用的匈牙利。
• 调了很久的原因
  这个调的是真tm久，至少放了5h上去。
  原因：两个连通块中的一个可能和原连通块编号相同。这样撤回时可能清空新连通块时，把原本的也清空了。
  改一下顺序，先删除，再添加就不会影响添加了。
• code:

#include
using namespace std;
const int N=305;
const int M=N*N;
typedef long long ll;
struct edge {int x,y,z;}E[M],U[M];
bool cmp(edge u,edge v) {return u.z