1 Eve_Miracle*

尚未进行身份认证

哈哈哈吼吼吼吼

等级
TA的排名 2w+

提升vector性能的几种方法 & 线性求容器中第k小

提升 vectorvectorvector 性能的几种方法:提前分配空间向 vectorvectorvector 插入元素时使用 emplace_back()emplace\_back()emplace_back() 而非 push_back()push\_back()push_back()在填充或者拷贝 vectorvectorvector 的时候,使用赋值,而非 insert()ins...

2020-04-06 15:35:30

【带权并查集 He 种类并查集 详详详详详详详hhh】经典例题

POJ 1182 食物链 之 两种解法 de 详解:带权并查集、种类并查集。真详解,窝窝窝,窝不骗人!要记得当初横冲直撞的那个一步步追寻的我~ 博文完结撒花撒花撒花~~~~

2020-04-04 19:02:54

U41492 树上数颜色【dsu on tree】

题目链接题意:有一棵以 111 为根结点的树,树上每个结点有一个颜色,多组询问:问以 uuu 为根的子树上共有多少种不同的颜色。解决该题,最暴力的做法就是对于每一棵子树都dfs一遍统计出答案,统计完清空:O(n2)O(n^2)O(n2)。但“听说”可以用dsu on tree优化:dsu on tree [ O(nlogn)O(nlogn)O(nlogn) ]统计以结点 uuu 为根结点...

2020-04-04 14:45:52

Codeforces Round #630 (Div. 2)

A. Exercising Walk题意:小猫初始位置在(x,y)(x,y)(x,y),要求小猫左右下上各走a、b、c、da、b、c、da、b、c、d步。限制小猫咪必须在左下角为(x1,y1)(x_1, y_1)(x1​,y1​) 右上角为(x2,y2)(x_2, y_2)(x2​,y2​) 的区域内。问小猫咪是否能够完成任务?思路:首先应该判断小猫咪是否可以移动:左右任意一个方向要...

2020-04-01 17:04:51

操作集锦

题目链接题意:长度为 nnn 的字符串中有多少个长度为 kkk 并且不同的子序列。定义 dp[i][j]dp[i][j]dp[i][j] 表示截至 s[i−1]s[i-1]s[i−1] 为止,长度为 jjj 的子序列的个数dp[i][j]=dp[i−1][j]+dp[i−1][j−1]dp[i][j]=dp[i-1][j]+dp[i-1][j-1]dp[i][j]=dp[i−1][j...

2020-03-31 20:49:09

拉普兰德的愿望【切比雪夫距离+树状数组】

题目链接题意:给出n个点的坐标,求曼哈顿距离不小于d的点对数。我们将坐标①(x,y)(x,y)(x,y)变换为②(x+y,x−y)(x + y, x - y)(x+y,x−y),那么①的曼哈顿距离等于②的切比雪夫距离。切比雪夫距离dis=max(x2−x1,y2−y1)dis=max(x_2-x_1, y_2-y_1)dis=max(x2​−x1​,y2​−y1​)那么对于点 iii 来...

2020-03-30 23:01:16

P3964 [TJOI2013]松鼠聚会【切比雪夫距离】

P3964 [TJOI2013]松鼠聚会题意:给出nnn个点(xi,yi)(x_i,y_i)(xi​,yi​),找到某个点,使得所有点到该点的切比雪夫距离和最小。一、A(x1,y1),B(x2,y2)A(x_1, y_1), B(x_2, y_2)A(x1​,y1​),B(x2​,y2​)三种距离:①欧几里得距离:(x2−x1)2+(y2−y1)2\sqrt{(x_2-x_1)^2 ...

2020-03-30 20:14:30

求解逆序数

两行代码vector求逆序数(冒泡)冒泡排序是保证前面冒完的泡泡是有序的~,所以说,我们可以直接利用这一点,二分找到要插入的数值应该在哪个位置,那么原位置减去当前应该在的位置就是它的逆序数#include <iostream>#include <algorithm>#include <cstdio>#include <vector>usi...

2020-03-27 22:34:27

计算1至n中数字x出现的次数

题目:计算1至n中数字x出现的次数直接炒栗子!如果x=[1,9]2059 5个位:205个10,205∗1+1205*1+1205∗1+1:[1,2050)+[2050, 2059] 个位9>5十位:20个100,20∗10+(9+1)20*10+(9+1)20∗10+(9+1):[1,2000)+[2000,2059] 十位5=5百位:2个1000,2∗1002*1002∗10...

2020-03-27 16:08:41

记录一些CF-DP题(qwq)

CodeForces 1195C Basketball Exercise题意:有两排小哥哥,每排都有nnn个小哥哥。我们要从这2n2n2n个小哥哥里选择任意个,使得这些小哥哥的身高总和最大(花痴脸). 限制我们选择的小哥哥不能是一排中相邻的两个。思路:定义dp[ ][3]dp[ \ ][3]dp[ ][3]其中dp[pos][0]dp[pos][0]dp[pos][0]表...

2020-03-26 22:07:47

CodeForces 1326D2【Manacher】

Prefix-Suffix Palindrome (Hard version)题意:给定一个串sss,找出一个回文串ttt,使得ttt = s.prefixs.prefixs.prefix + s.suffixs.suffixs.suffix,并且ttt的长度不大于sss.思路:ManacherManacherManacher算法中radius[i]radius[ i ]radius...

2020-03-20 14:51:59

CodeForces 1326D2【前缀数组next[ ]】

Prefix-Suffix Palindrome (Hard version)题意:给定一个串sss,找出一个回文串ttt,使得ttt = s.prefixs.prefixs.prefix + s.suffixs.suffixs.suffix,并且ttt的长度不大于sss.思路:我们找到最大的ppp,使得s[0]=s[len−1],s[1]=s[len−2],...,s[p]=s[l...

2020-03-20 13:59:11

C++_内联函数 带默认形参值的函数 重载函数 constexpr 取整 点灯

/*NO.1 内联函数(1)内联函数是在“编译时”将函数体嵌入在每一个调用处,相当于宏定义define(2)inline关键字只是表示一个要求,编译器并不承诺将inline修饰的函数作为内联(3)在现代编译器中,没有用inline修饰的函数也可能被编译为内联(4)内联函数应该是比较简单的函数,结构简单,语句少,频繁调用(5)带有递归调用或者循环的函数不能以内联方式处理*//*...

2020-03-16 21:20:53

HDU - 4292【最大流_拆点_建图】

Food题意:有nnn个人,有fff种食物,ddd种饮料,问能拿到自己钟意的食物和饮料的人最多有多少?思路s−food−people1−people2−drink−ts - food - people1 - people2 - drink - ts−food−people1−people2−drink−t【people1people1people1和people2people2pe...

2020-03-12 18:49:34

CodeForces - 1312E - Array Shrinking【dp+栈】

题意相邻的两个相等的数x可以合并为x+1,问可以通过合并操作得到的数列最小长度?思路我们用dp[r]dp[r]dp[r]表示数列[1,r][1, r][1,r]的最小长度。显然如果数列[l,r][l, r][l,r]的元素可以合并为一个数,也就是数列 [l,r][l,r][l,r] 的长度为111,那么我们可以得到dpdpdp方程:dp[r]=min(dp[r],dp[l−1]+1)...

2020-03-10 12:46:11

CodeForces - 1312D - Count the Arrays【组合数学】

题意:从mmm个数中选出n−1n-1n−1个数,构造出一个有一个峰值,峰值左严格递增,峰值右严格递减的数列。思路从mmm个数中选出n−1n-1n−1个数: C(m,n−1)C(m, n-1)C(m,n−1)最大的数作为峰值,毫无疑问从剩下的n−2n-2n−2个数中选择一个作为峰值左右相同的数:n−2n-2n−2现在还剩n−3n-3n−3个数,怎么处理嘞?这n−3n-3n−3个数...

2020-03-10 10:18:17

HDU 6598 Harmonious Army【最小割_网络流建图】

题目链接题意:n个士兵,m组信息:u v a b c。对于士兵u v:如果都是战士(Warrior),那么军队power增加a;如果都是法师(Mage),那么军队power增加c;如果一个是战士,一个是法师,那么军队power增加b. 其中b=a/4+c/3b = a/4+c/3b=a/4+c/3. 问军队power最大是多少?思路如果每个士兵可以选择两个职位,那么军队power=...

2020-03-09 20:37:39

HDU - 6579 Operation【线性基】

题目链接这道题和CodeForces−1100F−IvanandBurgersCodeForces - 1100F - Ivan and BurgersCodeForces−1100F−IvanandBurgers这道题是一样的,唯一的区别就是这道题强制在线。还有啊TAT,题目说的是mod n+1mod\ n + 1mod n+1不是mod (n+1)mod\...

2020-03-08 16:42:24

CodeForces - 1100F - Ivan and Burgers【前缀_线性基】

CodeForces - 1100F - Ivan and Burgers题意给定一个长度为n的数列. 然后有q次查询,查询[L, R]区间中的某个子集异或和最大。思路我们定义p[r][i]p[r][i]p[r][i]为[1,r][1, r][1,r]的线性基,并且这个线性基区别于平常从左往右插入,这个是从右往左插。于是我们查询[L,R][L, R][L,R]某些向量异或和最大时...

2020-03-08 16:11:10

[CodeForces-1323B] - Count Subrectangles

[CodeForces-1323B] - Count Subrectangles题意:给定两个只包含01的数列a[ ], b[ ],我们可以得到一个矩阵c[i][j] = a[i] * b[j]. 我们需要找到矩阵c中,面积为k的子矩阵个数。思路:可以肯定的是a数组连续1和b数组连续1才有可能构成合法矩阵。问题是我们如何得到所有合法矩阵的个数,也就是如何遍历呢?长度为n的数组a,...

2020-03-08 13:08:11

查看更多

勋章 我的勋章
  • 签到达人
    签到达人
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 技术圈认证
    技术圈认证
    用户完成年度认证,即可获得
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。