看了题解才明白了什么。来一手官方题解连接：https://ac.nowcoder.com/discuss/151522?type=101&order=0&pos=1&page=0&channel=666&source_id=discuss_tag题解：首先题目说明了肯定会有解的。这样的话我们用一个点来把所有的点给连接起来（加单向边），并且把w赋值为0。然后我们知到，如果点u->v之间有路可走，无论是dij还是spfa，每次松弛的判断是dis[v]>dis[u]+w，如果大于遍修改dis[v]；所以经过spfa后，他便不可以松弛了，也就是说di...

这题也是看了别人题解也才会做的。题解：本题用的记忆优化搜索，题目说了给的颜色可以恰好图够所有木块。题目给了能涂几块木块的颜色一共有几种。因为我们不可以连续图，所以我们把他分开来涂色。用dp[a][b][c][d][e][last]表示能涂a​表示的是能涂1个木块颜色还有a个，前一个涂得颜色是last个颜色时方案总数。表示能涂b​表示的是能涂2个木块颜色还有b个，前一个涂得颜色是last个颜色时方案总数。 既然不可以连续图，所以我们把能连续图的颜色拆分开来使用。比如说我要用一下子可以涂四个木块的颜色来涂，因为不可以连续，所以我们只让这个颜色图一个木块，那么这个颜色还可以图三个木块，所以我们让可以...

题解：把这个双重求和公式按照最简单的方法展开，可以将其n=3，4，5都展开，观察其式子规律n=5时，(a1 + a2 + a3 + a4 + a5) * w1+(a1 + 2 * a2 + 2 * a3 + 2 * a4 + a5) * w2+(a1 + 2 * a2 + 3 * a3 + 2 * a4 + a5) * w3+(a1 + 2 * a2 + 2 * a3 + 2 * a4 + a5) * w4+(a1 + a2 + a3 + a4 + a5) * w5下面为n=4的时候展开方法。展开三四项发现其规律后，就利用前缀和在O(1)的复杂度下计算出区间长度即可 /*Keep on goi...

题解：容斥原理要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回有三个集合相交的部分，再减去所有四个集合相交的部分....依此类推，一直计算到所有集合相交的部分。拿这个题举个栗子。你先计算出单个数被整除的次数加起来，你会发现比如说10这个数字，会被2 和5同时整除，所以你要再减去10的倍数。再看110这个数字，会同时被2 5 11整除，这样的话会被记录三次，因为我们减去了两两之间最小的公倍数，所以是减去了3，这样的话会导致110这个数字没有被记录上，所以我们同时再加上三三之间的倍数。。。。。以此类推。 #include <iostrea...

没看题解的时候实在是一头雾水不知从何下手题意：windy的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。现在包括windy ，一共有 N 个人来分这块大蛋糕，要求每个人必须获得相同面积的蛋糕。windy主刀，每一切只能平行于一块蛋糕 的一边（任意一边），并且必须把这块蛋糕切成两块。这样，要切成 N 块蛋糕，windy必须切 N-1 次。为了使得每块蛋糕看起来漂亮，我们要求 N块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么？ 题解：他要保证的是每块面积都要相同，所以我们在爆搜的时候只需要让他的面积保持不变即可，我们横着切和竖着切如果平...

通过这题发现了double的坑点，本来认为double表示范围可能跟long long差不了多少，在wa了n次之后发现double表示的长度是16位，而2的60次方已经到了18位的长度了，当然不对，所以这题不能图省劲直接用powhan's题解：这题就是让我们算这颗树最不平衡的时候根节点左右子数结点的差，所以我们让一颗树满结点，另一棵树是最少结点的个数即可算出，满结点的树可以一下算出结点个数，呢么怎么算那一颗不满结点的树呢？我们可以从上往下推公式dp[i]=dp[i-1]+dp[i-d-1]+1dp[i]表示深度为i的子树最少总节点个数意思就是在深度为i的结点是由左子树深度（i-1）和右子树（i...

感觉这种形式得动态规划也有很多类型，反正就是从两边取数，按照一定得规则把这个数做一个计算。题解：看这个题，他问的是一个矩阵如何取数，我们可以发现，对于每一行如何取数，题目中只是说从两边取，并没有说明行与行之间的要求，那么这个问题就可以化简一下了，我们对每行进行动态规划，分别求出每行如何取数的最大值然后加起来即可。那么对于每一行应该如何取数呢。递推的话，题目是从两边开始往内取，如果我们按照题目的要求从两边递推，似乎有点难办所以我们就倒着来，先确定了区间长度，然后这个区间可以由两边推得，那么相应的 计算方法也会变成2的（m-length+1）次方了，因为一需要先把两边的数取干净才可以。2的80次方...

700ms飘过你可能不相信 我先加了inline又加了快读。。。然后TLE->AC题意：第一行两个整数n和m，表示图的点数和边数（1≤ n≤ 100000, 1≤ m≤ n+100）。接下来m行每行两个整数a和b，表示一条边（1≤ a, b≤ n）。保证没有自环和重边。保证图连通。接下来一个整数q表示询问的个数（1≤ q≤ 100000）。接下来q行每行两个整数a和b表示询问a和b之间的最短路。题解：这不是LCA的板子题吗？等等，m<n+100，那好像不是一棵树了？？？是一张图 仔细一看你会发现，m仅比n多一百个，也就是说会如果把这一百条边给挑出来，他还是一个LCA的模板题，所以这...

参考：https://www.bilibili.com/video/BV1rt411j7Ff?t=703大佬视频 一份代码，代码中有注释，对应着洛谷的P3369 【模板】普通平衡树 /*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> const int maxn = 2e5+10; const int MaxN = 0x3f3f3f3f; const int MinN = 0xc0c0c00c; ty...

题目描述：在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来n天的借教室信息，其中第i天学校有ri个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为dj, sj, tj，表示某租借者需要从第sj天到第tj天租借教室（包括第sj天和第tj天），每天需要租借dj个教室。我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供dj个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。...

包含了二叉搜索树的插入，删除，查找，中序遍历，找最大值最小值的操作，代码中有注释。 /*Keep on going Never give up*/ //#pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> using namespace std; struct Node{ int data; Node *l,*r,*parent; }; //由大到小排序（中序遍历二叉树） void sortx(Node *rt){ if(rt==NULL)...

python读取txt文件至列表当中 首先看txt文件中内容。上代码：readlines() 方法用于读取所有行(直到结束符 EOF)并返回列表每一行的内容为列表种的一个元素 我们通过循环将内容拆分即可 msg = msg.strip('\n') 用来消除每个元素最后最后的换行字符 adm = msg.split(' ') 用来将每一行的元素按空格分开 file=open('adm.txt',mode='r',encoding='UTF-8') admin=[] contents = file.readlines() print(contents) for msg in contents:...

python将列表按行写入至.csv文件 # coding:utf-8 import csv list=[[1,2,3,4],[5,6,7,8],[89,55,66666,5],['张三','李四','王五','tom']] f = open('222.csv','w') writer = csv.writer(f) for i in list: writer.writerow(i) f.close() 效果图：我们会发现它每一行都会有间隔，如何去掉这个间隔呢？ f = open('222.csv','w',newline='') 这段代码解决了这个问题 # coding:utf-8 ...

E1 - Reading Books (easy version) 题意：一共有n本书，看完每本书都有一个花费时间，每本书上都有两个标记，小a是否喜换，小b是否喜换，小a小b是否共同喜换，他们只会阅读自己喜换的书，他们每个人至少阅读k本书，如果他俩共同喜换，那么花费阅读这一本书的时间，会使他俩已经阅读的书总是各加一，求花费最少时间阅读完成k本书的情况，如果无法完成则输出-1。题解：那么我们对每本书的情况进行分类1.小a喜换小b不喜欢。2.小b喜换小a不喜欢。3.小a小b都喜欢。4.小a小b都不喜欢。 这四种情况，可以看出第4种情况的书没有意义，我们直接丢弃即可（因为没人会去看） 那么我们先特判...