夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

CSP-S2考前综合强化刷题（第二场）

2020-10-02 7 min read # 计数题 # 培训题 # 比赛题 # 猜结论 # 动态规划

QAQ

T2被降智

A

二分答案

判断的时候我们先让之前(如果有灯)就放光放过去,照亮一些路灯

然后再找到第一个照不亮的我们从哪个点向后找第二个要照亮的路灯就好了

时间复杂度O(nlogn)

考场空间开小?成为全场唯一90

以后1.5倍空间一定要开!!!

code:


#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 7;

int n, k, a[MAXN];

inline int chk(int x) {
	int lstl = 0;
	int lstu = 1;
	lstu = 1;
	lstl = 1;
	while(fabs(a[lstl + 1] - a[lstu]) <= x && lstl <= n) {
		++lstl;
	}
	lstu = lstl + 1;
	for(int i = 2; i <= k; ++i) {
		while(fabs(a[lstu] - a[lstl]) <= x && lstu <= n) {
			++lstu;
		}
		lstl = lstu;
		while(fabs(a[lstl + 1] - a[lstu]) <= x && lstl <= n) {
			++lstl;
		}
		lstu = lstl + 1;
	}
	while(fabs(a[lstu] - a[lstl]) <= x && lstu <= n)
		++lstu;
	return lstu > n;
}

signed main() {
	scanf("%lld%lld", &n, &k);
	a[n + 1] = 2e9;
	a[0] = -2e9;
	int	L = 0, R = 2e9, ans = 0;
	for(int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	while(L <= R) {
		int mid = (L + R) >> 1;
		if(chk(mid)) {
			ans = mid;
			R = mid - 1;
		} else {
			L = mid + 1;
		}
	}
	printf("%lld\n", ans);
	return 0;

}

B

惨

首先n^2很easy

然后考虑怎么观察来优化

你会发现我们就算交换很鬼畜也会有很多不动的位置

比如12345对于2交换一次

21435

1,3,5都没有变

但是数组整个下标其实向后平移了一位,然后有一些特殊位置要暴力修改....

做法就很显然了...开个2n的数组就行了

然后每次我们交换交换特殊位置...QAQ

code:


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e6 + 7;
int n, p[MAXN];
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)p[i] = i;
	for(int i = 2; i <= n; ++i) {
		int nw = 0;
		for(int j = 1; j <= n; j += i) {
			swap(nw, p[j + i - 2]);
		}
		p[i + n - 1] = nw;

	}
	for(int i = n; i < 2 * n; ++i) {
		printf("%d ", p[i]);
	}
	puts("");
	return 0;
}

C

随便dp即可

单指针计数可以实现快速判断最近的是哪个

同时计算一段贡献也很basic

code:


#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 205;
const int MAXK = 32;
ll a[MAXN], sum[MAXN], b[MAXN], suf[MAXN];
int n, k;
ll f[MAXN][MAXK][2];
inline ll cst1(int l, int r) {//l light ->r
	return sum[r] - sum[l - 1] - 1ll * (r - l + 1) * a[l];
}

inline ll cst2(int l, int r) {//r light -> l
	return suf[l] - suf[r + 1] - 1ll * (r - l + 1) * b[r];
}

int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		sum[i] = sum[i - 1] + a[i];
	}
	for(int i = 1; i <= n; ++i) {
		b[i] = a[n] - a[i];
	}
	for(int i = n; i >= 1; --i) {
		suf[i] = suf[i + 1] + b[i];
	}
	memset(f, 0x3f3f3f3f, sizeof(f));
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= min(i, k); ++j) {
			if(j != 1) {
				int lstu = i;
				for(int k = i - 1; k >= 1; --k) {
					while(a[i] - a[lstu - 1] < a[lstu - 1] - a[k]) --lstu;
					f[i][j][1] = min(f[i][j][1], f[k][j - 1][1] + cst1(k, lstu - 1) + cst2(lstu, i));
				}
			} else {
				f[i][j][1] = min(f[i][j][1], cst2(1, i));
			}
			for(int k = i - 1; k >= 1; --k)
				f[i][j][0] = min(f[i][j][0], f[k][j][1] + cst1(k, i));
		}
	}
	printf("%lld\n", min(f[n][k][0], f[n][k][1]));
	return 0;
}

D

fi,jf_{i,j}表示点i子树到i距离为j的点数有多少个

然后gi,jg_{i,j}表示点i子树中满足dis(LCA(x,y),x)=dis(LCA(x,y),y)=dis(LCA(x,y),i)+jdis(LCA(x,y),x)=dis(LCA(x,y),y)=dis(LCA(x,y),i)+j
的有多少个

你会发现g数组更新其实很简单

gi,j+=gv,j+1g_{i,j}+=g_{v,j+1}

gi,j+1+=fv,j∗fi,j+1g_{i,j+1}+=f_{v,j}*f_{i,j+1}

第二行相当于加入了新的三元组

f转移一样简单

code:


#include<bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
const int MAXN = 1e5 + 7;
const int MAXM = 2e5 + 7;
int home[MAXN], nxt[MAXM], to[MAXM], ccnt, n;
ll a[MAXN], ans;

inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

int fa[MAXN];
ll sum1[MAXN][5], sum2[MAXN][5];

inline void dfs1(int u, int F) {
	fa[u] = F;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		dfs1(v, u);
		sum1[u][1] += a[v];
		sum1[u][3] += sum1[u][2] * sum1[v][1];
		sum1[u][2] += sum1[v][1] * sum2[u][2];
		sum2[u][2] += sum1[v][1];
	}
	return;
}

signed main() {
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);

	scanf("%lld", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	for(int i = 1, x, y; i < n; ++i) {
		scanf("%lld%lld", &x, &y);
		ct(x, y);
		ct(y, x);
	}
	dfs1(1, 0);
	//case 1
	for(int u = 1; u <= n; ++u) {
		int v = fa[fa[u]];
		if(v == 0)continue;
		ans += a[v] * sum1[u][2];
	}
	//case 2
	for(int u = 1; u <= n; ++u) {
		ans += sum1[u][3];
	}
	//case 3
	for(int u = 1; u <= n; ++u) {
		int v = fa[u];
		if(v == 0)continue;
		ll tp = sum1[v][1] - a[u];
		ans += tp * sum1[u][2];
	}
	printf("%lld\n", ans);
	return 0;
}
Powered by Gridea RSS