【牛客7872 L】吃火锅-超级源点跑单源最短路-浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛（同步赛） 传送门 链接：https://ac.nowcoder.com/acm/contest/7872/L来源：牛客网 题目描述 有n个城市，m条双向道路。每条道路连接连接俩个城市，经过道路需要交路费。第i条路线可用于从城市vi到城市ui（以及从ui到vi），并且使用该路线需要花费wi。每个城市都开了一个相同的火锅店，但是由于位置不同，每家火锅店的价格不同，为了简化问题。假设到第i个店吃的花费是val[i]。这个n个城市的人发现了这个漏洞，请你计算每个城市的人最少的吃火锅花费（花费包括来回的...

【牛客7872 A】离散化-求一个数列第b项是第a项的多少倍 传送门 题意 一个数列，初值为1，递推公式为 求第b项是第a项的多少倍，a和b的范围是1e8，1e5组询问 显然可以初始处理出第1项~第1e8项的值（取模） 然后取我们需要的，取的这个过程需要离散化一下提高效率，把所有询问到的点存在一个c数组里，排个序，在初始处理的时候碰到这个数组里的值就把这个答案记下来初始化完成后就可以对每一组询问计算答案即可 哔哔赖赖 据说还可以map搞一下，下次再说咕咕咕 Code /**************************** * Author : W.A.R * * D...

【牛客7872 D】尼姆博弈 传送门 题意 A和B玩游戏，给n个数，每次能对一个数进行操作，如果一个数是1那么不能对它进行操作。每次操作可以选择这个数x大于1的因子a，把这个数变成x/a。最后无法操作的人输。 问谁能赢？ 题解 这是一道比较裸的尼姆博弈题，尼姆博弈是n堆石子，每堆石子有一定数量的石子，每次可以取一堆中一部分石子或者整堆取走，但是不能不取。对应到这道题目里，选择一个>1&&<自身的因此就相当于取走了一部分石子，选择自身这个因子就相当于直接整堆取走。那么每堆石子有多少个呢，答案就是这个数的质因子个数。然后根据尼姆博弈的结论，判断异或和是否为0，若为0则先...

【牛客7502 D行列式】 传送门更好的阅读体验点这里 题意 求一个n阶行列式的值，行列式第行第列的元素是,特别的时，需要额外加上一个xa和b是两个给定的长度为n的数组，x是一个给定的数。如图 题解 这道题最主要的就是关于这个行列式的化简用到了一个小技巧：升阶法 来源：我是从这里学到的！猪真是个好地方针不戳针不戳 具体方法是在最左边和最上面加一行一列，让n阶行列式变为n+1阶行列式，第一列除第一行的位置其他全为0，第一行除第一列的位置其他全为b[1]~b[n]，如图 这样升阶后，把第一行分别乘上加到第行去，这样一来行列式除第一行第一列的部分就变成了主对角线全为x，其他部分全为0，如图 这样...

【牛客7872 C变强的秘药】dp 传送门 题意 给n个数，按这个n个数给出的顺序取数，每一次至少取k个数，每一次取数的==收益==是取的序列后三个数之积 - 前三个数之积。例如我本次取a[1]~a[10]，我能得到的收益是a[10] * a[9] * a[8] - a[1] * a[2] * a[3]。求怎么取能获得最大收益？ 题解 dp[i]代表以 i 为取的某一次的右端点时，答案的最大值是多少。那么我们求的就是dp[n]，因为显而易见n一定是某一次取的右端点。考虑这个答案是由几部分组成的是由3部分组成的，首先第一部分是，这一部分是雷打不动的那另外两部分就是与相对于的这一次的左端点会带来的...

【2020小米网络选拔赛D Router Mesh Tarjan求每个点属于哪几个点双连通分量】求删掉一个点后的连通块个数，对每个点进行一次询问 传送门 题意 给一个无向图，对每一个结点做一个询问，询问为，若删掉该点（及所有与其相关的连边），整个图有几个连通块？ 题解 用Tarjan算法的思路来写，dfn[i]代表结点 i 的dfs序，low[i]代表从结点 i dfs下去能到达的dfn值最小的结点的dfn值。若u为当前结点，v为一个u的未被访问过的子节点，若对 v dfs完毕后，得到 low[v] >= dfn[u]则说明从u的父亲结点，经过u能够到达v，如果把结点u删掉，则不能到达结...

【牛客小白月赛27 A 巨木之森】 题意 给一棵n个结点的树，m块钱。定义从一个点出发遍历整棵树的花费是路径的边权和。 求最多能选择多少个不同的起点使得从这些起点分别遍历整棵树的花费<=m。 题解 首先，肯定的是用贪心的思想来做，假设现在已知从每个结点出发遍历整棵树的花费分别是多少，那么只需要把花费从小到大排序，从小到大取，取到不能取为止。 那么现在问题转化成为怎么求所有点作为起点遍历整棵树的花费。 首先考虑，给定一个起点，怎么求遍历整棵树的最小花费，对于每一个起点，我们势必是要最小化花费使得节省出更多的钱，希望供更多的起点使用。 那如何求最小花费呢。 考虑从一个起点出发，如果最后要求需...

牛客练习赛68 A-牛牛的Mex 传送门 题意 给一个0~n-1的排列，q个询问，询问区间的Mex。 Mex定义为最小未出现的自然数。 题解 我们队三个人看到这题第一反应上莫队，jhlp哈哈哈哈 然后掏出莫队板子火速A了 我是赛后再来回顾的，发现由于这题数组比较特殊是有更符合这道题背景的做法的。 莫队 首先考虑莫队做法 莫队的话首先要对询问区间排个序，然后主要就是考虑Add和Del函数怎么写。 用一个cnt数组记录在当前区间某个数出现过的次数，tmpans代表当前区间的Mex，初始置为0 ①Add，区间扩展的时候，扩展的这个位置上的这个数的cnt++。考虑这一位的cnt++会给答案造成什么样的...

牛客练习赛68 A-牛牛的Mex 传送门 题意 给一个0~n-1的排列，q个询问，询问区间的Mex。 Mex定义为最小未出现的自然数。 题解 我们队三个人看到这题第一反应上莫队，jhlp哈哈哈哈 然后掏出莫队板子火速A了 我是赛后再来回顾的，发现由于这题数组比较特殊是有更符合这道题背景的做法的。 莫队 首先考虑莫队做法 莫队的话首先要对询问区间排个序，然后主要就是考虑Add和Del函数怎么写。 用一个cnt数组记录在当前区间某个数出现过的次数，tmpans代表当前区间的Mex，初始置为0 ①Add，区间扩展的时候，扩展的这个位置上的这个数的cnt++。考虑这一位的cnt++会给答案造成什么样的...

        if(pow(a,d)+pow(b,e)+pow(c,f)==g)printf("Yes\n");         else printf("No\n");         ll s1=pow(a,d);         ll s2=pow(b,e);         ll s3=pow(c,f);         if(s1+s2+s3==g)printf("Yes\n");         else printf("No\n"); ...