首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
CToshi
获赞
15
粉丝
1
关注
1
看过 TA
0
男
华南农业大学
2020
IP属地:未知
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑CToshi吗?
发布(5)
刷题
CToshi
2018-08-17 20:49
华南农业大学
多校⑨ Prefix Sum 分块暴力
题意略 思路:先来一种暴力的,每次修改后O(n*k)维护整个矩阵,查询O(1),考虑对操作分块,当查询数达到blocksize时,才维护整个矩阵,否则不更新,此时需要考虑的问题是:没有维护到矩阵的修改对查询有什么影响? 问题转化:设矩阵为v,矩阵的值的计算方式是v[i][j] = v[i-1][j] + v[i][j-1],每一个格的值都是左边的值加上上面的值,换一个方式,我们让v[i+1][j] += v[i][j],v[i][j+1] += v[i][j],让一个格子的值自己加到右边和下边的格子上,则对于第一行的格子v[0][i],它对第k行的格子v[k][j]都有一个贡献,贡...
0
点赞
评论
收藏
转发
CToshi
2018-08-03 13:10
已编辑
华南农业大学
多校(五)D-inv 线段树区间加值
题意:给一个偶数序列和一个固定的奇数序列[1、3、5...n-1],要求归并两个序列使得最终序列逆序对数最少 思路:考虑偶数序列不动,用奇数去插入,假设奇数i已经插入到最优位置k,考虑i+2的最优位置,假设已经算出i在每个插入位置的贡献,转移到i+2的话,只有i+1会产生影响,此时有两种情况 1)i+1位置在k左边,此时i+1对i+2不产生贡献,k依旧是最优位置 2)i+1位置在k右边,此时i+1对i+2产生了贡献,而最优位置只可能在右边 所以,每个奇数的最优位置已经满足从左到右的排列,那只需要计算每个奇数的最优位置的贡献相加即可(当然偶数序列内部的逆序对也要算)。 ...
0
点赞
评论
收藏
转发
CToshi
2018-07-23 11:01
已编辑
华南农业大学
多校训练营(第二场)B 基环树dp
本题解是在官方题解基础上写些自己的理解。题意略 大致思路:对于每个i和f[i],将其视为一条边f[i] -> i,则有n个点n条边,是多个基环树(一棵树加任意一条边则形成基环树),思路是断环为链 子问题:考虑少一条边时,即树的情况怎么做。 本来n条边时,每个点都有入边,少一条边后,设没有入边的点为root,即少了 f[root] -> root边。此问题用树dp即可 状态定义:设dp[u][way]表示u点及其孩子的总的最小费用,且u点必须使用way的方式购买,way为0,1,2分别表示,免费、第一种优惠和第二种优惠 如何转移:way为1或2时,u与其...
0
点赞
评论
收藏
转发
CToshi
2018-07-21 11:09
已编辑
华南农业大学
多校(第一场)E-Removal
这题挺多人已经补了,还是说下我对官方题解做法的理解 状态定义:dp[i][j]表示从前i个数字中删去j个数字且以s[i]结尾的不同序列个数 转移的思路:在dp[i][j]状态,考虑增加一个数字c,假设i位置后面的原序列是这样,xxxc1yyyyc2,其中x、y是任意是非c的数字,如果这个c是c1,那要删除xxx,如果这个c是c2,那要删除xxxc1yyyy,由于加哪个c结果都一样,为了不算重复,只算i位置后的第一个c 转移:设next(i, c)表示位置 i 后第一个字符 c 的位置,枚举下一个字符c,从dp[i][j]转移到dp[ next(i, c) ] [ j + n...
0
点赞
评论
收藏
转发
CToshi
2018-07-24 12:16
已编辑
华南农业大学
I substring题解
虽然已经有官方题解,这个算是个稍微详细那么一点的题解吧 题意: 给出一个串S,问最多可以选出多少个子串使得选出的子串两两不同构,同构的定义是,两个字符串A和B,通过一个映射函数f,让B的每个字符c通过映射函数c = f(c)后得到B',如果A == B',则A,B同构。例如ab和bc同构,映射函数是f(a) = b,f(b) = c,f(c) = a 思路:这题其实就是算S有多少个不同构的子串。先看个小例子,aab、bbc、aac,怎么算这3个串中有多少个不同构的串?这题字符只有abc三种,则映射函数只有3! = 6种(即将abc做全排列 后与abc一一对应即可得到映射函...
0
点赞
评论
收藏
转发
1
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务