Codeforces Round #769 (Div. 2)D,E
D.New Year Concert
传送门
题目大意：
一个长为
N
(
1
≤
N
≤
2
×
1
0
5
)
N(1\leq N\leq2\times 10^5)
N(1≤N≤2×105)的序列
A
A
A，对于
[
l
,
r
]
[l,r]
[l,r]，如果
g
c
d
(
A
l
,
A
l
+
1
,
.
.
.
,
A
r
)
=
r
−
l
+
1
gcd(A_{l},A_{l+1},...,A_{r})=r-l+1
gcd(Al,Al+1,...,Ar)=r−l+1，称这一段不好，每次操作可以将数列上任意一个位置上的数字替换为任意一个正整数。对序列的每个前缀，求出最少操作多少次可以使该前缀上没有不好的段。
思路：
因为可以修改为任意的正整数，所以我们只要将
A
i
A_{i}
Ai修改为一个很大的素数，那么所有包含
i
i
i的不好的段都会变好。
再考虑从每个左端点
l
l
l开始的段，显然随着
r
r
r的增加，本段的
g
c
d
gcd
gcd不增，而
r
−
l
+
1
r-l+1
r−l+1会逐渐增大，也就是
g
c
d
gcd
gcd与
r
−
l
+
1
r-l+1
r−l+1最多有一个交点，也就是对于每个左端点，最多有
1
1
1个不好的段，不好的段总数最多为
N
N
N。
我们可以用
S
T
ST
ST表来求区间
g
c
d
gcd
gcd，然后枚举每个左端点二分求出所有不好的段。
接下来就是求最少修改多少个点可以使所有不好的段消失，我们可以对求出的所有不好的段按右端点排序，按右端点从小到大枚举，如果该段仍然存在，就修改该段右端点上的元素，同时所有包含该点的不好的段也都消失。最后对表示每个点是否被修改的数组求一个前缀和即为答案。
代码：
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
//#define int LL
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#pragma warning(disable :4996)
const double eps = 1e-8;
const LL mod = 1000000007;
const LL MOD = 998244353;
const int maxn = 200010;
int N, A[maxn], ST[maxn][30];
vector<PII>seg;
int ans[maxn];
bool cmp(const PII& a, const PII& b)
{
if (a.second == b.second)
return a.first < b.first;
return a.second < b.second;
}
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
void GCD_init(int n)
{
for (int i = 0; i < n; i++)
ST[i][0] = A[i];
for (int j = 1; (1 << j) <= n; j++)
{
for (int i = 0; i + (1 << j) - 1 < n; i++)
ST[i][j] = gcd(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
}
}
int GCD(int l, int r)//[l,r)
{
if (l >= r)
return 0;
int k = floor(log2(r - l));
return gcd(ST[l][k], ST[r - (1 << k)][k]);
}
void solve()
{
GCD_init(N + 1);
for (int i = 1; i <= N; i++)
{
int lo = i, hi = N + 1;
while (hi - lo > 1)
{
int mid = (lo + hi) / 2;
if (GCD(i, mid + 1) >= mid + 1 - i)
lo = mid;
else
hi = mid;
}
if (GCD(i, lo + 1) == lo + 1 - i)
seg.push_back(PII(i, lo));
}
sort(seg.begin(), seg.end(), cmp);
int lst = 0;
for (auto& s : seg)
{
int l = s.first, r = s.second;
if (l <= lst)
continue;
lst = r;
ans[r] = 1;
}
for (int i = 1; i <= N; i++)
{
ans[i] += ans[i - 1];
cout << ans[i] << ' ';
}
cout << endl;
}
int main()
{
IOS;
cin >> N;
for (int i = 1; i <= N; i++)
cin >> A[i];
solve();
return 0;
}
E.Distance Tree
题目大意：
给定一颗以
1
1
1为根的有
N
(
N
≤
3
×
1
0
5
)
N(N\leq3\times10^5)
N(N≤3×105)个节点的树，每条边长度为
1
1
1，
d
(
v
)
d(v)
d(v)为
1
1
1到
v
v
v的最短距离，设
f
(
x
)
f(x)
f(x)为添加完一条长为
x
x
x的边之后最小的所有
d
(
v
)
d(v)
d(v)的最大值，求
f
(
1
)
∼
f
(
N
)
f(1)\sim f(N)
f(1)∼f(N)。
思路：
显然新加入的边一端连在
1
1
1是最优的。我们可以考虑对于每个
f
(
x
)
f(x)
f(x)来二分求得，我们设
f
m
i
d
f_{mid}
fmid为在树中两个深度
>
m
i
d
>mid
>mid的节点的最远距离（如果
m
i
d
≥
mid\geq
mid≥树的深度，显然最终的答案
≤
m
i
d
\leq mid
≤mid），那么，我们将新加入边的另一端连接到这一条路径的中点上，就可以使
d
(
v
)
d(v)
d(v)的最大值最小，此时的最大值为
⌈
f
m
i
d
2
⌉
+
x
\lceil \frac{f_{mid}}{2}\rceil + x
⌈2fmid⌉+x，如果这个值
≤
m
i
d
\leq mid
≤mid，就说明最终的答案
≤
m
i
d
\leq mid
≤mid，否则
>
>
>。
对于
f
m
i
d
f_{mid}
fmid，我们可以通过
d
f
s
dfs
dfs预处理出来。对于每个节点
v
v
v，我们可以找到其深度最大的两棵子树，记深度为
a
v
,
b
v
(
b
v
≤
a
v
)
a_{v},b_{v}(b_{v}\leq a_{v})
av,bv(bv≤av)，若
b
v
>
0
b_{v}>0
bv>0，则
f
b
v
−
1
=
m
i
n
(
f
b
v
−
1
,
a
v
+
b
v
−
2
×
d
e
p
t
h
v
)
f_{b_{v}-1}=min(f_{b_{v}-1},a_{v}+b_{v}-2\times depth_{v})
fbv−1=min(fbv−1,av+bv−2×depthv)，即用深度为
a
v
,
b
v
a_{v},b_{v}
av,bv两点的路径长度去更新
f
b
v
−
1
f_{b_{v}-1}
fbv−1，如果
a
v
,
b
v
a_{v},b_{v}
av,bv中某个值不存在，就将其直接设为
d
e
p
t
h
v
depth_{v}
depthv即可。最后再从
N
−
2
∼
0
N-2\sim 0
N−2∼0遍历，令
f
i
=
m
a
x
(
f
i
,
f
i
+
1
)
f_{i}=max(f_{i},f_{i+1})
fi=max(fi,fi+1)即可，这样每个
f
i
f_{i}
fi就会被所有
j
>
i
j>i
j>i的
f
j
f_{j}
fj更新到。
代码：
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
//#define int LL
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#pragma warning(disable :4996)
const double eps = 1e-8;
const LL mod = 1000000007;
const LL MOD = 998244353;
const int maxn = 300010;
vector<int>G[maxn];
int depth[maxn], maxdep;
int T, N;
int a[maxn], b[maxn];
int f[maxn];
void add_edge(int from, int to)
{
G[from].push_back(to);
G[to].push_back(from);
}
void dfs(int v, int d)
{
depth[v] = d;
maxdep = max(maxdep, depth[v]);
a[v] = b[v] = d;
for (int i = 0; i < G[v].size(); i++)
{
int to = G[v][i];
if (depth[to] == -1)
{
dfs(to, d + 1);
if (a[to] > a[v])
{
b[v] = a[v];
a[v] = a[to];
}
else if (a[to] == a[v])
b[v] = a[to];
else if (a[to] > b[v])
b[v] = a[to];
}
}
if (b[v] > 0)
f[b[v] - 1] = max(f[b[v] - 1], a[v] + b[v] - 2 * depth[v]);
}
bool Check(int x, int ans)
{
if (ans >= maxdep || (f[ans] + 1) / 2 + x <= ans)
return true;
return false;
}
void solve()
{
dfs(1, 0);
for (int i = N - 2; i >= 0; i--)
f[i] = max(f[i], f[i + 1]);
for (int x = 1; x <= N; x++)
{
int lo = -1, hi = N;
while (hi - lo > 1)
{
int mid = (hi + lo) / 2;
if (Check(x, mid))
hi = mid;
else
lo = mid;
}
cout << hi << ' ';
}
cout << endl;
}
int main()
{
IOS;
cin >> T;
while (T--)
{
cin >> N;
maxdep = -1;
for (int i = 1; i <= N; i++)
G[i].clear();
memset(depth, -1, sizeof(depth));
memset(f, -1, sizeof(f));
int u, v;
for (int i = 1; i < N; i++)
{
cin >> u >> v;
add_edge(u, v);
}
solve();
}
}
最新文章
- Drawable实战解析：Android XML shape 标签使用详解（apk瘦身，减少内存好帮手）
- css3线条围绕跑马+jquery打字机效果
- Spring-Context之七:使用p-namesapce和c-namespace简化bean的定义
- centos7 静态ip设置
- UIProgressView和UISlider
- html中input输入框屏蔽鼠标右键
- 【DFS/BFS】NYOJ-58-最少步数（迷宫最短路径问题）
- MySQL 错误日志(Error Log)
- NOI十连测 第四测 T2
- 初识 Cloudera Impala
- IDL 矩阵运算
- LeetCode 628. Maximum Product of Three Numbers （最大三数乘积）
- vim 使用学习操作
- 微信小程序中样式问题
- C#4.0 HTTP协议无法使用TLS1.2的问题
- atom编辑器使用“apm install”无法响应的解决方案
- CentOS7 下 keepalived 的安装和配置
- 法线从object space到eye space的转换((normal matrix)
- 007 jquery过滤选择器-----------（屬性过滤选择器）
- EF的学习