2020华东师范大学可信人工智能优秀大学生夏令营(机试+面试)
首先,吹一波ECNU的软工,真的挺强的。由于疫情,夏令营改为线上举行。据老师说,因为线上,还扩大了人数,也许因此本双非才有资格入营,所以也算自己有运气吧。最终参加的有59个人,24个优营。
一、具体安排
(另外,15号的讲座换了zoom这个非常“上流”的平台,懂的都懂。)
对于优营,比较重要的就是机试和面试,我就说一下我的经历吧,有些记不清了,大体说一下。(另外有一个小建议,就是前两天的讲座一定要检查自己是否闭麦,不然会有很尴尬的场面出现。)
一、机试
时间2个小时(有点少。。。),不计罚时。总共6道题,每道题满分100。按过得样例点给分,据说交的太多且一分不得的话会有负分。另外今年不像往年,是看不到自己的排名的,所以心里挺没谱的。
A.
题意:n个操作,p个人。才开始时,p个人按1~p顺序等待接受服务。有3种操作。操作1,队首接受服务,之后,把他放在队尾。操作2,排在x放在队首。操作3,输出当前队首。(1 <= n,p <= 1e6)
思路:既然是队列,而普通队列又不能实现,那就优先队列。每个人有一个被服务的等级,等级小的更优先,并且用一个数组nowlevel记录每个人当前等级。对于操作1,给队首的人赋一个新的等级,该等级是当前最大等级+1,并放入队列,修改nowlevel的值。对于操作1,给输入的x赋一个新的等级,该等级是当前最小等级-1,并放入队列,修改nowlevel的值。对于3,直接输出。对于操作1和3,首先要判断当前队首元素的等级是不是nowlevel记录的值,不是则需要pop到是为止。复杂度应该是2nlog(2n)。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+10;
struct node{
ll id,level;
friend bool operator<(node a,node b){
return a.level>b.level;
}
}now;
ll nowle[N];
ll male,mile;
int n,p,op,x;
int main(){
scanf("%d%d",&n,&p);
male=p;
mile=0;
priority_queue<node> q;
for(int i=1;i<=p;i++){
q.push(node{i,i});
nowle[i]=i;
}
while(n--){
scanf("%d",&op);
if(op==1){
while(!q.empty()){
now=q.top();
if(now.level!=nowle[now.id])
q.pop();
else break;
}
now=q.top();
q.pop();
nowle[now.id]=++male;
q.push(node{now.id,nowle[now.id]});
}else if(op==2){
scanf("%d",&x);
nowle[x]=--mile;
q.push(node{x,nowle[x]});
}else{
while(!q.empty()){
now=q.top();
if(now.level!=nowle[now.id])
q.pop();
else break;
}
printf("%lld\n",q.top().id);
}
}
return 0;
}
B.
题意:给出一个n*m矩阵。才开始时,矩阵的值自上往下,自左往右依次为,1,2,3,4,...,m,m+1,....,n*m。有k个操作,操作有2类。第一类,给某一行的值都乘上一个数;第二类,给某一列的值都乘上一个数。最后,求整个矩阵值得和。(对1e9+7取余)(1 <= n,m <= 1e18)(数据范围不太记得了,反正很大,不能遍历矩阵,应该是推公式吧,我不太会,暴力的,得了50分)(PS:有大佬得100分,tql。)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+10;
const ll mod = 1e9+7;
ll n,m,k;
ll x,y,r[N],c[N],ans;
char op[10];
int main(){
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=n;i++)
r[i]=1;
for(int i=1;i<=m;i++)
c[i]=1;
while(k--){
scanf("%s%lld%lld",op+1,&x,&y);
if(op[1]=='R')
r[x]=r[x]*y%mod;
else
c[x]=c[x]*y%mod;
}
ans=0;
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++)
ans=(ans+(1LL*(i-1)*m%mod+j)%mod*r[i]%mod*c[j]%mod)%mod;
printf("%lld\n",ans);
return 0;
}
C.
题意:原先有n杯水,问变成k杯水的最小花费。同时给出一个n*n的矩阵,c[i][j]代表把第i个杯子里的水倒进第j个杯子的花费。(1 <= n,k <= 100)
思路:由于时间太短,直接暴力贪心的,每次都找最小的花费,并且被倒空的杯子里有水。(时间太紧张了,现在想想应该保证两个杯子都有水。)贪的不太对,只得了40分。贴的是保证两个杯子都有水的代码。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 110;
int c[N][N];
bool book[N];
int n,k,ans;
int main(){
ans=0;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&c[i][j]);
int temp=n;
while(temp>k){
int minc=1e6,r,cc;
for(int i=1;i<=n;i++){
if(book[i]) continue;
for(int j=1;j<=n;j++){
if(book[j]) continue;
if(minc>c[i][j]){
minc=c[i][j];
r=i;
cc=j;
}
}
}
book[r]=1;
ans+=minc;
temp--;
}
printf("%d\n",ans);
return 0;
}
D.
没做。。(PS:有大佬得100分,tql,tql。orzorzorzorz。)
E.
题意:忘记了,反正就是能推出一个公式,然后让你输出公式的第n项,由于答案是浮点数,误差不大于1e-4就行。(1 <= n <= 1e18)
思路:打表推公式,最后推出的公式是1+1/2+1/3+1/4+1/5+...+1/n。眼熟吧,自行参考百度。https://zhidao.baidu.com/question/1887618574455104268.html
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int N = 1e6+10;
ll n;
long double ans;
int main(){
scanf("%lld",&n);
ans=1;
for(ld i=2;i<=n;i++){
ans=ans+(ld)1.0/i;
}
printf("%.11Lf",ans);
return 0;
}
F.
题意:给出一个树的前序、中序,输出后序。
思路:通过中序来确定左右子树的范围,递归处理就好。(感谢PAT。)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100;
char pre[N],in[N],ans[N];
int n,cnt=0;
void dfs(int prel,int prer,int inl,int inr){
if(inl>inr) return;
if(inl==inr){
ans[++cnt]=in[inl];
return;
}
int pos=inl;
while(pos<=inr&&in[pos]!=pre[prel])
pos++;
if(inl<=pos-1)
dfs(prel+1,prel+pos-inl-1,inl,pos-1);
if(pos+1<=inr)
dfs(prel+pos-inl+1,prer,pos+1,inr);
ans[++cnt]=pre[prel];
}
int main(){
scanf("%s%s",pre+1,in+1);
n=strlen(pre+1);
dfs(1,n,1,n);
ans[cnt+1]='\0';
printf("%s",ans+1);
return 0;
}
二、面试
每个人20分钟,问了挺多问题的。捡记得的说一下吧。
1、用英文介绍一下自己以及自己的家乡(济宁),3分钟。
事前准备过,背的滚瓜烂熟,一顿暴背。然后说家乡说太多了,超时间了,被打断了。
2、介绍一个自己认为做过的最好的项目。
我没做过什么拿的出手的项目,回答的是写过论文,老师让说了一下。由于是学科交叉,老师只问了几个人做的,然后就没多问。
3、网络原理方面
(1)说一下NAT?
真忘了,让老师重复了几遍,没想起来。主要是自己没有复习完,这个不该不知道的。
NAT(Network Address Translation,网络地址转换)是1994年提出的。当在专用网内部的一些主机本来已经分配到了本地IP地址(即仅在本专用网内使用的专用地址),但现在又想和因特网上的主机通信(并不需要加密)时,可使用NAT方法。这种方法需要在专用网连接到因特网的路由器上安装NAT软件。装有NAT软件的路由器叫做NAT路由器,它至少有一个有效的外部全球IP地址。这样,所有使用本地地址的主机在和外界通信时,都要在NAT路由器上将其本地地址转换成全球IP地址,才能和因特网连接。另外,这种通过使用少量的公有IP 地址代表较多的私有IP 地址的方式,将有助于减缓可用的IP地址空间的枯竭。
(2)说一下ARP?
这个我会,ARP是地址解析协议,实现物理(MAC)地址到IP地址的映射。
(3)ARP使用广播还是多播?
当寻找目的主机的MAC地址时使用广播,返回目的MAC地址时使用单播。
4、数据结构方面
(1)使用最多的排序?为什么?
快排。最稳定,效率高。
(2)B树、B+树?
我请求说的红黑树,说了红黑树的5个性质。又问了红黑树的应用。我说的,“应用于关联数组,就是一个key值,一个value值,比如C++的STL的map就是用红黑树实现的。”
(3)介绍一下DFS、BFS。
DFS就是“不撞南墙不回头”,一直搜到不能再搜为止。BFS就是一层层的搜。(有点简短,其实很多问题我都答得比较简短,但是我认为还是能多说就多说一点。)
5、计组方面
(1)cache 的应用
解决CPU和主存之间速度不匹配的问题。类似的应用我不会。
6、时政方面
(1)华为遭到美英的制裁,对中国的启示?
(2)有没有关注最近的两会?
7、主观题目
(1)对于一个数,怎么判断他能被30整除?
没get到老师的点,就说“看看取余后是不是等于0”。
(2)为什么选择读研而不是就业?
三、总结
我觉得老师们都很nice,即使你答不上来也会说“没事,没事”,自我感觉挺好的,没有紧张。由于机试不知道排名,另外感觉面试的问题有的能答得更好,所以我失眠了。一直到公布优营名单都是很紧张的,幸运的是自己侥幸拿到了优营,很开心。最后希望这篇博客能给需要的人一些帮助。祝好。
上一篇: 《java基础》7-事务的可见性
下一篇: AQS 简单介绍