7.30 day 1

P2392 kkksc03考前临时抱佛脚

数组长度20,直接爆搜. 注意这里要从左往右搜,不能乱序搜,乱序的复杂度$O(n!)$,20也受不住啊

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
bool v[25];
int a[25];
int res;
int l, r;
void dfs(int tot, int now)
{
if(now > tot){
res = min(res, max(l, r));
return;
}
l += a[now];
dfs(tot, now + 1);
l -= a[now];
r += a[now];
dfs(tot, now + 1);
r -= a[now];
}
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int s[5];
fors(i, 1, 4) cin >> s[i];
int ans = 0;
fors(i, 1, 4){
mem(v);
res = inf;
l = r = 0;
fors(j, 1, s[i]) cin >> a[j];
dfs(s[i], 1);
ans += res;
}
cout << ans << endl;
return 0;
}

P1441 砝码称重

依然是搜索,只不过搜索终点套了一个01背包。

依然提醒我,搜索一定要顺次,不要乱序,不然就T傻。

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
int n, m;
int a[25];
bool v[25] = {0};
bool f[2005];
int sum;
int ans = 0;
void dfs(int num, int last)
{
if(num == m){
mem(f);
int cnt = 0;
f[0] = 1;
fors(i, 1, n){
if(v[i]) continue;
for(int j = sum; j - a[i] >= 0; --j){
if(!f[j] && f[j - a[i]]) cnt++;
f[j] |= f[j - a[i]];
}
}
ans = max(ans, cnt);
return;
}
fors(i, last + 1, n){
if(!v[i]){
v[i] = 1;
dfs(num + 1, i);
v[i] = 0;
}
}
}
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
cin >> n >> m;
sum = 0;
fors(i, 1, n) cin >> a[i], sum += a[i];
dfs(0, 0);
cout << ans << endl;
return 0;
}

P3370 【模板】字符串哈希

  1. 使用进制哈希法,让每个字母对应唯一一个数字,然后按进制运算,整个字符串对应一个唯一数字。为防止结果数字过大,对质数取模。不放心冲突的话可以再加上一个小质数。如果想省空间,那就得排序,用$log$时间复杂度换空间。

  2. 使用trie树,平均复杂度$O(nlog|s|)$(代码是进制哈希)

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int mod = 1e9 + 7;
const int prime = 711451417;
int a[10005];
int hashe(string s)
{
int ans = 0;
for(auto x : s){
ans = (ans * 117 + (int)x) % mod + prime;
}
return ans;
}
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int t;
cin >> t;
int ans = 0;
fors(i, 1, t){
string s;
cin >> s;
a[i] = hashe(s);
}
sort(a + 1, a + 1 + t);
fors(i, 1, t){
if(a[i] != a[i - 1]) ans++;
}
cout << ans << endl;
return 0;
}

P1621 集合

用线性筛预处理1e5内的素数,然后在区间内枚举每个质数的倍数,通过并查集合并。

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 1e5 + 10;
int a, b, p;
int fa[maxn];
int prime[maxn];
const int N = 2e7 + 10;
bool is[N];
int cnt = 0;
void Prime(){
mem(is);
is[0] = is[1] = 1;
for (int i = 2; i < N; ++i) {
if(!is[i]) prime[cnt++] = i;
for(int j = 0; j < cnt && prime[j] * i < N; ++j){
is[prime[j] * i] = 1;
if(i % prime[j] == 0) break;
}
}
}
int find(int x)
{
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void join(int x, int y)
{
int fx = find(x), fy = find(y);
if(fx == fy) return;
fa[fy] = fx;
}
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
Prime();
cin >> a >> b >> p;
fors(i, a, b) fa[i] = i;
int x = 0;
while(prime[x] < p) x++;
for(int i = x; prime[i] <= b; ++i){
int s = prime[i];
while(s < a) s += prime[i];
vector<int> v;
while(s <= b){
v.pb(s);
s += prime[i];
}
for(int i = 1; i < v.size(); ++i){
join(v[i], v[i - 1]);
}
}
int ans = 0;
fors(i, a, b) if(fa[i] == i) ans++;
cout << ans << endl;
return 0;
}

7.31 day 2

出去太久了加上在补cf的题以及写题解,没时间写洛谷的题orz

P1892 [BOI2003] 团伙

复习一下最基本的带权并查集。其实用反集概念即可。

顺便回归一下最朴素的码风

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005;
int fa[maxn];
int n, m;
int find(int x)
{
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void join(int x, int y){
int fx = find(x), fy = find(y);
if(fx == fy) return;
fa[fy] = fx;
}
int main()
{
// 敌人:合并n+x,y
cin >> n >> m;
for(int i = 1; i <= 2 * n; ++i) fa[i] = i;
for(int i = 0; i < m; ++i){
char x;
int l, r;
cin >> x >> l >> r;
if(x == 'F') join(l, r);
else join(l, r + n), join(r, l + n);
}
int cnt = 0;
for(int i = 1; i <= 2 * n; ++i){ if(fa[i] == i) cnt++;}
cout << cnt << endl;
return 0;
}

P4305 [JLOI2011]不重复数字

可以用拉链哈希做。懒得写了,但是哈希题写unordered_map太敷衍,于是写了个排序

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
#include <bits/stdc++.h>
// #define int long long
using namespace std;
const int maxn = 5e4 + 10;
struct node
{
int x, id;
}a[maxn];
bool cmp(const node& x, const node& y){
if(x.x != y.x) return x.x < y.x;
return x.id < y.id;
}
bool re(const node& x, const node& y){
return x.id < y.id;
}
signed main()
{
int t;
scanf("%d", &t);
while(t--){
int n, x;
scanf("%d", &n);
for(int i = 0; i < n; ++i){ scanf("%d", &a[i].x); a[i].id = i; }
sort(a, a + n, cmp);
vector<node> v;
v.push_back(a[0]);
for(int i = 1; i < n; ++i){
if(a[i].x != a[i - 1].x){
v.push_back(a[i]);
}
}
sort(v.begin(), v.end(), re);
for(auto x : v){
printf("%d ", x.x);
}
printf("\n");
}
return 0;
}

8.1 day 3

P3405 [USACO16DEC]Cities and States S

如果组合是$a,b$,从$b,a$保存的容器中获得贡献,然后向$a,b$容器加1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int main()
{
unordered_map<string, int> mp;
int n;
cin >> n;
int ans = 0;
for(int i = 0; i < n; ++i) {
string a, b;
cin >> a >> b;
if(a.substr(0, 2) == b.substr(0, 2));
else{
mp[a.substr(0, 2) + b]++;
ans += mp[b + a.substr(0, 2)];
}
}
cout << ans << endl;
return 0;
}

P3879 [TJOI2010]阅读理解

map裸题

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
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, x;
cin >> n;
map<string, bool> mp[n + 1];
for(int i = 0; i <= n; ++i){
string s;
getline(cin, s);
stringstream ss;
ss << s;
ss >> x;
while(ss >> s){
mp[i][s] = 1;
}
}
int m;
cin >> m;
for(int i = 0; i < m; ++i){
string s;
cin >> s;
for(int j = 1; j <= n; ++j){
if(mp[j].count(s)){
cout << j << ' ';
}
}
cout << endl;
}
return 0;
}

P3916 图的遍历

反向dfs,求较大的点能去哪些点,这样就能进行不回溯的dfs了。

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
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> v[100005];
int ans[100005] = {0};
void dfs(int i, int f)
{
for (auto x : v[i]) {
if (!ans[x]) {
ans[x] = f;
dfs(x, f);
}
}
}
int main()
{
cin >> n >> m;
// n次bfs,复杂度O(n(n+m)), 不可接受
// n次dfs,不访问已经访问过的节点,复杂度O(n+m),好!
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
v[y].push_back(x);
}
for (int i = n; i >= 1; --i) {
if(!ans[i]) ans[i] = i;
dfs(i, i);
}
for (int i = 1; i <= n; ++i ) {
cout << ans[i] << ' ';
}
return 0;
}

8.2 day 4

学习网络流算法+摸鱼

8.3 day 5

多校自闭+摸鱼

8.4 day 6

今天摸摸Unity,诶嘿……

8.5 day 7

多校自闭,摸了会Unity,感觉最近状态很差……依然没有做洛谷。

8.6 day 8

伞兵才会一天玩五六个小时bf

8.7 day 9

P1918 保龄球

水题,找找状态(洛谷100AC纪念,2021-08-07 12:19:41)

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
/**
* @file :vsDebug.cpp
* @brief :
* @date :2021-08-05
* @Motto :Love Sakurai Yamauchi Forever
*/
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
unordered_map<int, int> mp;
int n;
cin >> n;
fors(i, 1, n){
int x;
cin >> x;
mp[x] = i;
}
int q;
cin >> q;
while(q--){
int x;
cin >> x;
cout << mp[x] << endl;
}
return 0;
}

P2814 家谱

评测机出锅了,下载下来和std输出一模一样判我wa了,不管了

字符串并查集

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
/**
* @file :vsDebug.cpp
* @brief :
* @date :2021-08-05
* @Motto :Love Sakurai Yamauchi Forever
*/
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
unordered_map<string, string> fa;
string find(string x){
if(fa[x] == x){
return x;
}
return fa[x] = find(fa[x]);
}
void join(string x, string y){
string fx = find(x), fy = find(y);
fa[fy] = fx;
}
signed main()
{
// DDLC_ESCAPE_PLAN_FAILED;
// freopen("out.txt", "w", stdout);
string s;
string f;
while(getline(cin, s) && s != "$"){
if(s[0] == '#'){
f = s.substr(1, s.size() - 1);
if(!fa.count(f)) fa[f] = f;
}
else if(s[0] == '+'){
if(!fa.count(f)) fa[f] = f;
if(!fa.count(s.substr(1, s.size() - 1))) fa[s.substr(1, s.size() - 1)] = s.substr(1, s.size() - 1);
join(f, s.substr(1, s.size() - 1));
}
else{
string u = s.substr(1, s.size() - 1);
if(!fa.count(u)) fa[u] = u;
cout << u << ' ' << find(u) << endl;
}
}
return 0;
}

P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

二叉堆基础题

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;

signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int n;
cin >> n;
priority_queue<int, vector<int>, greater<int>> q;
int x;
fors(i, 1, n){
cin >> x;
q.push(x);
}
int ans = 0;
while(q.size() > 1){
int x = q.top(); q.pop();
int y = q.top(); q.pop();
ans += x + y;
q.push(x + y);
}
cout << ans << endl;
return 0;
}

P1168 中位数

优先队列好例题,维护一个大顶堆和一个小顶堆即可

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;

signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
priority_queue<int> q;
priority_queue<int, vector<int>, greater<int>> gq;
int n;
cin >> n;
int x;
int mid;
cin >> x;
cout << (mid = x) << endl;
fors(i, 2, n){
cin >> x;
if(x > mid) gq.push(x);
else q.push(x);
while(gq.size() > q.size()){
q.push(mid);
mid = gq.top();
gq.pop();
}
while(q.size() > gq.size()){
gq.push(mid);
mid = q.top();
q.pop();
}
if(i & 1) cout << mid << endl;
}
return 0;
}

P2085 最小函数

维护一个容量为m的优先队列即可。

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;

signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int n, m;
cin >> n >> m;
priority_queue<int> q;
while(n--){
int a, b, c;
cin >> a >> b >> c;
int x = 1;
while(1){
int fx = a * x * x + b * x + c;
if(q.size() < m || (q.size() >= m && q.top() > fx)){
q.push(fx);
if(q.size() > m) q.pop();
}
else break;
x++;
}
}
vector<int> ans;
while(!q.empty()){
ans.pb(q.top());
q.pop();
}
for(int j = m - 1; j >= 0; --j){
cout << ans[j] << ' ';
}
cout << endl;
return 0;
}

P1631 序列合并

和上面P2085的思路很相近,都是找Top 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
/**
* @file :vsDebug.cpp
* @brief :
* @date :2021-08-07
* @Motto :Love Sakurai Yamauchi Forever
*/
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn], b[maxn];
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int n;
cin >> n;
fors(i, 1, n){
cin >> a[i];
}
fors(i, 1, n){
cin >> b[i];
}
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + n);
priority_queue<int> q;
fors(i, 1, n){
fors(j, 1, n){
if(q.size() >= n && a[i] + b[j] > q.top()) break;
else q.push(a[i] + b[j]);
if(q.size() > n) q.pop();
}
}
vector<int> ans;
fors(i, 1, n){
ans.pb(q.top());
q.pop();
}
for(int j = n - 1; j >= 0; --j){
cout << ans[j] << ' ';
}
cout << endl;
return 0;
}

8.8 day 10

P1801 黑匣子

和P1168一样,只不过这里不一定是中位数,而是位置随时可能改变

感觉还题目可以更进一步,位置左右任意移动

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = (int)(-2e9) - 1;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
queue<int> u;
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int m, n;
cin >> m >> n;
priority_queue<int> q;
priority_queue<int, vector<int>, greater<int>> gq;
fors(i, 1, m) cin >> a[i];
fors(i, 1, n){
int x;
cin >> x;
u.push(x);
}
int mid = inf;
int p = 0;
fors(i, 1, m){
if(mid == inf){
gq.push(a[i]);
}
else if(a[i] > mid){
gq.push(a[i]);
}
else{
q.push(a[i]);
}
while(p && q.size() >= p){
gq.push(mid);
mid = q.top();
q.pop();
}
while(u.front() == i){
u.pop();
if(mid != inf) q.push(mid);
mid = gq.top();
gq.pop();
cout << mid << endl;
p++;
}
}
return 0;
}

P4053 [JSOI2007]建筑抢修

优先队列贪心

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2e5 + 10;
struct node
{
int time;
int limit;
}a[maxn];
bool cmp(const node& x, const node& y){
return x.limit < y.limit;
}
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int n;
cin >> n;
priority_queue<int> q;
fors(i, 1, n) cin >> a[i].time >> a[i].limit;
sort(a + 1, a + 1 + n, cmp);
int time = 0;
fors(i, 1, n){
if(a[i].time + time > a[i].limit){
if(a[i].time < q.top()){
time -= q.top();
q.pop();
q.push(a[i].time);
time += a[i].time;
}
continue;
}
q.push(a[i].time);
time += a[i].time;
}
cout << (int)q.size() << endl;
return 0;
}

8.9 day 11

没打

8.10 day 12

P2613 【模板】有理数取余

多校之后,再复习一下分数取模

以后分数取逆元再也不查资料惹

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
/**
* @file :vsDebug.cpp
* @brief :
* @date :2021-08-10
* @Motto :Love Sakurai Yamauchi Forever
*/
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int mod = 19260817;

int fpow(int x, int p, int m)
{
int ans = 1;
while(p){
if(p & 1) ans = (ans * x) % m;
x = (x * x) % m;
p >>= 1;
}
return ans;
}
int divi(int x, int y)
{
return (x % mod * fpow(y, mod - 2, mod)) % mod;
}
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int t;
t = 1;
while(t--)
{
int a = 0, b = 0;
string s1, s2;
cin >> s1 >> s2;
for(int i = 0; i < s1.size(); ++i){
a = (a * 10 + s1[i] - '0') % mod;
}
for(int i = 0; i < s2.size(); ++i){
b = (b * 10 + s2[i] - '0') % mod;
}
if(b % mod == 0) cout << "Angry!" << endl;
else
cout << divi(a, b) << endl;
}
return 0;
}

8.11 day 13

8.12 day 14

这两天具体去干了什么我就不说了

感觉自己这也想干,那也想干

最后什么也没干成

确实是有B students的好奇心和求知欲

但是没有B students的远见,也缺乏A students的定力

最后自己的技能就是

四不像

什么也不会

这样子真的不好,回想一下高中老师是怎么教我的 其实我是有把一件事做好做精的能力的吧。只是面对的选择太多的时候,我会什么都尝试一下,然后浅尝辄止。

是时候好好想一想,我要的到底是什么,我应该去做什么

然后就去做,不要再去看哪个可以搞哪个有意思了,我什么也不看,我只做好自己之前想做的

多学点知识吧。

8.13 day 15

P3865 【模板】ST 表

今天学ST表~

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
#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
// #define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int f[maxn][30];
int n;
void process()
{
for(int i = 1; i <= n; i ++) f[i][0] = a[i];
int t = log(n) / log(2) + 1;
for(int j = 1; j < 20; j ++)
{
for(int i = 1; i <= n - (1 << j) + 1; i ++)
{
f[i][j] = max(f[i][j-1],f[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int x, int y){
int t = log(abs(y-x + 1))/ log(2);
int a = f[x][t];
int b = f[y - (1 << t) + 1][t];
return max(a,b);
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
signed main()
{
// DDLC_ESCAPE_PLAN_FAILED;
int m;
int l, r;
n = read();
m = read();
fors(i, 1, n) a[i] = read();
process();
while(m--){
l = read();
r = read();
printf("%d\n", query(l, r));
}
return 0;
}