1201考试总结

1201考试总结

T1

题目链接

​ 我tm直接双指针, 水题不硕了.

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
	long long s = 0, f = 1; char ch;
	while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
	return s * f;
}

const int N = 1e6 + 5;
int n, k, cnt, now, ans;
int in[65];
struct node { int p, c; } a[N];

int cmp(node a, node b) {
	return a.p < b.p;
}

int main() {
	
	n = read(); k = read();
	for(register int i = 1, x;i <= k; i++) {
		x = read(); 
		for(register int j = 1;j <= x; j++) a[++ cnt].p = read(), a[cnt].c = i;
	}
	sort(a + 1, a + n + 1, cmp);
	int l = 1; ans = 1e9;
	for(register int i = 1;i <= n; i++) {
		while(a[l].c == a[i].c && l < i) { 
			if(now == k) ans = min(ans, a[i - 1].p - a[l].p); 
			in[a[l].c] --; if(!in[a[l].c]) now --; l ++; 
		}
		if(!in[a[i].c]) now ++; in[a[i].c] ++; 
		if(now == k) ans = min(ans, a[i].p - a[l].p);
		while(in[a[l].c] > 1) { 
			if(now == k) ans = min(ans, a[i].p - a[l].p); 
			in[a[l].c] --; l ++; 
		}
		if(now == k) ans = min(ans, a[i].p - a[l].p); 
	}
	printf("%d", ans);

	return 0;
}

T2

题目链接

​ 容斥 + 缩索 + 剪枝

​ 首先我们可以预处理出只含有"6, 8"这两个数字的数, 我们把这些数存在\(num\)数组里, 然后容斥求区间\([l,r]\)内这些数的倍数.

​ 直接容斥肯定会T, 考虑剪枝.

​ 如果说\(num_i \% num_j == 0\), 也就是存在倍数关系, 那么\(num_i\)是没用的.

​ 对于\(num_i >= r / 2\)的那些数也是不用容斥的, 直接给答案加上\(r / num_i - (l - 1) / num_i\)就好, 因为这种数字不可能与其他数字的\(lcm\)小于\(r\).

​ 对\(num_i\)数组从大到小排序, 使\(lcm\)更快大于\(r\).

​ 复杂度玄学, 但是跑的飞快.

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
	long long s = 0, f = 1; char ch;
	while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
	return s * f;
}

const int N = 1e6 + 5;
long long a, b, ans, num[N];
int cnt, vis[N];

int cmp(int a, int b) { return a > b; }

void make_num(int now, long long sum) {
	if(sum > b) return ;
	if(sum != 0) num[++ cnt] = sum;
	if(now > 10) return ; 
	make_num(now + 1, sum * 10 + 6); make_num(now + 1, sum * 10 + 8);
}

void cut() {
	int t = 0;
	for(register int i = 1;i <= cnt; i++) 
		if(!vis[i]) {
			if(num[i] <= b / 2) num[++ t] = num[i];
			else ans += b / num[i] - a / num[i];
			for(register int j = i + 1;j <= cnt; j++) 
				if(!(num[j] % num[i])) vis[j] = 1;
	 	}
	cnt = t;
}

void dfs(int now, long long s, int t) {
	if(s > b) return ;
	if(now == cnt + 1) {
		if(s != 1) ans += (b / s - a / s) * ((t & 1) ? 1 : -1);
		return ;
	}
	dfs(now + 1, s, t);
	long long tmp = num[now] / __gcd(num[now], s);
	if(tmp * s <= b) dfs(now + 1, tmp * s, t + 1); 
}

int main() {

	a = read(); b = read(); a --;
	make_num(1, 0); sort(num + 1, num + cnt + 1); cut();
	sort(num + 1, num + cnt + 1, cmp);
	dfs(1, 1, 0); printf("%lld", ans);

	return 0;
}

T3

题目链接

​ cdq分治.

​ 话说第一次做cdq分治竟然是在考试. 另一种解法是\(KD-Tree\)但我不会233.

​ 先介绍一下cdq分治, 它的全称应该是基于时间的分治算法, 主要流程是这样的.

​ 把修改操作和查询操作放一起, 按某个标准排序, 然后进行分治:

​ 1.递归计算\(solve(l,mid)\);

​ 2.递归计算\(solve(mid+1, r)\);

​ 3.计算\([l, mid]\)中的修改操作对\([mid + 1, r]\)中查询操作的影响.

​ 那么这道题怎么做呢?

​ 假设只有操作二, 也就是没有修改操作, 我们对于每一个询问\((x, y)\)要求的是 : \(\sum_{i = 1}^n min(\mid x - x_i\mid, \mid y - y_i\mid)\) ;

​ 考虑把绝对值去掉, 那么这个平面上的点可以被\((x,y)\)分成左下, 左上, 右上, 右下四部分.对于左下部分的, 要求的是 : \(min(x - x_i, y - y_i)\) = \(x + y - max(x_i+ y_i)\).

​ 然后我们将这些节点按\(x\)为第一关键字, \(y\)为第二关键字排序, 保证\(x_i <= x\), 然后用树状数组取找那些\(y_i<=y\)的点, 树状数组维护的是\(x_i + y_i\)的最大值.

​ 对于左上, 右上, 右下也是一样的.

​ 然后把修改操作考虑上, 这时候就要用到cdq分治了. 我们把所有的修改和询问和初始节点按\(x\)为第一关键字, \(y\)为第二关键字排序, 然后进行cdq分治, 每次计算\([l, mid]\)中的修改操作对\([mid + 1, r]\)中查询操作的影响的时候, 像上面一样考虑四个部分就好了.

​ 注意每次修改完树状数组后有撤销这些操作, 不然会对后面造成影响, 并且不能够开一个新的树状数组.

#include <bits/stdc++.h>

#define lowbit(x) x & -x
#define mid ((l + r) >> 1)

using namespace std;

inline long long read() {
	long long s = 0, f = 1; char ch;
	while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
	return s * f;
}

const int N = 1e6 + 5, inf = 0x3f3f3f3f;
int n, m;
int t[N], ans[N];
struct node { int x, y, z; } a[N], b[N];

int cmp(node a, node b) { return a.x == b.x ? a.y < b.y : a.x < b.x; } 

void change(int x, int y) { for(; x < N; x += lowbit(x)) t[x] = max(t[x], y); return ; }

void change_inf(int x) { for(; x < N; x += lowbit(x)) t[x] = -inf; return ; }

int query(int x) { int res = -inf; for(; x ; x -= lowbit(x)) res = max(res, t[x]); return res; }

void calc(int s, int tt, int dx, int dy, int f) {
	for(int i = s;i != tt; i += f) {
		int y = dy == -1 ? N - b[i].y : b[i].y; // 当dy为-1时, 要查询的下标变成了-yi, 加上1e6转正(其实我也不透彻, 也不知道这么解释对不对)
		int tmp = b[i].x * dx + b[i].y * dy;
		if(a[b[i].z].z == 1) change(y, tmp);
		else ans[b[i].z] = min(ans[b[i].z], abs(tmp - query(y))); //这里要加绝对值是因为query相当于是对称节点, 画个图就明白了
	}
	for(int i = s;i != tt; i += f) {
		int y = dy == -1 ? N - b[i].y : b[i].y;
		if(a[b[i].z].z == 1) change_inf(y); 
	}
}

void cdq(int l, int r) {
	if(l < mid) cdq(l, mid); if(mid + 1 < r) cdq(mid + 1, r);
	int t = 0;
	for(int i = l;i <= r; i++) if(i <= mid && a[i].z == 1 || i > mid && a[i].z == 2) b[++ t] = a[i], b[t].z = i;
	sort(b + 1, b + t + 1, cmp);
	calc(1, t + 1, 1, 1, 1); calc(1, t + 1, 1, -1, 1); 
	calc(t, 0, -1, -1, -1); calc(t, 0, -1, 1, -1);
}

int main() {

	n = read(); m = read();
	for(int i = 1;i <= n; i++) a[i].x = read(), a[i].y = read() + 1, a[i].z = 1;
	for(int i = 1;i <= m; i++) a[i + n].z = read(), a[i + n].x = read(), a[i + n].y = read() + 1;
	n += m; memset(ans, 0x3f, sizeof(ans)); memset(t, 0xcf, sizeof(t));
	cdq(1, n);
	for(int i = 1;i <= n; i++) if(a[i].z == 2) printf("%d\n", ans[i]);

	return 0;
}

T4

题目链接

​ 树形DP找直径 + 单调队列优化 + 基环树.

这个题可把我恶心坏了, 口区

​ 首先转化题意 : 给定一张基环树森林, 让你求出所有基环树的直经之和. 为啥转化成这样了呢? 首先\(n\)个点\(n\)条边, 并且每一个点都会有一条出边, 所以它是一张基环树森林.

​ 看题目中这句话 : "渡船:你可以选择这种方法,仅当没有任何桥和以前使用过的渡船的组合可以由 S 走到 D (当检查是否可到达时,你应该考虑所有的路径,包括经过你曾游览过的那些岛)。"这话啥意思呢?这句话的意思就是, 你从一个联通块里出来, 就不可以在回去了, 这是因为从\(S\)渡船到\(D\), 这条路本来就是通过一些桥和渡船, 所以从D到S走这条路也可以. 也就是说你要在每个联通块内找一条最长的路径, 那肯定就是直径了.

​ 如何找一颗基环树的直径呢?我们可以把那个环提出来, 然后枚举环上的每个点, 这个直径可能是每个节点的子树内的直径, 也可能是\(dis(i,j) + d_i + d_j\).\(dis(i,j)\)是环上两点距离, \(d_x\)是\(x\)这棵子树内的最长链.

​ 对于第一种情况, 直接树形DP求最长链和直径就好了.对于第二种情况, 我们需要断环成链, 变成原来环的2倍.但是不可直接枚举\(i, j\) , 可以尝试用单调队列优化, 上面式子可以用前缀和表示为 : \(s_i - s_j + d_i + d_j = d_i + s_i + (d_j - s_j)\), 然后我们用单调队列维护一个\(d-s\)的最大值就好了.

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
	long long s = 0, f = 1; char ch;
	while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
	return s * f;
}

const int N = 1e6 + 5;
int n, st, cnt;
long long ans, ans1, ans2, s[N], dep[N], Dep[N];
int v[N], q[N], id[N], head[N];
bool vis[N];
struct edge { int to, nxt, val; } e[N << 1];

void add(int x, int y, int z) {
	e[++ cnt].nxt = head[x]; 
	head[x] = cnt; 
	e[cnt].to = y; 
	e[cnt].val = z;
}

int dfs(int x, int fa) {
	if(v[x]) {
		v[x] = 2; id[++ cnt] = x; vis[x] = 1; return 1;
	}
	v[x] = 1;
	for(int i = head[x]; i ; i = e[i].nxt) {
		int y = e[i].to; if(i == ((fa - 1) ^ 1) + 1) continue ;
		if(dfs(y, i)) {
			if(v[x] == 2) { s[st - 1] = s[st] - e[i].val; return 0; }
			if(v[x] == 1) { ++ cnt; s[cnt] = s[cnt - 1] + e[i].val; vis[x] = 1; id[cnt] = x; }
			return 1;
		}
	}
	return 0;
}

void get_dep(int x) {
	vis[x] = 1; 
	for(int i = head[x]; i ; i = e[i].nxt) {
		int y = e[i].to; if(vis[y]) continue ;
		get_dep(y);
		ans1 = max(ans1, dep[x] + e[i].val + dep[y]);
		dep[x] = max(dep[x], dep[y] + e[i].val);
	}
}

long long work(int u) {
	st = cnt + 1; ans1 = ans2 = 0;
	dfs(u, 0); 
	for(register int i = st;i <= cnt; i++) {
		get_dep(id[i]);
		Dep[i] = Dep[cnt + i - st + 1] = dep[id[i]];
		s[cnt + i - st + 1] = s[cnt + i - st] + s[i] - s[i - 1];
	}
	int l = 1, r = 0;
	for(register int i = st;i <= 2 * cnt - st + 1; i++) {
		while(l <= r && q[l] <= i - cnt + st - 1) l ++;
		if(l <= r) ans2 = max(ans2, Dep[i] + s[i] + Dep[q[l]] - s[q[l]]);
		while(l <= r && Dep[q[r]] - s[q[r]] <= Dep[i] - s[i]) r --;
		q[++ r] = i;
	}
	return max(ans1, ans2);
}

int main() {
	
	n = read(); 
	for(register int i = 1, y, z;i <= n; i++) {
		y = read(), z = read(), add(i, y, z), add(y, i, z);
	}
	cnt = 0;
	for(register int i = 1;i <= n; i++) if(!vis[i]) ans += work(i);
	printf("%lld\n", ans);

	return 0;
}
上一篇:1201【毕设课设】基于8086数码管计算器设计


下一篇:1201:菲波那契数列