Description G公司有n个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使n个仓库的库存数量相同。 搬运货物时，只能在相邻的仓库之间搬运。 对于给定的n个环形排列的仓库的库存量，编程计算使n个仓库的库存数量相同的最少搬运量。 Input 第1行中有1个正整数n（n<=100)，表示有n个仓库。第2行中有n个正整数,表示n个仓库的库存量。 Output 一个整数，表示最少搬运量 Sample Input 5 17 9 14 16 4 Sample Output 11 给个提交链接：负载平衡问题 这个题如果和第17题...

机器人问题 这个题很明显跟费用有关，每个机器人可以看作是最大的通过的流量 源点S，汇点T，图中的任何一个点都是中间点，这些都好理解 那么，费用怎么理解？ 求最大费用最大流啊！ 不仅仅有拆点，还会有拆边！ 每两个点的路径分成两条边啊：有一种边是容量为1，费用为边上的价值：（u，v，1，value）；有一种边是容量是无限的，费用为0，（u，v，INF，0） 然后跑模板就好了啊 #include<bits/stdc++.h> using namespace std; const int maxm=1050; const int maxn=1050; const...

题目链接：骑士共存问题 贴一个很相似的题吧：方格取数 这两个题：如果放在了一起，相信应该都会有思路的吧！ 黑白染色法：求得最小割，然后用所有的可行点减去最小割就是：最大独立集 然后呢，建图有两种方法的 第一种方法：不拆点：那么我们需要对每个节点黑白染色：注意！ 这个染色与方格取数不一样了：因为有些点是障碍，那么黑白点的染色方案就变了 在计算的时候，只有非障碍点才编号 然后在连边的时候 源点S向所有的（i+j）%2==1的连边 所有的（i+j）%2==0向汇点T连边 然后，按照骑士的规则 枚举所有的可能情况就好 int main(){ //freo...

很经典的一道网络流了 相信网上的题解也很多很多 这里的重点放在两张图上 是上图还是下图 就会明白这个题到底什么意思的 点权和边权到底如何解释 //#include<bits/stdc++.h> #include<stdio.h> #include<cstdio> #include<algorithm> #include<cstdlib> #include<cstring> #include<string.h> using namespace std; const i...

算是总结几点mod的坑点吧 A：（a*b）%mod = （a%mod）*（b%mod）%mod 这个性质在a和b是大数的时候是有用的 B：快速幂中，求a^b%mod C：算是个细节 有的编译器，计算5%3=2；有的算出来5%3=-1 为了避免两种的差别 我们统一用：ans=（ans+mod）%mod 就可以把这个都化成正的最小的那个啦 D：请问： ans=ans*((n-m+i)*(quickpow(i,mod-2)%mod))%mod; ans=ans*((n+i-m)*quickpow(i,mod-2)%mod)%mod; 上两行式子有什么区别吗？ 第二行是更好的...

这个题的题意理解真是废了劲了 题意：有n个城市，编号1~n，有n-1条边，连成了一条从1到n的顺序的链 每条边都有花费cost【i】 每条边只能开关一次！！！ 门在打开时每天都有一个花费。这时候需要运输一些东西，告诉你开始和终止的城市，你需要保证有路径可以到达。最后输出每天的花费即可。 要理解题意，就要从样例看起 4 3 1 2 3 1 3 3 4 2 4 为什么从3到4这组样例的答案是5而不是3？ 那是因为，下面还有一组2到4 因为每条边只能开关一次，所以2到3这条边在3到4查询的时候是不能关闭的 怎么处理呢？要求所需要的钱最少 那么就是：每条边都开得尽...

这个题纯属脑洞啊 看到题目很明显就是找规律填数字，让我们一直加某一个数字使得可以开方成为一个整数 开到样例中的值 2，6，12，20，想到什么了吗？ 为什么输入4和输入3和输入2的答案不一样？ 由于这个是special judge，那么出题人的想法我们就能猜了 2=1*2 6=2*3 12=3*4 20=4*5 所以后面几个肯定是5*6=30，6*7=42…… 所以，我们可以打表了 #include<bits/stdc++.h> using namespace std; #define LL __int64 const int maxn=1e...

bin神模板大法好 题意：从A到B，有多少条最短路径 搞法是： 先从A到B跑一遍最短路算法（以A为起点，B为终点，遍历全图） 再从B到A跑一遍最短路算法（以B为起点，A为终点，遍历全图） 然后，因为我们要求的是A到B的最短路径的条数，如果我们把图中不在A和B最短路径上的点和边全部删掉 就变成了求从A到B的流量问题，求的是最大流 我们在两遍最短路之后，判断每条边是不是在A到B的最短路径上 如果在，就添加到边集合中（准备跑最大流算法） 注意，这个题卡的时间比较高，SAP过不了 亲测，bin神的ISAP两种模板都能过 这种题目主要还是靠脑洞吧，然后就是靠模板 ...

这个题是多个解法的题啦 题目中问： 删除多少个点，使得从起点1到终点n的最短路径大于K（到达不了算是INF） 如果用BFS+DFS就是搜索题 现在用网络流的思路来想这个题 删除点怎么和网络流量建立起来关系？！ 拆点：把点拆成i，i+n，连接一条流量为1的边。意味着如果拆i点，在流量中等价于拆i->i+n的边 当然，由于题目中说了不能拆1和n这两个点，那么这两个点在拆点后的连边的权值为INF 然后，用floyd预处理任意两点的最短路 对m条边的任意边<u，v>，如果有mp【1】【u】+mp【u】【v】+mp【v】【n】<=k 就说明这条边是...

这个题的数据量一看就是个数学题。。。然后就找啊找啊找规律！ 一开始走错了方向，因为k=2 然后呢，找到了一个规律：（只对k=2适合） 第一轮的删掉的数：x%k=0 第二轮的删掉的数：x%k^2=k 第三轮的删掉的数：x%k^3=k^2 然后发现…… 只对k=2适合 还是贴个程序纪念一下错误的数学思路吧 #include<bits/stdc++.h> using namespace std; #define LL __int64 LL calc(LL n,LL mod,LL left){ LL x=n/mod; LL y=(n-(n/mo...

一个好题！ 题意是：能否把题中的所有边遍历一遍，而且每条边只走一次 如果可以，要求走过的点的异或值最大 边遍历一遍就是：在图中能否找到一条欧拉路径！ 那么，我们首先得判断所有的点是不是连通的（注意，如果有孤立点是合法的！因为，它不与任何其他点有边的关系，也就不需要走到它了） 判断连通，肯定就是并查集了 然后呢，我们知道欧拉路的条件是：奇数点的个数为0或者为2（否则无解） 当奇数点个数为2的时候： 说明起点和终点已经固定了，只可能有一种走法 现在我们来想点的度数和走过的次数的关系 举几个例子就能得到结论 degree【i】=1，需要 degree【i】=2，需要...

#1383 吐槽一下北京网赛，感觉又是跟去年一样的风格 两个模拟，手速快的可以进，然而弱wa了全场 赛后补题补了这个，觉得学到了很多字符串模拟和STL的姿势 先说说题意：把用/分开的目录按照缩进的方式排列好 优先级的定义为：有目录的优先把目录放前面（有目录的时候，也是按照字典序的优先级），如果没有目录，按照字典序的优先级 然后呢，这个题可以当作linux的树状结构来说 虚拟建立一个根节点：作为一开始的树根root节点来做，避免讨论起点到底先输出哪个 剩下的细节，先贴代码再来分析吧 #include<bits/stdc++.h> using ...

题目链接：#1385 这个题比1383好理解，也好过，因为不需要那么纠结的数据结构，随便暴力搞就好（但是一个模拟有80%的AC率你信不信） 题意：找到由空格分隔的两个单词（连续的多个空格当作一个），然后对这些单词都进行计数。 需要求的是出现次数最多的<单词+一个空格+单词>的格式的词组，而且要输出出现次数 首先想到的就是：暴力模拟 枚举每一个空格（后面连续的用另外的指针选择忽略掉） 然后用一个指针往左边扫描，用一个指针往右边扫描 得到一个词组 把这个词组放到map里查询一下，乱搞一发，注意细节就好 注意：h     h h h这种的：最后答案是h h：...

题目链接：飞行员配对方案 【线性规划与网络流24题 1】飞行员配对方案 Description 第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1 名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。 对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行...