腾讯2021批笔试题解

总结：一套算是正常的笔试…算是让大家有点思考了…都没那么一眼秒（除了强烈谴责某T5最短路板子。我还差点没看到这题hhh（（

（另一套题的T5）
T5

题目大意：给出n个红球，n个黑球，给出交叉排列的序列。每次操作可以交换两个相邻的球，要使得两种颜色的球都递增，问最小操作次数
$n < = 3000$

真有你的腾讯。。。ARC的C都能拉来当笔试了（不过我做过hhh

思路：考虑 $d p [i] [j]$ 为第i个黑球，第j个红球按顺序的最小操作次数，那么转移就是 $d p [i] [j] = m i n (d p [i - 1] [j] + B (i, j), d p [i] [j - 1] + W (i, j))$
$B (i, j)$ 为i号黑球前，有几个比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;
}

题目大意：给出数组A,求出一个长度为2*n的子序列B使得：前n部分递减，后n部分递增，B[n]=B[n+1]
$n<=1000,A_i<=10000$

首先预处理时，顺着对每个点求一边最长不升子序列，1到i处LDS为 $d p [i]$ 。
然后倒着处理一遍最长不降子序列，i处到结尾的LIS为 $d p 2 [i]$
由于n只有1000，直接枚举i和j，当 $a [i], a [j]$ 相等时即可统计答案。
统计答案为 $a n s = m a x (a n s, 2 * m i n (d p [i], d p 2 [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;
}

题目大意：给出一元n次方程组，求出所有根。(保留两位小数)
$n<=5,abs(A_i)<=10$

枚举每个点即可…如果 $f (x) * f (x + 0.001) < 0$ 则 $[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;
}

题目大意：给出长度为n的线段，如果当前长度>L就随机切一刀，舍弃左边，保留右边，问期望切多少刀后无法继续操作。（答案保留两位小数）
$n < = 200, L < = 200$

怎么有神仙网友随机模拟过了啊…真是太强了…学到许多Orzzz…

以及这是神仙网友的正解数学做法…太神了！学到许多Orzzz…
答案是 $l n L - l n D + 1$
（我老数学fw了…只能跪跪跪

upd:已更新随机模拟程序（自测基本能有三位小数的正确性…交上去确实应该稳过emm）

#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 main()
{srand(time(0));double x1,x2; cin>>x1>>x2;int cnt=0,T=1000000;rep(z,1,T){double n=x1,d=x2;while(n>=d){int x=rand();n=n*x; n/=32767; cnt++;}}double ans=(double)cnt/T;cout<<ans<<endl;printf("%.2lf\n",ans);return 0;
}

题目大意：给出n个集合(数字顺序无关)，每个集合有6个数(Ai)，问是否存在两个集合相等。
$n<=1e6,A_i<=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;
}

题目大意：给出一张有向图，求T次从1走到n再走回1的最短路。
$n < = 1 e 5, m < = 1 e 5$

怎么又是最短路板子题。。。

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