技術文章 » 位元組跳動2021批筆試題解

位元組跳動2021批筆試題解

2020-09-21 12:00:42

總結：…這場打的心累…

（具體題解馬上更新）

T3

題目大意：給出平面上n個點 ( x , y ) (x,y) (x,y)，求在給定的m個點中，到n個點的曼哈頓距離和最小的一個點；
( a , b ) (a,b) (a,b)到 ( c , d ) (c,d) (c,d)曼哈頓距離為: ∣ a − c ∣ + ∣ b − d ∣ |a-c|+|b-d| ∣a−c∣+∣b−d∣

顯然x和y可以分開處理…只看一維的話,就可離散化+開兩個bit處理解決了；將次操作也對y進行即可。

程式碼超長如下：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e18
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

ll c1[maxn],c2[maxn],n,m,a[maxn],b[maxn],X[maxn],y[maxn];
ll cnt,p[maxn],ans[maxn],ax,ay;

inline void a1(int x,int val){for(int i=x;i<=cnt;i+=i&-i) c1[i]+=val;}
inline void a2(int x,int val){for(int i=x;i<=cnt;i+=i&-i) c2[i]+=val;}
inline ll q1(int x){ll res=0; for(int i=x;i;i-=i&-i) res+=c1[i]; return res;}
inline ll q2(int x){ll res=0; for(int i=x;i;i-=i&-i) res+=c2[i]; return res;}

int main()
{
	freopen("t1.in","r",stdin);
	n=read(); m=read();
	rep(i,1,n) a[i]=read(),b[i]=read();
	rep(i,1,m) X[i]=read(),y[i]=read();
	
	rep(i,1,n) p[++cnt]=a[i];
	rep(i,1,m) p[++cnt]=X[i];
	sort(p+1,p+cnt+1); cnt=unique(p+1,p+cnt+1)-p-1;
	
	rep(i,1,n)
	{
		int x=lower_bound(p+1,p+cnt+1,a[i])-p;
		a1(x,1); a2(x,a[i]);
	}
	rep(i,1,m)
	{
		int x=lower_bound(p+1,p+cnt+1,X[i])-p;
		ll tmp=q1(x-1)*X[i]-q2(x-1);
		tmp+=(q2(n)-q2(x))-(n-q1(x))*X[i];
		ans[i]+=tmp;
	}
	
	cnt=0;
	
	rep(i,1,n+m) c1[i]=0,c2[i]=0;
	
	rep(i,1,n) p[++cnt]=b[i];
	rep(i,1,m) p[++cnt]=y[i];
	sort(p+1,p+cnt+1); cnt=unique(p+1,p+cnt+1)-p-1;
	rep(i,1,n)
	{
		int x=lower_bound(p+1,p+cnt+1,b[i])-p;
		a1(x,1); a2(x,b[i]);
	}
	rep(i,1,m)
	{
		int x=lower_bound(p+1,p+cnt+1,y[i])-p;
		ll tmp=q1(x-1)*y[i]-q2(x-1);
		tmp+=(q2(n)-q2(x))-(n-q1(x))*y[i];
		ans[i]+=tmp;
	}
	
	ll nw=inf;
	rep(i,1,m)
	{
		if(ans[i]<nw) ax=X[i],ay=y[i],nw=ans[i];
	}
	cout<<ax<<" "<<ay<<endl;
	return 0;
}

Java版：

import java.io.*;
import java.util.*;

public class zbr01
{
	public static int n,m;
	public static long c1[]=new long [200005];
	public static long c2[]=new long [200005];
	public static int X[]=new int [200005];
	public static int y[]=new int [200005];
	public static int a[]=new int [200005];
	public static int b[]=new int [200005];
	public static int p[]=new int [200005];
	public static long ans[]=new long[100005];
	public static int ax,ay;
	
	public static void a1(int x,int val)
	{
		for(int i=x;i<=n+m;i+=i&-i) c1[i]+=val;
	}
	
	public static void a2(int x,int val)
	{
		for(int i=x;i<=n+m;i+=i&-i) c2[i]+=val;
	}
	
	public static long q1(int x)
	{
		long res=0;
		for(int i=x;i!=0;i-=i&-i) res+=c1[i];
		return res;
	}
	
	public static long q2(int x)
	{
		long res=0;
		for(int i=x;i!=0;i-=i&-i) res+=c2[i];
		return res;
	}
	
	public static void main(String args[])
	{
		Scanner S=new Scanner(System.in);
		n=S.nextInt(); m=S.nextInt(); p[0]=10000000;
		for(int i=1;i<=n;i++) {a[i]=S.nextInt(); b[i]=S.nextInt();}
		for(int i=1;i<=m;i++) {X[i]=S.nextInt(); y[i]=S.nextInt();}
		
		Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
		
		int cnt=0,c3=0;
		for(int i=1;i<=n;i++) p[++cnt]=a[i];
		for(int i=1;i<=m;i++) p[++cnt]=X[i];
		Arrays.sort(p,1,cnt+1);
		for(int i=1;i<=cnt;i++) if(p[i]!=p[i-1]) mp.put(p[i],++c3);
		
		for(int i=1;i<=n;i++)
		{
			int x=mp.get(a[i]);
			a1(x,1); a2(x,a[i]);
		}
		
		for(int i=1;i<=m;i++)
		{
			int x=mp.get(X[i]);
			long tmp=q1(x-1)*X[i]-q2(x-1);
			tmp+=(q2(n+m)-q2(x))-(n-q1(x))*X[i];
			ans[i]+=tmp;
		}
		
		cnt=0; c3=0; mp.clear();
		for(int i=1;i<=n+m;i++) {c1[i]=0; c2[i]=0;}
		
		for(int i=1;i<=n;i++) p[++cnt]=b[i];
		for(int i=1;i<=m;i++) p[++cnt]=y[i];
		Arrays.sort(p,1,cnt+1);
		for(int i=1;i<=cnt;i++) if(p[i]!=p[i-1]) mp.put(p[i],++c3);
		
		for(int i=1;i<=n;i++)
		{
			int x=mp.get(b[i]);
			a1(x,1); a2(x,b[i]);
		}
		for(int i=1;i<=m;i++)
		{
			int x=mp.get(y[i]);
			long tmp=q1(x-1)*y[i]-q2(x-1);
			tmp+=(q2(n+m)-q2(x))-(n-q1(x))*y[i];
			ans[i]+=tmp;
		}
		
		long nw=ans[1]; ax=X[1]; ay=y[1];
		for(int i=2;i<=m;i++)
		{
			if(ans[i]<nw)
			{
				ax=X[i]; ay=y[i]; nw=ans[i];
			}
		}
		System.out.println(ax+" "+ay);
	}
}

T4

題目大意：給出一顆權值為0/1的樹，單次操作可將該節點及和自己相鄰的節點進行翻轉(0變成1，1變成0)，問是否能將全部節點變成0.
n < = 5 e 5 n<=5e5 n<=5e5

由於某些奇怪的原因沒有提交這份程式碼…正確性未知…感覺很對hhh

（演演算法待更）

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
struct data_p{int hed,f[2],b;}pot[500005];
struct data_l{int to,nxt;}lin[1000005];
int t,n,top,ans;
void add_l(int a,int b){lin[++top].to=b;lin[top].nxt=pot[a].hed;pot[a].hed=top;}
void dp(int a,int fa)
{
	int b;
	pot[a].f[1]=pot[a].b^1;pot[a].f[0]=pot[a].b;
	for(int i=pot[a].hed;i;i=lin[i].nxt)
	{
		b=lin[i].to;
		if(b==fa)continue;
		dp(b,a);
		if(pot[b].f[1])pot[a].f[0]^=1;
		else pot[a].f[1]^=1;
	}
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);top=0;
		for(int i=1;i<=n;i++)
		{
			pot[i].hed=0;
			scanf("%d",&pot[i].b);
		}
		for(int i=1;i<n;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			add_l(x,y);add_l(y,x);
		}
		dp(1,1);
		if((pot[1].f[0]==1||pot[1].f[1]==1))printf("YES\n");
		else printf("NO\n");
	}
	
	
	return 0;
}

T2

題目大意：簽到的正常小模擬題…

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

const ll mod=1000000007;

inline ll pw(ll a,ll b)
{
	ll ans=1,base=a;
	while(b)
	{
		if(b&1) ans=(ans*base)%mod;
		base=(base*base)%mod; b>>=1;
	}
	return ans;
}

int main()
{
	freopen("t1.in","r",stdin);
	int T=read();
	while(T--)
	{
		ll n,m;
		cin>>n>>m; char opt; cin>>opt;
		if(opt=='+') printf("%lld\n",(n+m)%mod);
		else if(opt=='-') printf("%lld\n",n-m);
		else if(opt=='*') printf("%lld\n",(n*m)%mod);
		else printf("%lld\n",pw(n,m));
	}
	return 0;
}

T1

題目大意：求一個字串的最小回圈節
l e n < = 1 e 8 len<=1e8 len<=1e8

kmp板子題，程式碼如下：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 100000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}

int nxt[maxn];
char s[maxn];

int main()
{
	//freopen("t1.in","r",stdin);
	scanf("%s",s+1); int l=strlen(s+1);
	for(int i=2,k=0;i<=l;i++)
	{
		while(k&&s[i]!=s[k+1]) k=nxt[k];
		if(s[i]==s[k+1]) k++;
		nxt[i]=k;
	}
	int p=l-nxt[l]; if(l%p!=0) p=l;
	rep(i,1,p) printf("%c",s[i]);
	return 0;
}

（待更）