20210816 你相信引力吗,marshland,party?,半夜

考场

第一眼都不可做

T1 长得就像单调栈/单调队列，推了推性质发现优弧、劣弧都合法的点对很好处理，其他情况只在一种情况合法，那么开两个单调队列分别统计距离 \(\le\frac2n,>\frac2n\) 的即可，感觉很难写。

T2 甚至不知道往哪方面想，而且我会的暴力是 \(O(5^{\frac{n^2}2})\) 的，感觉要凉

T3 树剖| bitset 很好求出每个人能带的特产，但不知道怎么分配

T4 先想到了 LCIS，于是一直在想能不能通过 hash 来维护最小表示快速转移

8.20 才开写，T1 直接调到 10.00，一直在面向数据编程，打了无数补丁终于过拍了。但复杂度多了一个 \(\log\)，测了下速好像还比较稳

迅速敲了 T2 T4 俩裸暴力，T4 一开始尝试最小表示法判合法，写一半不会了，改成 \(n^2\)。

10.40 想到了 T3 二分答案+网络流的做法，复杂度上界在网络流，可以快乐跳 fa，迅速 rush，11.05 过了样例

res

rk1 100+0+71+10

T2 少算了代价+\(i,j\) 写错挂 10pts

rk1 yzf 100+0+71+10

rk5 szs 10+100+0+0

rk11 曹浩宇 30+0+14+50

总结

昨天的反思确实有用，T3 的网络流差点没想到，但也不能老反思啊。

还是写不出来细节多的题。T1 中间重新检验过一次算法，虽然正确性没假但复杂度多了 \(\log\)，写之前也只有大致思路，导致中间 debug 了很久，浪费了不少时间，以后尽量在开写之前做好正确性检验和正确的复杂度分析。

有些不常用的算法（最小表示法，LCIS）学了记不住，还是昨天的说的问题

你相信引力吗

不是正解

破环成链。维护两个单调队列，队内元素递减，每次加入元素时在队列上二分找有贡献的区间

考场代码

const int N = 1e7+5;

int n,a[N];

int mxa,mxa2,m;

LL ans;

int f1=1,r1,q1[N],f2=1,r2,q2[N];

int lower(int fro,int rea,int *que,int x) {

	int l = fro, r = rea;

	while( l < r ) {

		int mid = l+r>>1;

		if( a[que[mid]] > x ) l = mid+1;

		else r = mid;

	}

	return l-(l!=fro&&a[que[l]]<=x);

}

signed main() {

//	freopen("a1.in","r",stdin);

//	freopen("a1.out","w",stdout);

	read(n); m = n+1>>1;

	For(i,1,n) read(a[i]), a[n+i] = a[i], ckmax(mxa,a[i]);

	For(i,1,n) ans += a[i]==mxa;

	ans = -ans * (ans-1) / 2;

	if( !ans ) {

		For(i,1,n) if( a[i] < mxa ) ckmax(mxa2,a[i]);

		For(i,1,n) ans -= a[i]==mxa2;

	}

//	cerr<<ans<<endl;

	For(i,1,n+n) {

		while( f1<=r1 && q1[f1]+m < i ) ++f1;

		if( i > n ) {

			ans += r1-lower(f1,r1,q1,a[i])+1;

//			cerr<<"q1 "<<i<<':';

//			For(j,lower(f1,r1,q1,a[i]),r1) cerr<<' '<<q1[j];

//			cerr<<endl;

			while( f2<=r2 && q2[f2]+n <= i ) ++f2;

			while( f2<=r2 && a[q2[r2]] < a[q1[f1]] ) --r2;

			if( a[i] >= a[q1[f1]] ) {

				ans += r2-lower(f2,r2,q2,a[i])+1;

//				cerr<<"q2 "<<i<<':';

//				For(j,lower(f2,r2,q2,a[i]),r2) cerr<<' '<<q2[j];

//				cerr<<endl;

			}

		}

		while( f1<=r1 && a[i] > a[q1[r1]] ) --r1;

		q1[++r1] = i;

		while( f2<=r2 && a[i-m] > a[q2[r2]] ) --r2;

		q2[++r2] = i-m;

	}

	write(ans);

	return iocl();

}

marshland

费用流

把有危险的格子拆点放中间，费用为 \(V_{x,y}\)，其余点按行数奇偶放到两边，分别与源汇连。中间的格子向它四周的各自连边。答案为危险值之和减最大费用。

正确性：显然每个 \(L\) 型拐角处的格子一定有危险，即其余两个格子没有危险且在相邻两行。这样连边每个 \(L\) 型依次流过了三个格子，用流量限制了石头不能重叠，EK 保证了费用从大到小选择。

注意可以不用完 \(m\) 个石头，跑费用流至费用为负即可。

zsy 说能构造出负环，但这题不用消圈就过了。

code

const int N = 55, dx[]={-1,0,1,0}, dy[]={0,1,0,-1};

int n,m,k,a[N][N];

bool ban[N][N];

const LL inf = 0xcfcfcfcfcfcfcfcf;

int ind,id[N][N][2];

LL sum;

namespace F {

const int N = ::N*::N*2, M = N*N*2;

int s,t,mm=1,head[N],pre[N];

LL dis[N];

bool vis[N];

struct Edge { int to,c,w,nxt; } e[M];

queue<int> que;

void adde(int x,int y,int z,int w) {

	e[++mm] = Edge{y,z,w,head[x]}, head[x] = mm;

	e[++mm] = Edge{x,0,-w,head[y]}, head[y] = mm;

}

bool spfa() {

	mem(dis,0xcf,t);

	dis[s] = 0, que.push(s);

	while( !que.empty() ) {

		int u = que.front(); que.pop();

		vis[u] = 0;

		for(int i = head[u], v; i; i = e[i].nxt)

			if( e[i].c && dis[u]+e[i].w > dis[ v=e[i].to ] ) {

				dis[v] = dis[u]+e[i].w, pre[v] = i;

				if( !vis[v] ) vis[v] = 1, que.push(v);

			}

	}

	return dis[t] > 0;

}

LL ek(int T) {

	LL cost = 0;

	while( T-- && spfa() ) {

		for(int u = t, i; u != s; u = e[i^1].to) {

			i = pre[u];

			--e[i].c, ++e[i^1].c;

		}

		cost += dis[t];

	}

	return cost;

}

}

signed main() {

//	freopen("a.in","r",stdin);

//	freopen("a.out","w",stdout);

	read(n,m,k);

	For(i,1,n) For(j,1,n) read(a[i][j]), sum += a[i][j];

	For(i,1,k) { int x,y; read(x,y); ban[x][y] = 1; }

	For(i,1,n) For(j,1,n) if( !ban[i][j] )

		id[i][j][0] = ++ind, id[i][j][1] = ++ind;

	F::s = ++ind, F::t = ++ind;

	For(i,1,n) For(j,1,n) if( !ban[i][j] ) {

		if( a[i][j] ) {

			F::adde(id[i][j][0],id[i][j][1],1,a[i][j]);

			For(k,0,3) {

				int x = i+dx[k], y = j+dy[k];

				if( x<1||x>n||y<1||y>n || ban[x][y] ) continue;

				if( x & 1 ) F::adde(id[x][y][0],id[i][j][0],1,0);

				else F::adde(id[i][j][1],id[x][y][0],1,0);

			}

		} else {

			if( i & 1 ) F::adde(F::s,id[i][j][0],1,0);

			else F::adde(id[i][j][0],F::t,1,0);

		}

	}

	write(sum-F::ek(m));

	return iocl();

}

party?

这题分值貌似与题面不符

树剖+线段树维护 bitset，没有修改于是可以预处理每个点到重链顶的 bitset 减少一个 \(\log\)。

得到每个人能带的特产集合后二分答案，每个人拆成 \(mid\) 个点，转化为二分图匹配，但不需要真的跑。发现只有 \(c\) 类点，根据 \(\text{hall}\) 定理可以得到 \(|s|\times mid\le to_s\)，\(2^c\) 枚举 \(s\) 即可。

sol 建议手写 bitset，亲测不如 STL 快。rnm，退钱

code

namespace Bitset {

const unsigned size = (1<<16)-1;

unsigned bc[1<<16];

struct BS {

	ULL a[16];

	void reset() { memset(a,0,sizeof a); }

	BS() { reset(); }

	void set(int i) { a[i>>6] |= 1ull<<(i&63); }

	bool test(int i) { return a[i>>6] & (1ull<<(i&63)); }

	unsigned count() {

		unsigned res = 0;

		For(i,0,15) res += bc[a[i]&size]+bc[(a[i]>>16)&size]+

						   bc[(a[i]>>32)&size]+bc[(a[i]>>48)&size];

		return res;

	}

};

BS operator | (const BS &x,const BS &y) {

	BS res;

	For(i,0,15) res.a[i] = x.a[i] | y.a[i];

	return res;

}

}

using Bitset::BS;

const int N = 3e5+5, M = 1e3+5;

int n,m,q,fa[N],a[N];

int c,p[6];

BS out[6];

namespace Lca {

int ind,dep[N],siz[N],son[N],top[N],dfn[N],id[N];

BS col[N],t[N*4];

vector<int> to[N];

void dfs1(int u) {

	siz[u] = 1, dep[u] = dep[fa[u]] + 1;

	for(int v : to[u]) {

		dfs1(v);

		siz[u] += siz[v];

		if( siz[v] > siz[son[u]] ) son[u] = v;

	}

}

void dfs2(int u,int top) {

	Lca::top[u] = top, dfn[u] = ++ind, id[ind] = u;

	if( son[u] ) {

		col[son[u]] = col[u], col[son[u]].set(a[son[u]]);

		dfs2(son[u],top);

	}

	for(int v : to[u]) if( v != son[u] )

		col[v].set(a[v]), dfs2(v,v);

}

#define u(l,r) ((l+r)|(l!=r))

void build(int l,int r) {

	if( l == r ) { t[u(l,r)].set(a[id[l]]); return; }

	int mid = l+r>>1;

	build(l,mid), build(mid+1,r);

	t[u(l,r)] = t[u(l,mid)] | t[u(mid+1,r)];

}

BS query(int l,int r,int ql,int qr) {

	if( ql <= l && r <= qr ) return t[u(l,r)];

	int mid = l+r>>1;

	BS res;

	if( ql <= mid ) res = query(l,mid,ql,qr);

	if( mid < qr ) res = res | query(mid+1,r,ql,qr);

	return res;

}

#undef u

int lca(int u,int v) {

	while( top[u] != top[v] ) {

		if( dep[top[u]] < dep[top[v]] ) swap(u,v);

		u = fa[top[u]];

	}

	return dep[u]<dep[v] ? u : v;

}

void calc(int i,int u,int anc) {

	out[i].reset();

	while( top[u] != top[anc] ) {

		out[i] = out[i] | col[u];

		u = fa[top[u]];

	}

	out[i] = out[i] | query(1,n,dfn[anc],dfn[u]);

}

void init() { dfs1(1), dfs2(1,1), build(1,n); }

}

signed main() {

	For(i,1,Bitset::size) Bitset::bc[i] = Bitset::bc[i>>1] + (i&1);

	read(n,m,q);

	For(i,2,n) read(fa[i]), Lca::to[fa[i]].pb(i);

	For(i,1,n) read(a[i]);

	Lca::init();

	while( q-- ) {

		read(c); For(i,1,c) read(p[i]);

		int anc = p[1]; For(i,2,c) anc = Lca::lca(anc,p[i]);

		For(i,1,c) Lca::calc(i,p[i],anc);

		int ans = m, all = (1<<c)-1;

		For(s,1,all) {

			int cnt = 0; out[0].reset();

			For(i,1,c) if( s & (1<<i-1) ) ++cnt, out[0] = out[0] | out[i];

			ckmin(ans,(int)out[0].count()/cnt);

		}

		write(ans*c);

	}

	return iocl();

}

巴特西

20210816 你相信引力吗,marshland,party?,半夜

考场

res

总结

你相信引力吗

marshland

party?

半夜

最新文章

热门文章