akuna一面直接做题 没有自我介绍第一题 求一个数的奇偶校验位第二题 求二叉树节点最大值第三题 给一个函数，要求修改成线程安全的第四题 手写priority_queue（构造，析构，push,top,pop）做完题反问结果第二天就出（回来补）

J题  题目大意：有n个珠宝，每个坐标为(xi , yi , zi),且过t时间珠宝下沉至（xi , yi , zi + t * vi) , vi为每个珠宝下沉速度。每个时间只能打捞一个珠宝，代价为d²，d为（0，0，0）到该珠宝的距离。求打捞全部珠宝的最小代价。  思路：我们发现这是一个完全偶图求最佳匹配的问题。那么直接上KM板子！下面是大佬n³的板子，现在它就是我的了） ac代码： #include using namespace std; const int N = 1010; long long n,x[N],y[N],z[N],v[N]; long long w[N][N]; nam...

E题  题目大意：给出n个点，每个点的点权取值范围[ L[i] , R[i] ]；给出n-1条边，边的边权w表示连接的两个点的点权的异或值为w。问合法的取值有多少套。  思路：假设确定了第一个点的值，那么其他所有点的值就确定下来了。不妨令第一个点的初始值为0，此时所有点初始值被定好。设第一个点最终值为a，第i个点初始值为x，而第i个点的最终值要满足L[i] <= (x xor a）<= R[i]，即a要满足 (L[i] xor x) <= a <= (R[i] xor x)，而我们知道区间异或某个数后不一定连续，考虑线段树维护0 ~ (1<<30)-1的区间...

B题  题目大意：n * m的方格，每个方格的值表示把这个方格涂黑的代价，2 * 2的方格内如果有三个已经涂黑，那么第四个自动涂黑，即代价为0.问将所有方格涂黑的最小代价。n,m<5000  思路：可以发现，只需要涂n+m+1个方格就可以将整个图涂黑。将w[i,j]看作i和j两个点之间的边权，转化为最小生成树问题，在n*m条边中选出n+m条边构成最小生成树。因为是稠密图所以选择prim算法。注意如果行编号从1 ~ n,则列编号从n+1 ~ n + m，避免边的表示重复。 ac代码： #include <bits/stdc++.h> using namespace std; c...

K题  题目大意：给出n,k，表示一共n个数，生成单调栈序列b，接下来k行每行输入p和v表示b[p] = v，请写出一个满足要求的序列。n<1e6。  思路：k可能小于n，那么将b数组都填满，按如下的规则：若当前b有值，则从此位置到前一个有值的b之间填充b[i]-1,b[i]-2......，最后一个有值的b右边都用最后一个b的值填充。比如已知b[2]=2,b[5]=4,则完整的填充序列为1,2,2,3,4。接下来按从小到大，从右到左的原则排序并赋值。 ac代码： #include <bits/stdc++.h> using namespace std; const int ...

A题  题目大意：Alice和Bob轮流取石子，两堆分别为n和m，每次从一堆取k(k>0)，另一堆取s*k(s>=0)，输入为t组，每组输入n,m，问谁会赢。（t<1e4,n,m<5e3)  思路：f(i,j)表示输赢状态，1为必胜，0为必败，从当前必败推出f(i+k,j+sk)和f(i+sk,j+k)必胜。代码 #include <bits/stdc++.h> using namespace std; const int N = 5010; bitset<N> f[N]; int main(){ int t; for(int S = 0;S &...