2024年西安铁一中集训DAY1---- 杂题选讲

文章目录

    • 牛客练习赛125 E 联谊活动（枚举，分讨）
    • 牛客练习赛125 F 玻璃弹珠（类莫队，离线询问，数据结构）
    • 2024ccpc长春邀请赛 D Parallel Lines（随机化）
    • 2024ccpc长春邀请赛 E Connected Components（单调栈）
    • 2024ccpc长春邀请赛 B Dfs Order 0.5（动态规划）
    • 2024 CCPC东北邀请赛 H. Meet（二分答案，树上公共祖先，树上差分）
    • 2024 CCPC东北邀请赛 I. Password（动态规划）
    • 2024 CCPC东北邀请赛 K. Tasks（贪心，构造）
    • 2024 CCPC东北邀请赛 L. Bracket Generation（组合数学，数数）
    • 2024 CCPC东北邀请赛 G. Diamond（根号分治）

牛客练习赛125 E 联谊活动（枚举，分讨）

          题面：
在这里插入图片描述

题目

分析：

在这里插入图片描述
          发现选用距离矩形越近的关键点答案会越优。注意到 x , y x,y x,y 的取值范围很小，我们对于每一个位置处理出 在它所在的行中，离它最近的左边 / 右边 的关键点，然后每次询问可以扫描 S x ∼ E x S_x \sim E_x Sx​∼Ex​ 行，设当前行是 l i n e line line，查询 ( l i n e , S y ) (line, S_y) (line,Sy​) 这个位置左右最近的关键点，分别拿这两个关键点去更新答案即可。时间复杂度 O ( m × x + x × y ) O(m\times x + x \times y) O(m×x+x×y)。
CODE：

#include<bits/stdc++.h>
using namespace std;
const int M = 1100;
const int N = 1e5 + 10;
int n, m, sx, sy, ex, ey, px[N], py[N];
int Left[M][M], Right[M][M];
bool f[M][M];
void pre_work() {
	memset(Left, -1, sizeof Left);
	memset(Right, -1, sizeof Right);
	for(int i = 1; i <= 1000; i ++ ) {
		int now = -1;
		for(int j = 1; j <= 1000; j ++ ) {
			if(f[i][j]) now = max(now, j);
			Left[i][j] = now;
		}
		now = 1001;
		for(int j = 1000; j >= 1; j -- ) {
			if(f[i][j]) now = min(now, j);
			Right[i][j] = (now == 1001 ? -1 : now);
		}
	}
}
int solve(int sx, int sy, int ex, int ey) {
	int res = 1e9, c = abs(sx - ex) + abs(sy - ey);
	for(int i = 1; i <= 1000; i ++ ) { // 扫描每一层 
		if(i < min(sx, ex)) {
			int tx = i, ty = min(sy, ey);
			if(Left[tx][ty] != -1) res = min(res, 2 * (min(sy, ey) - Left[tx][ty]) + 2 * (min(sx, ex) - i) + c);
			if(Right[tx][ty] != -1) {
				if(Right[tx][ty] <= max(sy, ey)) res = min(res, 2 * (min(sx, ex) - i) + c);
				else res = min(res, 2 * (Right[tx][ty] - max(sy, ey)) + 2 * (min(sx, ex) - i) + c);
			}
		}
		else if(i >= min(sx, ex) && i <= max(sx, ex)) {
			int tx = i, ty = min(sy, ey);
			if(Left[tx][ty] != -1) res = min(res, 2 * (min(sy, ey) - Left[tx][ty]) + c);
			if(Right[tx][ty] != -1) {
				if(Right[tx][ty] <= max(sy, ey)) {
					res = min(res, c);
					break;
				}
				else res = min(res, 2 * (Right[tx][ty] - max(sy, ey)) + c);
			}
		}
		else {
			int tx = i, ty = min(sy, ey);
			if(Left[tx][ty] != -1) res = min(res, 2 * (min(sy, ey) - Left[tx][ty]) + 2 * (i - max(sx, ex)) + c);
			if(Right[tx][ty] != -1) {
				if(Right[tx][ty] <= max(sy, ey)) res = min(res, 2 * (i - max(sx, ex)) + c);
				else res = min(res, 2 * (Right[tx][ty] - max(sy, ey)) + 2 * (i - max(sx, ex)) + c);
			}			
		}
	}
	return res;
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++ ) {
		scanf("%d%d", &px[i], &py[i]);
		f[px[i]][py[i]] = 1;
	}
	pre_work();
	for(int i = 1; i <= m; i ++ ) {
		scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
		printf("%d\n", solve(sx, sy, ex, ey));
	}
	return 0;
}

牛客练习赛125 F 玻璃弹珠（类莫队，离线询问，数据结构）

          题面：
在这里插入图片描述

题目

分析：
          在线处理很难在允许的时间复杂度内通过，我们考虑 离线：发现题目上给的 区间不相交 这一条性质，启示我们像莫队一样通过两个 指针 来不断更新当前维护区间的信息。具体来讲：设 l t lt lt， r t rt rt 分别是当前区间的左右端点。将查询区间离线后按照左端点排序，通过指针的逐步跳转实现维护区间的改变。由于指针 只会向后跳，因此最多跳 n n n 次，这一部分复杂度是 O ( n ) O(n) O(n) 的。我们考虑怎样维护当前区间的信息：一个操作 1 1 1 显然会在它的左端点第一次被用到，在它的右端点处作用消失。因此我们将每一个操作 1 1 1 的信息分别存进区间的做右端点内。左端点处为 添加 信息，当 r t rt rt 经过左端点时将这个信息加入数据结构中。右端点处为 删除 信息，当 l t lt lt 经过右端点时将信息从数据结构中删除。这样就解决了 位置 这一偏序。每条信息形如 某种颜色 c c c 在时间 t t t 时出现。由于 只有最小的 t t t 有用，添加时我们把 t t t 插入 c c c 对应的 s e t set set 里， 删除时把它从 s e t set set 里删掉。然后在 以时间为下标的树状数组 里更新不同最早时间出现的颜色数量。查询时查找 小于当前查询区间时间的前缀和 即可。
时间复杂度： O ( m l o g 2 m ) O(mlog_2m) O(mlog2​m)。

CODE:

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef pair< int, int > PII;
const int N = 5e5 + 10;
int n, m, op, l, r, col, tot;
struct BIT {
	int c[N];
	int lowbit(int x) {return x & -x;}
	void add(int x, int y) {for(; x < N; x += lowbit(x)) c[x] += y;}
	int ask(int x) {
		int res = 0;
		for(; x; x -= lowbit(x)) res += c[x];
		return res;
	}
}t;
vector< PII > A[N], D[N];
set< int > tc[N]; // 维护当前区间所有涉及的加颜色操作所带来的每种颜色的时间戳
struct range {
	int l, r, tim, ans;
}q[N];
bool cmp(range x, range y) {
	return x.l < y.l;
}
void add(int x) {
	for(auto v : A[x]) {
		int col = v.first, tim = v.second;
		if(!tc[col].empty()) {
			auto it = tc[col].begin();
			int Tim = (*it); 
			t.add(Tim, -1);
		}
		tc[col].insert(tim);
		auto it = tc[col].begin();
		int T = (*it);
		t.add(T, 1);
	} 
}
void del(int x) {
	for(auto v : D[x]) {
		int col = v.first, tim = v.second;
		if(!tc[col].empty()) {
			auto it = tc[col].begin();
			int Tim = (*it);
			t.add(Tim, -1);
		}
		tc[col].erase(tim);
		if(!tc[col].empty()) {
			auto It = tc[col].begin();
			int Gm = (*It);
			t.add(Gm, 1);
		}
	}
}
bool cmp2(range x, range y) {
	return x.tim < y.tim;
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++ ) {
		scanf("%d", &op);
		if(op == 1) {
			scanf("%d%d%d", &l, &r, &col);
			A[l].pb(make_pair(col, i));
			D[r].pb(make_pair(col, i));
		}
		else {
			scanf("%d%d", &l, &r);
			q[++ tot] = (range) {l, r, i};
		}
	}
	sort(q + 1, q + tot + 1, cmp);
	int lt = 1, rt = 0;
	for(int i = 1; i <= tot; i ++ ) {
		while(rt < q[i].r) {++ rt; add(rt);}
		while(lt < q[i].l) {del(lt); lt ++;}
		q[i].ans = t.ask(q[i].tim);
	}
	sort(q + 1, q + tot + 1, cmp2);
	for(int i = 1; i <= tot; i ++ ) {
		printf("%d\n", q[i].ans);
	}
	return 0;
}

启示：遇到存在 时间 和 位置 两种限制的询问和修改，可考虑如果修改可以离线（与在线状态无关）。那么可以将操作离线，按照位置进行 双指针 或者 莫队 跳动，在满足位置限制的同时用 数据结构 来维护时间限制。

2024ccpc长春邀请赛 D Parallel Lines（随机化）

在这里插入图片描述

          题目

          分析：考虑如果我们求出一个 斜率，如何检验这个斜率是否正确。一个很好的思路是对每个点算出在这个斜率下经过该点的直线的纵截距，然后判断是否有 k k k 个不同的纵截距以及每个纵截距是否对应大于等于 2 2 2 个不同的点即可。时间复杂度 O ( n ) O(n) O(n)。如果枚举两个点去算斜率，那么时间复杂度为 O ( n 2 ) O(n^2) O(n2)，显然不能接受。我们发现平行线的数量很少，意味着有较多的点在同一条直线上。直接随机出两个点算斜率并判断是否合法。可以证明随机出合法点对的最小概率为 O ( 1 k ) O(\frac{1}{k}) O(k1​)。所以可以在 O ( k ) O(k) O(k) 次随机出合法的点对，总时间复杂度为 O ( n × k ) O(n \times k) O(n×k)。

在这里插入图片描述

CODE:

#include<bits/stdc++.h>// 随机化 
#define pb push_back
using namespace std;
const int N = 1e4 + 10;
const int K = 51;
typedef double db;
int n, k, tot, cnt[N];
db X[N], Y[N];
const db INF = 1e18;
map< db, int > mp;
vector< int > node[N];
int random(int n) {
	return ((unsigned long long)rand() * rand() % n);
}
db B(int p, int q, db x, db y) {
	if(X[p] == X[q]) return x;
	else return (X[q] - X[p]) * y - (Y[q] - Y[p]) * x;
}
bool check(int p, int q) {
	tot = 0; memset(cnt, 0, sizeof cnt);
	for(int i = 1; i <= n; i ++ ) {
		db b = B(p, q, X[i], Y[i]);
		if(!mp[b]) mp[b] = ++ tot;
		cnt[mp[b]] ++;
	}
	bool f = 1;
	for(int i = 1; i <= n; i ++ ) {
		db b = B(p, q, X[i], Y[i]);
		if(cnt[mp[b]] == 1) {f = 0; break;}
	}
	if(tot == k && f) {
		for(int i = 1; i <= n; i ++ ) {
			db b = B(p, q, X[i], Y[i]);
			node[mp[b]].pb(i);
		}
		return 1;
	}
	for(int i = 1; i <= n; i ++ ) {
		db b = B(p, q, X[i], Y[i]);
		mp[b] = 0;
	}
	return 0;
}
int main() {
	srand(time(0));
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i ++ ) {
		scanf("%lf%lf", &X[i], &Y[i]);
	} 
	while(true) {
		int i = random(n) + 1, j = random(n) + 1;
		if(i == j) continue;
		else if(check(i, j)) {
			for(int i = 1; i <= tot; i ++ ) {
				printf("%d", node[i].size());
				for(int j = 0; j < node[i].size(); j ++ ) 
					printf(" %d", node[i][j]);
				puts("");
			}
			break;
		}
	}
	return 0;
}

2024ccpc长春邀请赛 E Connected Components（单调栈）

在这里插入图片描述
题目

          分析：
          不难想到将式子移项，将只含 i i i 的放一起，将只含 j j j 的放一起。我们可以得到 i i i 与 j j j 之间有连边，当且仅当：

a i − i ≤ a j − j ， b i − i ≥ b j − j a_i -i \leq a_j - j，b_i - i \geq b_j - j ai​−i≤aj​−j，bi​−i≥bj​−j 或者 a i − i ≥ a j − j ， b i − i ≤ b j − j a_i - i \geq a_j - j，b_i - i \leq b_j - j ai​−i≥aj​−j，bi​−i≤bj​−j 。这两个式子可以看作 j j j 往 i i i 连边 或 i i i 往 j j j 连边。我们令 x i = a i − i x_i = a_i - i xi​=ai​−i， y i = b i − i y_i = b_i - i yi​=bi​−i，那么 i i i 往 j j j 连边的条件就是 x i ≥ x j ， y i ≤ y j x_i \geq x_j，y_i \leq y_j xi​≥xj​，yi​≤yj​。将元素按照 x x x 从小到大排序，那么每种元素只可能往前边连边。我们使用 单调栈 维护 y y y。从前往后往栈里加入元素，那么只有 y i y_i yi​ 小于栈顶元素的 y y y 时 i i i 才能往栈顶元素所在连通块连边。我们考虑此时将栈顶元素弹出，然后接着比较直到 y i y_i yi​ 大于栈顶元素的 y y y。接下来存在一个问题：由于栈顶元素的 y y y 越大越容易连边，而我们刚把 y y y 元素较大的栈顶元素弹出，此时 i i i 一定与刚刚弹出的栈顶元素在同一个连通块中，如果仅仅把 i i i 放进栈中，那么后面的元素就有可能没有连上原来和这个连通块的边。想到一个连通块的 y y y 只有最大的有用，因此我们每次拿 y i y_i yi​ 和栈顶元素所在联通块的的最大 y y y 比较来判断是否连边就不会错。注意连边的时候更新连通块的最大 y y y 值。
时间复杂度 O ( n ) O(n) O(n)

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, sz[N], bin[N], mh[N], p, q;
struct element {
	int x, y;
}a[N];
bool cmp(element u, element v) {
	return ((u.x < v.x) || (u.x == v.x && u.y > v.y));
}
stack< int > s;
int Find(int x) {return x == bin[x] ? x : bin[x] = Find(bin[x]);}
void Merge(int x, int y) {
	int f1 = Find(x), f2 = Find(y);
	bin[f2] = f1; sz[f1] += sz[f2];
	mh[f1] = max(mh[f2], mh[f1]);
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) {
		scanf("%d%d", &p, &q);
		a[i].x = p - i;
		a[i].y = q - i;
	}
	sort(a + 1, a + n + 1, cmp);
	for(int i = 1; i <= n; i ++ ) {
		bin[i] = i; sz[i] = 1;
		mh[i] = a[i].y;
	}
	for(int i = 1; i <= n; i ++ ) {
		while(!s.empty() && a[i].y <= mh[Find(s.top())]) {
			Merge(i, s.top());
			s.pop();
		}
		s.push(i);
	}
	int cnt = 0;
	for(int i = 1; i <= n; i ++ ) {
		if(Find(i) == i) cnt ++;
	}
	cout << cnt << endl;
	return 0;
}

2024ccpc长春邀请赛 B Dfs Order 0.5（动态规划）

在这里插入图片描述
题目

          分析：
          为了方便，我们把子树大小为 偶数 的点称作 偶点，奇数 的点称作 奇点。 偶儿子 与 奇儿子 的称呼类似。
          容易想到状态定义 d p i , 0 / 1 dp_{i,0/1} dpi,0/1​ 表示 i i i 点的 d f n dfn dfn 序为偶数/奇数时， 以 i i i 为根的子树的最大权值和。考虑转移，分两类情况：

  1. 存在 奇儿子：那么每个偶儿子可以选 0 / 1 0/1 0/1 中较大的。设点 i i i 的状态为 t t t，奇儿子的数量为 m m m，那么显然有 ⌈ m 2 ⌉ \left \lceil \frac{m}{2} \right \rceil ⌈2m​⌉ 个奇儿子需要选 t ⊕ 1 t \oplus 1 t⊕1，另外的选 t t t。那么只需要将所有 d p s o n , t ⊕ 1 − d p s o n , t dp_{son,t \oplus 1} - dp_{son, t} dpson,t⊕1​−dpson,t​ 拿出来从大到小排序，选出前 ⌈ m 2 ⌉ \left \lceil \frac{m}{2} \right \rceil ⌈2m​⌉ 大，并把所有 d p s o n , t dp_{son, t} dpson,t​ 累加即可。
  2. 不存在 奇儿子：那么所有儿子的状态都只能是 t ⊕ 1 t \oplus 1 t⊕1，加起来就好了。

CODE:

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5 + 10; 
typedef long long LL;
int n, T, u, v, sz[N];
LL a[N], dp[N][2];
vector< int > E[N];
bool cmp(LL x, LL y) {
	return x > y;
}
void dfs(int x, int fa) {
	sz[x] = 1;
	if(E[x].empty()) {
		dp[x][0] = a[x];
		dp[x][1] = 0;
		return ;
	}
	bool flag = 0;
	for(auto v : E[x]) {
		if(v == fa) continue;
        dfs(v, x); sz[x] += sz[v];
        if(sz[v] & 1) flag = 1;
	}
	if(flag) { // 存在奇点   所有偶点取较大 
	    LL tmp = 0, tg = 0, th = 0;
	    int cnt = 0;
		vector< LL > g, h;
		for(auto v : E[x]) {
			if(v == fa) continue;
			if(sz[v] & 1) {
				g.pb(dp[v][0] - dp[v][1]);
				tg += dp[v][1];
				h.pb(dp[v][1] - dp[v][0]);
				th += dp[v][0];
				cnt ++;
			}
			else tmp += max(dp[v][0], dp[v][1]);
		}
		sort(g.begin(), g.end(), cmp);
		sort(h.begin(), h.end(), cmp);
		LL c = 0;
		for(int i = 1; i <= ((cnt & 1) ? (cnt + 1) / 2 : cnt / 2); i ++ ) c += h[i - 1];
		dp[x][0] = tmp + th + c + a[x];
		c = 0;
		for(int i = 1; i <= ((cnt & 1) ? (cnt + 1) / 2 : cnt / 2); i ++ ) c += g[i - 1];
		dp[x][1] = tmp + tg + c;
	}
	else {
		dp[x][0] = dp[x][1] = 0;
		dp[x][0] += a[x];
		for(auto v : E[x]) {
			if(v == fa) continue;
			dp[x][0] += dp[v][1];
			dp[x][1] += dp[v][0];
		}
	}
}
void solve() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
	for(int i = 1; i <= n; i ++ ) dp[i][0] = dp[i][1] = 0;	
	for(int i = 1; i <= n; i ++ ) {
		vector< int > tmp; swap(tmp, E[i]);
	}
	for(int i = 1; i < n; i ++ ) {
		scanf("%d%d", &u, &v);
		E[u].pb(v); E[v].pb(u);
	}
	dfs(1, 0);
	printf("%lld\n", dp[1][1]);
}
int main() {
	scanf("%d", &T);
	while(T -- ) {
		solve();
	}
	return 0;
}

2024 CCPC东北邀请赛 H. Meet（二分答案，树上公共祖先，树上差分）

在这里插入图片描述

题目

          分析：
          直接求解最优答案显然不好搞，我们发现答案越大越容易满足，因此具有单调性，可以二分答案。设 x x x 为二分的答案，考虑怎样检验：
在这里插入图片描述
          实际上这个问题等价于是否至少存在一个点 p p p，使得 p p p 作为根时所有点对到它们 l c a lca lca 的距离都小于 x x x。

          由于 u ， v u，v u，v 的 l c a lca lca 一定在它们的路径上，我们考虑选取不同点作为根时 u ， v u，v u，v 的 l c a lca lca 有什么规律。

          如果以红色点为树根，那么 u , v u,v u,v 的 l c a lca lca 就是 u − v u - v u−v 路径上红色点的祖先。也就是说：如果我们首先以任意一个点为根，那么检验时选取作为根的点在 u − v u-v u−v路径上哪个点的子树中，那个点就是真正的 l c a lca lca。如果选取的点在子树外，那么当前的 l c a lca lca 就是真正的 l c a lca lca。

          对于二分出的答案 x x x，我们可以对于点对中的每个点算出 路径上那些点可以作为 l c a lca lca。那么这些点子树中的点都可以作为选定根。我们把包含这些点的最小子树加 1 1 1，最后判断上是否有点的权值等于 2 × m 2 \times m 2×m 即可。

时间复杂度 O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)。

CODE：

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e5 + 10;
inline int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
	while(isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}
	return x * f;
}
int n, m, u, v, pu[N], pv[N], dfn[N], fat[N][25], dep[N], rk;
int L[N], R[N];
vector< int > E[N];
struct BIT {
	int c[N];
	void Clean() {memset(c, 0, sizeof c);}
	int lowbit(int x) {return x & -x;}
	void add(int x, int y) {for(; x < N; x += lowbit(x)) c[x] += y;}
	int ask(int x) {
		int res = 0;
		for(; x; x -= lowbit(x)) res += c[x];
		return res;
	}
}t;
void dfs0(int x, int fa) {
	dfn[x] = ++ rk; dep[x] = dep[fa] + 1;
	fat[x][0] = fa; L[x] = rk;
	for(int i = 1; i <= 20; i ++ ) fat[x][i] = fat[fat[x][i - 1]][i - 1];
	for(auto v : E[x]) {
		if(v == fa) continue;
		dfs0(v, x);
	} 
	R[x] = rk;
}
int LCA(int x, int y) {
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 20; i >= 0; i -- ) {
		if(dep[fat[x][i]] >= dep[y]) x = fat[x][i];
	}
	if(x == y) return x;
	for(int i = 20; i >= 0; i -- ) {
		if(fat[x][i] != fat[y][i]) x = fat[x][i], y = fat[y][i];
	}
	return fat[x][0];
}
int Kth(int x, int k) {
	for(int i = 20; i >= 0; i -- ) {
		if((k >> i) & 1) x = fat[x][i];
	}
	return x;
} 
void OP(int u, int v, int len) {
	int lca = LCA(u, v);
	if(dep[u] + dep[v] - 2 * dep[lca] <= len) t.add(1, 1);
	else if(dep[u] - dep[lca] > len) {
		int ancestor = Kth(u, len);
		t.add(L[ancestor], 1);
		t.add(R[ancestor] + 1, -1);
	}
	else {
		int ancestor = Kth(v, dep[v] - dep[lca] - (len + 1 - (dep[u] - dep[lca])));
		t.add(1, 1);
		t.add(L[ancestor], -1);
		t.add(R[ancestor] + 1, 1); 
	}
}
bool check(int len) {
	t.Clean();
	for(int i = 1; i <= m; i ++ ) {
		OP(pu[i], pv[i], len); OP(pv[i], pu[i], len);
	}
	for(int i = 1; i <= n; i ++ ) {
		if(t.ask(i) == m * 2) return 1;
	}
	return 0;
}
int main() {
	n = read(), m = read();
	for(int i = 1; i < n; i ++ ) {
		u = read(), v = read();
		E[u].pb(v); E[v].pb(u);
	}
	for(int i = 1; i <= m; i ++ ) {
		pu[i] = read(), pv[i] = read();
	}
	dfs0(1, 0);
	int l = 0, r = 1e5 + 10, mid, res = -1;
	while(l <= r) {
		mid = (l + r >> 1);
		if(check(mid)) res = mid, r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n", res);
	return 0;
}

2024 CCPC东北邀请赛 I. Password（动态规划）

在这里插入图片描述
题目

          分析：
          如果 [ i − k + 1 , i ] [i - k + 1, i] [i−k+1,i] 是一个 1 1 1 到 k k k 的排列，我们称 i i i 是一个 结尾。那么由于每个位置都需要在一个排列的区间中，因此有一个性质：两个结尾的距离一定不超过 k k k。有了这个性质我们就可以 d p dp dp 了。 设 d p i dp_{i} dpi​ 表示只考虑前 i i i 个位置，每个位置都是好的的并且第 i i i 和位置是一个 结尾 的序列数。转移考虑枚举上一个结尾：

d p i = ∑ j = 1 k d p i − j × g j dp_i = \sum_{j = 1}^{k} dp_{i -j} \times g_j dpi​=∑j=1k​dpi−j​×gj​

          这里 g j g_j gj​ 是转移系数。因为如果直接乘 j ！ j！ j！，那么一定会有重复。这是因为没有满足 i − j i - j i−j 是上一个结尾的转移条件。如果乘 j ！ j！ j！，那么会出现 ( i − j , i ) (i -j, i) (i−j,i) 之间某个位置成为了一个结尾的情况，这样就会多算。

          考虑 g j g_j gj​ 如何计算。思考 g j g_j gj​ 的意义：现在有一个排列，你要在后面接 j j j 个数字，使得最后一个位置作为右端点长度为 k k k 的区间形成一个排列，并且前面没有别的位置能作为右端点形成排列。那么根据 g j g_j gj​ 的含义来容斥求 g g g。

g i = i ! − ∑ j = 1 i − 1 g j g_i = i! - \sum_{j = 1}^{i - 1}g_j gi​=i!−∑j=1i−1​gj​

          这个式子可以理解为 总方案数减去不合法的方案数，其中 ∑ j = 1 i − 1 g j \sum_{j = 1}^{i -1}g_j ∑j=1i−1​gj​ 可以理解为 把不合法方案按照最前面能形成排列的位置分组 求贡献。因为 g j g_j gj​ 说明 j j j 位置能形成排列，但是前面不能形成形成排列。因此是一个天然的划分。这样就能把所有不合法方案不重不漏计算在内了。

时间复杂度 O ( n × k ) O(n \times k) O(n×k)

#include<bits/stdc++.h> 
using namespace std;
const int N = 1e5 + 10;
const int K = 1e3 + 10;
typedef long long LL;
const LL mod = 998244353;
int n, k;
LL dp[N], g[K], fac[N];
int main() {
	scanf("%d%d", &n, &k);
	if(k > n) {puts("0"); return 0;}
	else {
		fac[0] = 1LL;
		for(int i = 1; i < N; i ++ ) fac[i] = (fac[i - 1] * (1LL * i)) % mod;
		g[1] = 1LL;
		for(int i = 2; i <= k; i ++ ) {
			g[i] = fac[i];
			for(int j = 1; j < i; j ++ ) { // 枚举非法情况中，第一个提前匹配成排列的位置 
				g[i] = ((g[i] - g[j] * fac[i - j] % mod) % mod + mod) % mod;
			}
		}
		dp[k] = fac[k];
		for(int i = k + 1; i <= n; i ++ ) {
			for(int j = i - 1; j >= i - k; j -- ) {
				dp[i] = (dp[i] + dp[j] * g[i - j] % mod) % mod;
			}
		}
		printf("%lld\n", dp[n]);
	} 
	return 0;
}

2024 CCPC东北邀请赛 K. Tasks（贪心，构造）

在这里插入图片描述
题目

          分析：感觉思路挺不好想的。考虑按照烦躁值分组。首先 对于同组的，不能出现区间包含的情况。因为这样会让更大的那个区间不成立。然后就是在区间不互相包含的情况下，每个区间越长 越好。这样可以让烦躁值更大的区间更容易被包含。并且由于只需要让每个区间的烦躁值等于包含它的区间的最大烦躁值 + 1 +1 +1 即可，因此 不需要考虑当前区间是否会包含烦躁值很大的区间从而影响合法性。知道了这两个性质我们就可以对从小到大对每一层进行构造了。注意 每一层按照左端点排序后应从大到小 考虑，这样才能构造出最优的方案。具体细节参见代码。

时间复杂度： O ( n ) O(n) O(n)

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e6 + 10;
const int Limit = 1e6;
typedef pair< int, int > PII;
int n, l[N], b[N];
vector< int > F[N];
map< PII, int > ans;
inline int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
	while(isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}
	return x * f;
}
void calc(int depth) {
	if(depth == 0) {
		int now = Limit;
		for(int i = F[depth].size() - 1; i >= 0; i -- ) {
			ans[make_pair(depth, F[depth][i])] = now;
			now --;
		}
	}
	else {
		if(F[depth - 1].empty()) {
			puts("-1");
			exit(0);
		}
		int nl = F[depth - 1].size() - 1; int nr = ans[make_pair(depth - 1, F[depth - 1][nl])];
		for(int i = F[depth].size() - 1; i >= 0; i -- ) {
			int p = F[depth][i];
			while(nl >= 0 && p < F[depth - 1][nl]) {
				nl --;
				if(nl != -1) nr = min(nr, ans[make_pair(depth - 1, F[depth - 1][nl])]);
			}
			if(nl == -1) {puts("-1"); exit(0);}
			else {
				if(p == F[depth - 1][nl] && nr == ans[make_pair(depth - 1, F[depth - 1][nl])]) nr --;
				if(nr >= p) {
					ans[make_pair(depth, p)] = nr;
					nr --;
				}
				else {
					puts("-1");
					exit(0);
				}
			}
		}
	}
}
int main() {
	n = read();
	for(int i = 1; i <= n; i ++ ) {
		scanf("%d%d", &l[i], &b[i]);
		F[b[i]].pb(l[i]);
	}
	for(int i = 0; i <= Limit; i ++ ) {
		sort(F[i].begin(), F[i].end());
		for(int j = 1; j < F[i].size(); j ++ ) {
			if(F[i][j] == F[i][j - 1]) {
				puts("-1");
				return 0;
			}
		}
	}
	for(int i = 0; i <= Limit; i ++ ) {
		if(F[i].empty()) continue;
		else calc(i);
	}
	for(int i = 1; i <= n; i ++ ) {
		printf("%d\n", ans[make_pair(b[i], l[i])]);
	}
	return 0;
}

2024 CCPC东北邀请赛 L. Bracket Generation（组合数学，数数）

在这里插入图片描述
题目

          分析：连续的一对的 ( ( ( 和 ) ) )，那它肯定是由一个 1 1 1 操作产生的，其余的左括号和右括号肯定都是由 2 2 2 操作产生。我们注意到所有的 2 2 2 操作都有一个限制，那就是 必须在它括住的最后一个 1 1 1 后才能使用。因此我们可以统计出有多少个 1 1 1 操作，并统计出每个 1 1 1 操作由多少个 所属的 2 2 2 操作。这里 所属 就是必须在这个 1 1 1 后才能出现的意思。那么对于每个 1 1 1 操作内部的 2 2 2，首先有一个 阶乘 的贡献，表示内部不同的顺序。由于 1 1 1 操作只能向后面加，所以所有的 1 1 1 操作的顺序是定的，就是从左到右的顺序。我们只需要再累乘起分别插入每组 2 2 2 操作的贡献即可。

时间复杂度 O ( n ) O(n) O(n)。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
const LL mod = 998244353;
int n, tot, cnt[N];
LL fac[N], inv[N], res;
char str[N];
LL Pow(LL x, LL y) {
	LL res = 1LL, k = x;
	while(y) {
		if(y & 1) res = (res * k) % mod;
		y >>= 1;
		k = (k * k) % mod;
	}
	return res;
}
LL C(int n, int m) {
	return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {
	scanf("%s", str + 1);
	n = strlen(str + 1);
	fac[0] = 1LL;
	for(int i = 1; i < N; i ++ ) fac[i] = fac[i - 1] * (1LL * i) % mod;
	inv[N - 1] = Pow(fac[N - 1], mod - 2LL) % mod;
	for(int i = N - 2; i >= 0; i -- ) inv[i] = inv[i + 1] * (1LL * (i + 1LL)) % mod; 
	for(int i = 1; i <= n; i ++ ) {
		if(str[i] == '(' && str[i + 1] == ')') {
			tot ++; int c = 0;
			for(int j = i + 2; j <= n; j ++ ) {
				if(str[j] == ')') c ++;
				else break;
			}
			cnt[tot] = c;
		}
	}
	res = 1LL; int room = 0;
	for(int i = tot; i >= 1; i -- ) {
		res = (res * fac[cnt[i]]) % mod; // 内部2的贡献 
		res = res * C(room + cnt[i], cnt[i]) % mod;
		room = room + cnt[i] + 1;
	}
	printf("%lld\n", res);
	return 0;
}

2024 CCPC东北邀请赛 G. Diamond（根号分治）

在这里插入图片描述
题目

          分析：比较难的一道题。我们发现如果每次询问的 p p p 和 q q q 数量比较少，那么每次询问就可以暴力做。如果比较多，那么这样的 p p p 或者 q q q 的数量就比较少。这启示我们 根号分治。

          注意到逆序对就是 小数前面的大数数量。我们给数量大于 n \sqrt{n} n ​ 的数编号，处理出 f i , j f_{i, j} fi,j​ 表示第 i i i 个位置前面编号为 j j j 的数字个数，这个可以在 O ( n n ) O(n\sqrt{n}) O(nn ​) 的复杂度内处理出来。 然后我们处理出 S i , j S_{i, j} Si,j​ 表示前 i i i 个位置里每个值为 a i a_i ai​ 的位置前面编号为 j j j 的数字数量 的和。这个可以对每个位置记一个前驱求出来。最后计算答案是简单的：只需要 S S S 数组的前缀相减再减去 [ 1 , l − 1 ] [1, l-1] [1,l−1] 对 [ l , r ] [l, r] [l,r] 的贡献即可。比较恶心的是这道题卡空间，可以将阈值设大来减小大数的数量。这样可以优化空间。

时间复杂度 O ( n n ) O(n\sqrt{n}) O(nn ​)。

CODE：

          还没调过就不放了。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/793515.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

分布式应用系统设计：即时消息系统

分布式应用系统设计：即时消息系统

即时消息(IM)系统&#xff0c;涉及&#xff1a;站内消息系统 组件如下&#xff1b; 客户端&#xff1a; WEB页面&#xff0c;IM桌面客户端。通过WebSocket 跟ChatService后端服务连接 Chat Service&#xff1a; 提供WebSocket接口&#xff0c;并保持跟“客户端”状态的维护。…
阅读更多...
彻底解决找不到d3dcompiler_43.dll问题，总结几种有效的方法

彻底解决找不到d3dcompiler_43.dll问题，总结几种有效的方法

运行软件时提示找不到d3dcompiler_43.dll无法继续执行代码&#xff0c;如何解决&#xff1f;解决这个问题的方法有很多&#xff0c;但具体问题需要具体分析&#xff0c;有些方法可能并不适用于解决d3dcompiler_43.dll的问题。因此&#xff0c;需要根据实际情况来选择合适的方法…
阅读更多...
8627 数独

8627 数独

为了判断数独解是否合法&#xff0c;我们需要遵循以下步骤&#xff1a; 1. **检查每一行**&#xff1a;确保1到9每个数字在每一行中只出现一次。 2. **检查每一列**&#xff1a;确保1到9每个数字在每一列中只出现一次。 3. **检查每个3x3的宫**&#xff1a;确保1到9每个数字在…
阅读更多...
模式物种葡萄基因组（T2T）--文献精读29

模式物种葡萄基因组（T2T）--文献精读29

The complete reference genome for grapevine (Vitis vinifera L.) genetics and breeding 葡萄&#xff08;Vitis vinifera L.&#xff09;遗传学和育种的完整参考基因组 摘要 葡萄是全球最具经济重要性的作物之一。然而&#xff0c;以往版本的葡萄参考基因组通常由成千上万…
阅读更多...
星辰考古：TiDB v4.0 进化前夜

星辰考古：TiDB v4.0 进化前夜

前情回顾TiDB v4 时间线TiDB v4 新特性 TiDBTiKVPDTiFlashTiCDCTiDB v4 兼容性变化 TiDBTiKVPD其他TiDB 社区互助升级活动TiDB 3.0.20 升级到 4.0.16 注意事项升级速览直观变化总结素材来源&#x1f33b; 往期精彩 ▼ 前情回顾 在前面的章节中&#xff0c;我们共同梳理了 TiDB …
阅读更多...
【刷题汇总 -- 最长回文子串、买卖股票的最好时机(一)、[NOIP2002 普及组] 过河卒】

【刷题汇总 -- 最长回文子串、买卖股票的最好时机(一)、[NOIP2002 普及组] 过河卒】

C日常刷题积累 今日刷题汇总 - day0101、最长回文子串1.1、题目1.2、思路1.3、程序实现 2、买卖股票的最好时机(一)2.1、题目2.2、思路2.3、程序实现2.4、程序实现 -- 优化 3、[NOIP2002 普及组] 过河卒3.1、题目3.2、思路3.3、程序实现 -- dp 4、题目链接 今日刷题汇总 - day0…
阅读更多...
一个便捷的web截图库~【送源码】

一个便捷的web截图库~【送源码】

随着时间的发展&#xff0c;前端开发的范围越来越广&#xff0c;能够实现的功能也越来越多&#xff0c;要实现的功能也五花八门&#xff0c;今天就给大家介绍一个web截图库,让前端也能实现截图功能—— js-web-screen-shot js-web-screen-shot js-web-screen-shot 是一个基于 …
阅读更多...
Linux服务器CPU占用率达到100%排查思路

Linux服务器CPU占用率达到100%排查思路

1、找到最耗CPU的进程pid&#xff0c;执行命令 top 2、找到最耗CPU的线程tid // 执行 top -Hp [pid] 定位应用进程对应的线程 tid // 按shift p 组合键&#xff0c;按照CPU占用率排序 > top -Hp 14246 3、将线程pid转化为16进制 // printf "%x\n" [tid] 将tid…
阅读更多...
Redis+Caffeine 实现两级缓存实战

Redis+Caffeine 实现两级缓存实战

RedisCaffeine 实现两级缓存 背景 ​ 事情的开始是这样的&#xff0c;前段时间接了个需求&#xff0c;给公司的商城官网提供一个查询预计送达时间的接口。接口很简单&#xff0c;根据请求传的城市仓库发货时间查询快递的预计送达时间。因为商城下单就会调用这个接口&#xff…
阅读更多...
camunda最终章-springboot

camunda最终章-springboot

1.实现并行流子流程 1.画图 2.创建实体 package com.jmj.camunda7test.subProcess.entity;import lombok.AllArgsConstructor; import lombok.Data; import lombok.NoArgsConstructor;import java.io.Serializable; import java.util.ArrayList; import java.util.List;Data …
阅读更多...
ComfyUI+MuseV+MuseTalk图片数字人

ComfyUI+MuseV+MuseTalk图片数字人

电脑配置 GPU12G&#xff0c;如果自己电脑配置不够&#xff0c;选择云gpu&#xff0c;我就是用的这个&#xff0c;自己电脑太老配置跟不上 环境&#xff1a; Python 3.11.8 torch 2.2.1 cuda_12.1 资源提供&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1_idZbF…
阅读更多...
开始Linux之路(暑假提升)

开始Linux之路(暑假提升)

人生得一知己足矣&#xff0c;斯世当以同怀视之。——鲁迅 Linux操作系统简单操作指令 1、ls指令2、pwd命令3、cd指令4、mkdir指令(重要)5、whoami命令6、创建一个普通用户7、重新认识指令8、which指令9、alias命令10、touch指令11、rmdir指令 及 rm指令(重要)12、man指令(重要…
阅读更多...
【视频】R语言广义加性模型GAMs非线性效应、比较分析草种耐寒性实验数据可视化

【视频】R语言广义加性模型GAMs非线性效应、比较分析草种耐寒性实验数据可视化

全文链接&#xff1a;https://tecdat.cn/?p36979 原文出处&#xff1a;拓端数据部落公众号 广义加法模型&#xff08;Generalized Additive Models, GAMs&#xff09;作为一种高度灵活的统计工具&#xff0c;显著扩展了广义线性模型&#xff08;Generalized Linear Models, …
阅读更多...
C基础day9

C基础day9

一、思维导图 二、课后练习 1> 使用递归实现 求 n 的 k 次方 #include<myhead.h>int Pow(int n,int k) {if(k 0 ) //递归出口{return 1;}else{return n*Pow(n,k-1); //递归主体} }int main(int argc, const char *argv[]) {int n0,k0;printf("请输入n和k:&…
阅读更多...
Python统计实战：时间序列分析之绘制观测值图和按年折叠图

Python统计实战：时间序列分析之绘制观测值图和按年折叠图

为了解决特定问题而进行的学习是提高效率的最佳途径。这种方法能够使我们专注于最相关的知识和技能&#xff0c;从而更快地掌握解决问题所需的能力。 &#xff08;以下练习题来源于《统计学—基于Python》。请在Q群455547227下载原始数据。&#xff09; 练习题 下表是某地区2…
阅读更多...
复杂度（上卷）

复杂度（上卷）

前言 在正式进入今天的主题之前&#xff0c;我们不妨先来回顾一下初步学习数据结构后必须知道的概念。&#x1f3b6; 数据结构 数据结构是计算机存储、组织数据的方式&#xff0c;指相互间存在一种或多种特定关系的数据元素的集合。 &#xff08;没有一种单一的数据结构能够…
阅读更多...
如何保证RocketMQ消息不丢失

如何保证RocketMQ消息不丢失

rocket mq在生产阶段、Brocker存储阶段、消费阶段都会出现消息丢失。 1、生产者防止丢失消息。 a.同步阻塞的方式发送消息&#xff0c;加上失败重试机制&#xff0c;可能broker存储失败&#xff0c;可以通过查询确认 b.异步发送需要重写回调方法&#xff0c;检查发送结果 c…
阅读更多...
人脸表情识别Facial Expression Recognition基于Python3和Keras2（TensorFlow后端）

人脸表情识别Facial Expression Recognition基于Python3和Keras2（TensorFlow后端）

人脸表情识别项目是一个结合了计算机视觉和深度学习技术的高级应用&#xff0c;主要用于分析和理解人类面部表情所传达的情感状态。这样的系统可以用于多种场景&#xff0c;比如情绪分析、用户交互、市场调研、医疗诊断以及人机接口等领域。 一个典型的人脸表情识别项目可以分…
阅读更多...
kafka与zookeeper的SSL认证教程

kafka与zookeeper的SSL认证教程

作者 乐维社区&#xff08;forum.lwops.cn&#xff09;许远 在构建现代的分布式系统时&#xff0c;确保数据传输的安全性至关重要。Apache Kafka 和 Zookeeper 作为流行的分布式消息队列和协调服务&#xff0c;提供了SSL&#xff08;Secure Sockets Layer&#xff09;认证机制&…
阅读更多...
红酒与威士忌：跨界碰撞的味觉火花

红酒与威士忌：跨界碰撞的味觉火花

在品酒的世界里&#xff0c;红酒与威士忌&#xff0c;两者如同两位优雅的舞者&#xff0c;各自在舞台上闪耀着不同的光芒。然而&#xff0c;当它们相遇&#xff0c;那跨界碰撞的味觉火花&#xff0c;却仿佛一场不可预测的华丽盛宴&#xff0c;让人为之倾倒。 一、红酒的浪漫与威…
阅读更多...
最新文章

Copyright @ 2022~2023