2 拔光祖国小草

尚未进行身份认证

存放一下做的题。

等级
博文 121
排名 5w+

POJ2104(主席树求区间第K大)

模板题,模板来自B站UESTCACM#include<iostream>#include<algorithm>#include<queue>#include<stack>#include<cstdio>#include<string>#include<cstring>#inclu

2018-05-31 20:02:45

BZOJ 1036 (树链剖分模板题)

#include<iostream>#include<algorithm>#include<queue>#include<stack>#include<cstdio>#include<string>#include<cstring>#include<vector&

2018-05-11 15:33:57

CodeForces - 557D Vitaly and Cycle (二分图染色判定)

题意:给定一个无向图,问最少添加多少条边可以得到一个奇圈以及其方案数。题解:是个简单的二分图染色判定1:一条边没有的时候1:一条边没有的时候1:一条边没有的时候2:每个联通分量至多只有2个点时binomn+12k2:每个联通分量至多只有2个点时binomn+12k2:每个联通分量至多只有2个点时binom{n+1}{2k}...

2018-05-10 21:04:04

codeforces 602 E. Kleofáš and the n-thlon (概率dp)

题意:有nnn个人进行了mmm场比赛,告诉你了自己的每场排名,并且一场比赛中不会有并列,问最后自己的期望排名题解:很明显期望dpdpdp,dp[i][j]表示进行了i场比赛得分为j的期望人数dp[i][j]表示进行了i场比赛得分为j的期望人数dp[i][j]表示进行了i场比赛得分为j的期望人数那么转移就是dp[i][j]=(∑j−1k=j−mdp[i][k]−dp[i][j−a[i]])/(m...

2018-05-03 07:45:08

codeforces 595E(思维暴力)

题意:给你平面上n个点,删除小于等于k(k<=10)个点使得能用一个最小的平行于坐标系的矩阵覆盖所有点题解:显然,一定是删除“最外面”的点是最优的。那么对所有点分别以x、y排序,枚举上下左右边界,判断最小面积。这个思路第一次见,很神奇#include<iostream>#include<algorithm>#include<...

2018-05-02 23:28:33

codeforces 571A(组合+容斥)

题意:给定三根木棍的长度,可以任意木棍增加任意长度,但总和不超过L,问最后能构成三角形的方案数是多少题解:用所有方案数-不能构成的方案数对于长度l,能够构成的方案数是(l+22)(l+22){l+2\choose2},因为相当于一个长度为lll的线段分成三份,并且可以同时去两个000。不能构成的方案数则是,枚举a、b、ca、b、ca、b、c当做最长的线段,然后对其增加i(0<...

2018-05-01 23:25:03

codeforces 610D(树状数组+离散化)

题意:给你n条只平行于x轴或者y轴的线段,问有多少个整数点在线段上。题解:正好前几天碰到一个几乎一模一样的题,实际上只要处理有多少个交点,将平行于x轴的退化为一个点,将横竖所有y坐标离散,对于平行于x轴的点左端点进行+1,右端点-1的操作,垂直于y轴的便进行区间查询,(其实相当于从无线远向右扫),那么就是树状数组维护一下坑就是这题还要处理重叠和相交的线段,心累补:后来看网上题解才发...

2018-04-27 23:24:33

Codeforces 660E (dp || 组合数学)

dp[i][j]dp[i][j]dp[i][j]表示长度为iii,以字符jjj结尾的答案是多少对于普通的来说,一个经典的转移方程dp[i][j]=∑mk=0(dp[i−1][k]∗2−dp[pre[j]−1][k])dp[i][j]=∑k=0m(dp[i−1][k]∗2−dp[pre[j]−1][k])dp[i][j]=\sum_{k=0}^m(dp[i-1][k]*2-dp[pre[j]...

2018-04-19 21:50:31

codeforces 645E (贪心+dp)

对于求子串个数明显是用dp,对于每添加一个字符ch,必然是多2*dp[i-1]个串,那必然还有重复的串,就是之前ch出现位置的串,需要减去。对于添加字母,贪心的加上之前出现位置最小的字母。#include<iostream>#include<algorithm>#include<queue>#include<stack>#...

2018-04-18 22:55:40

codeforces 632E (完全背包)

题意:给你n个物品的重量,问取k个能获得多少种不同的重量感觉是一个dp的套路,乍一看像是个多重背包,但是没法同时维护多个值,所以将所有重量减去最轻的,那么最轻的就变成0了,转而变成一个完全背包dp[i]表示重量为i的情况下所需要的最小个数,如果该个数小于k的话,就可以用最轻的那个补上#include<iostream>#include<algorit...

2018-04-17 00:21:18

FZU 2277 (dfs序+线段树)

用dfs序可以维护出所有子节点对于更新,我们将更新变为deep[i]k−deep[j]kdeep[i]k−deep[j]kdeep[i]k-deep[j]k,deep[j]kdeep[j]kdeep[j]k就是当前自己的深度,是可以直接计算的,那么对于deep[i]kdeep[i]kdeep[i]k,就是父亲节点的深度,另外别忘了还有xxx,所以我们对于父亲节点的所有儿子首先更新x+dee...

2018-04-13 09:39:50

Gym - 101128A(dfs)

当成拓扑写了,少了很多情况维护一下当前这个人控制的人数=x,和选这个人需要选的人=y,那么对于某个人必选,就是这个人不选(控制的人也就不能选了),剩下的人不足a(b),就必选n-x<a(b)对于某个人不可能选中,就是选这个人需要的人y>b#include<iostream>#include<algorithm&g...

2018-04-11 23:04:20

Gym - 101128J (凸包+二分)

题意:问有多少个黑点在任意三个红点组成的三角形内题解:必然一眼能看出是求点在红色点组成的凸包内吧。然后暴力枚举黑点与凸包判叉积的话会T,所以有一个优化是,将凸包分成x个三角形(固定一个起点,枚举任意两个相邻的点),然后进行二分,找到一个叉积>=0一个<=0的时候,再判断是否在第三条边左侧就ok了(因为在凸包外也有满足叉积>=0&&叉积<=0的情况)...

2018-04-11 17:40:28

ZOJ 2688 (最远曼哈顿距离)

将绝对值拆开,无非是32种情况,对于x1,x2,x3,x4,x5如果取值为10011的话,那么y1,y2,y3,y4,y5的取值必然是01100,那么只要保存每个状态的最大值,最后求其互补状态的最大值就行了#include<iostream>#include<algorithm>#include<queue>#include<st...

2018-04-03 21:43:11

UVA 11261(递推+找规律)

题意:一个n*n的棋盘中放置m个点,每个点会占用所在的两条斜对角线,问最后有多少个格子没有被占用题解:按从左上往右下(id=n+x-y)对角线pos,从右上往左下(id=x+y-1)对角线neg分成两部分,dp[i]表示第i条neg对角线没有被占用的格子数,然后根据pos找规律递推neg没有被占用的格子,最后判断neg上有没有被占用进行累加#include<iost...

2018-03-28 22:47:38

POJ3761 (组合数学)

组合数学真难啊。。预备知识需要的太多了东拼西凑来学习证明网上很多,我也是这么学来的#include<iostream>#include<algorithm>#include<queue>#include<stack>#include<cstdio>#include<string>#inc...

2018-03-27 19:04:07

UVA10617 (区间dp)

题意:一个串删除一些字母使得剩下的串是回文串,问有多少种方法题解:直觉就是区间dp吧,状态也肯定是dp[i][j]表示i−j有多少个回文串dp[i][j]表示i−j有多少个回文串dp[i][j]表示i-j有多少个回文串状态转移真的不好想啊==**枚举删除s[i]和s[j]dp[i][j]=dp[i+1][j]+dp[i][j−1]−dp[i+1][j−1]dp[i][j]...

2018-03-26 23:33:33

UVA1151 (MST + 剪枝)

主要是剪枝不好想吧先跑一遍原图的MST,那么二进制枚举所有的套餐,相当于加进去一些长度为0的边,那么之前原图跑出选中的边就相当于往后挪了,(克鲁斯卡尔按边权值排序)那么再选n-1条边的时候一定不会选到之前没选到的边(大大剪枝了)那么久一定是在原图MST中的n-1条边选(再怎么样选这n-1条边也能得出一个MST)#include<iostream>#include&...

2018-03-26 21:15:45

HDU 6034(模拟)

给出n个只包含小写字母的串,分别给其中出现的字母赋值,以26进制赋值(1-25),不同字母只能是不同的值,且不能出现前导0,问所有串所能获得最大权值和一个O(26*1e6)的复杂度,按位算贡献,把低位的进到高位,然后按高位排序,出现前导零就与他前面一个字母交换权值(死于前导0去除单个串的情况)#include<iostream>#include<al...

2018-03-26 14:28:53

UVA1153 (贪心+优先队列)

给出n个任务的执行时间qiqiq_i,截止时间didid_i,在互不交叉的情况下最多能完成几个任务题解:想复杂了,题目中暗示按d排序,优先队列每次抛出完成时间最长的就可以了(我当时想着万一抛出两个怎么办,后来想如果队列中较大的q都可以放进去,并且现在的q还小,那么此时的q一定只会使队列中抛出一个就可以放进去了,太弱智了自己)#include<cstdio>#includ...

2018-03-26 11:33:31
奖章
    暂无奖章