vector如何释放内存

关于vector释放内存

考个csp认证被这个鬼问题卡了,真是服了。

1
2
vector<int> vec;
vec.clear(); // 不会释放内存,仅仅长度为0。

释放内存:

  1. 将要释放内存的vector与一个空vector进行交换,然后将空vector释放掉。
1
vector<int>().swap(vec);
  1. 在调用clear()之后再调用shrink_to_fit(),将vector的容量减小到与其大小相等,从而释放多余的内存空间。
1
2
vec.clear();
vec.shrink_to_fit();
  1. 使用resize()方法重新分配vector的大小,从而释放多余的内存空间。
1
vec.resize(n);

CF1943D1

CF1943D1 - Counting Is Fun (Easy Version)

题意:定义好数组为:一个由$m$个非负整数组成的数组$b$中,若$b$中所有元素可以通过以下操作使其为$0$。选择一个区间$(l, r)(1\le l< r\le m), \forall{i}, \ i\in(l, r),b_i$减去$1$。询问长度为$n$的数组,每个元素最大为$k$时,好数组个数。

可以证明,一个三元组$(a, b, c)$,当$a+c\ge b$时可以将其减为$0$。

于是设$dp[i][a][b]$为前i个数,第i-1个是a,第i个是b时的方案数。那么转移方程则为$dp[i][b][c] = \sum\limits_{a=b-c}^{k}{dp[i-1][a][b]}$。

对于求和用前缀和维护则可做到$O(n^3)$。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 410;

void work() {
int n, k, p;
cin >> n >> k >> p;
vector<vector<int>> dp(k + 1, vector<int>(k + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n + 2; i++) { // n + 2, 0, 0 will be the ans.
vector<vector<int>> sum(k + 1, vector<int>(k + 1, 0));
for (int b = 0; b <= k; b++) {
sum[b][0] = dp[0][b];
for (int a = 1; a <= k; a++)
sum[b][a] = (dp[a][b] + sum[b][a - 1]) % p;
}
for (int b = 0; b <= k; b++) {
for (int c = 0; c <= k; c++) {
if (b - c > 0) dp[b][c] = (sum[b][k] - sum[b][b - c - 1] + p) % p; // a > b - c is ok
else dp[b][c] = sum[b][k]; // any a is ok
}
}
}
cout << dp[0][0] << '\n';
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--)
work();
return 0;
}

树的直径

CF1944E - Tree Compass

题意:给定一棵树,最初所有结点为白色。你可以进行操作:选定一个节点v和距离k,使树上与v的简单路径距离为k的所有点染色为黑色。构造操作序列,使操作次数最小化。

不难发现,影响操作次数的是树中最长的一条路径,即树的直径。所以我们只要找出树的直径并选定最中间的点(奇数长度则一个,偶数则两个),然后再使距离包含整条直径即可。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;

const int N = 2010;

int n, fa[N];
vector<int> e[N];

void add(int x, int y) {
e[x].emplace_back(y);
e[y].emplace_back(x);
}
// 两次bfs找树的直径
int find(int x) {
queue<int> q;
vector<int> dep(n + 10, -1);
dep[x] = 0;
fa[x] = -1;
q.push(x);
while (!q.empty()) {
int now = q.front();
q.pop();
for (auto nxt: e[now]) {
if (dep[nxt] != -1) continue;
fa[nxt] = now;
dep[nxt] = dep[now] + 1;
q.push(nxt);
}
}
int ans = -1, ansid = 0;
for (int i = 1; i <= n; i++) {
if (dep[i] > ans) {
ansid = i;
ans = dep[i];
}
}
return ansid;
}

void work() {
cin >> n;
for (int i = 1; i <= n; ++i)
e[i].clear();
for (int i = 1, x, y; i < n; ++i) {
cin >> x >> y;
add(x, y);
}
int x = find(1); // begin
int y = find(x); // end
vector<int> a;
for (int i = y; i != -1; i = fa[i]) {
a.emplace_back(i);
} // fa[x] = -1
int len = a.size();
vector<pair<int, int>> ans;
if (len & 1) {
int p = a[len >> 1];
for (int i = 0; i <= (len >> 1); ++i) {
ans.emplace_back(p, i);
}
} else {
int p1 = a[(len >> 1) - 1], p2 = a[len >> 1];
for (int i = 1; i <= (len >> 1); i += 2){
ans.emplace_back(p1, i);
ans.emplace_back(p2, i);
}
}
cout << ans.size() << '\n';
for (auto [x, y]: ans) {
cout << x << ' ' << y << '\n';
}
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--)
work();
return 0;
}

双Hash

CF1944D - Non-Palindromic Substring

题意:称一个字符串为$k$-good字符串,当该字符串至少有一个长度为$k$的子串不是回文串。给定一个字符串,询问$[l, r]$子串的$\sum{k}$

通过模拟可以发现对于一个字符串:

  1. 不是回文串,则$k$可以取$2 \sim len$中的每一个值。

  2. 每个字符都相同,则答案为$0$。

  3. 是交错型的字符串,则$k$可以取$2 \sim len$中的每一个偶数。

  4. 只是回文串,则$k$可以取$2 \sim {len - 1}$中的每一个值。

    判断回文串使用了双Hash(好久没用过了,写一个规范点的出来用)

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;

const int N = 200010;
namespace RAND {
unsigned int SEED() {
auto now = chrono::system_clock::now();
auto timestamp = chrono::duration_cast<chrono::milliseconds>(now.time_since_epoch());
return static_cast<unsigned int>(timestamp.count());
}
mt19937 R(SEED());
} // namespace RAND

unsigned long long mod1 = RAND::R(), mod2 = RAND::R();
class HASH {
typedef unsigned long long ull;
typedef pair<ull, ull> pULL;
public:
ull base, pow1[N], pow2[N];
vector<ull> hash1, hash2;
HASH() {
base = 27;
pow1[0] = pow2[0] = 1;
for (int i = 1; i < N; ++i) {
pow1[i] = (pow1[i - 1] * base) % mod1;
pow2[i] = (pow2[i - 1] * base) % mod2;
}
}
// 默认字符串从1开始
void init(string s) {
int len = s.size() - 1;
hash1.reserve(s.size()), hash2.reserve(s.size());
hash1[0] = hash2[0] = 0;
for (int i = 1; i <= len; ++i) {
hash1[i] = (hash1[i - 1] * base + s[i] - 'a') % mod1;
hash2[i] = (hash2[i - 1] * base + s[i] - 'a') % mod2;
}
}
pULL subHash(int l, int r) {
if (l == 1) return make_pair(hash1[r], hash2[r]);
pULL tmp;
tmp.first = (hash1[r] - hash1[l - 1] * pow1[r - l + 1] % mod1 + mod1) % mod1;
tmp.second = (hash2[r] - hash2[l - 1] * pow2[r - l + 1] % mod2 + mod2) % mod2;
return tmp;
}
} hashFront, hashBack;

int n, q;
string s;
void work() {
cin >> n >> q;
cin >> s;
hashFront.init(" " + s);
reverse(s.begin(), s.end());
hashBack.init(" " + s);
reverse(s.begin(), s.end());
int len = s.size();
s = " " + s;
unsigned long long ans, L;
vector<int> id(n + 1); // 判断交错
id[1] = 1, id[2] = 2;
for (int i = 3; i <= len; i++) {
if (s[i] == s[i - 2]) id[i] = id[i - 2];
else id[i] = i;
}
vector<int> con(n + 1); // 判断连续
con[1] = 1;
for (int i = 2; i <= len; i++) {
if (s[i] == s[i - 1]) con[i] = con[i - 1];
else con[i] = i;
}
for (int i = 1, l, r; i <= q; ++i) {
cin >> l >> r;
L = (r - l + 1);
if (L == 1) {
cout << "0\n";
continue;
}
if (L == 2) {
if (s[l] == s[r]) cout << "0\n";
else cout << "2\n";
continue;
}
auto x1 = hashFront.subHash(l, r);
auto x2 = hashBack.subHash(len - r + 1, len - l + 1);
if (x1 == x2) {
bool flag = 1;
if (con[r] == con[l]) {
cout << 0 << '\n';
continue;
}
if (id[l] == id[r] && id[l + 1] == id[r - 1]) {
unsigned long long tmp = (L / 2) * 2;
ans = (2 + tmp) * (L / 2) / 2;
} else {
ans = (1 + L - 1) * (L - 1) / 2 - 1;
}
} else {
if (id[l] == id[r - 1] && id[l + 1] == id[r]) {
ans = (2 + L) * L / 4;
} else ans = (2 + L) * (L - 1) / 2;
}
cout << ans << '\n';
}
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--)
work();
return 0;
}

CF1946

A - Median of an Array

题意:加多少次1可以改变中位数大小。

显然比中位数位置大的与中位数相同的数有多少个就加多少次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int a[100000];
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1);
int k = (n + 1) / 2, ans = 0;
for (int i = k; i <= n; i++) {
if (a[i] == a[k])
ans++;
}
cout << ans << endl;
}
return 0;
}

B - Maximum Sum

题意:一个长度为$n$的数组$a$,你可以进行k次操作,每一次操作选一个子段和添加到数组的任意位置,最大化数组总和。

当最大子段和小于$0$时显然不进行操作,当最大子段和大于$0$时不断加入$k$次目前最大子段和。

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
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007ll;

long long T, a[200010], SUM;
void work() {
int n, k;
SUM = 0;
cin >> n >> k;
for (int i = 1; i <= n; ++i)
cin >> a[i], SUM += a[i], SUM %= mod;
long long ans = 0, sum = 0;
for (int i = 1; i <= n; ++i) {
sum += a[i];
if (sum > ans) {
ans = sum;
} else if (sum < 0) {
sum = 0;
}
}
sum = 0;
for (int i = 1; i <= k; ++i) {
sum = (sum + ans) % mod;
ans = (ans + ans) % mod;
}
cout << (SUM + sum + 2ll * mod) % mod << endl;
}

int main() {
cin >> T;
while (T--)
work();
return 0;
}
Read more

各种积分

$Guass$积分

$$\int_{0}^{+\infty}e^{-x^{2}}dx$$

设$I(t)={(\int_{0}^{t} e^{-x^{2}}dx)}^2$, 则求

$$\sqrt{\lim\limits_{t \to +\infty}I(t)}$$

$$I^{‘}(t) = 2(\int_{0}^{t}e^{-x^{2}}dx)e^{-t^2} = 2\int_{0}^{t}e^{-x^2-t^2}dx = 2\int_{0}^{1}2te^{(y^2+1)t^2}dy$$

$$\frac{dI(t)}{dt} = \frac{\int_0^1\frac{e^{-(y^2+1)t^2}}{-(y^2+1)}dy}{dt}$$

$$I(t) = \int_0^1\frac{e^{-(y^2+1)t^2}}{-(y^2+1)}+C$$

$$I(0)=\int_0^1\frac{-1}{y^2+1}dy+C = -\frac{\pi}{4} + C=0,C=\frac{\pi}{4}$$

$$I(t) = \int_0^1\frac{e^{-(y^2+1)t^2}}{-(y^2+1)}+\frac{\pi}{4}$$

$$\lim\limits_{t \to +\infty}I(t)=0+\frac{\pi}{4} = \frac{\pi}{4}$$

$$\therefore\int_{0}^{+\infty}e^{-x^{2}}dx=\frac{\sqrt{\pi}}{2}$$

Read more