Atcoder ABC 401

C

给定正整数

N

和

K

。按如下所示定义长度为

N+1

的序列

A = (A_0, A_1, \ldots, A_N)

：

$A_i = 1， 0 \leq i < K$
$A_i=A_{i-K}+A_{i-K+1}+\ldots+A_{i-1}$ , $K \le i$ 。

求

A_N

模

10^9

。

思路：第k项开始，后面每一项计算的整体变化很少，维护当前的和，减去最前面一项。注意：因为取模的原因，导致后面的计算会出现负数，所以计算时，把模数加上。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
const int mod = 1e9;
int n, k;
long long a[N],s;
signed main(){
	scanf("%lld%lld", &n, &k);
	for(int i = 0; i < k; i++) a[i] = 1;
	s = k;
	for(int i = k; i <= n; i++){
		a[i] = s;
		s = (s + a[i] - a[i - k] + mod) % mod;
	}
	//for(int i = 0; i <= n; i++)
	// 	cout << i <<':' << a[i] << endl;
	printf("%lld", a[n]);
	return 0;
}

D

一个长度为

N

的字符串

S

，其中包含字符.，o，和？. 在

S

中，可以通过使用.或o，替换每个？.

设

X

是满足以下所有条件的字符串的集合：

o数量正好是 $K$ 。
没有两个o是相邻的。

保证

X

非空。

输出长度为

N

且满足以下条件的字符串

T

（设

T_i

表示

T

的第

i

个字符）:

如果 $X$ 中每个字符串的第 $i$ 个字符是.，然后是 $T_i=$ ..
如果 $X$ 中每个字符串的第 $i$ 个字符是o，则 $T_i=$ 为o。
如果 $X$ 同时包含一个字符串的第 $i$ 个字符为., 一个字符串的第 $i$ 个字符为o的字符串，则 $T_i=$ ?

思路：S的?处能否确定为.或者是o, 不能确定则输出为?

预处理，对于输入字符串中的每个?,如果与其相邻位置有确定的字符o，那么这个?肯定是.,可以直接修改。

同时，对于每一个确定的字符o,我们可以直接将其从数量中减去，之后让

K

表示还需要让多少个字符？修改成o.

特判情况：若k == 0, 则必须将所有?替换成.
只有当现存的每一段连续?都应该放满字符o,也就是无法让o随意调正位置，我们才能确定?的最终字符。所以需要求出当前剩余的?最多能替换成多少o。
计算每段? 可放 o 的最大数量

? 个数为偶数（设数量为t ）：o放置有两种形式（“o.o.o.o.” 或者 “.o.o.o.o” ），每个位置字符不能确定，能放o的最大数量为 $(\frac{t}{2})$ .

?个数为奇数（设数量为 t ）：第一个和最后一个字符一定是 'o' ，每个位置字符可确定，能放 “o” 的最大数量为 $(\lceil\frac{t}{2}\rceil=\lfloor\frac{t}{2}\rfloor + 1)$ 。

确定最终字符 循环遍历字符串，找出最多还能放的 o 字符数量。若该数量等于 K ，按照上述规则，将每段数量为奇数的? 字符改为确定的字符。

E

给定一个具有

N

个顶点和

M

条边的无向图。顶点编号为

1,2,\ldots,N

，第

i

条边

(1 \le i \le M)

连接顶点

u_i

和

v_i

。

对于每个

k = 1,2,\ldots,N

，解决以下问题：

考虑以下操作。

选择一个顶点，并删除该顶点及其关联的所有边。

判断是否可以重复此操作以满足以下条件：

从顶点 $1$ 出发，通过边能够到达的顶点集恰好由 $k$ 个顶点 $(1, 2, \ldots, k)$ 组成。

如果可能，找出这样做所需的最小操作数。

思路:

对于每个

k

,我们需要满足以下条件：

1：连通性：顶点1到

k

必须构成一个连通块

2：隔离性：这些顶点不能与任何编号大于k的顶点相连（对应的顶点必须删除）

动态维护：按

k

从小到大处理，逐步构建连通块，并记录需要删除的顶点，放入set中维护。具体步骤：

处理到k时，若k的邻接点

v

：

$v < k$ ，则 $merge(v, k)$
$v \geq k$ ，则将v点放入集合set中

若当前顶点1的连通块大小不为

k

，则输出

-1

. 否则输出集合大小。

F

两棵树：树

1

，其

N_1

个顶点的编号为

1

到

N_1

。以及具有编号为

1

到

N_2

的

N_2

顶点的树

2

。树

1

的第

i

条边双向连接顶点

u_{1,i}

和

v_{1,i}

，树

2

的第

i

条边双向连接顶点

u_{2,i}

和

v_{2,i}

。可以在树

1

的顶点

i

和树

2

的顶点

j

之间添加双向边以获得单个树。

设

f(i,j)

是这棵树的直径。

查找

\displaystyle \sum_{i=1}^{N_1}\sum_{j=1}^{N_2} f(i,j)

。

这里，树的两个顶点之间的距离是在它们之间移动所必须使用的最小边数，

树的直径是两个顶点之间的最大距离。

思路:

给定两棵树，将两棵树通过添加一条边后形成新树，求所有可能的链接方式下新树的直径的总和。

1.树的直径与最远距离：

树的直径是树中最长路径的长度。对于每个节点，其到直径两端点的距离的较大值即为该节点的最远距离。
预处理每棵树中每个节点的最远距离 $d$ ，并排序。

2.合并后的直径：

合并后的新树直径可能为原两树直径的最大值，或由两树中某两个节点的最远距离加上新边构成的新路径长度。
对于每对节点 $(i,j)$ ，新直径为三者最大值： $max(D1,D2,d1[i]+d2[j]+1)$ ，其中 $D1$ 和 $D2$ 为原两树直径。

3.计算总和：

对树 $2$ 的 $d$ 数组排序并预处理后缀和，且 $M=max(D1,D2)$ 。
对树 $1$ 中的每个节点 $i$ ，计算需要树 $2$ 中满足 $d2[j]≥(M−d1[i]−1)$ 的节点数及其距离和，将贡献分为两部分计算。

做法

1.预处理每棵树的节点最远距离：

通过两次 $DFS$ 找到树的直径端点，并计算每个节点到两端点的距离，取最大值作为该节点的 $d$ 值。
将 $d$ 数组排序，并计算后缀和数组 $s$ 。

2.计算总和：

遍历树 $1$ 的每个节点 $i$ ，确定树 $2$ 中满足条件的节点范围。
使用二分查找确定分界点，或者双指针维护，结合后缀和数组快速计算两部分贡献。
前半部分由于不能形成新的直径，所以直径还是原来的。
后半部分由于形成新的直径，就是 $d1[i]+d2[j]+1$ 。

CPP

#include <bits/stdc++.h>
#define pb emplace_back

using namespace std;
typedef long long ll;

typedef pair<ll, ll> pii;

const int maxn = 200100;

ll n1, n2, a[maxn], b[maxn], c[maxn], d[maxn];
vector<int> G1[maxn], G2[maxn];

ll mxd, U;

void dfs(int u, int fa, int d, ll *a) {
	if (d > mxd) {
		mxd = d;
		U = u;
	}
	a[u] = d;
	for (int v : G1[u]) {
		if (v == fa) 
			continue;
		dfs(v, u, d + 1, a);
	}
}

void dfs2(int u, int fa, int d, ll *a) {
	if (d > mxd) {
		mxd = d;
		U = u;
	}
	a[u] = d;
	for (int v : G2[u]) {
		if (v == fa) 
			continue;
		dfs2(v, u, d + 1, a);
	}
}

void solve() {
	scanf("%lld", &n1);
	for (int i = 1, u, v; i < n1; ++i) {
		scanf("%d%d", &u, &v);
		G1[u].pb(v);
		G1[v].pb(u);
	}
	scanf("%lld", &n2);
	for (int i = 1, u, v; i < n2; ++i) {
		scanf("%d%d", &u, &v);
		G2[u].pb(v);
		G2[v].pb(u);
	}
	// 计算第一棵树每个点都能走的最远距离和直径 
	mxd = U = -1;
	dfs(1, -1, 0, a);//先找出第一个直径的端点 
	int u = U;
	mxd = U = -1;
	dfs(u, -1, 0, a);//再找出第二个直径的端点 
	ll x = mxd;
	int v = U;
	dfs(v, -1, 0, b);//每个点到第二个端点的距离 
	
	// 计算第二棵树每个点都能走的最远距离和直径 
	// 方法同上 
	mxd = U = -1;
	dfs2(1, -1, 0, c);
	u = U;
	mxd = U = -1;
	dfs2(u, -1, 0, c);
	x = max(x, mxd);
	v = U;
	dfs2(v, -1, 0, d);
	for (int i = 1; i <= n1; ++i)  
		a[i] = max(a[i], b[i]);// 取第一个端点还是第二个端点 
	
	for (int i = 1; i <= n2; ++i) 
		c[i] = max(c[i], d[i]);
	
	ll ans = 0;
	sort(a + 1, a + n1 + 1);
	sort(c + 1, c + n2 + 1);
	ll s = 0;
	for (int i = 1; i <= n2; ++i) 
		s += c[i];
	
	for(int i = n1, j = 0; i >= 1; i--){ // j要从0开始，因为有可能没有一个点能够满足<=x 
		while(j + 1 <= n2 && a[i] + c[j + 1] + 1 <= x){
			s -= c[j + 1];
			j++;
		}
		ans += x * j + (a[i] + 1) * (n2 - j) + s;
	}
	
	printf("%lld\n", ans);
}

int main() {
	solve();
	return 0;
}

文章操作

C

D

E

F

相关推荐

评论

Atcoder ABC 401