生活随笔
收集整理的这篇文章主要介绍了
Acwing第 25 场周赛【完结】
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
被T2演了好久，T3比较简单。
目录 4073. 找规律输出【签到】 4074. 铁路与公路【一般 / 思维 最短路】 4075. 染色【一般 / 并查集 贪心】
4073. 找规律输出【签到】
# include <bits/stdc++.h> using namespace std
;
int main ( void )
{ int n
; cin
>> n
; for ( int i
= 1 ; i
<= n
- 1 ; i
++ ) { if ( i
& 1 ) cout
<< "I hate that " ; else cout
<< "I love that " ; } if ( n
& 1 ) cout
<< "I hate it " ; else cout
<< "I love it " ; return 0 ;
}
4074. 铁路与公路【一般 / 思维 最短路】
可以确定的是，必有一种是直接1步从1-n的。 故两者跑最短路取一个max即可
# include <bits/stdc++.h> using namespace std
;
const int N
= 1e3 + 10 ;
int g
[ N
] [ N
] , w
[ N
] [ N
] , dist
[ N
] , st
[ N
] , n
, m
;
int Dijkstra ( int s
)
{ memset ( st
, 0 , sizeof st
) ; memset ( dist
, 0x3f , sizeof dist
) ; memset ( w
, 0x3f3f3f3f , sizeof w
) ; for ( int i
= 1 ; i
<= n
; i
++ ) for ( int j
= 1 ; j
<= n
; j
++ ) if ( g
[ i
] [ j
] == s
) w
[ i
] [ j
] = 1 ; dist
[ 1 ] = 0 ; for ( int i
= 0 ; i
< n
; i
++ ) { int t
= - 1 ; for ( int j
= 1 ; j
<= n
; j
++ ) if ( ! st
[ j
] && ( t
== - 1 || dist
[ j
] < dist
[ t
] ) ) t
= j
; st
[ t
] = 1 ; for ( int j
= 1 ; j
<= n
; j
++ ) dist
[ j
] = min ( dist
[ j
] , dist
[ t
] + w
[ t
] [ j
] ) ; } return dist
[ n
] ;
}
int main ( void )
{ cin
>> n
>> m
; for ( int i
= 1 ; i
<= m
; i
++ ) { int a
, b
; cin
>> a
>> b
; g
[ a
] [ b
] = g
[ b
] [ a
] = 1 ; } int ans
= max ( Dijkstra ( 1 ) , Dijkstra ( 0 ) ) ; cout
<< ( ans
== 0x3f3f3f3f ? - 1 : ans
) << endl
; return 0 ;
}
4075. 染色【一般 / 并查集 贪心】
# include <bits/stdc++.h> using namespace std
;
const int N
= 1e5 * 3 + 10 ;
int a
[ N
] , p
[ N
] , n
, m
, k
, ans
;
vector
< int > ve
[ N
] ;
int find ( int x
)
{ if ( x
!= p
[ x
] ) p
[ x
] = find ( p
[ x
] ) ; return p
[ x
] ;
}
int main ( void )
{ cin
>> n
>> m
>> k
; for ( int i
= 1 ; i
<= n
; i
++ ) cin
>> a
[ i
] , p
[ i
] = i
; for ( int i
= 0 ; i
< m
; i
++ ) { int l
, r
; cin
>> l
>> r
; if ( find ( l
) != find ( r
) ) p
[ find ( r
) ] = find ( l
) ; } for ( int i
= 1 ; i
<= n
; i
++ ) ve
[ find ( i
) ] . push_back ( i
) ; for ( int i
= 1 ; i
<= n
; i
++ ) { if ( ve
[ i
] . size ( ) ) { int t
= 0 ; unordered_map
< int , int > mp
; for ( int j
= 0 ; j
< ve
[ i
] . size ( ) ; j
++ ) t
= max ( t
, ++ mp
[ a
[ ve
[ i
] [ j
] ] ] ) ; ans
+= ve
[ i
] . size ( ) - t
; } } cout
<< ans
; return 0 ;
}
总结
以上是生活随笔 为你收集整理的Acwing第 25 场周赛【完结】 的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔 网站内容还不错，欢迎将生活随笔 推荐给好友。
