Codeforces Round 1002 (Div. 2)(A-D)

题目链接：Dashboard - Codeforces Round 1002 (Div. 2) - Codeforces

A. Milya and Two Arrays

思路

数组a中不同数的数量*数组b的，就是能够组成不同数的数量

代码

void solve(){
    int n;
    cin>>n;
    int cnt1=0;
    int cnt2=0;
    map<int,bool> mp;
    map<int,bool> mp1;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        if(!mp[x]){
            mp[x]=true;
            cnt1++;
        }
    }
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        if(!mp1[x]){
            mp1[x]=true;
            cnt2++;
        }
    }
    int t=cnt1*cnt2;
    if(t>=3){
        cout<<"YES\n";
    }else{
        cout<<"NO\n";
    }
}

B. Cost of the Array

思路

此题考查思维，有一个很恶心的点没考虑到wa了1发

首先我们了解到n=k时我们是没法操作的，结果是几就是几；

n>k时，我们贪心地去考虑，最终最小成本只能是1或2两种可能，这与前面1的数量(设为x)有关

我们最多只能将t=n-k+1个数放在一组里面

如果t>=x说明我们完全可以将前面的1全部放在第一个索引里面，这样再拼接时，b开头的第一个数就不是1，最小成本就是1

如果t<x说明我们将b开头的第一个数只能设为1，那么b={1,1...}这样就能使得最小成本为2

那么前面1的数量具体是什么，给出一个例子：

8 6

2 1 1 1 1 4 1 1

我们发现第一个数一定是要划分进索引1的所以我们就不用管，所以前面的1的数量是4，t-1<x的所以答案是2

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcount
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

void solve(){
    int n,k;
    cin>>n>>k;
    vi a(n+10);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int t=n-k;
    if(t==0){
        int ct=1;
        for(int i=2;i<=n;i+=2){
            if(a[i]==ct){
                ct++;
            }else{
                break;
            }
        }
        cout<<ct<<"\n";
    }else{
        int cnt=0;
        for(int i=2;i<=n;i++){
            if(a[i]==1) cnt++;
            else break;
        }
        if(t>=cnt){
            cout<<"1\n";
        }else{
            cout<<"2\n";
        }
    }
}
signed main() {
    vcoistnt
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

C. Customer Service

思路

看见n<=300以为可以直接暴力，结果

首先我们观察到这个和后缀和有关，0一定是在数组x中的，a>=1后缀和一定是单增的;

然后我们推以下1什么时候在x中，发现只有在一个队列里最后一个数为1时我们在n-1时刻将队列清零，最后得到1

以此根据a>=1来推2，3，4....

发现只有后缀全是1的数才能够可能将其添加至x，添加的范围为 [0,后缀1的数量] ，我们贪心地将其依次从小到大添加即可

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcount
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

void solve(){
    int n;cin>>n;
    vector<vi> a(n+10,vi(n+10));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    vi suf(n+10);
    for(int i=1;i<=n;i++){
        for(int j=n;j>=1;j--){
            if(a[i][j]!=1) break;
            suf[i]++;
        }
    }
    priority_queue<int,vector<int>,greater<int>> q;
    for(int i=1;i<=n;i++){
        q.push(suf[i]);
    }
    int ans=1;
    while(!q.empty()){
        int t=q.top();q.pop();
        if(t>=ans) ans++;
    }
    cout<<min(ans,n)<<"\n";
}
signed main() {
    vcoistnt
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

D. Graph and Graph

思路

最短路板子题，只要想到点实现并不困难

首先我们要明白什么时候它不是无限大的，发现当图1与图2同时存在u-v这条边，我们就可以一直在这两个顶点上移动，使得成本为0，这样就可以让成本固定

我们称这样的顶点为好顶点，那么我们只需要求图1从s1出发，图2从s2出发到同一个好顶点的最小成本即可，跑一遍djikstra

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcount
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

void solve(){
    int n,s1,s2;
    cin>>n>>s1>>s2;
    s1--,s2--;
    vector<vi> g1(n),g2(n);
    vb good(n);
    set<pll> edges;
    int m1;
    cin>>m1;
    for(int i=0;i<m1;i++){
        int v,u;
        cin>>v>>u;
        v--,u--;
        if(v>u) swap(v,u);
        edges.insert({v,u});
        g1[v].push_back(u);
        g1[u].push_back(v);
    }
    int m2;
    cin>>m2;
    for(int i=0;i<m2;i++){
        int v,u;
        cin>>v>>u;
        v--,u--;
        if(v>u) swap(v,u);
        if(edges.find({v,u})!=edges.end()){
            good[v]=true;
            good[u]=true;
        }
        g2[v].push_back(u);
        g2[u].push_back(v);
    }

    vector<vi> d(n,vi(n,inf));
    d[s1][s2]=0;
    priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> q;
    q.push({0,{s1,s2}});
    while(!q.empty()){
        auto [v,u]=q.top().second;
        q.pop();
        for(auto to1:g1[v]){
            for(auto to2:g2[u]){
                int w=abs(to1-to2);
                if(d[to1][to2]>d[v][u]+w){
                    d[to1][to2]=d[v][u]+w;
                    q.push({d[to1][to2],{to1,to2}});
                }
            }
        }
    }
    
    int ans=inf;
    for(int i=0;i<n;i++){
        if(!good[i]) continue;
        ans=min(ans,d[i][i]);
    }
    if(ans==inf) ans=-1;
    cout<<ans<<"\n";
}
signed main() {
    vcoistnt
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}