目录

个人情况预推免复试机试(2020.9.23 14:00-17:00)1.求多项式相乘系数2.最值问题3.并查集+结构体排序4.堆排序 面试（9.28-9.29） 后记

个人情况

    江浙沪地区某中流不知名211，成绩排名20%(对，没看错就是这么辣鸡的成绩)，综合排名5%(还好不只看成绩，才让我有了保研资格)，无论文科研，有一个正在进行中的数据挖掘项目，和几个没有获过奖的服务外包之类的项目，参加过很多ACM竞赛。有一些学生工作的任职，都和学术/竞赛挂钩。

    很早就有了保研的打算，也试着报名了一(hen)些(duo)夏令营。但是因为暑假还没有出综合排名，只能用成绩排名去投夏令营，导致几乎没有过初审的，甚至连本校的夏令营初审都被拒了，所以一直到九月中旬，我还是一个offer都没有，只能每天关注更新的预推免消息，不断地海投、海投……这是最焦虑的时期，一度认为自己没有学校上了。     转机出现在9.20，日常打开报名过的每个学校预推免系统，意外地发现浙大软院的初审居然通过了，我决定抓住这次机会……

预推免复试

机试(2020.9.23 14:00-17:00)

    由于没有计划上浙大，过初审也很突然，我没有考过PAT，所以尽管看着大家在20年7月那次很水的PAT中全都是满分的成绩很眼馋，也无奈只能参加机试。机试我其实不是很担心，因为自己毕竟有一些ACM的经历，也参加过浙大承办的天梯赛，所以9.23号下午的机试过程及其放松。这里复盘一下当时的题目吧：     总共有四道题，难度逐渐提升：

1.求多项式相乘系数

    对于一个多项式$(x-a_1^{})(x-a_2^{})\cdots (x-a_n^{})$，给定$a_1^{}$到$a_n^{}$的值(均为整数)，求相乘后除最高次项以外各项的系数。     这题还是比较水的，直接模拟乘的过程就好了。

#include <bits/stdc++.h> using namespace std; const int maxn = 15; int a[maxn],b[maxn],c[maxn]; int main(){ int n; scanf("%d",&n); for(int i = 1;i <= n;i++)scanf("%d",&a[i]); b[0] = 1; for(int i = 1;i <= n;i++){ memset(c,0,sizeof(c)); for(int j = 0;j < maxn;j++){ c[j] += b[j] * -a[i]; c[j+1] += b[j]; } memcpy(b,c,sizeof(c)); } bool flag = false; for(int i = maxn-1;i >= 0;i--){ if(b[i] && !flag){ flag = true; continue; } if(flag)printf("%d%c",b[i],i==0?'\n':' '); } return 0; }

2.最值问题

    给出三个集合$s_1^{},s_2^{},s_3^{}$(每个集合至多1e4个元素)，从每个集合中分别取出一个数，分别记为$a,b,c$，求$|a-b|+|b-c|+|c-a|$的最小值和此时的$a,b,c$，如果有多种$a,b,c$得到相同的最小值，输出三元组$(a,b,c)$更大的一个。     首先明确不能采用$O(n_{}^3)$的枚举，因为必然会超时。但这道题没能拿满分，因为算法fake了。我的想法是把三个集合融合成一个集合$s$，然后遍历$s$中的每一个元素$x$，找到三个集合中最小的满足$\ge x$的值作为$a,b,c$。这个思路显然可以得到$|a-b|+|b-c|+|c-a|$的最小值，但是不能满足三元组$(a,b,c)$是最大的。反例:$(1,2,5)$和$(1,4,5)$的答案相等，而后者三元组更大。     所以赛后整理了一下思路，首先，我们可以根据$a,b,c$的相互大小关系对$|a-b|+|b-c|+|c-a|$分类讨论，可以发现该式的值等于$2\ast (max-min)$。我们枚举$(a,b,c)$中的最大元素$max$，即遍历$s$中的每一个元素$x$，找到三个集合中最大的满足$\le x$的值作为$a,b,c$，验证$|a-b|+|b-c|+|c-a|$的值是否更优即可。     10.03更新，下面代码已经满分。

#include <bits/stdc++.h> using namespace std; int n[4]; set<int>s[4]; int calc(int a,int b,int c){ return abs(a-b) + abs(b-c) + abs(c-a); } int main(){ for(int i = 1;i <= 3;i++)scanf("%d",&n[i]); for(int i = 1;i <= 3;i++) for(int j = 1;j <= n[i];j++){ int x; scanf("%d",&x); s[0].insert(x); s[i].insert(x); } int ans = 0x3f3f3f3f,a,b,c; for(auto & x : s[0]){ auto it1 = s[1].upper_bound(x); auto it2 = s[2].upper_bound(x); auto it3 = s[3].upper_bound(x); if(it1 == s[1].begin() || it2 == s[2].begin() || it3 == s[3].begin())continue; it1--,it2--,it3--; if(ans >= calc(*it1,*it2,*it3))ans = calc(*it1,*it2,*it3),a = *it1,b = *it2,c = *it3; } printf("MinD(%d, %d, %d) = %d\n",a,b,c,calc(a,b,c)); return 0; }

3.并查集+结构体排序

    在一场比赛中，每个人有一个四位数的编号。给出一个人的部分队友列表(可能不完整)和这个人的分数，队友的队友也视为自己的队友，每个队的队长为该队内序号最小的一个。要求按照队伍总分为第一关键词、队伍人数为第二关键词、队长序号为第三关键词排序，输出每个队的队长序号、队伍总分、队伍人数。     并查集能很好地处理这种关系传递情况，所以用并查集合并具有队友关系的每两个人，为了保存“队长”的信息，合并时应以序号较小的节点作为较大的节点的父亲。     然后就是常规的结构体排序，直接重载小于运算符即可。

#include <bits/stdc++.h> using namespace std; const int maxn = 10010; int fa[maxn],score[maxn]; int find(int x){ return x == fa[x] ? x : (fa[x] = find(fa[x])); } int merge(int x,int y){ int fx = find(x),fy = find(y); if(fx < fy)fa[fy] = fx; else fa[fx] = fy; } struct node{ int id,score,s; }p[maxn]; bool operator < (const node& a,const node& b){ if(a.score == b.score && a.s == b.s)return a.id < b.id; if(a.score == b.score)return a.s < b.s; return a.score > b.score; } set<int>st; int main(){ int id,k,n; scanf("%d",&n); for(int i = 0;i < maxn;i++)fa[i] = i; for(int i = 1;i <= n;i++){ scanf("%d %d",&id,&k); st.insert(id); int x; while(k--){ scanf("%d",&x); st.insert(x); merge(id,x); } scanf("%d",&score[id]); } for(auto & x : st){ // printf("d ",x); int y = find(x); if(y == x)p[x].id = x; p[y].score += score[x]; p[y].s++; } // puts(""); vector<node>v; for(auto & x : st) if(p[x].s)v.push_back(p[x]); sort(v.begin(),v.end()); printf("%d\n",v.size()); for(auto & x : v) printf("d %d %d\n",x.id,x.s,x.score); return 0; }

4.堆排序

    超市搞促销，有$n$种商品和$n$种优惠，每种商品有无限个，同种商品只能用每种优惠一次。现在有$m$块钱，问最多能买多少件商品，在保证买到件数最多的情况下，最多还能剩多少钱？数据保证每种商品优惠后至少还有1块钱，不会存在白给和倒贴的现象。     理解起来可能有些抽象，来看一组样例：

三样商品价格分别为7,9,13 三种优惠分别为2,5,6 初始有12元钱 则对于第一种商品，可以通过1,2,5,7,7,7……的价格买到，对于第二种商品，可以通过3,4,7,9,9,9……的价格买到，对于第三种商品，可以通过7,8,11,13,13……的价格买到 可以买第一种商品最便宜的两件，第二种商品最便宜的两件，买到4件，余2元。

    做法：使用一个优先队列，对于每种商品放进去一个三元组(哪种商品,价格,用了第几个优惠)，每次从优先队列取出来一个当前最便宜的商品，加进去一个该类商品次贵的三元组。循环该过程即可。需要注意的是，出题人假设所有商品都要用优惠买，当没有了优惠之后不按原价购买。

#include <bits/stdc++.h> using namespace std; static const int maxn = 100010; int a[maxn],b[maxn]; struct node{ int x,y,z; }; bool operator <(const node& i,const node& j){ return i.y > j.y; } int main(){ int n,m; scanf("%d %d",&n,&m) ; for(int i = 1;i <= n;i++)scanf("%d",&a[i]); for(int i = 1;i <= n;i++)scanf("%d",&b[i]); sort(a+1,a+1+n); sort(b+1,b+1+n); reverse(b+1,b+1+n); priority_queue<node>pq; for(int i = 1;i <= n;i++)pq.push(node{i,a[i] - b[1],1}); int ans = 0; while(!pq.empty()){ node p = pq.top(); pq.pop(); if(m < p.y)break; ans++; m -= p.y; if(p.z < n)pq.push(node{p.x,a[p.x] - b[p.z+1],p.z+1}); } printf("%d %d\n",ans,m); return 0; }

面试（9.28-9.29）

    浙软的面试需要提前至少两天提交个人陈述材料，没提交的就当作弃考了，所以做ppt还是很重要的，内容要不多不少，恰好讲够八分钟，自己要多锻炼，找hxd模拟面试几次。正式面试的时候老师们围坐在一个圆桌上，对着一个大屏幕，麦克风离老师有点儿远，我说了好多遍“老师您可以大点儿声吗？我听不太清楚”，然后老师重复几遍之后我才发现问的问题我不会- -这就很尴尬。。不过好在有惊无险，发挥中规中矩，多亏老师看得见机试分数，还是得了一个不错的分数。

后记

    浙软出结果非常快，全部面试完第二天上午就出结果了，详细地记录着每个人机试和面试的分数，非常透明。就打算上岸浙软了，菜鸡能去华五已经很满意辽~