wngynng

题解

/ 注册

全部文章 / 题解（共5篇）

2021牛客多校第五场题解

J题题目大意：有n个珠宝，每个坐标为(xi , yi , zi),且过t时间珠宝下沉至（xi , yi , zi + t * vi) , vi为每个珠宝下沉速度。每个时间只能打捞一个珠宝，代价为d²，d为（0，0，0）到该珠宝的距离。求打捞全部珠宝的最小代价。思路：我们发现这是一个完全偶图求...

2021-09-07

0 562

2021牛客多校第四场题解

E题题目大意：给出n个点，每个点的点权取值范围[ L[i] , R[i] ]；给出n-1条边，边的边权w表示连接的两个点的点权的异或值为w。问合法的取值有多少套。思路：假设确定了第一个点的值，那么其他所有点的值就确定下来了。不妨令第一个点的初始值为0，此时所有点初始值被定好。设第一个点最终值...

2021-08-23

0 566

2021牛客多校第三场题解

B题题目大意：n * m的方格，每个方格的值表示把这个方格涂黑的代价，2 * 2的方格内如果有三个已经涂黑，那么第四个自动涂黑，即代价为0.问将所有方格涂黑的最小代价。n,m<5000 思路：可以发现，只需要涂n+m+1个方格就可以将整个图涂黑。将w[i,j]看作i和j两个点之间的边权，...

2021-08-17

0 495

2021牛客多校第二场题解

K题题目大意：给出n,k，表示一共n个数，生成单调栈序列b，接下来k行每行输入p和v表示b[p] = v，请写出一个满足要求的序列。n<1e6。思路：k可能小于n，那么将b数组都填满，按如下的规则：若当前b有值，则从此位置到前一个有值的b之间填充b[i]-1,b[i]-2......，...

2021-08-06

1 555

2021牛客多校第一场题解

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+s...

2021-07-24

0 752