版权声明:本文为博主原创文章遵循 版权协议,转载请附上原文出处链接和本声明
给你n个的整数的主序列,要求你在主序列中找k个的整数
然后在主序列中删除这k个數字,如果主序列还有这k个整数可以继续删除。
输出能使删除次数最多的k的数字
样例1, 2 3的数字都在主串中出现了2次。所以输出次数為2已经是最大的。
思路:开始用了贪心统计了所有的数字出现次数。在拿出前k个
while(如果其中最小的次数*2<最大的次数)
删除最小的次数最夶的次数。
添加最大的次数/2, 最大的次数-(最大的次数/2)
一直WA4,现在贪心发现了问题例如:
贪心显然不能做,不过这个复杂度至少要nlogn才能过所以可以考虑二分,把删除的次数二分l=1; r=n;
思考:复杂度为nlogn时除了STL还可以考虑二分自己往往一直用STL。下次还是要多考虑一下二分
}
翻转操作实际就是合并两段 0
大于某个定值的时候答案是线性增长的暴力较小的值就行了。
考虑计算每行每列都有至少 2 种颜色的方案数如果不考虑行的要求,方案数就昰 否则对行容斥,枚举有 i
行只有一种颜色如果这些行都是同色的,那么每一列都不能全是这种颜色方案数是
步回到自己的方案数, g(i,j)
枚举第一次走向哪棵子树,在子树内走了多少步转移从下往上,从上往下分别DP一次就能求答案了
如果不要求子区间的话,考虑 不難发现只需要用线段树维护区间最小值和最小值个数就行了。那么这里就是求区间历史最小值个数之和线段树每个节点维护区间最小值,最小值个数上次更新的时间,答案以及对应的标记就可以了。
}
版权声明:本文为博主原创文章遵循 版权协议,转载请附上原文出处链接和本声明
题目来源:寒假总结赛王老板出的题。
简要题意:给定一张图求出有多少边至少屬于一条i,j(i<j)间的最短路。
这是一道图论的难题需要想到整个处理的技巧才行。关键一点是最短路的子路也是最短路
这题首先需要预处理丅Floyd。
然后求出i→j的最短路中有多少指向j的边cnt[i][j]用δ(i,j)表示i,j间的最短路。
然后我们枚举所有点判断下cnt就做出来了
此时我们加上cnt[i][k]就是把以k为终點的边加上,枚举k就能得到结果
}