Rk#57 (1h22min AK, Unofficial)

A. Escalator Conversations

题意

有一个电梯，有 mm 级台阶，第 i (1≤i≤m)i\ (1\le i \le m) 级高度为 i⋅ki\cdot k。
现在你的身高为 HH，其他有 nn 个人的身高为 h1,h2,…,hnh_1,h_2,\ldots,h_n。

两个人可以对话，当且仅当它们站在不同的电梯台阶上且电梯台阶的高度差等于它们的身高差。请问：你可以分别和不同的几个人对话？

解法

两个人可以对话，当且仅当身高差 Δh=p⋅k (p∈Z,1≤p<m)\Delta h = p\cdot k\ (p \in Z,1\le p <m)，O(n)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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

void solve(int kase){
    int n=read(),m=read(),k=read(),h=read();
    int ans = 0;
    for(int i=1;i<=n;i++){
        int a=read();
        int diff = abs(a-h);
        if(diff%k==0){
            diff/=k;
            if(diff>0 && diff<m){
                ans++;
            }
        }
    }
    printf("%d\n",ans);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

B. Parity Sort

题意

有一个序列 a1,a2,…,ana_1,a_2,\ldots,a_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
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;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N= 2e5+5;
bool even[N];
void solve(int kase){
    int n=read();
    vector<int> v1,v2;
    for(int i=0;i<n;i++){
        int x=read();
        if(x%2==0){
            even[i]=1;
            v2.push_back(x);
        }
        else{
            even[i]=0;
            v1.push_back(x);
        }
    }

    sort(all(v1));
    sort(all(v2));

    vector<int> a;
    auto it1=v1.begin(),it2=v2.begin();
    for(int i=0;i<n;i++){
        if(even[i])a.push_back(*(it2++));
        else a.push_back(*(it1++));
    }
    if(is_sorted(all(a)))YES;
    else NO;
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

C. Tiles Comeback

题意

有 nn 个格子，每个格子的颜色为 cic_i。
有整数 kk，请问你是否能从 nn 个格子中选出 pp 个（必须要选第一个和最后一个），使得：

  • pp 是 kk 的倍数；
  • pp 个格子按 kk 个分组后，组内颜色都相同。

解法

注意到一定要选第一个和最后一个。我们直接贪心。

如果第一个和最后一个颜色一样，只要第一个的颜色的格子超过 kk 个，就有合法解。
如果第一个和最后一个颜色不一样，我们找到第一个格子颜色的格子超过 kk 个至少需要的左端点，以及最后一个格子颜色的格子超过 kk 个的右端点，只要左端点小于右端点，那么就可以构造出长度为 2k2k 的一个合法解。

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

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
int c[N];
void solve(int kase){
    int n=read(),k=read();
    for(int i=0;i<n;i++){
        c[i]=read();
    }

    if(c[0]==c[n-1]){
        int cnt = 0;
        for(int i=0;i<n;i++){
            if(c[i]==c[0])cnt++;
        }

        if(cnt>=k)YES;
        else NO;
    }
    else{
        int cnt=0;int pos1=-1,pos2=-1;
        for(int i=0;i<n;i++){
            if(c[i]==c[0])cnt++;

            if(cnt==k){
                pos1=i;break;
            }
        }
        cnt=0;
        for(int i=n-1;i>=0;i--){
            if(c[i]==c[n-1])cnt++;

            if(cnt==k){
                pos2=i;break;
            }
        }

        if(pos1==-1 || pos2==-1){
            NO;
        }else{
            if(pos1<pos2)YES;
            else NO;
        }
    }
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

D. Prefix Permutation Sums

题意

给你一个前缀和，但是被删去了一个数。请判断给你的这个残缺的前缀和是否可能是由一个 1∼n1\sim n 排列的前缀和删去一个数得来的。

解法

我们先做一次前缀差，得到 n−1n-1 个数。前缀差这么定义：

d1=a1,di=ai−ai−1 (i≥2)d_1=a_1,\\ d_i=a_i-a_{i-1} \ (i\ge 2)

我们观察一下这个前缀差。

  1. 如果前缀和删去的是最后一个前缀和，那么前缀差就是 1∼n1\sim n 中的 n−1n-1 个不同整数。
  2. 如果前缀和删去的是中间的一个前缀和，那么有一个前缀差就是剩下没出现两个元素的和。

第一种情况很好维护，看看第二种情况，我们用一个 vector 动态维护如果不算第 ii 个前缀差，剩下的前缀差在 1∼n1\sim n 中还缺少哪些。如果缺少两个并且第 ii 个前缀差就是这两个的和，那么就有解。

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

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
T read(){
    T f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
ll a[N],d[N];
int vis[N];
void solve(int kase){
    int n=read();
    for(int i=1;i<n;i++){
        a[i]=read<ll>();
        d[i]=a[i]-a[i-1]; // 前缀差
    }
    for(int i=1;i<=n;i++){
        vis[i]=0; // 1~n 这个数出现了几次
    }

    int cnt = 0;
    for(int i=1;i<n;i++){
        if(1<=d[i] && d[i]<=n){
            vis[d[i]]++; 
            if(vis[d[i]]==1)cnt++;
        }       
    }
    if(cnt==n-1){
        YES;
        return;
    }

    vector<ll> loss; // 1~n 中还缺少的元素
    for(int i=1;i<=n;i++){
        if(vis[i]==0)loss.push_back(i); 
    }

    for(int i=1;i<n;i++){
        if(1<=d[i] && d[i]<=n){ // 动态维护缺少的元素
            vis[d[i]]--;
            if(vis[d[i]]==0)loss.push_back(d[i]);
        }       

        if(loss.size()==2){
            if(loss[0]+loss[1]==d[i]){
                YES;
                return;
            }
        }

        if(1<=d[i] && d[i]<=n){ // 动态维护缺少的元素
            vis[d[i]]++;
            if(vis[d[i]]==1)loss.pop_back();
        }
    }
    NO;
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

E. Nastya and Potions

题意

有 nn 个药水，每个卖 cic_i 元。
现在有 kk 个药水 m1,m2,…,mkm_1,m_2,\ldots,m_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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
T read(){
    T f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
ll cost[N];
vector<int> recipe[N];
vector<int> G[N];
ll in[N];

void solve(int kase){
    int n=read(),k=read();
    for(int i=1;i<=n;i++){
        cost[i]=read();
        recipe[i].clear();G[i].clear();
        in[i]=0;
    }

    for(int i=1;i<=k;i++){
        int p=read();
        cost[p]=0;
    }

    queue<int> q;

    for(int i=1;i<=n;i++){
        int l=read();
        for(int j=1;j<=l;j++){
            recipe[i].push_back(read());
        }

        if(cost[i]!=0){
            for(int j:recipe[i]){
                in[i]++;
                G[j].push_back(i);
            }

            if(in[i]==0)q.push(i);
        }else{
            q.push(i);
        }
    }

    while(q.size()){
        int u=q.front();q.pop();

        if(recipe[u].size()){
            ll price = 0;
            for(int v:recipe[u]){
                price+=cost[v];
            }

            cost[u]=min(cost[u],price);
        }

        for(int v:G[u]){
            in[v]--;
            if(in[v]==0)q.push(v);
        }
    }

    for(int i=1;i<=n;i++){
        printf("%lld ",cost[i]);
    }
    puts("");
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

F. Lisa and the Martians

题意

有 nn 个在 [0,2k)[0,2^k) 范围内的整数 a1,a2,…,ana_1,a_2,\ldots,a_n，你要确定 i,j,x (1≤i,j≤n,i≠j,0≤x<2k)i,j,x\ (1\le i,j\le n,i\ne j, 0\le x < 2^k)，使得 (ai⊕x)&(aj⊕x)(a_i\oplus x)\&(a_j\oplus x) 最大。

解法

我们注意到一个事实。(ai⊕x)&(aj⊕x)(a_i\oplus x)\&(a_j\oplus x) 最大等价于 ai⊕aja_i \oplus a_j 最小。因为若 aia_i 和 aja_j 的某一位相同，那么 xx 只要这一位和它们反着取，就可以让最终答案的这一位置为 11。所以答案即为 ¬(ai⊕aj)\neg (a_i \oplus a_j)。（注意我们这里的取反指的是 kk 位内的取反）

现在问题转化为求这些数的异或最小值。由 ABC308G 我们知道，异或最小值一定是在排序之后，两两异或得到的。（如果你不知道这个性质，开一颗 Trie，O(nlog⁡n)O(n\log n) 找到异或最小值）

这样就可以找到异或最小值，xx 的值即为 ¬(ai&aj)\neg (a_i \& a_j)。复杂度 O(n)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
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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
T read(){
    T f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

const int N = 2e5+5;
pii a[N];

void solve(int kase){
    int n=read(),k=read();
    for(int i=1;i<=n;i++){
        a[i]={read(),i};
    }
    sort(a+1,a+1+n);

    int ans = INT_MAX;
    int p,q,a1,a2;

    for(int i=2;i<=n;i++){
        if((a[i].first^a[i-1].first)<ans){
            ans = a[i].first^a[i-1].first;
            p=a[i].first,q=a[i-1].first;
            a1=a[i].second,a2=a[i-1].second;
        }
    }
    int x = ((1<<k)-1)&(~(p&q));
    printf("%d %d %d\n",a1,a2,x);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

G. Vlad and the Mountains

题意

有 nn 个节点，每个节点有高度 hih_i。有 mm 条无向道路。若从节点 ii 走到节点 jj，需要消耗 hj−hih_j-h_i 个能量（当 hj−hi<0h_j-h_i<0 时恢复能量）。你的能量不能在任意时刻小于 00。

你要回答 qq 个询问。每个询问是：假设你初始有 ee 点能量，能不能从 uu 点走到 vv 点。

解法

首先我们注意到一个事实，初始有 ee 点能量，从 uu 能且仅能经过高度小于等于 hu+eh_u+e 的节点。我们只需要判断在这么一些节点中，是否能让 uu 走到 vv 即可。

下一步，我们离线处理每个询问，按照 hu+eh_u+e 排序，小的先处理。每次处理一个询问时，把新加入的节点所连的边连起来（用并查集），最后判断 uu 个 vv 是否在一个连通分量内即可。

复杂度 O(qlog⁡q+nlog⁡n)O(q\log q + n\log 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
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;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
T read(){
    T f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

const int N = 2e5+5;
vector<int> G[N];

int fa[N];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int i,int j){
    fa[find(i)]=find(j);
}

struct Query
{
    int u,v,val,id;
} q[N];


pii h[N];
int ans[N];
bool ok[N];

void solve(int kase){
    int n=read(),m=read();
    for(int i=1;i<=n;i++){
        h[i]={read(),i};
        ok[i]=0;
        fa[i]=i;
        G[i].clear();
    }

    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        G[u].push_back(v);
        G[v].push_back(u);
    }

    int c=read();
    for(int i=0;i<c;i++){
        int u=read(),v=read(),e=read();
        q[i]={u,v,h[u].first+e,i};
    }

    sort(q,q+c,[](const Query& a,const Query& b){
        return a.val<b.val;
    });

    sort(h+1,h+1+n);
    int now = 1;
    for(int i=0;i<c;i++){(now<=n && h[now].first<=q[i].val){
            int u = h[now].second;
            ok[u]=1;
            for(int v:G[u]){
                if(ok[v]){
                    merge(u,v);
                }
            }
            now++;
        }


        if(find(q[i].u)==find(q[i].v))ans[q[i].id]=1;
        else ans[q[i].id]=0;
    }

    for(int i=0;i<c;i++){
        if(ans[i])YES;
        else NO;
    }
}   


int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}