騰訊2021批筆試題解

總結：一套算是正常的筆試…算是讓大家有點思考了…都沒那么一眼秒（除了強烈譴責某T5最短路板子，我還差點沒看到這題hhh（（

（另一套題的T5）
T5

題目大意：給出n個紅球，n個黑球，給出交叉排列的序列，每次操作可以交換兩個相鄰的球，要使得兩種顏色的球都遞增，問最小操作次數
n<=3000

真有你的騰訊，，，ARC的C都能拉來當筆試了（不過我做過hhh

$ARC097C$ARC097C
我的提交記錄

思路：考慮$dp[i][j]$dp[i][j]為第i個黑球，第j個紅球按順序的最小操作次數，那么轉移就是$dp[i][j]=min(dp[i?1][j]+B(i,j),dp[i][j?1]+W(i,j))$dp[i][j]=min(dp[i?1][j]+B(i,j),dp[i][j?1]+W(i,j))
$B(i,j)$B(i,j)為i號黑球前，有幾個比i號黑球大，比j號紅球大的球，
$W(i,j)$W(i,j)為i號紅球前，有幾個比i號黑球大，比j號紅球大的球，
（因為考慮前i個黑，j個紅球都順序正常了，那么就只用考慮剩下的了，）

這兩個東西用樹狀陣列預處理一下就好，

C++代碼：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 4005
#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 c1[maxn],c2[maxn],B[maxn][maxn],W[maxn][maxn],n,x[maxn];
int x1[maxn],x2[maxn],cnt1,cnt2,dp[maxn][maxn];
char s[maxn],q;

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

int main()
{
	n=read(); rep(i,1,2*n) cin>>s[i],x[i]=read();
	rep(i,1,2*n)
	{
		if(s[i]=='B')
		{
			a1(x[i],1);
			rep(j,0,n) B[x[i]][j]=i-q1(x[i])-q2(j);
		}
		else
		{
			a2(x[i],1);
			rep(j,0,n) W[j][x[i]]=i-q1(j)-q2(x[i]);
		}
	}
	rep(i,0,n) rep(j,0,n) dp[i][j]=inf; dp[0][0]=0;
	rep(i,0,n) rep(j,0,n)
	{
		if(i!=0) dp[i][j]=min(dp[i][j],dp[i-1][j]+B[i][j]);
		if(j!=0) dp[i][j]=min(dp[i][j],dp[i][j-1]+W[i][j]);
	}
	cout<<dp[n][n]<<endl;
	return 0;
}

T1

題目大意：給出陣列A,求出一個長度為2*n的子序列B使得：前n部分遞減，后n部分遞增，B[n]=B[n+1]
n<=1000,Ai?<=10000

首先預處理時，順著對每個點求一邊最長不升子序列，1到i處LDS為$dp[i]$dp[i]，
然后倒著處理一遍最長不降子序列，i處到結尾的LIS為$dp2[i]$dp2[i]
由于n只有1000，直接列舉i和j，當$a[i],a[j]$a[i],a[j]相等時即可統計答案，
統計答案為$ans=max(ans,2?min(dp[i],dp2[j]))$ans=max(ans,2?min(dp[i],dp2[j]))，

C++代碼：

#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;
}

int n,dp[maxn],dp2[maxn],a[maxn];

int main()
{
	int T=read();
	while(T--)
	{
		n=read(); rep(i,1,n) a[i]=read();
		int ans=0;
		rep(i,1,n) dp[i]=1,dp2[i]=1;
		rep(i,1,n) rep(j,1,i-1) if(a[i]<a[j]) dp[i]=max(dp[i],dp[j]+1);
		per(i,n,1) per(j,n,i+1) if(a[i]<a[j]) dp2[i]=max(dp2[i],dp2[j]+1);
		rep(i,1,n) rep(j,i+1,n) if(a[i]==a[j]) ans=max(ans,2*min(dp[i],dp2[j]));
		cout<<ans<<endl;
	}
	return 0;
}

T2

題目大意：給出一元n次方程組，求出所有根，(保留兩位小數)
n<=5,abs(Ai?)<=10

列舉每個點即可…如果f(x)?f(x+0.001)<0 則$[x,x+0.001]$[x,x+0.001]間存在一個根，

C++代碼：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,ans=0;
double a[10];
double f(double x)
{
	double now=1,num=0;
	for(int j=0;j<=n;j++)
	{
		num+=now*a[j];
		now*=x;
	}
	return num;
}
int main()
{
	scanf("%d",&n);
	double x=1e12;
	for(int i=n;i>=0;i--)
	{
		scanf("%lf",&a[i]);
	}
	for(double i=-20.000;i<=20.000;i+=0.001)
	{
		if(f(i)*f(i+0.001)<0||f(i)==0){
			ans=1;
			printf("%.2lf ",i);
		}
		
	}
	if(!ans)printf("No");
	return 0;
}

T3

題目大意：給出長度為n的線段，如果當前長度>L就隨機切一刀，舍棄左邊，保留右邊，問期望切多少刀后無法繼續操作，
n<=200,L<=200

怎么有神仙網友隨機模擬過了啊…真是太強了…學到許多Orzzz…

以及這是神仙網友的正解數學做法…太神了！學到許多Orzzz…
（我老數學fw了…只能跪跪跪

T4

題目大意：給出n個集合(數字順序無關)，每個集合有6個數(Ai)，問是否存在兩個集合相等，
n<=1e6,Ai?<=1e9

每個集合內元素排序，然后hash一下集合的值，map判斷即可

C++代碼：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned 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;
}

int a[maxn];
ull h[maxn];

map <ull,int> p;

int main()
{
	int T=read();
	while(T--)
	{
		int n=read(),F=0; p.clear();
		rep(i,1,n)
		{
			rep(j,1,6) a[j]=read(); sort(a+1,a+7);
			ull tmp=0;
			rep(j,1,6) tmp=tmp*233+a[j];
			if(p[tmp]) F=1; p[tmp]++;
		}
		if(F==1) puts("YES"); else puts("NO");
	}
	return 0;
}

T5

題目大意：給出一張有向圖，求T次從1走到n再走回1的最短路，
n<=1e5,m<=1e5

怎么又是最短路板子題，，，

C++代碼：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
struct data_p{int hed,bj;ll ans;}pot[10005];
struct data_l{int nxt,to;ll v;}lin[500005];
int n,m,st,top=0,que[100005];
ll ans,T;
void add_l(int a,int b,ll c)
{lin[++top].to=b;lin[top].v=c;lin[top].nxt=pot[a].hed;pot[a].hed=top;}
void SPFA()
{
	for(int i=1;i<=n;i++){pot[i].ans=2147483647;pot[i].bj=0;}
	int l=0,r=0;
	que[r++]=st;pot[st].ans=0;
	while(l<r)
	{
		int now=que[l++];pot[now].bj=0;
		for(int i=pot[now].hed;i;i=lin[i].nxt)
		{
			if(pot[lin[i].to].ans<=pot[now].ans+lin[i].v)continue;
			pot[lin[i].to].ans=pot[now].ans+lin[i].v;
			if(pot[lin[i].to].bj)continue;
			pot[lin[i].to].bj=1;
			que[r++]=lin[i].to;
		}
	}
}
int main()
{
	while(scanf("%d%d%lld",&n,&m,&T)!=EOF)
	{
		top=0;st=1;
		for(int i=1;i<=n;i++)pot[i].hed=0;
		for(int i=1;i<=m;i++)
		{
			int x,y;ll z;
			scanf("%d%d%lld",&x,&y,&z);
			add_l(x,y,z);
		}
		SPFA();
		ans+=pot[n].ans;
		st=n;
		SPFA();
		ans+=pot[1].ans;
		printf("%lld\n",ans*T);
		ans=0;
	}
	return 0;
}

END：海星…算是從這次筆試中學到了神仙的隨機模擬做法…可太神了，震撼.jpg，以及以后要記得每題都先看看…首先切掉T5這種大板子題hhh…