阿里研发0304笔试情况和题解
时长:90分钟
笔试题目：6道单选+6道多选+3道编程
这次的编程题比前几天字节的简单一些，不过最后一题也挺难的，选择题只能听天由命了。。更一下编程三道题题解吧。
第一题：晶体
题目内容如下：
可以通过找规律发现，若边长是 ，那么每过1秒，单位晶体的增量会增加
。或者说，增量为一个等差数列。
可以直接模拟等差数列求和，或套用求和公式均可。代码如下:
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,i;
long long res=0;
cin>>n;
for(i=0;i<n;i++){
long long a,b;
cin>>a>>b;
int d=a-2;
res+=(1+1+b*d)*(b+1)/2;
}
cout<<res;
}
这题py写起来更短：
n=int(input())
res=0
for _ in range(n):
a,b=[int(i) for i in input().split()]
res+=((b+1)+(a-2)*(1+b)*b/2)
print(int(res))
这种找规律的题，校招不多，但是竞赛里面可能签到题经常遇见，只要多练就很容易掌握技巧。
这里有一道类似的：https://www.nowcoder.com/practice/609bd97833c4441eaaabf86ddf92f9b1?tpId=196&tqId=40407&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Ftab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
第二题：等腰三角形
题目是：
牛牛在纸上画了一个正n边形，他想知道多边形中等腰锐角三角形的数量。（三角形的顶点要在多边形的顶点上）
不同的三角形的定义：两个三角形，只要有一个点不在同一个位置上就算做不同的三角形。
等腰锐角三角形的定义：顶角是锐角的等腰三角形被成为等腰锐角三角形。
题解：
（这道题的特判卡了我挺久了，wa了很多发。。）
显然，对于每个点而言以该点为顶角的等腰三角形数量是相同的，其数量为 。原因是，除了该点以外的
个点可以两两配对。
在形成的这 个三角形中，钝角三角形的数量一定是
个。首先需要把这个减去。之后可以算出所有的直角和锐减等腰三角形。
然后就需要处理两种特殊情况：
是4的倍数时，每个顶点可以形成一个等腰直角三角形，需要减去。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
long long p=(n-1)/2;
p=(p+1)/2;
long long sum=n*p;
if(n%4==0)sum-=n;
if(n%3==0)sum-=n/3*2;
cout<<sum;
}
第三题：扫雷游戏
这道题数据范围是 4*4 的棋盘，所以 状压枚举就可以了。大家一定要学会看数据范围知解法的窍门（滑稽←_←）
我之前刷牛客dp专题的时候，练状压dp写二进制枚举对这个题帮助挺大的，熟练了之后十几分钟就能写完，就是判断雷的细节有点多，容易写错。具体的细节看代码吧，状压的精髓就是:
for(i=0;i<1<<n;i++) ……
利用 的二进制情况进行枚举。
#include<bits/stdc++.h>
using namespace std;
string s[5];
int main(){
int n,i,j,k,x,y;
for(i=0;i<4;i++)cin>>s[i];
int cnt=0;
int tong[4][4]={};
for(i=0;i<1<<16;i++){
int mp[4][4]={};
for(j=0;j<16;j++){
if(i&(1<<j)){
mp[j/4][j%4]=-1;
if(s[j/4][j%4]!='.')break;
}
}
if(j<16)continue;
for(j=0;j<4;j++){
for(k=0;k<4;k++){
if(mp[j][k]==-1){
for(x=-1;x<=1;x++){
for(y=-1;y<=1;y++){
if(j+x>=0&&j+x<4&&k+y>=0&&k+y<4&&mp[j+x][k+y]!=-1){
mp[j+x][k+y]++;
}
}
}
}
}
}
int jud=0;
for(j=0;j<4;j++){
for(k=0;k<4;k++){
if(s[j][k]!='.'&&s[j][k]-'0'!=mp[j][k])jud=1;
}
}
if(!jud){
cnt++;
for(j=0;j<4;j++){
for(k=0;k<4;k++){
tong[j][k]+=mp[j][k]==-1;
}
}
}
}
if(cnt==0){
cout<<-1;
}
else{
for(i=0;i<4;i++){
for(j=0;j<4;j++){
if(s[i][j]=='.'){
if(tong[i][j]==cnt)cout<<"X";
else if(tong[i][j]==0)cout<<"O";
else cout<<".";
}
else cout<<s[i][j];
}
cout<<endl;
}
}
}
之前打了一些竞赛区的算法比赛，刷了挺多算法题，然后面试也突击完牛客的剑指offer和算法首页的那个题单，感觉效果还行，手速和思维提升都挺大的。不过目前感觉自己的图论还是弱了一些，希望牛客能更新图论方面的题单
最后推荐一下我觉得对我帮助挺大的dp题单，刷过一遍之后，基本现在不是特别难的dp都能找到递推的思路：https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=230
#阿里巴巴##笔经##实习##笔试时间##笔试题目#
