Codeforces Round 1002 (Div. 2)

A. Milya and Two Arrays

看两个数组能组成多少个不同的数即可。

 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>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

int n;
int a[N],b[N];
map<int,int>vis1,vis2;

void solve(){
    cin>>n;
    vis1.clear();vis2.clear();
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    int cnt1=0,cnt2=0;
    for(int i=1;i<=n;i++){
        if(!vis1[a[i]])cnt1++;
        vis1[a[i]]++;
    }
    for(int i=1;i<=n;i++){
        if(!vis2[b[i]])cnt2++;
        vis2[b[i]]++;
    }
    if(cnt1*cnt2>=3)cout<<"YES\n";
    else cout<<"NO\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

B. Cost of the Array

如果 n==k, 按顺序检查过去即可。

若 n!=k，答案只会有 1 或 2 这两种情况。

b 的起始位置可以是 [2,n-k+2] 中的任意一个，如果其中有不是 1 的，让 b 从这里开始，答案为 1。

若其中全为 1，答案就是 2，因为可以取靠前的一个位置，这样第二部分也是 1，答案就为 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


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e5+7, mod=1e9+7;

int n,k;
int a[N];

void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    int ans=-1;
    if(n==k){
        for(int i=2;i<=n;i+=2){
            if(a[i]!=i/2){
                ans=i/2;
                break;
            }
        }
        if(ans==-1)ans=n/2+1;
    }else{
        for(int i=2;i<=n-k+2;i++){
            if(a[i]!=1){
                ans=1;
                break;
            }
            else ans=2;
        }
    }
    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

C. Customer Service

看的是最后时刻，考虑后缀和，同时注意到是 MEX 的值，考虑后缀连续 1 片段。

记录每个队列后缀的连续 1 片段长度，排序后统计 MEX 值即可。

 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>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e3+7, mod=1e9+7;

int n,a[N][N],t[N];

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)cin>>a[i][j];
    for(int i=1;i<=n;i++){
        for(int j=n;j>=0;j--){
            if(a[i][j]!=1){
                t[i]=n-j;
                break;
            }
        }
    }
    sort(t+1,t+1+n);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(t[i]>ans)ans++;
    }
    cout<<min(ans+1,n)<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

D. Graph and Graph

会有无限大的情况，因为每一步的代价都是非负的，那么非无限大的情况才是特殊情况，如何找到这种情况是解题的关键。

注意到，如果 v1==v2，此时的代价就是 0，如果能无限循环这一步，答案就非无限大，即两个图中有条同样的边。

首先看范围，都小于 1e3，可以采用 $n^2$，来处理，用数组 f[i][j] 来记录两图移动到 i,j 位置上的最小代价，用 dijkstra 处理即可。

 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;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
#define int long long
const int N=1e3+7, mod=1e9+7, INF=1e9+7;

struct Node{
    int x,u,v;
    bool operator > (const Node t) const {
        return x>t.x;
    }
};

int n,s1,s2,m1,m2,ans;
int f[N][N];
vector<int>g1[N],g2[N];
bool vis[N][N];
bool G1[N][N],G2[N][N];
priority_queue<Node, vector<Node>, greater<Node>> pq;

void solve(){
    cin>>n>>s1>>s2;
    cin>>m1;
    for(int i=1;i<=n;i++){
        g1[i].clear();
        g2[i].clear();
        for(int j=1;j<=n;j++){
                f[i][j]=INF;
                G1[i][j]=G2[i][j]=0;
                vis[i][j]=0;
        }
    }
    for(int i=1;i<=m1;i++){
        int u,v;
        cin>>u>>v;
        g1[u].push_back(v);
        g1[v].push_back(u);
        G1[u][v]=G1[v][u]=1;
    }
    cin>>m2;
    for(int i=1;i<=m2;i++){
        int u,v;
        cin>>u>>v;
        g2[u].push_back(v);
        g2[v].push_back(u);
        G2[u][v]=G2[v][u]=1;
    }
    f[s1][s2]=0;
    while(!pq.empty()) pq.pop();
    pq.push({0,s1,s2});
    while(!pq.empty()){
        Node t=pq.top();
        pq.pop();
        int u1=t.u,u2=t.v,x=t.x;
        if(vis[u1][u2])continue;
        vis[u1][u2]=1;
        for(auto v1:g1[u1]){
            for(auto v2:g2[u2]){
                f[v1][v2]=min(f[v1][v2],x+abs(v1-v2));
                pq.push({f[v1][v2],v1,v2});
            }
        }
    }
    ans=INF;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(G1[i][j]&&G2[i][j]){
                ans=min({ans,f[i][i],f[j][j]});
            }
        }
    }
    if(ans==INF)cout<<-1<<endl;
    else cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}