2022牛客多校3

C. Concatenation

  • 拼接 个字符串,使得字典序最小

比较经典的问题了,判断

时间复杂度据出题人说是

不过正解是建 ,根据 序维护有序链表。

由于出题人怕卡常就让 复杂度的也过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
vector<string> s(n);
for(auto &i:s)cin>>i;
sort(s.begin(),s.end(),[](string a,string b){
return a+b<b+a;
});
for(auto &i:s)cout<<i;
}

A. Ancestor

一开始的题面实在谜语人

  • 树,每个顶点都有权值,给定 个顶点的集合 ,问有多少种方案,从 中删除一个顶点,使得 中的 的权值大于 的权值

先给出一个结论,一群点的 等于 序最小的点和 序最大的点的

那么做法就很显然了。

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
#include <bits/stdc++.h>
using namespace std;
struct Graph{
int tail,n;
struct Edge{int ne,to;};
vector<int> head,fa,siz,dep,son,dfn,rnk,top;
vector<Edge> edge;
void add(int x,int y){
edge[++tail]={head[x],y};head[x]=tail;
}
Graph(int x,int y){
tail=0;n=x;
head.assign(x+1,0);
edge.assign(y+1,{0,0});
fa.assign(x+1,0);
siz.assign(x+1,0);
dep.assign(x+1,0);
son.assign(x+1,0);
dfn.assign(x+1,0);
rnk.assign(x+1,0);
top.assign(x+1,0);
}
void hld(int root){
function<void(int)> dfs1=[&](int t){
dep[t]=dep[fa[t]]+1;
siz[t]=1;
for(int i=head[t],to;i;i=edge[i].ne){
to=edge[i].to;
if(to==fa[t])continue;
fa[to]=t;
dfs1(to);
if(siz[son[t]]<siz[to])son[t]=to;
siz[t]+=siz[to];
}
};dfs1(root);
int dfn_tail=0;
for(int i=1;i<=n;i++)top[i]=i;
function<void(int)> dfs2=[&](int t){
dfn[t]=++dfn_tail;
rnk[dfn_tail]=t;
if(!son[t])return;
top[son[t]]=top[t];
dfs2(son[t]);
for(int i=head[t],to;i;i=edge[i].ne){
to=edge[i].to;
if(to==fa[t]||to==son[t])continue;
dfs2(to);
}
};dfs2(root);
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]])x=fa[top[x]];
else y=fa[top[y]];
}
return dep[x]>dep[y]?y:x;
}
};

void solve(){
int n,k;
cin>>n>>k;
vector<int> x(k);
vector<int> val1(n+1),val2(n+1);
for(auto &i:x)cin>>i;

for(int i=1;i<=n;i++)cin>>val1[i];
Graph g1(n,n-1);
for(int i=2,j;i<=n;i++){
cin>>j;
g1.add(j,i);
}
g1.hld(1);

for(int i=1;i<=n;i++)cin>>val2[i];
Graph g2(n,n-1);
for(int i=2,j;i<=n;i++){
cin>>j;
g2.add(j,i);
}
g2.hld(1);

set<pair<int,int>> tree1,tree2;
for(auto &i:x){
tree1.insert({g1.dfn[i],i});
tree2.insert({g2.dfn[i],i});
}
int ans=0;
for(auto &i:x){
tree1.erase({g1.dfn[i],i});
tree2.erase({g2.dfn[i],i});
int lca1=g1.lca((*tree1.begin()).second,(*tree1.rbegin()).second);
int lca2=g2.lca((*tree2.begin()).second,(*tree2.rbegin()).second);
tree1.insert({g1.dfn[i],i});
tree2.insert({g2.dfn[i],i});
if(val1[lca1]>val2[lca2])ans++;
}
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
}

J. Journey

  • 每个路口连着其他路口,定义 路口到 路口的那条路,当你在 这条路上时,你可以左转,直行,右转,掉头,除了右转不需要等待红灯外,其他都需要。问从一条路到另一条路的需要等待红灯数量最小是多少?

我们将 看成点, 连着一条边,如果是右转的话,权值是 ,否则权值是

从起点到终点跑一下最短路就好了。

这题用 常数爆炸,可以用

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
#include<bits/stdc++.h>
using namespace std;
inline int inc(int x,int mo){
return x>=mo?x-mo:x;
}
struct Edge{
int ne,to,w;
};
struct comp{
long long operator()(pair<int,int> x)const{
return 1ll*x.first*521417+x.second;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
unordered_map<pair<int,int>,int,comp> roads;
int tail=0;
vector<int> head(4000005,0);
vector<Edge> edge(4000005*6,{0,0});
auto add=[&](int x,int y,int z){
edge[++tail]={head[x],y,z};
head[x]=tail;
};
int idx=0;
for(int i=1;i<=n;i++){
int road[4];
for(int j=0;j<4;j++){
cin>>road[j];
if(!road[j])continue;
if(!roads.count({road[j],i}))roads[{road[j],i}]=++idx;
if(!roads.count({i,road[j]}))roads[{i,road[j]}]=++idx;
}
for(int j=0;j<4;j++){
if(!road[j])continue;
if(road[inc(j+1,4)])add(roads[{road[j],i}],roads[{i,road[inc(j+1,4)]}],0);
if(road[inc(j+2,4)])add(roads[{road[j],i}],roads[{i,road[inc(j+2,4)]}],1);
if(road[inc(j+3,4)])add(roads[{road[j],i}],roads[{i,road[inc(j+3,4)]}],1);
add(roads[{road[j],i}],roads[{i,road[j]}],1);
}
}
auto dij=[&](int s,int t){
priority_queue<pair<int,int>> que;
vector<int> v(4000005,0),dis(4000005,0x3f3f3f3f);
dis[s]=0;
que.emplace(0,s);
while(!que.empty()){
int t=que.top().second;que.pop();
if(v[t])continue;
v[t]=0;
for(int i=head[t],to,w;i;i=edge[i].ne){
w=dis[t]+edge[i].w;
to=edge[i].to;
if(dis[to]>w){
dis[to]=w;
que.emplace(-dis[to],to);
}
}
}
return dis[t];
};
int s1,s2,t1,t2;
cin>>s1>>s2>>t1>>t2;
int s=roads[{s1,s2}],t=roads[{t1,t2}];
int ans=dij(s,t);
if(ans==0x3f3f3f3f)ans=-1;
cout<<ans<<"\n";
}
发布于

2022-07-25

更新于

2022-07-25

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...