夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

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

2020-10-05 9 min read # 分块 # 比赛题 # 动态规划

A

首先分析下题目性质

ii只比i−1i-1天多1

然后只比i−2i-2多2

那么会发现i要花费的天数可以是想化一些天追上i-1,然后在追上i−1i-1的前提下去追i−2i-2...

那么如果我们没追上i-1就追上i-2的话...i−1i-1也一定可以用哪个时间追上i−2i-2

这个东西就比较显然....相邻取min

code:


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

int n, a[MAXN], ans;

signed main() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	ans = 1e15;
	for(int i = 1; i < n; ++i) {
		ans = min(ans, a[i] - a[i + 1]);
	}
	printf("%lld\n", ans);
	return 0;
}

B

曼哈顿距离,屑啊

显然我们前n/2大的都要在左边,后n/2大的在右边

那么我们只需要看看那些位置不满足这个性质,然后把他们任意交换就好了

因为是曼哈顿距离....所以就是后n/2前n/2大的下标之和-前n/2后n/2大的下标之和


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
#define ll long long
ll ans;
int n;
struct  rec {
	int x, id;
	bool operator<(const rec &w)const {
		return x < w.x;
	}
} a[MAXN];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i].x);
		a[i].id = i;
	}
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n / 2; ++i) {
		if(a[i].id > n / 2) {
			ans += a[i].id;
		}
	}
	for(int i = n / 2 + 1; i <= n; ++i) {
		if(a[i].id <= n / 2) {
			ans -= a[i].id;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

C

显然我们直接排序然后k个分一组是错误的,因为我们切换字符可以直接砍掉一堆

但是这个东西是可以在trie树上做的

我们把所有串插入trie然后在上面dfs即可,统计每个子树和,然后我们回溯的时候如果子树中够k个就凑一下

因为这样做能保证每个组尽可能的深的地方匹配,所以是对的

时间复杂度O(n∗26)O(n*26)

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e6 + 7;
int n, k;
char s[MAXN];
int rt = 1, T = 1;
int ch[MAXN][27];
int ed[MAXN];
inline void ins(char *s, int L) {
	int nw = rt;
	for(int i = 0; i < L; ++i) {
		int t = s[i] - 'a';
		if(!ch[nw][t]) {
			ch[nw][t] = ++T;
		}
		nw = ch[nw][t];
	}
	ed[nw]++;//kk
	return ;
}

ll ans;
inline void dfs(int u, int dep) {
	for(int i = 0; i < 26; ++i) {
		if(ch[u][i]) {
			dfs(ch[u][i], dep + 1);
			ed[u] += ed[ch[u][i]];
		}
	}
	ans += 1ll * dep * (ed[u] / k);
	ed[u] %= k;
	return ;
}

int main() {
	// freopen("test.in", "r", stdin);
	// freopen("test1.out", "w", stdout);
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i) {
		scanf("%s", s);
		int l = strlen(s);
		ins(s, l);
	}
	dfs(1, 0);
	printf("%lld\n", ans);
	return 0;
}

D

对于k>∑Kk>\sqrt{\sum{K}}

考虑直接暴力,可以做到O(K(n+m))O(K(n+m))

做法就是把每个位置修改一下然后再考虑m次暴力即可

对于k<∑Kk<\sqrt{\sum{K}}

考虑快速回答询问

显然的是这个询问不会很快...此时会发现我们能够k2k^2二维数点了

李队有一个O(1)回答的做法,好像是根号平衡啊

就是考虑用前缀和分块,然后我们修改复杂度O(n)O(\sqrt n)

二维平面上我们就直接扫描线扫过去

可以离线做到一个log,复杂度O(Q \sqrtQ log)

code:


//数据处理题
//超高校级的幸运
//如果数据随机,\sum_K会减少的很快,暴力就快
//如果构造去他妈的
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 7;
namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE], *p1 = buf, *pend = buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0;
		char s = nc();
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;

int n, m, q, Bas, ccnt;
int home[MAXN], nxt[MAXN], tl[MAXN], tr[MAXN], ans[MAXN];
int q1[MAXN], q2[MAXN], t1, t2, a[MAXN];
inline void ct(int x, int y, int z) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	tl[ccnt] = y;
	tr[ccnt] = z;
}

const int BIG = 1e7 + 8;

struct rec {
	int u, v, x, y;
	rec(int u = 0, int v = 0, int x = 0, int y = 0) : u(u), v(v), x(x), y(y) {};
	bool operator<(const rec &w) const {
		return u == w.u ? x < w.x : u < w.u;
	}
} e[MAXN], qry[MAXN], mda[BIG];

inline void solve1() {
	for(int i = 1; i <= t1; ++i) {
		int id = q1[i];
		for(int k = home[qry[id].v]; k; k = nxt[k]) {
			int L = tl[k];
			int R = tr[k];
			for(int  j = L; j <= R; ++j)
				a[j] = i;
		}
		for(int j = 1; j <= m; ++j) {
			if(a[e[j].u] == i && a[e[j].v] == i) {
				ans[qry[id].v] = 1;
				break;
			}
		}
	}
	return ;
}

struct bit {
#define lowbit(x) (x&(-x))
	int tr[MAXN];
	inline void add(int x, int V) {
		for(; x <= n; x += lowbit(x))
			tr[x] += V;
	}
	inline int qry(int x) {
		int ret = 0;
		for(; x; x -= lowbit(x))ret += tr[x];
		return ret;
	}
} tre;
#define  lowbit(x) (x&(-x))
inline void solve2() {
	int tot = 0;
	for(int t = 1; t <= t2; ++t) {
		int i = q2[t];
		for(int j = home[qry[i].v]; j; j = nxt[j]) {
			for(int k = j; k; k = nxt[k]) {
				mda[++tot] = (rec) {
					tl[k] - 1, tl[j], tr[j], -qry[i].v
				};
				mda[++tot] = (rec) {
					tr[k], tl[j], tr[j], qry[i].v
				};
			}
		}
	}
	for(int i = 1; i <= m; ++i) {
		mda[++tot] = (rec) {
			e[i].u, e[i].v, -1
		};
	}
	sort(mda + 1, mda + tot + 1);
	for(int i = 1; i <= tot; ++i) {
		if(mda[i].x == -1) {
			tre.add(mda[i].v, 1);
		} else if(mda[i].y > 0) {
			if(mda[i].v == 1)ans[mda[i].y] += tre.qry(mda[i].x);
			else ans[mda[i].y] += tre.qry(mda[i].x) - tre.qry(mda[i].v - 1);
		} else {
			mda[i].y = -mda[i].y;
			if(mda[i].v == 1)ans[mda[i].y] -= tre.qry(mda[i].x);
			else ans[mda[i].y] -= tre.qry(mda[i].x) - tre.qry(mda[i].v - 1);

		}
	}
	return ;
}
int main() {
	// freopen("test.in", "r", stdin);
	n = read();
	m = read();
	q = read();
	for(int i = 1; i <= m; ++i) {
		e[i].u = read();
		e[i].v = read();
		if(e[i].u > e[i].v)swap(e[i].u, e[i].v);
	}
	for(int i = 1; i <= q; ++i) {
		qry[i].u = read();
		qry[i].v = i;
		for(int j = 1, x, y; j <= qry[i].u; ++j) {
			x = read();
			y = read();
			ct(i, x, y);
		}
	}
	Bas = 1e4;
	int res	 = 4e6; //循环展开
	sort(qry + 1, qry + q + 1);
	int i = q;
	int cnt = 1e8 / max(n, m);
	for(; i >= 1; --i) {
		if(qry[i].u * qry[i].u >= Bas && cnt) {
			q1[++t1] = i;
			--cnt;
		} else {
			break;
		}
	}
	int j = 1;
	for(; j <= i; ++j) {
		if(res) {
			q2[++t2] = j;
			res = max(0, res - qry[j].u * qry[j].u);
		} else {
			q1[++t1] = j;
		}
	}
	solve1();//暴力1
	solve2();//暴力2
	for(int i = 1; i <= q; ++i) {
		if(ans[i])printf("GG\n");
		else printf("SAFE\n");
	}
	return 0;
}
Powered by Gridea RSS