题目链接：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;
}