Blackops

初心易得，始终难守

0%

CF Educational #37 A B C E F G

发表于 更新于 分类于 ，

A.Water The Garden

题意就是给你$n$个待浇水的位置和$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
#include <bits/stdc++.h>
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 CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
int arr[210];
int vis[210];

int main(void)
{
    int T, n, i;
    scanf("%d", &T);
    while (T--)
    {
        int n, k;
        scanf("%d%d", &n, &k);
        for (i = 0; i < k; ++i)
        {
            scanf("%d", &arr[i]);
        }
        int ans = 0 ;
        for (i = 1; i <= 200; ++i)
        {
            CLR(vis, 0);
            for (int j = 0; j < k; ++j)
            {
                for (int l = arr[j]; l >= arr[j] - (i - 1) && l >= 1; --l)
                    vis[l] = 1;
                for (int l = arr[j]; l <= arr[j] + (i - 1) && l <= n; ++l)
                    vis[l] = 1;
            }
            if (accumulate(vis + 1, vis + 1 + n, 0) == n)
            {
                ans = i;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

B.Tea Queue

题意就是给你$n$个人和他的开始排队时间$l_i$，离开队伍时间$r_i$，按照开始排队时间进行入队，顺序小的排在前面，如果领到茶的时间大于$r_i$，那么这个人会离开队伍，求最后每个人领到茶的时间，无法领到记为$0$
优先队列维护排队顺序，然后按时间模拟一下，该领茶的领茶，该离开的离开。

代码：

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
#include <bits/stdc++.h>
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 CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1010;
int l[N], r[N];
struct info
{
    int l, r, id;
    bool operator<(const info &rhs)const {
        return l > rhs.l || (l == rhs.l && id > rhs.id);
    }
} arr[N];
int ans[N];

int main(void)
{
    int T, n, i;
    scanf("%d", &T);
    while (T--)
    {
        CLR(ans, 0);
        scanf("%d", &n);
        for (i = 1; i <= n; ++i)
        {
            scanf("%d%d", &l[i], &r[i]);
            arr[i].l = l[i];
            arr[i].r = r[i];
            arr[i].id = i;
        }
        sort(arr + 1, arr + 1 + n, [](info a, info b) {return a.l < b.l || (a.l == b.l && a.id < b.id);});
        int tm = 1;
        int sz = 1;
        priority_queue<info>Q;
        for (tm = 1; ; ++tm)
        {
            while (tm == arr[sz].l && sz <= n)
                Q.push(arr[sz++]);
            if (Q.empty())
                continue;
            info one = Q.top();
            Q.pop();
            if (one.r >= tm)
            {
                ans[one.id] = tm;
            }
            else
            {
                ans[one.id] = 0;
                --tm;
            }
            if (Q.empty() && sz > n )
                break;
        }
        for (i = 1; i <= n; ++i)
            printf("%d%c", ans[i], " \n"[i == n]);
    }
    return 0;
}

C.Swap Adjacent Elements

题意就是给你$n$个数，和一串字符串，表示一些位置是否可以和它前面一个位置交换数字，交换顺序和次数不限，求最后整个数列能否排成不降数列。

由于交换顺序和次数不限，因此连续的$1$对应的区间内一定是可以被排序的，因此可以把字符串中连续的$’1’$找到，然后把数列中对应的连续区间$sort$一下，这里要注意$s[i]==1$表示第$i$个位置可以和第$i+1$个位置交换，因此实际排序连续区间为$[l,r+1]$

代码：

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
#include <bits/stdc++.h>
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 CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 200010;
int arr[N];
char s[N];

int main(void)
{
    int n, i;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
        scanf("%d", &arr[i]);
    scanf("%s", s + 1);
    int l = -1, r = 0;
    for (i = 1; i <= n; ++i)
    {
        if(s[i] == '1')
        {
            if(l == -1)
                l = i;
            ++r;
        }
        else
        {
            if(l == -1)
                continue;
            sort(arr + l, arr + min(l + r + 1, n + 1));
            l = -1;
            r = 0;
        }
    }
    puts(is_sorted(arr + 1, arr + 1 + n) ? "YES" : "NO");
    return 0;
}

E.Connected Components?

题意就是给你$n$个点的完全图和$m$条边，表示有$m$对点对之间的边被删掉了，求最后图内连通块的个数和每个连通块的大小。

实际上这题就是暴力$BFS$所有连通块大小，看似复杂度很高，实际上如果只考虑点的话，$BFS$只把那些没访问过的点搜索一次，这样一来复杂度大大下降，用$map$记录一下删掉的边即可，燃鹅这里有个问题，每一次$for$邻接点的不能是$[1,n]$，这样就算一些点不会入队，但是循环次数仍然很多，很可惜没想到用set T到比赛结束……，实际应该用$set$优化，$set$记录图中未访问过的点，每一次把访问过的点从$set$中$erase$掉就可以用了，当然在遍历的时候$erase$可能会使迭代器失效报错，应该把要$erase$的点储存一下，遍历完后再删掉即可。

代码：

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
#include <bits/stdc++.h>
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 CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 200010;
int sz[N],  vis[N], vs;

unordered_map<int, int>no[N];
int n;
set<int>st;
int toerase[N], top;

int bfs(int s)
{
    queue<int>Q;
    Q.push(s);
    vis[s] = 1;
    st.erase(s);
    int ret = 1;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for (auto &v : st)
        {
            if (vis[v])
                continue;
            if (!no[u].count(v))
            {
                vis[v] = 1;
                ++ret;
                toerase[top++] = v;
                if (vs + ret >= n)
                    return ret;
                Q.push(v);
            }
        }
        while (top)
            st.erase(toerase[--top]);
    }
    return ret;
}
int main(void)
{
    register int m, i, a, b;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= m; ++i)
    {
        scanf("%d%d", &a, &b);
        no[a][b] = no[b][a] = 1;
    }
    for (i = 1; i <= n; ++i)
        st.insert(i);
    int Sz = 0;
    for (i = 1; i <= n; ++i)
        if (!vis[i])
            sz[Sz++] = bfs(i);
    sort(sz, sz + Sz);
    printf("%d\n", Sz);
    for (i = 0; i < Sz; ++i)
        printf("%d%c", sz[i], " \n"[i == Sz - 1]);
    return 0;
}

F.SUM and REPLACE

题意就是给你$n$的数的序列，记$D(x)$表示$x$的因子数，给定两种操作：
1.把$[l,r]$的每一个数$x$变成$D(x)$
2.求和$[l,r]$

先打个$D(x)$的表，一个数的因子数个数为它分解后所有的素因数上的指数$+1$的连乘。
然后就是个线段树剪枝优化问题，主要在于求和和更新的时候如果一个区间内的数完全相同，那么可以直接得到答案而不需要递归下去。

太菜了，$openinghack$之后被$1\;2\;1\;2….$这样的数据卡超时了，那么上再加一个区间是否需要被更新的标记$eq$就行了，如果这个整个区间都小于$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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
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 CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 3e5 + 7;
int phi[1000005];
int arr[N];

void pre(int n)
{
    for (register int i = 1; i <= n; ++i)
        for (register int j = i; j <= n; j += i)
            ++phi[j];
}
struct seg
{
    int l, mid, r, eq;
    LL v, one;
    inline int len() {
        return r - l + 1;
    }
} T[N << 2];

inline void pushup(int k)
{
    T[k].v = T[LC(k)].v + T[RC(k)].v;
    T[k].one = (T[LC(k)].one == T[RC(k)].one ? T[LC(k)].one : 0);
    T[k].eq = T[LC(k)].eq & T[RC(k)].eq;
}
inline void pushdown(int k)
{
    if (T[k].one && !T[k].eq)
    {
        T[LC(k)].one = T[RC(k)].one = T[k].one;
        T[LC(k)].v = (LL)T[LC(k)].len() * T[k].one;
        T[RC(k)].v = (LL)T[RC(k)].len() * T[k].one;
        T[k].one = 0;
    }
}
void update(int k, int l, int r)
{
    if (T[k].eq)
        return ;
    if (l <= T[k].l && T[k].r <= r && T[k].one)
    {
        T[k].one = phi[T[k].one];
        T[k].v = (LL)T[k].len() * T[k].one;
    }
    else
    {
        pushdown(k);
        if (l <= T[k].mid)
            update(LC(k), l, r);
        if (r > T[k].mid)
            update(RC(k), l, r);
        pushup(k);
    }
}
LL query(int k, int l, int r)
{
    if (l <= T[k].l && T[k].r <= r)
        return T[k].v;
    else
    {
        pushdown(k);
        LL ret = 0;
        if (l <= T[k].mid)
            ret += query(LC(k), l, r);
        if ( r > T[k].mid)
            ret += query(RC(k), l, r);
        return ret;
    }
}
void build(int k, int l, int r)
{
    T[k].l = l;
    T[k].r = r;
    T[k].mid = MID(l, r);
    if (l == r)
        T[k].one = T[k].v = arr[l], T[k].eq = (T[k].v <= 2);
    else
    {
        build(LC(k), l, T[k].mid);
        build(RC(k), T[k].mid + 1, r);
        pushup(k);
    }
}
int main(void)
{
    register int n, m, i, l, r, ops;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; ++i)
        scanf("%d", &arr[i]);
    pre(*max_element(arr + 1, arr + 1 + n));
    build(1, 1, n);
    while (m--)
    {
        scanf("%d%d%d", &ops, &l, &r);
        if (ops == 1)
            update(1, l, r);
        else
            printf("%I64d\n", query(1, l, r));
    }
    return 0;
}

G.List Of Integers

题意就是给你一堆询问${x,p,k}$，求大于$x$和$p$互质的数中第$k$小的数。

这里涉及到求$[1,n]$中与$p$互质的数的个数问题，需要用到容斥原理，如果$[1,p]$的话就可以直接欧拉函数了，但这个范围是会变的，因此我们应该算$[1,n]$中与$p$不互质的数的个数，因此求法如下：

  1. 将$p$质数分解（10+的阶乘就超过1e6了，最多只有十几个质数）
  2. 状压枚举用了哪些质数。
  3. 假设用到的质数的个数为$t$，乘积为$w$。
  4. 容斥原理可得当$t$为奇数的时候，答案应减去$n/w$，否则加上$n/w$。

好吧其实上面只是算出了$[1,n]$中不互质的个数,用$n$再减一下就是互质的个数了，然后得到$[1,n]$的计数，$[l,r]$的答案差分一下就是$[1,r] - [1,l-1]$。
由于题目固定左端点为$x+1$，那么二分一下右端点即可。

代码：

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
#include <bits/stdc++.h>
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 CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 12;
int P[N], sz;

inline void getfac(int n)
{
    sz = 0;
    for (int i = 2; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
            P[sz++] = i;
            while (n % i == 0)
                n /= i;
        }
    }
    if (n > 1)
        P[sz++] = n;
}
inline int calc(int l, int r)
{
    int R = 1 << sz;
    int ans = 0;
    for (register int i = 1; i < R; ++i)
    {
        int t = 1, one = 0;
        for (register int j = 0; j < N; ++j)
        {
            if ((i >> j) & 1)
                t *= P[j], ++one;
        }
        if (one & 1)
        {
            ans += r / t;
            ans -= (l - 1) / t;
        }
        else
        {
            ans -= r / t;
            ans += (l - 1) / t;
        }
    }
    return r - l + 1 - ans;
}
int main(void)
{
    register int T, x, p, k;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d", &x, &p, &k);
        int L = x + 1, R = 1e8;
        int ans = 0;
        getfac(p);
        while (L <= R)
        {
            int mid = MID(L, R);
            if (calc(x + 1, mid) >= k)
            {
                ans = mid;
                R = mid - 1;
            }
            else
                L = mid + 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}