E. Look Back
因为每次都是2，可以推出x<=y2^(n)，转化成 x/y<=2^(n)，求n直接取对数即可
注意：
1.答案很大要开LL
2.不要直接乘，会爆LL，直接利用原式即可，如果后面的大，就减去大多少的对数
3.记得向上取整
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
void bu_f() {
int n;
cin >> n;
vector<int> v(n);
for (auto& u : v)cin >> u;
LL ans = 0, r = 0;
for (int i = 1; i < n; i++) {
int t = ceil(log2(1.0 * v[i - 1] / v[i]));
r += t;
if (r < 0) {
r = 0;
}
ans += r;
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
bu_f();
}
return 0;
}
D. In Love
判断是否存在不相交的俩线段，可以考虑最左边和最右边的线段是否相交
那么可以利用multiset存储每个线段（因为它可以自动排序）
点击查看代码
#include<bits/stdc++.h>
using namespace std;
void bu_f() {
int n;
cin >> n;
multiset<int> sl, sr;
while (n--) {
char c;
cin >> c;
if (c == '+') {
int l, r;
cin >> l >> r;
sl.insert(l);
sr.insert(r);
}
else {
int l, r;
cin>>l>>r;
sl.erase(sl.find(l));
sr.erase(sr.find(r));
}
if (sl.size() > 1&&sr.size()>1 && *sr.begin() < *prev(sl.end())) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
}
int main() {
int t=1;
//cin >> t;
while (t--) {
bu_f();
}
return 0;
}
题意：寻找连续子数组，在子序列中唯一。
子序列：随机选取或者删除原序列的元素，剩余元素拼合
考虑：选择一个连续子序列，设al为该序列的最左端，如果在该序列的左侧有一个元素a_l，使得a_l==al，那么该序列不满足唯一（有子序列重复），同理对右侧也一样
思路：
1.寻找该元素最先出现的位置和最后出现的位置（保证唯一性）
2.累加求和
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
void bu_f() {
int n;
cin >> n;
vector<int> a(n+1);
map<int, int> first, last;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (!first.count(a[i])) first[a[i]] = i;
last[a[i]] = i;
}
LL num = 0,ans=0;//开LL
for (int i = 1; i <= n; i++) {
if (first[a[i]] == i) num++;
if (last[a[i]] == i) ans += num;
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
bu_f();
}
return 0;
}
G1. Dances (Easy version)
题意：选择在a,b数组中各删除一个数，随机排序使得a[i]<b[i],问最小操作次数
给定a的首元素为1
分析：如果删的越多，那么越可能满足，答案具有单调性，直接二分
对于每一个操作：删a中元素最大的，b中元素最小的
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
void bu_f() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(n);
a[0] = 1;
for (int i = 1; i < n; i++) cin >> a[i];
for (auto& v : b) cin >> v;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int l = -1, r = n + 1;
auto check = [&](int k) {
for (int i = 0; i < n - k; i++) {
if (a[i] >= b[i + k]) return false;
}
return true;
};
while (l + 1 < r) {//二分删的次数
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid;
}
cout << r << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
bu_f();
}
return 0;
}