Blackops

初心易得，始终难守

0%

CF Educational #41 A B C D E

发表于 分类于 ，

A.Tetris

题意就是有一个$n\times 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
48
49
50
51
52
53
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1010;
int G[N];

int main(void)
{
    int n, m, i, j;
    while (~scanf("%d%d", &n, &m))
    {
        for (i = 1; i <= m; ++i)
        {
            int x;
            scanf("%d", &x);
            ++G[x];
        }
        int cnt = 0;
        while (1)
        {
            int flag = 0;
            int Min = INF;
            for (i = 1; i <= n; ++i)
            {
                if (G[i] == 0)
                {
                    flag = 1;
                    break;
                }
                Min = min(G[i], Min);
            }
            if (flag)
                break;
            for (i = 1; i <= n; ++i)
                G[i] -= Min;
            cnt += Min;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

B.Lecture Sleep

题意就是有$n$分钟的时间有时候学习有时候睡觉，每分钟如果学习的话可以获得$a_i$的知识量，你可以选择强行学习$k$分钟，求$n$分钟之后最多能学到的知识。

枚举强行学习的区间$[i,i+k-1]$，那么此时答案是

$sum_{正常学习}(1,i-1)+sum_{强行学习}(i,i+k-1)+sum_{正常学习}(i+k,n)$，所有的可能取最大值就是答案，其中$sum$用前缀和预处理优化一下就行。

代码：

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
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
LL a[N], t[N];
LL pre[N], re[N];

inline LL SUM(int l, int r)
{
    if (l <= 0)
        l = 1;
    if (r <= 0)
        r = 0;
    return pre[r] - pre[l - 1];
}
inline LL RE(int l, int r)
{
    if (l <= 0)
        l = 1;
    if (r <= 0)
        r = 0;
    return re[r] - re[l - 1];
}
int main(void)
{
    int n, k, i;
    scanf("%d%d", &n, &k);
    for (i = 1; i <= n; ++i)
    {
        scanf("%I64d", &a[i]);
        pre[i] = pre[i - 1] + a[i];
    }
    for (i = 1; i <= n; ++i)
        scanf("%I64d", &t[i]), re[i] = re[i - 1] + t[i] * a[i];
    LL ans = 0;
    for (i = 1; i <= n - k + 1; ++i)
    {
        ans = max(RE(1, i - 1) + SUM(i, i + k - 1) + RE(i + k, n), ans);
    }
    printf("%I64d\n", ans);
    return 0;
}

C.Chessboard

题意就是给你$4$个块$n \times n$的$01$矩阵，要拼成一块$2n \times 2n$的$01$矩阵使得任意相邻的数都不同，你可以修改矩阵中的数使得符合条件，求最少修改的次数

一开始没想法， 后来发现实际上任意相邻的数都不同的矩阵只有两种，$01010…$或$101010…$，因此只要预处理出这两种$2n \times 2n$的矩阵，然后暴力枚举四个给的矩阵分别是在哪四个位置即可。

代码：

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
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 110;
int A[4][N][N];

int one[N << 1][N << 1];
int two[N << 1][N << 1];

int n;
inline int calc(int l, int r, int ll, int rr, int x, int C[4][N][N], int ST[N << 1][N << 1])
{
    int c = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (C[x][l + i][r + j] != ST[ll + i][rr + j])
                ++c;
        }
    }
    return c;
}
int per[4] = {0, 1, 2, 3};

char pos[N][N];

int main(void)
{
    int i, j, k;
    scanf("%d", &n);
    for (i = 0; i < 4; ++i)
    {
        for (j = 0; j < n; ++j)
        {
            scanf("%s", pos[j]);
            for (k = 0; k < n; ++k)
            {
                A[i][j][k] = pos[j][k] - '0';
            }
        }
    }
    for (i = 0; i < 2 * n; ++i)
    {
        for (j = 0; j < 2 * n; ++j)
        {
            one[i][j] = (i + j) & 1;
        }
    }
    for (i = 0; i < 2 * n; ++i)
    {
        for (j = 0; j < 2 * n; ++j)
        {
            two[i][j] = one[i][j] ^ 1;
        }
    }
    int ans = INF;
    do
    {
        ans = min(ans, calc(0, 0, 0, 0, per[0], A, one) + calc(0, 0, n, n, per[1], A, one) + calc(0, 0, n, 0, per[2], A, one) + calc(0, 0, 0, n, per[3], A, one));
    }
    while (next_permutation(per, per + 4));
    sort(per, per + 4);
    do
    {
        ans = min(ans, calc(0, 0, 0, 0, per[0], A, two) + calc(0, 0, n, n, per[1], A, two) + calc(0, 0, n, 0, per[2], A, two) + calc(0, 0, 0, n, per[3], A, two));
    }
    while (next_permutation(per, per + 4));
    printf("%d\n", ans);
    return 0;
}

D.Pair Of Lines

题意就是给你$n$个点，问是否能用不会超过两根直线将所有的点覆盖所有的点。

计算几何没怎么学过，叉积也早就忘记了（弱渣瑟瑟发抖）。

实际上这题只要用任意两个点去构成一条直线，然后去掉这条直线上的点，再看剩下的点是否在一条直线上即可。那么怎么看三个点是否在一条直线上呢，用向量叉积的方法：设$a(x1,y1),b(x2,y2),c(x3,y3)$，由于叉积的几何意义可以表示两个向量所构成的平行四边形面积，$\vec A \times \vec B = |A| \times |B|*sin(\vec A,\vec B)$，叉积为$0$说明他们形成的面积为$0$，这不就刚好说明他们在一条直线上吗，以前还傻傻地用斜率做，还要特判垂直的情况233。

代码：

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
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const int N = 1e5 + 7;
const double eps = 1e-2;
struct P
{
    double x, y;
    friend P operator - (P a, P b)
    {
        a.x -= b.x;
        a.y -= b.y;
        return a;
    }
};

inline double X(const P&a, const P&b)
{
    return (a.x * b.y) - (a.y * b.x);
}
inline double online(const P&a, const P&b, const P&c)
{
    return fabs(X(a - c, b - c)) <= eps;
}
inline int check(vector<P> &one, int a, int b)
{
    int sz = one.size();
    if (sz <= 3)
        return 1;
    vector<P>res;
    for (int i = 0; i < sz; ++i)
    {
        if (i == a || i == b)
            continue;
        if (!online(one[a], one[b], one[i]))
            res.pb(one[i]);
    }
    sz = res.size();
    if (sz <= 2)
        return 1;
    for (int i = 2; i < sz; ++i)
    {
        if (!online(res[0], res[1], res[i]))
            return 0;
    }
    return 1;
}
int main(void)
{
    int n, i;
    double x, y;
    while (~scanf("%d", &n))
    {
        vector<P>one;
        for (i = 0; i < n; ++i)
        {
            scanf("%lf%lf", &x, &y);
            one.push_back({x, y});
        }
        if (check(one, 0, 1) || check(one, 0, 2) || check(one, 1, 2))
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

E.Tufurama

题意就是给你季$n$的节目单，season $x$有$1\sim y$个episode，求存在season $x$有第$y$个episode且第$y$个season有第$x$个episode的对数、

一开始用离线树状数组wa了好几次，最后一分钟用主席树才过……。可以发现season $x$如果和episode$y$组成对数，那么就存在$j \in [1,y]$，$season[j] \ge x$，转换下题目也就是求$1 \sim episode_i$中大于等于$i$的个数，然后要注意除掉自己，自己不能和自己一组，那么用主席树就可以做到这个了。

最后统计出来是所有的对数，因此答案要除以$2$

代码：

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
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 2e5 + 7;
int arr[N];

struct seg
{
    int ls, rs;
    LL v, add;
} T[N * 34];
int root[N], sz;

void build(int &x, int l, int r)
{
    x = ++sz;
    T[x].ls = T[x].rs = 0;
    T[x].add = 0;
    if (l == r)
        T[x].v = 0;
    else
    {
        int mid = MID(l, r);
        build(T[x].ls, l, mid);
        build(T[x].rs, mid + 1, r);
        T[x].v = T[T[x].ls].v + T[T[x].rs].v;
    }
}
void update(int &x, int y, int l, int r, int ql, int qr, int v)
{
    x = ++sz;
    T[x] = T[y];
    T[x].v += (LL)(qr - ql + 1) * (LL)v;
    if (ql <= l && r <= qr)
        T[x].add += v;
    else
    {
        int mid = MID(l, r);
        if (qr <= mid)
            update(T[x].ls, T[y].ls, l, mid, ql, qr, v);
        else if (ql > mid)
            update(T[x].rs, T[y].rs, mid + 1, r, ql, qr, v);
        else
            update(T[x].ls, T[y].ls, l, mid, ql, mid, v), update(T[x].rs, T[y].rs, mid + 1, r, mid + 1, qr, v);
    }
}
LL query(int x, int y, int l, int r, int ql, int qr)
{
    if (ql <= l && r <= qr)
        return T[x].v - T[y].v;
    LL add = (LL)(qr - ql + 1) * (T[x].add - T[y].add);
    int mid = MID(l, r);
    if (qr <= mid)
        return query(T[x].ls, T[y].ls, l, mid, ql, qr) + add;
    else if (ql > mid)
        return query(T[x].rs, T[y].rs, mid + 1, r, ql, qr) + add;
    else
        return query(T[x].ls, T[y].ls, l, mid, ql, mid) + query(T[x].rs, T[y].rs, mid + 1, r, mid + 1, qr) + add;
}
int main(void)
{
    int n, i;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
    {
        scanf("%d", &arr[i]);
        if (arr[i] > n)
            arr[i] = n;
    }
    LL ans = 0;
    build(root[1], 1, n);
    for (i = 1; i <= n; ++i)
    {
        update(root[i], root[i - 1], 1, n, arr[i], arr[i], 1);
    }
    for (i = 1; i <= n; ++i)
    {
        ans += query(root[arr[i]], root[0], 1, n, i, n);
        if (arr[i] >= i)//去掉自己和自己一组的情况
            --ans;
    }
    printf("%I64d\n", ans >> 1);
    return 0;
}