|
梦想赛道
题意：
给定一个棵树，构造一个图，满足这棵树是图上的严格次小生成树，图上可以有重边，输出图的最小总权值和即可
思路：
因为可以有重边，还要最小化总权值和，我们可以考虑给权值次大的边加一条权值为
1
1
1 的边，但是如果这棵树所有边的权值都是
1
1
1，那么就无法构造
寒冬信使
题意：
n
n
n 个格子排成一排，每个格子是黑色或者白色的。
有双方在格子上进行博弈，根据先后手轮流进行操作，每次操作方可以选择一个白色格子并且翻转这个格子和它前面一个格子的颜色（如果选择的是第一个格子则只翻转这个格子的颜色）。
无法操作者败，求是否先手必胜。
思路：
可以发现答案只和操作数的奇偶性有关
模拟可以发现如果白块是偶数个，那么无论怎么操作消除白块，最后操作数的奇偶性和两两消除所有白块的奇偶性相同，
如果是奇数个，最后剩下一个，需要移动到第一块再消除
统计消除白块的操作数即可
与战锤
思路：
每次需要先把盾打破才能造成伤害，盾刷新的周期是
k
k
k，也就是我们每轮有
k
k
k 次攻击机会
因为每轮是任选子序列进行攻击，因为我们可以排序，每次选当前没有选过的前
k
k
k 大进行攻击
每次选出
k
k
k 个
复杂度
O
(
∑
k
=
1
n
n
k
)
=
O
(
n
l
o
g
n
)
O(\sum_{k=1}^n\frac{n}{k})=O(nlogn)
O(∑k=1n?kn?)=O(nlogn)
code：
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mem(x, d) memset(x, d, sizeof(x))
#define eps 1e-6
using namespace std;
const int maxn = 2e6 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
ll a[maxn];
ll sum[maxn];
void work()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + 1 + n, greater<ll>());
for(int i = 1; i <= n; ++i) sum[i] = sum[i-1] + a[i];
ll ans = 0;
for(int k = 1; k <= n; ++k){
ans = 0;
for(int i = 1; i <= n; i += k){
int j = i + k - 1;
j = min(j*1ll, n);
if(sum[j] - sum[i-1] - m > 0)
ans += sum[j] - sum[i-1] - m;
}
cout << ans << endl;
}
}
int main()
{
ios::sync_with_stdio(0);
work();
return 0;
}
妄想集合
题意：
初始有
n
n
n 个集合，每个集合中有一个数
a
i
a_i
ai?，
m
m
m 个操作，操作有两种：
Q
u
a
n
t
??
l
??
r
??
x
Quant \ \ l \ \ r \ \ x
Quant??l??r??x，往编号在
l
～
r
l\sim r
l～r 的每个集合中加入一个数
x
x
x。
A
s
k
l
r
：
Ask l r：
Asklr：询问能否从
l
～
r
l\sim r
l～r 的集合中取出三个数使得他们能作为边长组成一个三角形（即最小两个和要大于最大的）。
思路：
考虑无法组成三角形的情况，集合内的数由斐波那契数列的一部分构成，
1
,
1
,
2
,
3
,
5...
1,1,2,3,5...
1,1,2,3,5...
任选三个都无法组成三角形，递推可以发现，斐波那契数列在数据范围内只有至多
44
44
44 个
多出任意一个数据都会插到斐波那契数列的某个中间，就可以组成三角形了
也就是说，如果一个集合内的数大于
44
44
44 个，那么一定能选出来组成三角形的
同理，如果一个区间集合内总数大于
44
44
44，那么也一定可以选出来
因此考虑势能线段树
修改操作：每个集合至多含有
44
44
44 个数据，势能标记
m
a
r
k
mark
mark 记录区间内集合大小是否都
>
=
44
>=44
>=44，如果满足则没必要进行修改， 否则暴力修改即可，显然暴力修改操作是合理的，因此
p
u
s
h
d
o
w
n
pushdown
pushdown 也不需要了，只需要
p
u
s
h
u
p
pushup
pushup 向上合并即可
查询操作：如果区间集合总大小
>
44
>44
>44，显然可以，
<
3
<3
<3，显然不可能，否则区间大小至多为
44
44
44，暴力判断即可
code：
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mem(x, d) memset(x, d, sizeof(x))
#define eps 1e-6
using namespace std;
const int maxn = 1e6 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
int num[maxn << 2];
bool mark[maxn << 2];
vector <int> v[maxn];
#define ls p << 1
#define rs p << 1 | 1
void pushup(int p){
mark[p] = mark[ls] & mark[rs];
num[p] = num[ls] + num[rs];
}
void build(int p = 1, int cl = 1, int cr = n){
if(cl == cr){
int x;cin >> x;
++num[p];
v[cl].push_back(x);
return;
}
int mid = cl + cr >> 1;
build(ls, cl, mid);
build(rs, mid + 1, cr);
pushup(p);
}
void update(int l, int r, int d, int p = 1, int cl = 1, int cr = n){
if(l <= cl && cr <= r && mark[p]) return;
if(cl == cr){
++num[p];
v[cl].push_back(d);
if(num[p] > 44) mark[p] = 1;
return;
}
int mid = cl + cr >> 1;
if(l <= mid) update(l, r, d, ls, cl, mid);
if(mid < r) update(l, r, d, rs, mid + 1, cr);
pushup(p);
}
int qry(int l, int r, int p = 1, int cl = 1, int cr = n){
if(l <= cl && cr <= r) return num[p];
int ans = 0, mid = cl + cr >> 1;
if(l <= mid) ans += qry(l, r, ls, cl, mid);
if(mid < r) ans += qry(l, r, rs, mid + 1, cr);
return ans;
}
bool check(int l, int r){
vector <int> d;
for(int i = l; i <= r; ++i)
for(auto x : v[i]) d.push_back(x);
sort(all(d));
for(int i = 0; i < d.size(); ++i)
for(int j = i + 1; j < d.size(); ++j)
for(int k = j + 1; k < d.size(); ++k){
if(d[k] < d[i] + d[j]) return 1;
}
return 0;
}
void work()
{
cin >> n >> m;
build();
while(m--){
string s;int l, r, x;
cin >> s >> l >> r;
if(s[0] == 'Q'){
cin >> x;update(l, r, x);
}
else{
int d = qry(l, r);
if(d < 3){
cout << "NO\n";
}
else if(d > 44){
cout << "YES\n";
}
else{
cout << (check(l, r) ? "YES" : "NO") << endl;
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
work();
return 0;
}
根据上边线段树的分析，我们很多操作都是暴力，不能发挥线段树真正的作用
查询操作：如果区间大于
44
44
44，必然可以，否则我们暴力统计区间内集合大小，如果大于
44
44
44，也必然可以，小于
44
44
44 直接暴力判断即可
修改操作：集合大小
<
=
44
<=44
<=44 之前暴力修改即可，如果一个集合大于
44
44
44，我们就没必要进行修改操作了，就需要跳过去
这时候就可以用到并查集的经典应用，实现跳跃操作
设
f
[
i
]
f[i]
f[i] 表示集合
i
i
i 及之后第一个需要进行修改的集合的下标，
f
[
i
]
∈
[
i
,
n
+
1
]
f[i] \in [i,n+1]
f[i]∈[i,n+1]
code：
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mem(x, d) memset(x, d, sizeof(x))
#define eps 1e-6
using namespace std;
const int maxn = 1e5 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
int num[maxn];
vector <int> v[maxn];
int f[maxn];
int find(int x){
return f[x] == x ? x : f[x] = find(f[x]);
}
bool check(int l, int r){
vector <int> d;
for(int i = l; i <= r; ++i)
for(auto x : v[i]) d.push_back(x);
sort(all(d));
for(int i = 0; i < d.size(); ++i)
for(int j = i + 1; j < d.size(); ++j)
for(int k = j + 1; k < d.size(); ++k){
if(d[k] < d[i] + d[j]) return 1;
}
return 0;
}
void work()
{
cin >> n >> m;
for(int i = 1; i <= n + 1; ++i) f[i] = i;
for(int i = 1, x; i <= n; ++i){
cin >> x;
num[i] = 1;
v[i].push_back(x);
}
while(m--){
string s;int l, r, x;cin >> s >> l >> r;
if(s[0] == 'A'){
if(r - l + 1 > 44){
cout << "YES\n";continue;
}
ll sum = 0;
for(int i = l; i <= r; ++i) sum += num[i];
if(sum > 44){
cout << "YES\n";continue;
}
cout << (check(l, r) ? "YES" : "NO") << endl;
}
else{
cin >> x;
for(int i = find(l); i <= r; i = find(i + 1)){
v[i].push_back(x);
if(v[i].size() > 44){
f[i] = find(i + 1);
}
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
work();
return 0;
}
|