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() {vcoistntint _=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() {vcoistntint _=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() {vcoistntint _=1;cin>>_;while(_--) solve();return 0;
}