题目链接：https://ac.nowcoder.com/acm/problem/17376 题目大意：给你n个点。问算法存在至少有M个点在一条直线上。M/N>=x。 X为只有一位小数的实数。 思路：我们假设存在。那么M>=0.1n。 每次选择两个点至少有0.01的可能性选择到。当然这是最坏复杂度。我们随机找200次如果还不能找到就No。 #include <bits/stdc++.h> #define LL long long using namespace std; double x[10005], y[10005]; int check(int kx, i...

题目链接：http://poj.org/problem?id=3318 题目大意：多样例。给你3个n * n的矩阵A， B，C。问A*B=C是否成立。成立输出YES。不成立输出NO。并且题目提示O(N ^ 3)复杂度会T。 暴力肯定是O(N^3)。我们可以随机化一个N * 1的矩阵D。 如果A * B=C。那么A * B * D=C * D 并且B * D的复杂度为O(N ^ 2)得到一个N1的矩阵再和A相乘也是O(N ^ 2)。 CD的复杂度为O(N ^ 2)。现在得到左右两个结果矩阵，判断是否相等就可以了。 #include <math.h> #include <ve...

题目链接：https://codeforces.ml/contest/1313/problem/C2 题目大意： 有n栋房子。每个房子的最高的高度b[i]应该在[1, a[i]]区间里。现在要满足不存在i<j<k有a[i]>a[j]<a[k]。并且要b[i]的和最大。输出b[i]-b[n]。方案可能不唯一。随便输出一个就可以。 思路：我们可以知道b[i]数组是一个单峰函数。并且最高的b[i]一定等于a[i]。 <mstyle displaystyle=&quot...

题目链接：https://ac.nowcoder.com/acm/contest/4462/H 题目大意： 思路：我们可以把每个仓库当作一个时间点。把操作颜色离线保存。 那 么 对 于 一 个 操...

题目链接：https://www.luogu.com.cn/problem/P1020 题目大意： Dilworth定理:偏序集能划分成的最少的全序集个数等于最大反链的元素个数。 <mstyle displaystyle="false" scriptlevel="0"> 例 如 ...

题目链接：https://codeforces.ml/contest/1307/problem/D 题目大意： 有一个无向图n个点m条边，其中有k个特殊点。现在让你在两个特殊点之间连一条边。让1到n的最短路最大， 并且输出这个最短路的大小。 <mstyle displaystyle="false" scriptlevel="0"> d ...

题目链接：https://ac.nowcoder.com/acm/contest/3007/E 题目大意： 我们要求最大的A。 我们根据唯一分解定理： N = e 1 p 1 ...

题目链接：https://ac.nowcoder.com/acm/contest/3004/J 题目大意： 我们可以很容易得到一个K^2的算法。因为每个时间都不同。那么按时间排序。就是一个LIS。如果满足(j->i)时间差>=dis(i, j)那么就可以转移。 f [ i ] : ...

题目链接：https://codeforces.ml/contest/1304/problem/E 题目大意：给你一棵树。m次询问。每次询问输入x, y, a, b, k，添加一条x-y的边。问a到b的路径有没有经过k条边的。路径可以重复多次经过多条边和多个点。询问独立（加边仅作用于本次询问）。 思路：我们考虑没有加边的时候。如果k>=dis(x, y)并且k%2==dis(x,y)那么就是可行的。当添加了a-b。可能增加了一条简单路径：dis(x, a)+dis(b, y)+1或者dis(x, b)+dis(a, y)+1。我们判断就可以了。用倍增LCA。计算路径长度。 #inc...

题目链接：http://codeforces.com/contest/730/problem/J 题目大意： 有n个瓶子。每个瓶子有饮料a[i]。瓶子的体积为b[i]。现在想把所有的饮料倒在k个瓶子里。而且每倒一升的饮料。需要花费时间1。现在希望k最小的情况下并且花费的总时间t最少。 思路：我们可以直接求k。因为要优先满足k。那么就是： s o r t ...

题目链接：http://codeforces.com/contest/687/problem/C 题目大意： #include <bits/stdc++.h> #define LL long long using namespace std; int c[505]; int f[1500][1500]; int main() { int n, m; scanf("%d%d", &n, &m); for(int i=1; i<=n; i++){ scanf("%d", &c[i]...

题目链接：http://codeforces.com/contest/1303/problem/E 题目大意： 给你一个字符串S和一个字符串T。问能不能在S中找到一个子序列S1，然后从S中删除S1.再去删除后的字符串T中再找一个子序列S2。然后用S1+S2拼接成T。 思路：我们枚举T的分割点。进行dp。dp[i][j]：表示前i个字符和t1匹配到第j个字符时。能和t2匹配的最大长度。如果dp[|s|][|t1|]==|t2|就可行。注意t1和t2可能一个为空。特判就可以了。 #include <bits/stdc++.h> #define LL long long using ...

题目链接：https://ac.nowcoder.com/acm/contest/3005/I 题目大意： 题解： #include <bits/stdc++.h> using namespace std; struct node{ int x, y, z; }a[100005]; int cmp(node &a, node &b){ return a.x<b.x; } multiset<int> st; int main(){ int n, x, y, z, ans=0; scanf("%d...

题目链接：https://ac.nowcoder.com/acm/contest/3005/G 题目大意： 思路： 每个人的分数为： a [ i ] ∗ ( 1 ...