模板——补充2

发表于 更新于 分类于 ， 阅读次数： 作者 Pomelorin

模板——补充2

三分（整数三分，实数三分），Bitset，Tarjan 算法（及其变体）。

三分

三分用于单峰函数（例如二次函数）求最值等问题。

实数三分

求 calc 凹函数的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PII pair<ll, ll>
const ll mod = 1e9 + 7, N = 1e4 + 10, inf = 1e17;
const ld eps = 1e-9;

ll a[N], b[N], c[N], n;

ld calc(ld x) {
    ld ans = -inf;
    for (ll i = 1; i <= n; i++) {
        ans = max(ans, x * x * a[i] + x * b[i] + c[i]);
    }
    return ans;
}

void solve() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    ld l = 0, r = 1000;
    while (r - l > eps) {//或迭代固定次数
        ld m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
        if (calc(m1) < calc(m2)) {
            r = m2;
        } else {
            l = m1;
        }
    }
    cout << fixed << setprecision(4) << calc(l) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

整数三分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ll l, r;//凸函数极大值
while(l < r) {
    ll lmid = l + (r - l) / 3;
    ll rmid = r - (r - l) / 3;
    if(calc(lmid) <= calc(rmid))	l = lmid + 1;
    else r = rmid - 1;
}
printf("%lld\n", max(calc(l), calc(r)));

ll l, r;//凹函数极小值
while(l < r) {
    ll lmid = l + (r - l) / 3;
    ll rmid = r - (r - l) / 3;
    if(calc(rmid) >= calc(lmid))	r = rmid - 1;
    else l = lmid + 1;
}
printf("%lld\n", min(calc(l), calc(r)));

Bitset

一定要注意！！！bitset 不要和整数进行运算！！！而且整数没有 bitset 存的那么大！！！

头文件

1
#include <bitset>

指定大小

1
std::bitset<1000> bs;  // a bitset with 1000 bits

构造函数

  • bitset(): 每一位都是 false．
  • bitset(unsigned long val): 设为 val 的二进制形式．
  • bitset(const string& str): 设为 \(01\) 串 str．

运算符

  • operator []: 访问其特定的一位．

  • operator ==/operator !=: 比较两个 bitset 内容是否完全一样．

  • operator &/operator &=/operator |/operator |=/operator ^/operator ^=/operator ~: 进行按位与/或/异或/取反操作．

    注意：bitset 只能与 bitset 进行位运算，若要和整型进行位运算，要先将整型转换为 bitset．

  • operator <</operator >>/operator <<=/operator >>=: 进行二进制左移/右移．

此外，bitset 还提供了 C++ 流式 IO 的支持，这意味着你可以通过 cin/cout 进行输入输出．

成员函数

  • count(): 返回 true 的数量．
  • size(): 返回 bitset 的大小．
  • test(pos): 它和 vector 中的 at() 的作用是一样的，和 [] 运算符的区别就是越界检查．
  • any(): 若存在某一位是 true 则返回 true，否则返回 false．
  • none(): 若所有位都是 false 则返回 true，否则返回 false．
  • all(): 若所有位都是 true 则返回 true，否则返回 false．
    1. set(): 将整个 bitset 设置成 true．
    2. set(pos, val = true): 将某一位设置成 true/false．
    1. reset(): 将整个 bitset 设置成 false．
    2. reset(pos): 将某一位设置成 false．相当于 set(pos, false)．
    1. flip(): 翻转每一位．（\(0\leftrightarrow1\)，相当于异或一个全是 \(1\) 的 bitset）
    2. flip(pos): 翻转某一位．
  • to_string(): 返回转换成的字符串表达．
  • to_ulong(): 返回转换成的 unsigned long 表达（long 在 NT 及 32 位 POSIX 系统下与 int 一样，在 64 位 POSIX 下与 long long 一样）．
  • to_ullong():（C++11 起）返回转换成的 unsigned long long 表达．

另外，libstdc++ 中有一些较为实用的内部成员函数：

  • _Find_first(): 返回 bitset 第一个 true 的下标，若没有 true 则返回 bitset 的大小．
  • _Find_next(pos): 返回 pos 后面（下标严格大于 pos 的位置）第一个 true 的下标，若 pos 后面没有 true 则返回 bitset 的大小．

Tarjan 算法