scmmm's blog

暂时没有归类。 凸包 一道模板题 首先凸包的定义: 用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边形，它能包含点集中所有的点。 （百度百科给的解释） 因此以下就可以算是一个凸包 求法有两个 求法 1 第一个是把凸包分为上下两部分，对于下半部分不难发现斜率是在递增的，因此考虑先给所有点按照从左到右从下到上排序，然后类似于单调栈维护一个斜率。 然后伪代码大概就长这样 12345for(i=1;i<=n;i++){ s[++size]=p[i]; while(size>=3&&getk(s[size-2],s[size])<getk(s[size-2],s[size-1])) s[size-1]=s[size],size--;} getk(node  a,node  b)getk(node~~a,node~~b)getk(node  a,node  b) 是求AB所在直线斜率，特别注意A,B相等的时候返回一个极大值。 对于上半部分凸包，只需要从右向左枚举即可。 求法2 上面的求法不需要高中数学功底因 ...

这是一个91分的非dp代码（是我太弱） 剪枝八五个（实际上根本没那么多，主要是上课装逼，没想到他们dp水过去了），不过我的思路与dp不同； 1.层数到达i+1,return 这个必须有 2.当前剩余生命吃不到垃圾，return，必须有 3.当前答案比目前最优解大，return 4.到达第i个点，剩余相同的生命，但是比以前走的短，return 5.到达第t时间，剩余相同生命，同上return 6.增加一个上限阀值，这样目前的解很接近最正确答案（但是第二和5个数据点貌似专门在卡这个（是我太弱） 7.做两次dfs，第一次先贪存货时间久，第二次贪升高（玄学的是如果调换就会只有45） 8.烧香 尤其要注意的是，这道题并没有保证输入数据按从小到大来，因此你还需要对输入的数据排遍序！ 代码一： 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182 ...

看起来我做的和其他题解不一样 那就发一篇吧 首先本题情况看似无厘头，但是仔细观察，不难发现： 我们可以假设第一种情况，接着可以推出第二种 然后有了两个已知的后，第三个显而易见 如果你要问我怎么推出来的吗，我在里面说的的逻辑判断已经很明白了 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include<iostream>#include<cstdio>#include<cmath>#include<cstring>using namespace std;int boom[10086];int ans;int tj[10086];int looker[10086];int n;int pdf() //这段代码是用当前推完的雷局反推右边的数字，如果数字不一样就说明这个雷局不是答案。（因为我们第一颗棋子是假设的） ...

看了下SPFA题解，一个一个太麻烦了，另一个写的很不清楚，而且注释都变成了"???"不知道怎么过的，于是自己来一发SPFA算法。 Part 1.题意 MMM个仓库，卖给NNN个商店，两个问，第一问求运价最小值，第二问最大值。 显然是一个最小费用最大流(MCMF)。 Part 2.思路 1.连让每个仓库连接一个超级源点SSS，费用(dis)为0，流量为仓库的流量，表示每个仓库最多可以运出多少货物。 2.让每一个仓库连接每一家商店，边权为cost[i][j]cost[i][j]cost[i][j]，其中，i为仓库编号，j为商店编号编号，流量为need[j]need[j]need[j]，其实流量可以取得范围是[need[j]...INF][need[j]...INF][need[j]...INF] ，另外如果出现need[j]need[j]need[j]<这个仓库货物量的情况也可以不怕(这时候取值的下限变成min(hw[i],need[j])min(hw[i],need[j])min(hw[i],need[j])) hw指的是这家仓库的货物，还有注意编号的范围（我默 ...

这道题if写的太多，考察也比较多 首先这道题常数比较大，其次有争议的年份(3200，6400,9600）也没毒瘤 这个题比赛交的有TLE，然后优化了几个地方，TLE→AC 因为本人交的是爆搜，其实这道题完全可以打表打出存在的月份，然后直接这样，就好了，本人比赛比较懒，打了个素数表 因为这个素数表，常数优化（1万→1229）因此过了第九个点 可能你们认为打表不好，其实打一部分与题目有关的表后，对问题解决就简单多了 另外还有个优化，先判断这日是不是质数，然后月+日……看似微不足道然后本人过了低8和10个点 另外本人用的是dfs，这样按位来计算比较方便 还有就是有关日期存在的极为复杂的判断，我在dfs里面说一下吧 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100 ...

咦，怎么没有STL_Stack的题解？ 解释：玄学RE 因为手工模拟栈的过程中，即使栈内元素个数为0，也会有 s[top]==0s[top] == 0s[top]==0 这种情况存在，因此不会继续满足s的顶元素比插入的元素大 而在STL的情况下，由于元素个数为0，因此访问s.top()s.top()s.top()是非法的，解决的方法很简单，只要最开始在栈首插入一个小于等于0的元素就可以解决了。 不得不说印度女工真的办不好事，我第一次谢了10行头文件都被撤回了 1234567891011121314151617181920212223242526272829#include<cstdio>#include<stack>using namespace std;int ans,n;stack <int> s;int main(){ int i,j; scanf("%d",&n); int t1,t2; s.push(-100); scanf("%d %d",&t ...

这道题比 CF10D 更难 CF10D 是可以O(n3)O(n^3)O(n3) dp过的，但是这个只能O(n2)O(n^2)O(n2) n^3的思路是，设置f[i][j]f[i][j]f[i][j]表示 A[i]A[i]A[i] 与 B[j]B[j]B[j] 的最长LCIS，当A[i]==B[j]A[i]==B[j]A[i]==B[j]时，判断F[i−1][k(k−>(0,j−1))]F[i-1][k(k ->(0,j-1))]F[i−1][k(k−>(0,j−1))]的最大值。 因此我们得到以下方程。 12345678910for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(a[i]==b[j]) { for(k=0;k<j;k++) if(a[i]>b[k]&&f[i][j]<f[i-1][k]+1) f[i][j]=f[i-1][k]+1; } else f[i][j]=f[i-1][j]; } 但是这个复杂度太大了，甚至连T ...

这道题很适合作为P1629的加强版 因为这道题其实体现了反向建图的高效性 反向建图后： 单终点最短路径→单源最短路径。 因此两边Dij，然后再累计和即可 代码部分不难弄。直接上 先说明以下程序，有1的变量名与第一次dij有关（学生出来） 带2的与第二次dij有关（学生回家） 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114#include<iostream>#include<cmath>#include<cstdio>#include<queue>#include<cstring>using namespace s ...

看了下题解，发现说的tarjan+dagdp…… 然后翻到第三页才发现一个dagdp 然后呢，感觉讲的不是很清楚，而且压行，用了好多玄学操 作。。 关键是还没有注释，于是果断自己来一发 喜欢我的博客就来康康 另外关于后效性的讨论： 首先这个图不存在环了，如果存在环的话，该点入队次数必然高于该点入度，这个拿来用就好了 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129#include<iostream>#include<cstdio>#include<cmat ...

原来的题解误导了好多人。 hack数据有一个就是专门针对原来的题解的。 原来题解有两个地方： 12341 if(q[j].r<=r && q[j].r>=l)2 if (a[j].y>a[i].y)r=min(r,a[j].y); else l=max(l,a[j].y); 乍一看是没什么问题 但是 比如这么一组数据 6 4 4 1 2 4 1 4 3 2 1 画图后大概是这个样子 然后进行模拟，发现有了if输出9 然而实际最大的矩形面积是10 就像这张图，(4,3)这个点就被漏了，所以输出了9 因此只需要把这个错误的剪枝删去即可。 这种问题第一篇题解就有。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include<头文件自己想>using namespace std;int n,m,s;struct que{ ...