W.A.R

题解

牛客练习赛题解(1)

/ 注册

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

【牛客7872 H 德邦王国】dfs全排列跑图暴力冲过去

【牛客7872 H 德邦王国】dfs全排列跑图暴力冲过去传送门题目描述在遥远的德邦草原，有一个古老的国度。这里的国王有一种特殊的能力，他可以在限定次数内互换自己和某些子民的位置现在国王需要让自己的子民排列成一个整齐的方阵接受检阅，但是他们的动作太慢了 ...

dfs 暴力

2020-11-04

0 728

【牛客7872 L】吃火锅-超级源点跑单源最短路-浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛（同步赛）

【牛客7872 L】吃火锅-超级源点跑单源最短路-浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛（同步赛）传送门链接：https://ac.nowcoder.com/acm/contest/7872/L来源：牛客网题目描述有n个城市，m条双向道路。每条道路连接连接俩个城市，经过道路需要交...

超级源点图论单源最短路

2020-11-01

0 588

【牛客7872 A】离散化-求一个数列第b项是第a项的多少倍

【牛客7872 A】离散化-求一个数列第b项是第a项的多少倍传送门题意一个数列，初值为1，递推公式为求第b项是第a项的多少倍，a和b的范围是1e8，1e5组询问显然可以初始处理出第1项~第1e8项的值（取模）然后取我们需要的，取的这个过程需要离散化一下提高效率，把所有询问到的点存在一个c...

2020-10-31

1 636

【牛客7872 D】尼姆博弈

【牛客7872 D】尼姆博弈传送门题意 A和B玩游戏，给n个数，每次能对一个数进行操作，如果一个数是1那么不能对它进行操作。每次操作可以选择这个数x大于1的因子a，把这个数变成x/a。最后无法操作的人输。问谁能赢？题解这是一道比较裸的尼姆博弈题，尼姆博弈是n堆石子，每堆石子有一定数量的石子...

尼姆博弈博弈分解质因子

2020-10-31

0 650

【牛客7502 D行列式】

【牛客7502 D行列式】传送门更好的阅读体验点这里题意求一个n阶行列式的值，行列式第行第列的元素是,特别的时，需要额外加上一个xa和b是两个给定的长度为n的数组，x是一个给定的数。如图题解这道题最主要的就是关于这个行列式的化简用到了一个小技巧：升阶法来源：我是从这里学到的！猪真是个好...

数论行列式

2020-10-31

13 832

【牛客7872 C变强的秘药】dp

【牛客7872 C变强的秘药】dp 传送门题意给n个数，按这个n个数给出的顺序取数，每一次至少取k个数，每一次取数的==收益==是取的序列后三个数之积 - 前三个数之积。例如我本次取a[1]~a[10]，我能得到的收益是a[10] * a[9] * a[8] - a[1] * a[2] * a[...

dp

2020-10-30

1 508

【2020小米网络选拔赛D Router Mesh】Tarjan求每个点属于哪几个点双连通分量

【2020小米网络选拔赛D Router Mesh Tarjan求每个点属于哪几个点双连通分量】求删掉一个点后的连通块个数，对每个点进行一次询问传送门题意给一个无向图，对每一个结点做一个询问，询问为，若删掉该点（及所有与其相关的连边），整个图有几个连通块？题解用Tarjan算法的思路来写，...

Tarjan 点双连通分量

2020-10-25

4 802

【牛客小白月赛27 A 巨木之森】树的直径&&思维

【牛客小白月赛27 A 巨木之森】题意给一棵n个结点的树，m块钱。定义从一个点出发遍历整棵树的花费是路径的边权和。求最多能选择多少个不同的起点使得从这些起点分别遍历整棵树的花费<=m。题解首先，肯定的是用贪心的思想来做，假设现在已知从每个结点出发遍历整棵树的花费分别是多少，那么只需要...

牛客小白月赛树的直径思维

2020-09-01

4 529

牛客练习赛68 A-牛牛的Mex

牛客练习赛68 A-牛牛的Mex 传送门题意给一个0~n-1的排列，q个询问，询问区间的Mex。 Mex定义为最小未出现的自然数。题解我们队三个人看到这题第一反应上莫队，jhlp哈哈哈哈然后掏出莫队板子火速A了我是赛后再来回顾的，发现由于这题数组比较特殊是有更符合这道题背景的做法的。莫...

牛客练习赛莫队想法

2020-08-30

0 695