阿里研发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了很多发。。）

显然，对于每个点而言以该点为顶角的等腰三角形数量是相同的，其数量为 。原因是，除了该点以外的 个点可以两两配对。

在形成的这 个三角形中，钝角三角形的数量一定是 个。首先需要把这个减去。之后可以算出所有的直角和锐减等腰三角形。

然后就需要处理两种特殊情况：

1. 是4的倍数时，每个顶点可以形成一个等腰直角三角形，需要减去。

2. 是3的倍数时。每三个顶点形成的等边三角形是同一个，这部分重复计算的需要减去。

#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