Hackerrank 2020 February 2014 解题报告
比赛链接
Sherlock and Watson （20分）
题意：给定一个数组，向右平移K次，然后有Q个询问，问第x位置上是几
做法：直接模拟即可
#include <iostream>
using namespace std;
int n,k,q;
int a[],b[];
int main(){
ios::sync_with_stdio();
cin>>n>>k>>q;
for(int i=;i<n;i++){
cin>>a[i];
}
for(int i=;i<n;i++){
b[(i+k)%n] = a[i];
}
int x;
for(int i=;i<q;i++){
cin>>x;
// int tar = (x+k)%n;
cout<<b[x]<<endl;
}
return ;
}
Make it Anagram ( 30分 )
题意：给定两个字符串，问删除多少字符后两个串所含的字符以及对应的个数相同
做法：分别统计每个字符在两个串中出现的次数，统计差值并求和就是答案
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std; int p[],q[];
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
string a,b;
cin>>a>>b;
for(char x:a){
p[x]++;
}
for(char x:b){
q[x]++;
}
int ans = ;
for(int i='a';i<='z';i++){
int tmp = p[i]-q[i];
if(tmp<)tmp=-tmp;
ans+=tmp;
}
cout<<ans<<endl;
return ;
}
Cutting boards ( 40分 )
题意：有一个M*N的木板，要把它分成M*N个单位块。每次可以沿横向或纵向切割，连续切割的代价为x1,x2,x..n和y1,y2...yn。求完成任务的最小代价和。
做法：既然所有的链接处都要被切开，那么就优先切代价高的，这样可以减少连续切割的次数，总之就是贪心了。
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const ll mod = (ll)1e9+;
ll m,n,x[],y[];
int main() {
ios::sync_with_stdio();
int t;
cin>>t;
while(t--){
cin>>m>>n;
for(int i=;i<m-;i++)
cin>>x[i];
for(int i=;i<n-;i++)
cin>>y[i];
sort(x,x+m-,greater<ll>());
sort(y,y+n-,greater<ll>());
ll ans = ,a=,b=;
while(a<m- || b<n-){
if(a<m-){
if(b<n-){
if(x[a]>y[b]){
ans = (ans+x[a]*(b+))%mod;
a++;
}else{
ans = (ans+y[b]*(a+))%mod;
b++;
}
}else{
ans = (ans+x[a]*(b+))%mod;
a++;
}
}else{
ans = (ans+y[b]*(a+))%mod;
b++;
}
}
cout<<ans<<endl;
}
return ;
}
Bike Racers (60分)
题意：城市里有N个自行车手和M个自行车，现在要组织K个人比赛，需要他们都找到一辆车，车手的运动速度为1。求最少能在多少时间使得所有车手都到达所选的车？
做法：随着时间限制的增加，能够到达的车手一定是不减小的，因此我们可以二分时间t，转化为判定问题。显然车和人构成一个二分图，对于能够在时限内走到的，我们建一条边。然后对这个二分图做最大匹配，看是否有k个匹配。总复杂度O（N^3lg(N）)。
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll MAXN = ;
ll n,m,k;
ll a[MAXN][],b[MAXN][];
struct node{
ll u,v;
ll dis;
bool operator<(const node& r)const{
return dis<r.dis;
}
}data[MAXN*MAXN];
ll uN,vN;
ll g[MAXN][MAXN];
ll linker[MAXN];
bool used[MAXN];
bool dfs(ll u)
{
ll v;
for(v=;v<vN;v++)
if(g[u][v]&&!used[v])
{
used[v]=true;
if(linker[v]==-||dfs(linker[v]))
{
linker[v]=u;
return true;
}
}
return false;
}
ll hungary()
{
ll res=;
ll u;
memset(linker,-,sizeof(linker));
for(u=;u<uN;u++)
{
memset(used,,sizeof(used));
if(dfs(u)) res++;
}
return res;
}
ll calc(ll x){
memset(g,,sizeof(g));
for(ll i=;i<=x;i++){
ll x = data[i].u;
ll y = data[i].v;
g[x][y] = ;
}
return hungary();
}
ll solve(){
ll cnt = ;
uN = n;
vN = m;
for(ll i=;i<n;i++){
for(ll j=;j<m;j++){
data[cnt].u=i;
data[cnt].v=j;
data[cnt].dis = (a[i][]-b[j][])*(a[i][]-b[j][])+(a[i][]-b[j][])*(a[i][]-b[j][]);
cnt++;
} }
//cout<<"cnt="<<cnt<<endl;
sort(data,data+cnt);
//// for(ll i=0;i<cnt;i++)
// cout<<i<<":"<<data[i].dis<<endl;
ll lb=-1,ub=cnt;
while(ub-lb>){
ll mid = (ub+lb)/;
//cout<<mid<<" "<<calc(mid)<<endl;
if(calc(mid)>=k){
ub = mid;
}else{
lb = mid;
}
}
return data[ub].dis;
}
int main() {
ios::sync_with_stdio();
cin>>n>>m>>k;
for(ll i=;i<n;i++)cin>>a[i][]>>a[i][];
for(ll i=;i<m;i++)cin>>b[i][]>>b[i][];
ll ans = solve();
cout<<ans<<endl;
return ;
}
Library Query(80分)
题意：带单点修改的区间第k大
做法：因为数据很小(1 <= N <= 104 ,1 <= Q <= 104 )，直接分块就行。修改的时候暴力对相应的块进行排序，复杂度O（sqrt(n)*lg(n))。查询的时候通过二分转化为判断一个数是第几大的问题，由于中间部分每个块内都是排好序的，二分就可以了，对于边界上的两块或者一块直接暴力统计。复杂度O(sqrt(n)*lg(n)*lg(n))。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <functional>
#include <cmath>
typedef long long ll;
using namespace std;
int n,q,cmd,x,y,k;
int a[];
int lsize = ;
vector<int> v[];
int maxid;
int solve(int x,int y,int target){
int idx = x/lsize,idy=y/lsize;
//cerr<<"idx="<<idx<<" idy="<<idy<<endl;
int ans = ;
for(int i=x;i<lsize*(idx+);i++){
if(a[i]<=target)
ans++;
}
for(int i=idy*lsize;i<=y;i++){
if(a[i]<=target)
ans++;
}
for(int i=idx+;i<=idy-;i++){
if(target < v[i][])
continue;
else if(target >= v[i].back())
ans+=v[i].size();
else
{
int tmp = upper_bound(v[i].begin(),v[i].end(),target)-v[i].begin();
ans+=tmp;
} }
return ans;
}
int main(){
//freopen("int.txt","r",stdin);
//freopen("out1.txt","w",stdout);
ios::sync_with_stdio();
int cs;
cin>>cs;
while(cs--){
cin>>n;
//lsize = (int)sqrt(n);
for(int i=;i<=n/lsize;i++)
v[i].clear();
for(int i=;i<n;i++)
cin>>a[i];
maxid = ;
for(int i=;i<n;i++){
int id = i/lsize;
maxid = id+;
v[id].push_back(a[i]);
}
for(int i=;i<maxid;i++){
sort(v[i].begin(),v[i].end());
}
cin>>q;
//cout<<"q="<<q<<endl;
while(q--){
cin>>cmd;
if(cmd == ){
cin>>x>>k;
x--;
a[x] = k;
int id = x/lsize;
v[id].clear();
for(int i=id*lsize;i<n&&i<(id+)*lsize;i++){
v[id].push_back(a[i]);
}
sort(v[id].begin(),v[id].end());
}else{
cin>>x>>y>>k;
x--;
y--;
int idx = x/lsize,idy = y/lsize;
if(idx == idy){
vector<int> tmp(a+x,a+y+);
sort(tmp.begin(),tmp.end());
cout<<tmp[k-]<<endl;
}else{
int lb = -,ub=;
while(ub-lb>){
int mid = (ub+lb)/;
int rank = solve(x,y,mid);
//cerr<<"mid="<<mid<<" rank="<<rank<<endl;
if(rank >= k){
ub = mid;
}else{
lb = mid;
}
}
cout<<ub<<endl;
}
}
}
}
return ;
}