投的游戏研发工程师，难道传言只要985硕士是真的？AK4题都不能拿到面试资格卡吗

A 看见很多人先二进制分解然后反向比较，我觉得这一点都不优美我们可以利用栈的后进先出特点和队列的先进先出特点 #include<bits/stdc++.h> using namespace std; stack<int>st; queue<int>que; int main() { int _;cin>>_; while(_--) { int x;cin>>x; while(x) { st.push(x%2); que.push(x%2)...

参考资料https://ac.nowcoder.com/discuss/208861?type=101https://zhuanlan.zhihu.com/p/41867199http://blog.leanote.com/post/rockdu/TX20 题意 给定n,m,k,再给定n行m列数 求(修正：这里不是求和是异或和) 分析 以下推导统一用&表示按位与，^表示按位异或 这题考察fwt_xor，但和常规的考察不太一样，它并不是构造式子做卷积，而是关于做FWT后，得到的向量与原向量关系的应用 深入理解FWT_XOR walsh把信号在不同震荡频率方波下拆解，因此所有的系数都...

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9+7; const int N = 1e6+5; int n; ll siz[N]; ll d[2][25][25],pow2[25],pow3[25]; void ycl(){ int o=0; pow2[0] = pow3[0] = 1; for(int i=1;i<=n;i++){ siz[i] = n/i; } for(int i=1;i<...

#include<bits/stdc++.h> using namespace std; #define random(a,b) ((a)+Curl_rand()%((b)-(a)+1)) static unsigned int randseed; int n,cnt; unsigned int Curl_rand(void) { unsigned int r; /* 返回一个无符号32位整型的伪随机数. */ r = randseed = randseed * 1103515245 + 12345; return (r << 16) | ((r &gt...

题意 你有n个数字，范围[1, m]，你可以选择其中的三个数字构成一个三元组，但是这三个数字必须是连续的或者相同的，每个数字只能用一次，问这n个数字最多构成多少个三元组? 分析 这里想谈一下DP的一个套路，捆绑 有的DP题目，它可能会要求和一些东西捆绑，求方案数，这种时候如何单点设置状态呢？ 以这个题为例，只考虑前i种数字，对于数字i,它可能 (i,i,i) (i-2,i-1,i) (i-1,i) (i,) 如果是后两种，它还未构成一个合法的序列，我们还不知道是否存在i+1来完善它 也就是考虑前i种数字的时候，后两种不应该被计入方案数里，但转移的时候我们要用到他们的数量，这里就可以再用两...

题意 给定一个n阶方阵A,现在要从里面取出一个n/x阶子方阵B，使得使得对于对于A中每一个元素，都有 ,求x的最大值 分析 考虑这个关系式 $\frac{i}{x}-1 = \frac{i-x}{x}$ 也就是说，$B[\frac{i}{x}][\frac{j}{x}] = A[i-x+p][j-x+q] (1\leq p,q \leq x)$ 可以看出这是一个x阶子方阵矩阵 其实我们要求的就是将A平均分割成$\frac{n}{x}×\frac{n}{x}$个x阶方阵，每个方阵内的元素全都相等，求最大的x 我在这里维护了一个二维前缀和，这样对于一个子矩阵，只有和为0，或者和为矩...

题意 给一串01串，对该串进行若干次操作，直到串为空 操作为：选择一段连续的0或者1,删除它，拼接前后两部分成为新串，得到价值为a[删除的长度]（a为给定的数组） 思路 一个非常规的DP 考虑题目所给的操作，我们从中删除一段，再把前后拼接起来，如何设置状态？记录下断点的位置？不行，那样我们可能在其中插入很多断点，并且不便于转移 $...111000111...$ 如果我们仅仅研究中间的子串$111000111$ 我们删除中间的0,形成$111111$ 再删除中间的1,这样我们其实可以看做原串是$000\underline{111}111$ 也就是前面的1和后面的1其实是捆在...

题意 给你一个森林(若干棵树),向其中加边，使得最后形成一棵树，要求最后形成的树的直径最小，输出这棵树的直径和所加的边 分析 每加一条边，都可以将两棵树合并成一棵树，总共有t = n - m棵树 也就是说我们需要在这t棵树里面，分别选一个点，将他们连接起来，使得最后形成一棵直径最小的树 这个点的性质是，以这个点为根节点转化为有根树的画，树的高度一定是最小的（与重心类似，最长链最短可以保证合并后直径最短） 稍加分析可以知道，这个点一定是直径的中点（直径两端到该点的距离相差不超过1） 所以我们维护一棵树，可以维护以下几点性质： 1. 树的直径dig 2. 树的直径的中点序号cen...

题意 分析 如果我们已经求得了 f[L],f[L+1] ... f[mid],他们均能对f[mid+1],f[mid+2]...,f[R]产生贡献 对于x ∈ [mid+1,r] f[x] += \sum_{i=L}^{mid}(f[i]*g[x-i]) 等式右边满足卷积模式 具体看代码 代码 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int n; 5 ll gg[400005],f[400005],A[400005],B[400005]; ...

题意 分析 看似是期望问题，但是没有权重，就是求平均值，而答案要求乘上方案总数，所以 这是一个计数问题 考虑max,若三个绝对值分别为(x,y,z),则max = max(x,y,z) distance = max ^ Ib ^ (Ib+x) ^ Ab ^ (Ab + y) ^ Gb ^ (Gb + z)  我们统计出每种Ib^Ig ( |Ib - Ig| ≤ x ) 的方案数，同理其他属性也是，总共产生三个数组 根据乘法原理，我们可以求得 k = Ib ^ (Ib+x) ^ Ab ^ (Ab + y) ^ Gb ^ (Gb + z) 的方案数为∑ (cnt_I[ Ib ^ (...

题意 有n个人围成一圈，编号1到n，从1号开始报数，每报到第k个，此人出列，下一个人再从1开始报数，求第m个出列的人的编号(n,m,k ≤ 1e18, m,k其中一个小于1e6) 分析 我们知道，约瑟夫环的出队是有O(n)的递推算法的：f(n) = (f(n-1)+k-1)%n 约瑟夫环数学推导 但是这里是最后一个出列的人的情况（n个人第n个出列） 考虑一下n个人第m个出列，设状态为f(n,m),我们可以假设在m个人中再插上n-m个人，他们都比前m个人晚出队（具体放在哪里不用关心，只要认为他们一定不会先出队就行了），那么递推式就和刚刚的雷同 f(n,m) = (f(n-1,m-1)+...

参考资料 https://blog.csdn.net/lchi1997/article/details/77860085 五边形数和分拆数模板 ll p[100005]; ll q[200005]; const ll mod = 1e9+7; void init() { int tot = 0; q[0] = 0; int cnt=0; for(int i=1;i<=100000;i++) { ll x=i; q[++cnt] =( (ll)x*(3*x-1)/2)%mod; x = -x; q...