20210720 noip21

又是原题，写下题解吧

Median

首先时限有 2s（学校评测机太烂，加到 4s 了），可以放心地筛 \(1e7\) 个质数并算出 \(s_2\)，然后问题变为类似滑动求中位数。发现 \(s_2\) 几乎是随机的，可以用桶来维护中位数指针，每次暴力移动。

实现比较精妙

code

const int N = 1e7+5;

int n,k,w;

int pri,mid,p[N],s[N],s2[N],cnt[N*2];

bool vis[179424674];

void sieve(int n) {

	For(i,2,n) {

		if( !vis[i] ) p[++pri] = i;

		for(int j = 1; j <= pri && i*p[j] <= n; ++j) {

			vis[i*p[j]] = 1;

			if( i % p[j] == 0 ) break;

		}

	}

}

namespace sub1 {

int mid,pre,cur=-1;

LL ans;

void main() {

	mid = k/2+1;

	for(int i = 1; i < k; ++i) ++cnt[s2[i]];

	For(i,k,n) {

		++cnt[s2[i]], pre += s2[i]<=cur;

		if( i > k ) --cnt[s2[i-k]], pre -= s2[i-k]<=cur;

		while( pre < mid ) pre += cnt[++cur];

		while( pre-cnt[cur] >= mid ) pre -= cnt[cur--];

		ans += cur;

	}

	printf("%lld.0",ans);

	exit(0);

}

}

namespace sub2 {

int mid,prel,prer,l=-1,r=-1;

LL ans;

void main() {

	mid = k/2;

	for(int i = 1; i < k; ++i) ++cnt[s2[i]];

	For(i,k,n) {

		++cnt[s2[i]], prel += s2[i]<=l, prer += s2[i]<=r;

		if( i > k ) --cnt[s2[i-k]], prel -= s2[i-k]<=l, prer-= s2[i-k]<=r;

		while( prel < mid ) prel += cnt[++l];

		while( prel-cnt[l] >= mid ) prel -= cnt[l--];

		while( prer < mid+1 ) prer += cnt[++r];

		while( prer-cnt[r] >= mid+1 ) prer -= cnt[r--];

		ans += l+r;

	}

	printf("%.1lf",ans/2.0);

	exit(0);

}

}

signed main() {

	sieve(179424673);

	read(n,k,w); mid = k/2+1;

	For(i,1,n) s[i] = (LL)p[i] * i %w, s2[i] = s[i] + s[i/10+1];

	if( k & 1 ) sub1::main();

	else sub2::main();

}

Game

澄清题意：“分数差”指 Alice 的得分减 Bob 的得分

考虑用桶来维护 \(s\) 集合。设 \(mx\) 为桶中最大元素，则如果新加进来的数大于 \(mx\)，那么一定会立刻被选择，因此它就不用加入桶；否则移动 \(mx\) 找到桶中最大元素。整个过程中 \(mx\) 是单减的。时间复杂度 \(O(nk)\)。

需要大力卡常

code

const int N = 1e5+5;

int n,T,a[N],p;

int mx,lsh[N],cnt[N];

void solve() {

	LL ans = 0;

	read(p);

	for(int i = 1; i < p; ++i) {

		++cnt[a[i]];

		if( a[i] > mx ) mx = a[i];

	}

	int f = 1;

	for(int i = p; i <= n; ++i, f = -f) {

		if( a[i] >= mx ) { ans += f * lsh[a[i]]; continue; }

		++cnt[a[i]];

		while( !cnt[mx] ) --mx;

		ans += f * lsh[mx], --cnt[mx];

	}

	for(int i = 1; i < p; ++i, f = -f) {

		while( !cnt[mx] ) --mx;

		ans += f * lsh[mx], --cnt[mx];

	}

	write(ans);

}

signed main() {

	read(n,T);

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

	sort(lsh+1,lsh+n+1), lsh[0] = unique(lsh+1,lsh+n+1)-lsh-1;

	For(i,1,n) a[i] = lower_bound(lsh+1,lsh+lsh[0]+1,a[i])-lsh;

	while( T-- ) solve();

	return iocl();

}

Park

原题（不知道出题人改的什么鬼题面）

考虑先固定一个点，那么就可以直接 DP。时间复杂度 \(O(n^2)\)。

树上路径类问题通常尝试在 LCA 处将两条链拼起来，本题也不例外。发现对于一条路径，起点和终点是不等价的，因此设 \(f[i,j]\) 表示从 \(i\) 的子树走到 \(i\) 撒 \(j\) 个面包的最大差值，\(g[i,j]\) 为从 \(i\) 的子树走到 \(i\) 的。

转移见代码

code

const int N = 1e5+5;

int n,m,val[N];

vector<int> to[N];

LL ans,sum[N],f[N][105],g[N][105];

void dfs(int u,int fa) {

	For(i,1,m) f[u][i] = sum[u], g[u][i] = sum[u]-val[fa];

	//g[u]会在fa处用到（从fa走下来），无法让小朋友在u遇到fa的鸽子而自己不遇到

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

		dfs(v,u);

		For(i,0,m) ans = max(ans,f[u][i]+g[v][m-i]);

		// v之前的子树 -> u -> v -> 子树v

		For(i,1,m)

			f[u][i] = max(f[u][i],max(f[v][i],f[v][i-1]+sum[u]-val[v])),

			g[u][i] = max(g[u][i],max(g[v][i],g[v][i-1]+sum[u]-val[fa]));

			// 不变；u不放；u放

	}

}

signed main() {

	read(n,m);

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

	for(int i = 1; i < n; ++i) {

		int x,y; read(x,y);

		to[x].pb(y), to[y].pb(x);

		sum[x] += val[y], sum[y] += val[x];

	}

	dfs(1,0);

	For(i,1,n) reverse(to[i].begin(),to[i].end());

	// 答案与顺序有关，需要反转儿子来统计全

	dfs(1,0);

	write(ans);

	return iocl();

}

巴特西

20210720 noip21

Median

Game

Park

最新文章

热门文章