春招大厂笔经合集~
金三银四已然接近尾声，小虾也在四月初拿到了大厂的暑期实习研发岗offer。今天和大家分享一下这次暑期实习陪跑的笔经。
投的不多，有的代码没能及时保存好（着实可惜），品相比较好的都放在下面啦~
21年雷火游研岗的也顺手补上去了~
目录
04-01【2021网易雷火】游戏研发岗笔试
T1-打扑克-纯模拟（10分）
题目描述
输入输出描述
AC_code
T2-钱老板玩MMO-纯模拟（20分）
题目描述
输入输出描述
样例数据
AC_code
T3-接水果-DP（30分）
题目描述
输入输出描述
样例数据
AC_code
02-28【2022字节跳动】游戏研发岗笔试
第一题_走迷宫（20分）
题面
样例
思路
AC_Code
第二题_输出序列（20分）
题面
样例数据
思路
第三题_字符串染色（30分）
题面
样例数据
思路
03-05【2022美团校招】技术岗笔试
T1-四川麻将
输入输出描述
样例数据
AC_Code
T2-翻转最大子段和
题意
输入输出描述
样例数据
AC_Code
T3-切豆腐
题意
输入输出描述
样例数据
AC_Code
T4-区间操作求和
题意
样例数据
AC_Code
03-16【2022飞鱼科技】夏令营开发A卷（5/5）
T1-处理文本
题意
AC_Code
T2-判断正确IP地址
题意
AC_Code
T3-小红戴口罩
题意
输入输出描述
样例数据
AC_Code
T4-小萌是个WOW发烧友
题意
输入输出描述
样例数据
AC_Code_DP
AC_Code_DFS
T5-餐馆问题
题意
输入输出描述
样例数据
AC_Code
03-19【2022吉比特】春招技术笔试A卷（2/2）
T1-博弈论（10分）
题意
输入输出描述
样例数据
思路
AC_Code
T2-状压dp（20分）
题意
输入输出描述
样例数据
思路
AC_Code
03-23【2022西山居seed】开发岗笔试（2.5/3）
T1-异或得分路径条数（折半搜索）
题意
输入输出描述
数据样例
思路分析
代码呈现（50%的）
AC_Code
T2-循环阶梯（炼狱大模拟）
题意
输出描述
数据样例
AC_Code
T3-花香（ZKW线段树）
题目描述
输入输出描述
样例数据
思路分析
AC_Code
03-27【2022剑心互娱】程序岗笔试（2/3）
T1-地图的独立空间（核心代码模式）
题意
样例数据
AC_Code
T3-射击气球（ACM模式）
题意
输入输出描述
样例数据
Code（83.3%）
03-28【2022网易雷火】游戏研发笔试（3.85/4）
T1-小Y抽奖
题意
输入输出描述
样例数据
AC_Code
T2-打魔法牌
题意
输入输出描述
样例数据
AC_Code
T3-字母语句大模拟
题意
Code (85%)
T4-藏宝图
题意
输入输出描述
AC_Code
04-08【2022阿里灵犀互娱】游戏测开笔试（3/3）
T1-进制转换
题意
输入输出描述
样例数据
AC_Code
T3-特殊字符串
题意
输入输出描述
样例数据
AC_Code
04-01【2021网易雷火】游戏研发岗笔试
T1-打扑克-纯模拟（10分）
题目描述
你和小伙伴共四人一起打扑克，使用了两副牌，包括2-10、J、Q、K、A四种花色(红桃、黑桃、红方、黑花)各两张，以及大王、小王各两张，每人手中有27张牌。请计算出你手中的牌可以组合成几种同花顺。
五张数值连续的牌称为顺子，如果花色也相同，则称为同花顺。同花顺的数量是指手中的牌可以组合出的数量，这些同花顺无需同时存在，例如均为红桃的2、3、4、5、6、7，可以组合出2个同花顺 (2.3、4、5、6和3、4、5、6、7)。相同大小和花色的五张牌组成的同花顺只算一种，例如均为红桃的2、3、.4、5、6各两张，只能组合出1个同花顺。特别地，A既可以在A、2、3、4、5中，也可以在10.J、Q、K、A中，大、小王不组成顺子。
输入输出描述
输入描述
27行,每行一张牌。每张牌用两个数字表示，第一个数字表示数值，其中J=11、0=12、K=13、J=14、小王=15、大王=16;第二个数字表示花色，红桃=1，黑桃=2，红方=3，黑花=4，小王的花色为1,大王的花色为2。
输出描述
同花顺的数量。
样例数据
AC_code
#include using namespace std;const int N=1e5+10,M=3e5+10;typedef long long LL;typedef pair PII;int e[M],w[M],ne[M],h[N],idx;int dist[N];bool vis[N];int cnt[N];struct f {int num,id;}s[N];bool cmp(struct f x,struct f y) {if(x.id==y.id) return x.num<y.num;return x.id<y.id;}mapmp;int main(){int cnt=0;for(int i=1; i> a >> b;if(a==14){int aa = 1;if(!mp[{aa,b}]) s[++cnt]={aa,b},mp[{aa,b}]=1;}if(mp[{a,b}]) continue;mp[{a,b}] = 1;s[++cnt] = {a,b};}//cout<<endl;sort(s+1,s+cnt+1,cmp);int ans=0;//for(int i=1;i<=cnt;i++)//cout<<s[i].num<<" "<<s[i].id<<endl;for(int i=1; i=11) break;int flag=0;if(i+4>cnt) continue;for(int j=i+1; j14) flag=1;if(!flag) ans++;}cout << ans << endl;return 0;}T2-钱老板玩MMO-纯模拟（20分）
题目描述
钱老板玩MMO喜欢在二维的(X,Y)坐标系的场景内刷怪，钱老板一共有两个技能。
技能A：消灭一条直线上的怪，其中直线的方向只有横向(X轴方向)、竖向(Y轴方向)、斜45度和斜135度方向。
技能B：对一个怪M1释放一个AOE(群体伤害)，可以消灭以怪M1为中心,边长为2*N+1的正方形范围(包含正方形的边)内的所有怪，其中正方形的底边是与视野坐标x轴平行。
注意：不同怪物位置可以相同。
现在钱老板想知道某个时刻施放一个技能，最多能消灭的怪的数量。
输入输出描述
输入描述
技能s的正方形边长参数n(整数，0<= N<=30，边长为2*N+1)、怪物数量count（整数，0<=count<=200) 以及所有怪物的坐标(x，y)（x, y均为整数，0<=x<=300，0<=y<=300)。
输出描述
输出一个整数，表示最多可以消灭的怪物数量。
样例数据
AC_code
#include using namespace std;const int N=4e5+10;typedef long long LL;typedef pair PLL;int n,m;struct f {int x,y;}s[N];int check1(int u){int cnt1=0,cnt2=0,cnt3=0,cnt4=0;for(int i=1; i<=m; i++){if(s[i].x==s[u].x) cnt1++;if(s[i].y==s[u].y) cnt2++;if(s[i].x-s[u].x==s[i].y-s[u].y) cnt3++;if(s[u].x-s[i].x==s[i].y-s[u].y) cnt4++;}int res;res=max(cnt1,cnt2);res=max(res,cnt3);res=max(res,cnt4);//cout<<cnt1<<" "<<cnt2<<" "<<cnt3<<" "<<cnt4<<endl;return res;}int check2(int u){int cnt=0;int lx=s[u].x-n,rx=s[u].x+n,ly=s[u].y-n,ry=s[u].y+n;for(int i=1; i<=m; i++) if(s[i].x=lx&&s[i].y=ly) cnt++;return cnt;}int main(){cin >> n >> m;for(int i=1; i> a >> b;s[i]={a,b};}int ans=0;for(int i=1; i<=m; i++){int t = max(check1(i),check2(i));ans = max(ans,t);}cout << ans << endl;return 0;}T3-接水果-DP（30分）
题目描述
接水果游戏是个非常简单有趣的电子游戏。在游戏中，水果从屏幕上方由上至下掉落，玩家控制的篮子则在屏幕下方左右任意移动。当玩家控制的篮子触碰到掉落的水果时则成功接住，反之如果水果超过了屏幕的下方底线则失败。如果接住失败的水果大于或等于一定次数限制m (m>0）或者所有水果都被接完，则游戏结束。游戏中有不同的水果，每个水果的总分值也各不相同。最终篮子中接到的水果的总分数之和就是一局游戏的分数。由于篮子移动的速度是有限的，玩家还需要有选择地放弃接一些水果才能最终拿到更高的分数。
所有水果的位置在一轮游戏开始之前就预先设定好，并以坐标的形式(xi.yi)给出，单位为m，xi>=0，yi>0，游戏中不会有两个或两个以上的水果处于同一水平线上。当游戏开始时，所有水果延y轴方向垂直向下以1 m/s的速度匀速移动。
玩家的篮子也有个初始位置,横坐标为x0 m,x0>=0，纵坐标固定为0。篮子的移动速度固定为v m/s，v>0.
现在需要写—个程序,来帮助我们选择最佳的接水果路线。
输入输出描述
输入描述
第一行为4个整数，分别为篮子横向移动的速度v(m/a)、玩家的初始位置x0（m)、所有水果的总数量n、会导致游戏结束的接落失败水果数量m；接下来的n行，每行包括3个整数，分别为水果的x坐标x（m)、y坐标yi(m)，以及水果的分值w1(0<wi<=10)。0<n<=1e4，0<v<=100，1<=m<=100，0<=xi<=1000，0<yi<=2e5。
输出描述
一个整数，玩家以最优策略(之一)去接水果所能获得的最高分数。
样例数据
AC_code
#include using namespace std;const int maxn=10050;const int maxm=105;struct point{int x,y,val;point(int x=0,int y=0,int val=0):x(x),y(y),val(val){}};bool operator < (point a,point b){return a.y<b.y||(a.y==b.y&&a.x<b.x);}point p[maxn];int dp[maxn][maxm];int v,x0,n,m;void solve() {scanf("%d %d %d %d",&v,&x0,&n,&m);for(int i=1; i<=n; i++) scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].val);sort(p+1,p+n+1);p[0] = point(x0,0,0);int res=0;for(int i=1; i<=n; i++) {for(int j=1; j=0; j++) {for(int k=j-1; k=l&&p[i].x<=r) dp[i][k] = max(dp[i][k],dp[i-j][k-(j-1)]+p[i].val);}}for(int j=0; j<=m-1; j++) res = max(res,dp[i][j]);}printf("%d\n",res);}int main() {solve();return 0;}02-28【2022字节跳动】游戏研发岗笔试
字节游戏研发岗笔试第一批：2小时4题，满分一百，不能使用本地ide，代码为acm模式
第一题_走迷宫（20分）
题面
给出长n宽m的迷宫(n和m都在1~500之间)，迷宫由0和1组成，1表示有墙不能走，0表示能走。WASD分别表示向上下左右移动，给出由WASD组成的长度为q的字符串，表示走的方向。小红初始位置在迷宫的左上角(1,1)，求按照字符串表示的方向走完之后，小红在迷宫的最终位置;
样例
样例输入
3 3 4
000
100
001
WDDS
正确输出
2 3
思路
模拟，值得注意的是：地图的范围是(1~n)(1~m)，要把周围 0行 0列 n+1行 m+1列 那几部分设成1，表示边界，防止走出边界。在读入二维矩阵的时候，模拟小红走迷宫的时候要预判能否走动，能走动的话改变坐标。
AC_Code
#include using namespace std;int n,m,q,a[510][510];string s; int main() {cin >> n >> m >> q;int x=1, y=1; //小红的起始位置 //预处理边界和迷宫for(int i=0; i<=501; i++) for(int j=0; j<=501; j++) a[i][j]=1; //0~501是为了把周围部分设成1表示边界（想象有个围墙把迷宫围了起来） /*由于之前把表示迷宫的数组预处理了，现在想把需要读入的0/1排列 赋值给a[][]以表示迷宫。这里我们借用一个0/1字符串对a[][]按位赋值*/for(int i=1; i> t;for(int j=1; j> s; //读入表示行走方向的字符串 for(auto it : s) {if(it=='W' && !a[x-1][y]) x--; //预判能否向上走，若能，向上移动 if(it=='S' && !a[x+1][y]) x++; //预判能否向下走，若能，向下移动 if(it=='A' && !a[x][y-1]) y--; //预判能否向左走，若能，向左移动if(it=='D' && !a[x][y+1]) y++; //预判能否向右走，若能，向右移动}cout << x << " " << y << "\n"; //输出小红最后所在的位置 return 0;}第二题_输出序列（20分）
题面
给出n个数，每个数为1~n中某一个且这些数各不相同，要求构造一条k对相邻和为奇数的序列，输出一种合法的即可
样例数据
样例输入
8 4
正确输出
1 2 3 4 6 8 5 7
思路
我们首先要知道，奇偶交错排列才能保证相邻和为奇数，奇奇或偶偶的和只能为偶数；
其次，要满足k对相邻和为奇数的序列，考虑输出1~k+1；再保证剩下的数不增加相邻和为偶数对就可以了。下面用一幅图表示一下具体的做法：
第三题_字符串染色（30分）
题面
给出一个字符串S，由R和B组成，不同下标对应不同权值，求通过改变B为R，使得连续R的区间长度至少为K的权值花费的最小值
样例数据
输入
B B R R B R B R
1 3 5 6 7 4 2 9
4
输出
7
思路
固定长度K，然后扫一遍，用双指针操作。
03-05【2022美团校招】技术岗笔试
【自动车算法岗】差了5秒钟，终究还是没能AK呀。
第三题一开始只对了18%的数据，在还有20分钟的时候，发现题目看错了，码到cout<<ans<<endl; 的时候发现还剩5秒了，赶紧从ide复制到代码框内，光标刚刚放到保存代码上，发现按不动了，好家伙，时间截止了！
笔试题分为两大部分：4道算法题+3道人工智能相关知识的多选题。限时两个小时，每个子部分提交后可以再返回修改，这点还是很人性化的，不像有的笔试，子部分提交后就无法返回修改了，就不是那么的友好了。
题目大概都是力扣 [mid~hard] 的难度。
T1-四川麻将
题意
玩法是摸完牌之后选择3张花色一样的牌按某种顺序换给其他人。为了尽可能破坏对手的游戏体验，每次都会选择不连续的3张牌换出去。比如手上有 {1 4 5 6 8} 这5张条子，则可能会选择 {1 5 8} 这三张条子换出去。
把这个问题进行了简化，现在给你一个可重集合，并希望你从中选出一个尽可能大的子集使得其中没有两个数是 “连续” 的。
输入输出描述
输入
第一行一个整数n(1<=n<=100000)，代表可重集大小
第二行n个空格隔开的整数(范围在1到200000之间)，代表可重集
输出
输出满足条件的最大子集的大小
样例数据
输入
6
1 2 3 5 6 7
输出
4
AC_Code
#include using namespace std;const int N = 1e5+10, M = 2e5+10;int n, a[N], dp[M]; int main() {cin>>n;for(int i=1; i>a[i];for(int i=1; i<=n; i++) dp[a[i]] = 1 ;for(int i=1; i<M; i++) {if(dp[i]) dp[i] = max(dp[i],dp[i-2]+1);dp[i] = max(dp[i],dp[i-1]);}cout << dp[M-1] << endl;return 0;}T2-翻转最大子段和
题意
最大子段和是力扣上比较经典问题。这里对它进行了改编，允许在求解该问题之前翻转这个数组的连续一段，如翻转 (1,2,3.45.6) 的第3个到第5个元素组成的子数组得到的是 (1,2,5,4,3,6)，求翻转后该数组的最大子段和最大能达到多少。
输入输出描述
输入
第一行—个正整数n，(1<=n<=100000)，代表数组长度
第二行n个空格隔开的整数 (-1000<=ai< =1000)，代表数组元素大小
输出
求翻转后所得数组的最大子段和
样例数据
输入
6
-1 3 -5 2 -1 3
输出
7
AC_Code
#includeusing namespace std;const int N = 1e5+10, inf = 1e9+10;int n, a[N], p[N], s[N]; void solve() {p[0] = -inf;int sum=0;for(int i=1; i=1; i--) {sum = max(0, sum) + a[i];s[i] = max(s[i+1], sum);}} int main() {cin>>n;for(int i=1; i>a[i];solve();int ma = *max_element(p+1, p+n+1);for(int i=1; i<n; i++) ma = max(ma, p[i]+s[i+1]);cout << ma << endl;return 0;}T3-切豆腐
题意
为了切出更均匀的豆腐，想知道每一次下刀之后切出来的豆腐块中体积最大的那块有多大。
输入输出描述
第一行两个整数n,m (1<=n,m<=1000)，代表最开始长宽高均为n厘米，总共切了m刀。
第二行m个小写字母，每个字母都是 x,y,z 中的一个。第i个代表刀垂直于哪个坐标轴。
第三行m个大于0且小于n的正整数。第i个代表第i刀所在平面到豆腐的右上角 (或者任选一个角并固定，无论选哪个角答案均相同) 的距离。
保证切的时候豆腐不会产生形变且不会产生位移。每次下刀都会把整块豆腐切开，不存在切到一半收刀，切出来的每块小豆腐都是边长为正整数的长方体。
样例数据
输入
2 3
x y z
1 1 1
输出
4
2
1
AC_Code
#include using namespace std;const int N = 1e5+10, M = 2e5+10;int n, m; int main() {cin >> n >> m;vector op(m+1);for(int i=1; i>op[i];vector v(m+1);for(int i=1; i>v[i];multiset x,y,z;x.insert(0), x.insert(n);y.insert(0), y.insert(n);z.insert(0), z.insert(n);for(int i=1; i<=m; i++) {if(op[i][0]=='x') x.insert(v[i]);else if(op[i][0]=='y') y.insert(v[i]);else if(op[i][0]=='z') z.insert(v[i]);}int mx=0, my=0, mz=0, pre=0;for(auto it:x) mx = max(mx,it-pre), pre=it;pre=0;for(auto it:y) my = max(mx,it-pre), pre=it;pre=0;for(auto it:z) mz = max(mx,it-pre), pre=it;vector ans(m+1);for(int i=m; i>=1; i--) {ans[i] = mx*my*mz;if(op[i][0]=='x') {auto it = x.find(v[i]);int suf = *(++it);it--;int pre = *(--it);mx = max(mx, suf-pre);x.erase(v[i]);}if(op[i][0]=='y') {auto it = y.find(v[i]);int suf = *(++it);it--;int pre = *(--it);my = max(my, suf-pre);y.erase(v[i]);}if(op[i][0]=='z') {auto it = z.find(v[i]);int suf = *(++it);it--;int pre = *(--it);mz = max(mz, suf-pre);z.erase(v[i]);}}for(int i=1; i<=m; i++) cout << ans[i] << endl;return 0;}T4-区间操作求和
题意
给出一个长度为n的数组，进行m次数组上的区间操作，操作包含将区间内所有数加上一个值和查询一个区间内所有数的和。如果允许重新排列初始数组中的元素并依次进行操作，则操作中所有查询区间和的答案之和能够达到多大?
输入输出描述
输入
第一行有两个数 n,m(1<=n=<5000,1<=m<=500)，代表数组长度和操作次数。第二行有n个数，代表初始数组中的元素，接下来m行每行 1 l r 或 2 l r k，分别代表查询下标属于 [l,r] 的元素之和这一揭作和将下标属于 [l,r] 的元素全部加上定值k。l r k 满足1<=l<=r<=n，1<=k<=5000
输出
输出若允许重新排列初始数组，进行m次操作后产生的所有输出之和最大值
样例数据
输入
5 5
3 4 2 1 5
1 1 3
2 3 4 2
1 2 4
2 2 3 2
1 3 5
输出
42
AC_Code
#include using namespace std;const int N = 1e5+10, M = 2e5+10;int n, m; int main() {cin>>n>>m;vector a(n+1);for(int i=1; i>a[i];ll ans_sum=0;vector cnt(n+1),add(n+1);for(int i=1; i>op;if(op==1) {int l,r;cin>>l>>r;for(int i=l; i>l>>r>>k;for(int i=l; i<=r; i++) add[i] += k;}} sort(a.begin()+1,a.end()); sort(cnt.begin()+1,cnt.end()); for(int i=1; i<=n; i++) ans_sum += 1LL * cnt[i] * a[i];cout << ans_sum << endl;return 0;}03-16【2022飞鱼科技】夏令营开发A卷（5/5）
总卷130分满分，总共有以下题型，大概是下面这么个情况：
逻辑单选题：20题，2分/题，共计40分
专业单选题：5题，2分/题，共计10分
解答题：3题
填空题：3题
编程题：5题，10分/题，共计30分（选做3题即可）
T1-处理文本
题意
假设我们有一个nowcoder.txt，假设里面的内容如下
111:13443
222:13211
111:13643
333:12341
222:12123
现在需要你写一个脚本按照以下的格式输出
[111]
13443
13643
[222]
13211
12123
[333]
12341
AC_Code
declare -A mwhile read line do a=(${line//:/ }) m["${a[0]}"]="${m["${a[0]}"]}${a[1]}\n" done < nowcoder.txtk=0for i in ${!m[*]} do [ $k -eq 0 ] && k=1 && t="[$i]\n${m[$i]}" && continue printf "[$i]\n${m[$i]}" doneprintf "$t"T2-判断正确IP地址
题意
AC_Code
#!/bin/bashwhile read linedoa=(${line//./ })if [ ${#a[*]} -ne 4 ];thenprintf "error\n"else for((i=0;i<${#a[*]};i++))do[ ${a[${i}]} -gt 255 ] && printf "no\n" && breakdone[ $i == 4 ] && printf "yes\n"fidone < nowcoder.txtT3-小红戴口罩
题意
小红每个口罩戴—天的初始不舒适度为ai。有时会重复戴同一个口罩（重复戴时，口罩的不舒适度翻倍），求不舒服度总和不超过k的情况下，现有的口罩最多能撑几天。
输入输出描述
输入
第一行输入两个正整数n和k，分别代表口罩总数、最多能忍受的不舒适度总和。
第二行输入n个正整数ai，分别代表每个口罩初始的不舒适度。
1<=n<=1e5, 1<=ai, k<=1e9
输出
最多能度过的天数
样例数据
输入
2 30
2 3
输出
5
AC_Code
// 直接根据题意模拟#include #include #define ll long long using namespace std;ll n,k; int main(){ scanf("%lld %lld",&n,&k); priority_queue<ll, vector, greater> qu; for(int i=1; iqu.top()) { auto c = qu.top(); qu.pop(); k -= c; t++; qu.push(c*2); } printf("%d\n",t); return 0;}T4-小萌是个WOW发烧友
题意
对于小萌每次拿起的一个物品，装进包或者扔掉，且一个背包一旦不装东西，就不能再用。现在告诉你每个物品的体积，背包的个数和容量，以及拿物品的顺序，帮助她求出能拿走的最多物品个数。
输入输出描述
输入
第一行：一个整数T，代表测试数据组数。
第二行：三个正整数 N T M，分别表示物品的个数，背包的容量，背包的个数
第三行：N个数，表示每个物品的体积
1<=N,T,M<=20，0<=vi<=30
输出
每组数据输出一个整数，表示小萌可以拿走的最多物品个数
样例数据
看看给出的样例，明显不对呀。。。不过后台数据是对的，给出DP正确做法。
输入
2 5 5 2 4 3 4 2 1
输出
3
AC_Code_DP
c++提交运行时间：3ms
// 三维背包// cout<<i<<"个背包 "<<j<<"件物品 "<<k<<"容量"<<dp[i][j][k]<<endl;#include using namespace std;int dp[25][25][25];int main(){int T;cin>>T;while (T--){int n, t, m, a[25];cin >> n >> t >> m;for(int i=1; i>a[i];memset(dp, 0, sizeof(dp));for(int i=1; i<=m; ++i) //前i个背包for(int j=1; j<=n; ++j) //前j件物品for(int k=0; k= 0) //放入当前背包dp[i][j][k] = max(max(dp[i][j-1][k], dp[i][j-1][k-a[j]]+1), dp[i-1][j][t]); else //丢弃dp[i][j][k] = max(dp[i][j-1][k], dp[i-1][j][t]);}cout<< dp[m][n][t] <<endl;}return 0;} AC_Code_DFS
c++提交运行时间：7ms
#include #include #define ll long long using namespace std;int T;int main(){ cin>>T; while(T--) { int n,t,m; cin>>n>>t>>m; vector a(n+1); for(int i=1; i>a[i]; int ma=0; function dfs = [&](int pos,int cnt,int val,int used) { if(pos>n) { if(cnt<m&&val=m) return; dfs(pos+1, cnt, val, used); val += a[pos]; if(val>t) val=a[pos],cnt++; if(val<=t) dfs(pos+1, cnt, val, used+1); }; dfs(1,0,0,0); printf("%d\n",ma); } return 0;}T5-餐馆问题
题意
餐馆有n张桌子，每张桌子最大容纳人数为a；有m批客人，每批客人对应两个变量，b表示人数，c表示预计的消费。不能拼桌，选择一部分客人，求得最大总预计消费。
输入输出描述
输入
第一行：n和m，表示桌子数和客人批数（1<=n,m<=5e4）
第二行：n个a，每张桌子容纳的客人数目
接下来m行：每行一个b和c，表示每批客人的人数和预计消费金额
输出
总预计消费金额
样例数据
输入
3 5
2 4 2
1 3
3 5
3 7
5 9
1 10
输出
20
AC_Code
/*贪心策略对降序排列每批客人的消费金额，金额相同的升序排列；二分枚举处理最适合每批客人的桌子*/ #include #include #include 03-19【2022吉比特】春招技术笔试A卷（2/2）
总分共100分，有三四道选择没来得及，算法题AK，大概一共拿了八九十分
单选（2.5*20=50分）
填空（5*4=20分）
编程题（10+20=30分）
T1-博弈论（10分）
题意
一共有n个石子，编号1到n排成一排，一个常数k，每人可以从[1,k]中选择一个数，获取编号连续的k个石子。拿到最后的石子的人羸，也就是最后不能继续取的人输。每个回合都是小吉先手。假定两人都足够聪明，在给定n(1<=n<=1e6)、k(1<=k<=1e6)的情况下，如果小吉获胜输出"G win"，小特获胜输出"T win"。
输入输出描述
输入
每一行的输入都是n、k两个数。
输出
如果小吉获胜输出"G win"，小特获胜输出"T win" 。
样例数据
3 1
G win
思路
再经典不过的一道博弈论了
AC_Code
#include #define ll long long using namespace std;int n, k;int main(){ cin >> n >> k; if(n%(k+1) == 0) cout<<"T win"<<endl; else cout<<"G win"<<endl; return 0;}T2-状压dp（20分）
题意
摆摊地图是一个矩阵，里面有很多格子，每个格子有两种状态，可以摆摊和不可以摆摊，可以摆摊用1表示，否则用0表示，在这块地图中摆摊，要求两个相邻的格子不能同时摆摊(不包括斜着的)，即两个摊位不能相邻。问有多少种摆摊的方案(一个摊位也没有也是一种方案)。
输入输出描述
输入
第1行为两个整数n,m，1<=n<=12，1<=m<=12
第2行到第n+1行为m个整数，表示地图中每个格子是否可以摆摊
输出
方案数对987654321的取余
样例数据
输入
2 3
1 1 0
0 1 0
输出
9
思路
一看数据范围就不难想到是状压dp了，难点在于如何设立状态以及找状态转移方程。
对于这道题来说我们可以一行一行地处理，于是我们可以定义 dp[i][j] 为第 i 行状态为 j 的合法方案数，这样我们最后只需要把 dp[n][i] 累加起来输出即可。
题目中说保证两块区域不能相邻，相邻分为上下相邻和左右相邻，我们一行一行处理，因此可以在进行动态转移之前就先把一行中有相邻的情况给排除掉，假如某一行的状态是i，那么 （i&(i>>1))=0 就说明该方案没有两块是相邻的了。
至于上下相邻的情况，我们可以在动态转移的过程中处理，比如当前行状态是 i，下一行状态是 j，那么（i&j)=0 就说明上下没有两块是相邻的了。
那我们又该如何处理不能摆摊这个条件呢？我们可以用一个 F[i] 预处理出来第 i 行的所有状态，如果我们进行第 i 行的状态转移时用的状态都是 F[i] 的子集就可以满足情况了。
通过这道题目我们应该学到如何满足题目中所要求的限制条件，当然，这道题我们还可以把合法状态具体到每一行，也就是说我们把不可摆摊情况一开始就考虑进去，这样我们进行状态转移时只需要判断当前行的状态是否合理即可。
状态转移的合法状态应该在一开始就预处理出来，这样就不容易犯逻辑上的错误。
AC_Code
#include #define ll long long using namespace std;const int MOD = 987654321, N=13;int n,m,dp[N][1<<N], st[1<> n >> m;for(int i=1; i<=n; i++) {for(int j=1; j> f[i][j];F[i] = (F[i]<<1)+f[i][j];}}for(int i=0; i<1<>1))==0 ) st[i]=1;dp[0][0] = 1;for(int i=1; i<=n; i++) for(int j=0; j<1<<m; j++) if( st[j] && ( (j&F[i])==j ) ) for(int k=0; k<1<<m; k++) {if(j&k) continue;dp[i][j] += dp[i-1][k];dp[i][j] %= MOD; } ll ansa = 0;for(int i=0; i<1<<m; i++)ansa = (ansa+dp[n][i]) % MOD;printf("%lld", ansa);return 0;}03-23【2022西山居seed】开发岗笔试（2.5/3）
这次西山居seed开发B卷出的可以的，3道编程题60分均摊；剩余40分是选择填空之类（据说难于408）
由于西山居无法使用本地编译器，我又打开我的Devc重新把3份代码打了一遍（雾）
下面来分享一下这次的题目吧（幸好及时用笔抄了题，才能有机会写个题解）
喜欢西山居旗下的《双生视界》，封面是最近刚抽到的橙卡hh
T1-异或得分路径条数（折半搜索）
题意
一个 n*m 的矩形，每个格子上标有数字。小明从左上角出发走到右下角结束，每步只能向下或向右前进一个。小明的得分为路上经过的数字的异或和。求有多少条路径的得分为k。
输入输出描述
输入
第一行输入三个数，n m k，1<=n,m<=20
接下来输入n行m列，表示矩形上标的数字a[ ][ ]，1<=aij<=1e9
输出
输出得分为k的路径条数
数据样例
输入
2 3 15
1 2 4
2 4 8
输出
3
思路分析
这题乍一看肯定是一道迷宫类的搜索问题，但是常规的搜索只能拿到50%的分数（直接TLE超时），这里其实用到了折半搜索这一算法，笔试结束后和ICPC金牌爷大概说明了题意并请教了一番，发现是Codeforces原题 [2100+]，这让人不禁感慨题目的质量太高了，属实给我一个cu整不会了，出题人应该是某位大佬吧%%%
代码呈现（50%的）
AC_Code
思路：折半枚举， 先从(1, 1)开始限定深搜层数d， 对当前每个 (i, j) 记录了到达 (i,j) 且权值为 x 的路径有多少条。再从(n, m)搜， 走到一个已经搜过的 (i, j) 直接算对答案的贡献。复杂度为O(2^d*log(2^d) + 2^p*log(2^p))，(p+d=n+m)，当d取20的时候最优。
#include using namespace std;#define ll long long bool vis[25][25];ll k, res, a[25][25];unordered_map c[25*25];int n, m; int hxh(int x, int y){ return x * 21 + y;} void dfs_pre(int x, int y, ll cur, int deep){ if(x < 1 || y n || y > m || deep > 20) return ; vis[x][y] = 1; cur ^= a[x][y]; c[hxh(x, y)][cur] ++; dfs_pre(x + 1, y, cur, deep + 1); dfs_pre(x, y + 1, cur, deep + 1);} void dfs_suf(int x, int y, ll cur){ if(x < 1 || y n || y > m) return ; if(vis[x][y]) { res += c[hxh(x, y)][k ^ cur]; return ; } cur ^= a[x][y]; dfs_suf(x - 1, y, cur); dfs_suf(x, y - 1, cur);} int main(){ cin >> n >> m >> k; for(int i = 1; i <= n; i ++) for(int j = 1; j > a[i][j]; dfs_pre(1, 1, 0, 1); dfs_suf(n, m, 0); cout << res << '\n'; return 0;}T2-循环阶梯（炼狱大模拟）
题意
n*n的金字塔形阶梯，每一层可单独进行循环操作。俯视图为 n*n 的矩形。初始状态下，从第一层开始顺时针为每个方块标上序号。给出每层的循环格数，输出最终状态。（数据均在100以内）
输出描述
输出n行n列表示所有操作完成后阶梯的最终状态
数据样例
输入
5 3
1 3
2 11
3 5
输出
14 15 16 1 2
13 22 23 24 3
12 21 25 17 4
11 20 19 18 5
10 9 8 7 6
AC_Code
T3-花香（ZKW线段树）
题目描述
鲜花的芳香值为ai，每天会散发bi的芳香值。鲜花在芳香值为0时干枯。问每天会散发多少芳香值。
输入输出描述
输入
第一行输入N，表示经过了N天，1<=N<=1e6
第二行输入N个整数，表示鲜花的芳香值ai，1<=ai<=1e9
第三行输入N个整数，表示鲜花每天会散发bi点芳香值，1<=bi<.=1e9
输出
输出每天会散发的芳香值
样例数据
输入
4
5 7 9 3
3 4 5 1
输出
3 6 4 4
思路分析
这题要用线段树去解，用的ZKW线段树，比一般线段树已经短多了。或者用差分维护应该也行。
AC_Code
03-27【2022剑心互娱】程序岗笔试（2/3）
剑心有4题，1道根据游戏情景设计数据结构，剩下3道编程题（1道核心代码，1道工程函数填写，1道ACM模式）笔试时间1个小时，在给定时间内任意选择。代码题只写了T1和T3（没AC有点蓝瘦），T2骗个分不想管了，设计题看了下就交卷了。
T1-地图的独立空间（核心代码模式）
题意
现有二维数组 int height[m][n] 提供地表的高度信息，格子的值代表对应坐标的当前高度。当玩家处于其中一个格子时，可向前后左右四个方向移动。如果两个相邻格子的高度差大于等于2，则这两个格子间无法相互移动。求 height[m][n] 高度图表示的地形中有多少个不可互达的独立空间。
样例数据
输入
[ [1,2] , [3,4] ]
输出
2
AC_Code
class Solution {public: //const int N = 1e6+10; int fa[1000010], sz[1000010]; int find(int n) { return fa[n] == n ? n : fa[n] = find(fa[n]); } int get(int x,int y,int m) { return x*m+y; } void merge(int x, int y) { int fax = find(x), fay=find(y); if(fax==fay) return; fa[fax] = fay; sz[fay] += sz[fax]; } int CalculateAreaCount(vector<vector >& height) { int n = height.size(), m = height[0].size(); for(int i=0; i<n*m; i++) fa[i]=i,sz[i]=1; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { if(i && abs(height[i-1][j]-height[i][j])<2) merge(get(i-1,j,m),get(i,j,m)); if(j && abs(height[i][j-1]-height[i][j])<2) merge(get(i,j-1,m),get(i,j,m)); } } long long ansa = 0; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { int pos = get(i,j,m); if(find(pos)==pos) ansa++; } } return ansa; }};T3-射击气球（ACM模式）
题意
游戏允许玩家组队参加。小组的每人都有3颗橡胶子弹，轮流用气枪射击一面由4种不同颜色气球组成的墙。击破不同颜色的气球获得不同额度的奖金。墙上每种颜色的气球数量也不相同。
|
红色 |
400元/个 |
n1 |
|---|---|---|
|
蓝色 |
200元/个 |
n2 |
|
黄色 |
100元/个 |
n3 |
|
绿色 |
50元/个 |
n4 |
当所有人射击完毕后，获得的总奖金平均分配。但是如果射击技术足够好，那1个人参加游戏获得的人均奖金必然是最高的。为了鼓励更多人组队参加，补充规则：根据得到奖金的总数，制定了最少参加人数。若实际参加人数小于最少参加人数，得到的总奖金会根据最少参加人数来分配。
|
0~950 |
10 |
|---|---|
|
951~2550 |
12 |
|
2551~5550 |
15 |
|
5551~9550 |
20 |
|
9551~12550 |
25 |
|
12551~∞ |
30 |
输入输出描述
输入
每种气球的数里n1, n2, n3, n4 (0<=n1, n2 , n3, n4<200)
输出
能关得的人均奖金最高是多少（结果只取整数部分)
样例数据
输入
3 10 50 100
输出
395
Code（83.3%）
#include #include #include 03-28【2022网易雷火】游戏研发笔试（3.85/4）
3个小时，4道题目，雷火的题目不在于难，更在于对细节的把控和写大模拟的耐心，花了一个半小时，AC了3.85，直接交卷退了。第一题AC，第二题AC，第三题85%，第四题AC。下面分享一下大致的题意和对应的代码。
T1-小Y抽奖
题意
n行m列个奖励格子，每次抽奖消耗一个道具。每个格子奖励的数量有限且各不相司。每个格子被抽到一次，剩余的奖励数量-1。剩余的奖励数量为0时，则不会再抽到该格子。小Y抽了好多次，但一直没有抽到最想要的奖励，给出示例图中的情况。求再买几个猪心，才能保证抽到一次她想要的奖励。
输入输出描述
输入
第一行：两个正整救n和m (1<= n, m<=100)，表示n*m个奖励格子。
第二行：两个正整数x和y ( 1<= x<= n，1<=y<=m)，表示小Y想要抽到的奖励位置(奖励剩余数量不为0)。
接下来n行，每行m个整数，表示每个格子的奖励剩余a (0<=a<=1000)。
输出
输出一个数字，表示需要买几个道具，才能够保证抽到一次想要的奖励。
样例数据
输入
3 3
1 1
2 5 4
2 7 8
2 3 0
输出
32
AC_Code
// 遍历操作模拟一下即可#include #define ll long long using namespace std;int main(){int n,m,x,y;cin>>n>>m>>x>>y; vector<vector> a(n+1, vector(m+1));for(int i=1; i<=n; i++) for(int j=1; j>a[i][j]; int sum=0;for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(i==x && j==y) sum+=1; else sum += a[i][j]; cout<<sum<<endl;return 0;} T2-打魔法牌
题意
—套牌共N张，每张有数字和类别两个特征，数字范围为1~10，类别为A，B，C，D，E。要计算这套牌的倍数，默认1倍，有特殊的组合可以有更大的倍数（具体规则在图里面，真记不得了QAQ）。
输入输出描述
输入
第一行：一个整数M(1<=M<= 1000)，表示有M组数据；每组教据先输入N(1<= N<=5)，表示这套牌的张数；接下来两行，第一行是N个数字，表示N张牌的点数。第二行N个字母，表示对应的N张牌的花色。
输出
每组数据输出对应的套牌的倍数。
样例数据
输入
2
5
9 9 9 9 9 A B C D E 5
3 2 1 10 9 A A A A A
输出
15000
300
AC_Code
// 2#include #include T3-字母语句大模拟
题意
按如下要求模拟：
1. 每一行字符个数上限N(N>=20)，允许不填满N个。
2. 输入所有单词的长度<=N，单词不能分割在两行显示。如果当前行无法完整显示，则放到下一行显示。
3. 对于2的情兄，有一些特殊情况：如果当前行的最后一个单词只能部分显示在当前行，会导致当前行长度大于N，不满足。显示在下一行则当前行长度小于N，浪费当前行的长度。此时，如果提升当前行长度为N+M。(0<=M<=5，当前行允许显示N+M个字符)，就能在当前行完整显示，则允许突破。该突破在当前行最多只能一次。
4. 语句只有三种类型字符：26个字母大小写都认定为英文，连续英文组成单词；空格单独类(不存在连续空格)；其他都是标点符号(假定只存在长度为1的标点)。
5. 行首不能以空格开头。行首出现空格，则空格直接去掉。行末的空格强制去掉。
6. 行首不能以标点符号开头。标点符号开头则允许无条件突破前一行个数上限，将标点放在前一行末尾。无条件指不管前一行长度是多少，标点都可以放存末尾。
Code (85%)
#include #include T4-藏宝图
题意
水面每小时上涨1米。宝藏必须用船运回，只有当水面涨到同时淹没人和宝藏位置时，人才能驾船取回宝藏(假设船只能从当前位置向上下左右行驶)。求至少需要等待多少小时才能收获宝藏。
输入输出描述
输入
第一行：两个整教N M，表示群岛长宽。(1<=N<= 700, 1<=M<=700)
第二行：两个整数X Y，表示人当前所在位署，X为行，Y为列(1<X<= N，1<=Y<=M)
第三行：两个整数Z W，表示宝藏所处位署，Z为行，W为列(1<Z<=N，1<=W<=M)
之后一个N行M的二维整数数组，每个数字表示当前坐标位署处的每拔高度H(0<=H<N*M)
输出
最早T小时可以获得宝藏
AC_Code
#include #include 04-08【2022阿里灵犀互娱】游戏测开笔试（3/3）
90分钟，3道编程题+八股，第二题输出格式模拟题，没有存
T1-进制转换
题意
有一个数，可能是2～16进制的其中之一，算出所有可能的结果，并转成十进制后对1e9+7取模，答案从小到大排列，若存在相同的结果，只保留一个。
输入输出描述
输入
一个数，表示得到的数字。保证不会出现 '0'~'9'， 'A'~'F' 以外的字符，输入数字长度不超过100000，且保证无前导零
输出
每行输出可能的结果
样例数据
输入
11
输出
3 4 5 6 7 8 9 10 11 12 （换行输出）
AC_Code
#include #define ll long long using namespace std;int main(){string s; cin>>s;int n=s.length(); vector a(n); for(int i=0; i='0' && s[i]<='9') a[i]=s[i]-'0'; else a[i]=s[i]-'A'+10; } vector ans; int ma = max(2,*max_element(a.begin(), a.end())+1); for(int i=ma; i<=16; i++) { ll val = 0; for(auto x: a) val = (val * i % mod + x) % mod; ans.push_back(val); } sort(ans.begin(),ans.end()); ans.erase(unique(ans.begin(), ans.end()), ans.end()); for(auto x: ans) cout<< x <<endl; return 0;}T3-特殊字符串
题意
一个字符串仅包含小写字母，希望删除其中一个非空连续子串，使剩下的字符串至少有k种不同字母。求有多少种不同的删除方案。若删除的子串位置不同，则视为两种不同的方案。
输入输出描述
输入
第一行输入正整数n和k，代表字符串长度以及最终字符串的字母种类最小值。
第二行一个长度为n的只包含小写字母的字符串s (保证至少k种字符) 1<=n<=200000，1<=k<=26
输出
输出删除子串的方案数
样例数据
输入
5 2
aabba
输出
9
AC_Code
#include #define ll long long const int N = 2e5+10;using namespace std;char s[N]; int main(){int n, k;cin >> n >> k;scanf("%s",s+1);vector cnt(26); for(int i=1; i<=n; i++) cnt[s[i]-'a']++; ll ans=0; int l=1, r=1, pre=0, suf=0; for(int i=0; i<26; i++) if(cnt[i]) suf |= (1<<i); while(l<=n) { while(r1 && __builtin_popcount(pre | suf)>=k ) cnt[s[r++]-'a']--; else if( cnt[s[r]-'a']==1 && __builtin_popcount(pre | (suf ^ (1<=k ) suf ^= (1 << s[r]-'a'), cnt[s[r++]-'a']--; else break; } ans += max(0, r-l); pre |= (1<<(s[l++]-'a')); } printf("%lld\n", ans);return 0;}希望能给有需要的同学带来一点微不足道的帮助~
