Codeforces Round #419 (Div. 2) ABC

OI
  1. 1. A题
    1. 1.1. 题目描述
    2. 1.2. 解决方案
    3. 1.3. 代码
  2. 2. B题
    1. 2.1. 题目描述
    2. 2.2. 思路
      1. 2.2.1. 线段树法
        1. 2.2.1.1. 代码
      2. 2.2.2. 差分序列+前缀和
        1. 2.2.2.1. 代码
  3. 3. C题
    1. 3.1. 题目描述
    2. 3.2. 思路
    3. 3.3. 代码

A题

题目描述

原题地址:Codeforces

题意:判断回文时间。

解决方案

先搞出来一个判断回文的函数,然后枚举分钟。

代码

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>
using namespace std;
string s;
bool ispar(const string &t)
{
for (int i = 0, j = t.length() - 1; i <= j; ++i, --j)
{
if (t[i] != t[j])
return 0;
}
return 1;
}
struct mtime
{
int h, m;
string tostr()
{
string t1, t2;
if (h / 10 == 0)
t1 += '0';
t1 += to_string(h);

if (m / 10 == 0)
t2 += '0';
t2 += to_string(m);

return t1 + ':' + t2;
}
};

int main()
{
cin >> s;
mtime tm;
tm.h = (s[0] - '0') * 10 + s[1] - '0';
tm.m = (s[3] - '0') * 10 + s[4] - '0';
int ans = 0;
for (; !ispar(tm.tostr()); ++ans)
{
++tm.m;
if (tm.m >= 60)
tm.m -= 60, tm.h += 1;
if (tm.h >= 24)
tm.h -= 24;
}
cout << ans << endl;
}

B题

题目描述

原题地址:Codeforces

题意,给定一全零序列,对该序列执行若干区间加操作后,执行区间的询问操作,询问区间内有多少数大于常数$k$

思路

线段树法

本来以为这是个线段树裸题,结果附加信息不好维护。考虑到所有的询问都在修改之后,可以在修改操作结束后将所有lazy标记下放到叶子结点,然后递归维护节点信息

代码

不存在的,这个是wb的解法
现在存在了,线段树1A真爽啊。。bug-free code

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
#include <bits/stdc++.h>
using namespace std;
#define m ((l + r) >> 1)
int n, k, q;
struct node
{
int val;
bool isleaf;
node *lc, *rc;
node() { isleaf = val = 0, lc = rc = 0; }
};
node *root;
node *build(int l, int r)
{
node *x = new node();
if (l == r)
{
x->isleaf = 1;
return x;
}
x->lc = build(l, m);
x->rc = build(m + 1, r);
return x;
}
void update(node *t, int l, int r, int ql, int qr, int v)
{
if (ql <= l && r <= qr)
{
t->val += v;
return;
}
if (ql <= m)
update(t->lc, l, m, ql, qr, v);
if (qr > m)
update(t->rc, m + 1, r, ql, qr, v);
}
void pushall(node *t)
{
if (t->isleaf)
{
if (t->val >= k)
t->val = 1;
else
t->val = 0;
return;
}
t->lc->val += t->val, t->rc->val += t->val;
t->val = 0;
pushall(t->lc);
pushall(t->rc);
t->val = t->lc->val + t->rc->val;
}
int query(node *t, int l, int r, int ql, int qr)
{
if (ql <= l && r <= qr)
return t->val;
int ans = 0;
if (ql <= m)
ans += query(t->lc, l, m, ql, qr);
if (qr > m)
ans += query(t->rc, m + 1, r, ql, qr);
return ans;
}
int main()
{
cin >> n >> k >> q;
root = build(1, 200000);
for (int i = 1; i <= n; ++i)
{
int l, r;
cin >> l >> r;
update(root, 1, 200000, l, r, 1);
}
pushall(root);
for (int i = 1; i <= q; ++i)
{
int l, r;
cin >> l >> r;
cout << query(root, 1, 200000, l, r) << endl;
}
}

差分序列+前缀和

首先考虑到这是一个全零的序列,用差分会非常方便,先差分一下,搞出来修改操作后的序列,$O(n)$时间

具体操作是对差分序列求前缀和,得到修改后序列

然后考虑到“区间内大于k”这个操作是满足减法性质的,即记$g(l,r)$是区间$[l,r]$大于$k$的数的个数,则有$g(l,r)=g(1,r)-g(1,l-1)$,所以再用$O(n)$的时间求出前缀和。

然后利用减法性质,输出前缀和的差即可

代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int cf[maxn];
int n, k, q;
int main()
{
scanf("%d%d%d", &n, &k, &q);
for (int i = 1; i <= n; ++i)
{
int l, r;
scanf("%d%d", &l, &r);
cf[l]++, cf[r + 1]--;
}
for (int i = 2; i <= 200000; ++i)
cf[i] += cf[i - 1];
for (int i = 1; i <= 200000; ++i)
cf[i] = cf[i - 1] + (cf[i] >= k);
for (int i = 1; i <= q; ++i)
{
int l, r;
scanf("%d%d", &l, &r);
cout << cf[r] - cf[l - 1] << endl;
}
}

C题

题目描述

原题地址:Codeforces

思路

首先考虑到删数的顺序不会影响到是否合法,所以可以遍历每一行,每一列,分别求出其最小值,并进行修改,$O(n^2)$时间。

然后判断是否还有位置有数,如果是则不合法。

注意题目要求输出步数尽量小,考虑到这样一组数据

1
2
5
1 1 1 1 1

若先删列,需要5步,先删行则是1步,所以要先比较一下行列数,从较小的一个开始删。

代码

这是我仿制rk1dalao的代码

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
#include <bits/stdc++.h>
using namespace std;
int g[110][110];
const int INF = 1 << 30;
int n, m;
typedef pair<int, int> pii;
vector<pii> ans;
void row()
{
for (int i = 1; i <= n; ++i)
{
int minv = INF;
for (int j = 1; j <= m; ++j)
minv = min(minv, g[i][j]);
for (int j = 1; j <= m; ++j)
g[i][j] -= minv;
for (int j = 0; j < minv; ++j)
ans.push_back(pii(1, i));
}
}
void col()
{
for (int i = 1; i <= m; ++i)
{
int minv = INF;
for (int j = 1; j <= n; ++j)
minv = min(minv, g[j][i]);
for (int j = 1; j <= n; ++j)
g[j][i] -= minv;
for (int j = 0; j < minv; ++j)
ans.push_back(pii(0, i));
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> g[i][j];
if (m <= n)
col(), row();
else
row(), col();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (g[i][j])
{
cout << -1 << endl;
return 0;
}
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); ++i)
{
cout << (ans[i].first ? "row "
: "col ")
<< ans[i].second << endl;
}
}

这次CF又掉分了,B题被SystemJudge搞死了,所以还是要提高自己的姿势水平,提高码力啊qwq