Hackerrank 2020 February 2014 解题报告
比赛链接
Sherlock and Watson （20分）
题意：给定一个数组，向右平移K次，然后有Q个询问，问第x位置上是几
做法：直接模拟即可
1
#include <iostream>
2
using
namespace
std;
3
int
n,k,q;
4
int
a[
100100
],b[
100100
];
5
int
main(){
6
ios::sync_with_stdio(
0
);
7
cin>>n>>k>>
q;
8
for
(
int
i=
0
;i<n;i++
){
9
cin>>
a[i];
10
}
11
for
(
int
i=
0
;i<n;i++
){
12
b[(i+k)%n] =
a[i];
13
}
14
int
x;
15
for
(
int
i=
0
;i<q;i++
){
16
cin>>
x;
17
//
int tar = (x+k)%n;
18
cout<<b[x]<<
endl;
19
}
20
return
0
;
21
}
Make it Anagram ( 30分 )
题意：给定两个字符串，问删除多少字符后两个串所含的字符以及对应的个数相同
做法：分别统计每个字符在两个串中出现的次数，统计差值并求和就是答案
1
#include <cmath>
2
#include <cstdio>
3
#include <vector>
4
#include <iostream>
5
#include <algorithm>
6
#include <
string
>
7
using
namespace
std;
8
9
int
p[
255
],q[
255
];
10
int
main() {
11
/*
Enter your code here. Read input from STDIN. Print output to STDOUT
*/
12
string
a,b;
13
cin>>a>>
b;
14
for
(
char
x:a){
15
p[x]++
;
16
}
17
for
(
char
x:b){
18
q[x]++
;
19
}
20
int
ans =
0
;
21
for
(
int
i=
'
a
'
;i<=
'
z
'
;i++
){
22
int
tmp = p[i]-
q[i];
23
if
(tmp<
0
)tmp=-
tmp;
24
ans+=
tmp;
25
}
26
cout<<ans<<
endl;
27
return
0
;
28
}
Cutting boards ( 40分 )
题意：有一个M*N的木板，要把它分成M*N个单位块。每次可以沿横向或纵向切割，连续切割的代价为x1,x2,x..n和y1,y2...yn。求完成任务的最小代价和。
做法：既然所有的链接处都要被切开，那么就优先切代价高的，这样可以减少连续切割的次数，总之就是贪心了。
1
#include <cmath>
2
#include <cstdio>
3
#include <vector>
4
#include <iostream>
5
#include <algorithm>
6
#include <functional>
7
using
namespace
std;
8
typedef
long
long
ll;
9
const
ll mod = (ll)1e9+
7
;
10
ll m,n,x[
1000001
],y[
1000001
];
11
int
main() {
12
ios::sync_with_stdio(
0
);
13
int
t;
14
cin>>
t;
15
while
(t--
){
16
cin>>m>>
n;
17
for
(
int
i=
0
;i<m-
1
;i++
)
18
cin>>
x[i];
19
for
(
int
i=
0
;i<n-
1
;i++
)
20
cin>>
y[i];
21
sort(x,x+m-
1
,greater<ll>
());
22
sort(y,y+n-
1
,greater<ll>
());
23
ll ans =
0
,a=
0
,b=
0
;
24
while
(a<m-
1
|| b<n-
1
){
25
if
(a<m-
1
){
26
if
(b<n-
1
){
27
if
(x[a]>
y[b]){
28
ans = (ans+x[a]*(b+
1
))%
mod;
29
a++
;
30
}
else
{
31
ans = (ans+y[b]*(a+
1
))%
mod;
32
b++
;
33
}
34
}
else
{
35
ans = (ans+x[a]*(b+
1
))%
mod;
36
a++
;
37
}
38
}
else
{
39
ans = (ans+y[b]*(a+
1
))%
mod;
40
b++
;
41
}
42
}
43
cout<<ans<<
endl;
44
}
45
return
0
;
46
}
Bike Racers (60分)
题意：城市里有N个自行车手和M个自行车，现在要组织K个人比赛，需要他们都找到一辆车，车手的运动速度为1。求最少能在多少时间使得所有车手都到达所选的车？
做法：随着时间限制的增加，能够到达的车手一定是不减小的，因此我们可以二分时间t，转化为判定问题。显然车和人构成一个二分图，对于能够在时限内走到的，我们建一条边。然后对这个二分图做最大匹配，看是否有k个匹配。总复杂度O（N^3lg(N）)。
1
#include <cmath>
2
#include <cstdio>
3
#include <vector>
4
#include <iostream>
5
#include <algorithm>
6
#include <cstring>
7
using
namespace
std;
8
typedef
long
long
ll;
9
const
ll MAXN =
510
;
10
ll n,m,k;
11
ll a[MAXN][
2
],b[MAXN][
2
];
12
struct
node{
13
ll u,v;
14
ll dis;
15
bool
operator
<(
const
node& r)
const
{
16
return
dis<
r.dis;
17
}
18
}data[MAXN*
MAXN];
19
ll uN,vN;
20
ll g[MAXN][MAXN];
21
ll linker[MAXN];
22
bool
used[MAXN];
23
bool
dfs(ll u)
24
{
25
ll v;
26
for
(v=
0
;v<vN;v++
)
27
if
(g[u][v]&&!
used[v])
28
{
29
used[v]=
true
;
30
if
(linker[v]==-
1
||
dfs(linker[v]))
31
{
32
linker[v]=
u;
33
return
true
;
34
}
35
}
36
return
false
;
37
}
38
ll hungary()
39
{
40
ll res=
0
;
41
ll u;
42
memset(linker,-
1
,
sizeof
(linker));
43
for
(u=
0
;u<uN;u++
)
44
{
45
memset(used,
0
,
sizeof
(used));
46
if
(dfs(u)) res++
;
47
}
48
return
res;
49
}
50
ll calc(ll x){
51
memset(g,
0
,
sizeof
(g));
52
for
(ll i=
0
;i<=x;i++
){
53
ll x =
data[i].u;
54
ll y =
data[i].v;
55
g[x][y] =
1
;
56
}
57
return
hungary();
58
}
59
ll solve(){
60
ll cnt =
0
;
61
uN =
n;
62
vN =
m;
63
for
(ll i=
0
;i<n;i++
){
64
for
(ll j=
0
;j<m;j++
){
65
data[cnt].u=
i;
66
data[cnt].v=
j;
67
data[cnt].dis = (a[i][
0
]-b[j][
0
])*(a[i][
0
]-b[j][
0
])+(a[i][
1
]-b[j][
1
])*(a[i][
1
]-b[j][
1
]);
68
cnt++
;
69
}
70
71
}
72
//
cout<<"cnt="<<cnt<<endl;
73
sort(data,data+
cnt);
74
///
/ for(ll i=0;i
<cnt;i++)
75
// cout
<<i<<":"<<data[i].dis<<endl;
76
ll lb=-1,ub=cnt;
77
while
(ub-lb>
1
){
78
ll mid = (ub+lb)/
2
;
79
//
cout<<mid<<" "<<calc(mid)<<endl;
80
if
(calc(mid)>=
k){
81
ub =
mid;
82
}
else
{
83
lb =
mid;
84
}
85
}
86
return
data[ub].dis;
87
}
88
int
main() {
89
ios::sync_with_stdio(
0
);
90
cin>>n>>m>>
k;
91
for
(ll i=
0
;i<n;i++)cin>>a[i][
0
]>>a[i][
1
];
92
for
(ll i=
0
;i<m;i++)cin>>b[i][
0
]>>b[i][
1
];
93
ll ans =
solve();
94
cout<<ans<<
endl;
95
return
0
;
96
}
Library Query(80分)
题意：带单点修改的区间第k大
做法：因为数据很小(1 <= N <= 10 4 ,1 <= Q <= 10 4 )，直接分块就行。修改的时候暴力对相应的块进行排序，复杂度O（sqrt(n)*lg(n))。查询的时候通过二分转化为判断一个数是第几大的问题，由于中间部分每个块内都是排好序的，二分就可以了，对于边界上的两块或者一块直接暴力统计。复杂度O(sqrt(n)*lg(n)*lg(n))。
1
#include <iostream>
2
#include <cstdio>
3
#include <algorithm>
4
#include <vector>
5
#include <
set
>
6
#include <queue>
7
#include <
set
>
8
#include <map>
9
#include <cstring>
10
#include <functional>
11
#include <cmath>
12
typedef
long
long
ll;
13
using
namespace
std;
14
int
n,q,cmd,x,y,k;
15
int
a[
10100
];
16
int
lsize =
128
;
17
vector<
int
> v[
2000
];
18
int
maxid;
19
int
solve(
int
x,
int
y,
int
target){
20
int
idx = x/lsize,idy=y/
lsize;
21
//
cerr<<"idx="<<idx<<" idy="<<idy<<endl;
22
int
ans =
0
;
23
for
(
int
i=x;i<lsize*(idx+
1
);i++
){
24
if
(a[i]<=
target)
25
ans++
;
26
}
27
for
(
int
i=idy*lsize;i<=y;i++
){
28
if
(a[i]<=
target)
29
ans++
;
30
}
31
for
(
int
i=idx+
1
;i<=idy-
1
;i++
){
32
if
(target < v[i][
0
])
33
continue
;
34
else
if
(target >=
v[i].back())
35
ans+=
v[i].size();
36
else
37
{
38
int
tmp = upper_bound(v[i].begin(),v[i].end(),target)-
v[i].begin();
39
ans+=
tmp;
40
}
41
42
}
43
return
ans;
44
}
45
int
main(){
46
//
freopen("int.txt","r",stdin);
47
//
freopen("out1.txt","w",stdout);
48
ios::sync_with_stdio(
0
);
49
int
cs;
50
cin>>
cs;
51
while
(cs--
){
52
cin>>
n;
53
//
lsize = (int)sqrt(n);
54
for
(
int
i=
0
;i<=n/lsize;i++
)
55
v[i].clear();
56
for
(
int
i=
0
;i<n;i++
)
57
cin>>
a[i];
58
maxid =
0
;
59
for
(
int
i=
0
;i<n;i++
){
60
int
id = i/
lsize;
61
maxid = id+
1
;
62
v[id].push_back(a[i]);
63
}
64
for
(
int
i=
0
;i<maxid;i++
){
65
sort(v[i].begin(),v[i].end());
66
}
67
cin>>
q;
68
//
cout<<"q="<<q<<endl;
69
while
(q--
){
70
cin>>
cmd;
71
if
(cmd ==
1
){
72
cin>>x>>
k;
73
x--
;
74
a[x] =
k;
75
int
id = x/
lsize;
76
v[id].clear();
77
for
(
int
i=id*lsize;i<n&&i<(id+
1
)*lsize;i++
){
78
v[id].push_back(a[i]);
79
}
80
sort(v[id].begin(),v[id].end());
81
}
else
{
82
cin>>x>>y>>
k;
83
x--
;
84
y--
;
85
int
idx = x/lsize,idy = y/
lsize;
86
if
(idx ==
idy){
87
vector<
int
> tmp(a+x,a+y+
1
);
88
sort(tmp.begin(),tmp.end());
89
cout<<tmp[k-
1
]<<
endl;
90
}
else
{
91
int
lb = -
1
,ub=
1001
;
92
while
(ub-lb>
1
){
93
int
mid = (ub+lb)/
2
;
94
int
rank =
solve(x,y,mid);
95
//
cerr<<"mid="<<mid<<" rank="<<rank<<endl;
96
if
(rank >=
k){
97
ub =
mid;
98
}
else
{
99
lb =
mid;
100
}
101
}
102
cout<<ub<<
endl;
103
}
104
}
105
}
106
}
107
return
0
;
108
}
