JiayinDeng

分类

题解(3)

/ 注册

全部文章（共3篇）

牛客练习赛68 D题

D 题解初始人数分布可以看作初始状态，有一定概率转移到别的位置，视为状态转移，因此矩阵快速幂可以解决。但是直接使用矩阵快速幂的时间复杂度为，超时。需要改进矩阵乘法，观察到状态转移矩阵是一个循环矩阵，循环矩阵与循环矩阵相乘仍然为循环矩阵，因此，只需要保存矩阵的第一行，两个矩阵相乘时，通过两个矩阵第一...

2020-08-31

0 538

牛客算法周周练19 E题

E 题解看到大部分人都是dfs或bfs搜索做的，这里给一个并查集的方法：对于边缘处的'.'，与一个extra=m*n连接；对于不在边缘处的'.'，merge其上下左右的'.'和该点。最后遍历，遍历到不与extra连通的'.'，ans++。再把'#'加到答案中，代码 #include<bit...

2020-08-13

0 534

牛客编程巅峰赛S1第8场 - 黄金钻石 C题题解

C.牛牛摇骰子题解想到bfs，但是数据范围到1e9，内存和时间都会爆。为了优化，可以先考虑摇出一个较大的点数，尽可能多的摇出11，就可以尽快摇出这个点数。因此，猜测摇出某一点数的次数是有规律的（即，摇出大点数的次数可以由摇出小点数的次数直接算出）。对于较小的数据打表，如下，其中第一行数据是摇出1...

2020-08-05

0 1193