2 岛屿失梦°

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 15w+

HDU 6796 X Number

HDU 6796 X Numberinput31 10 11 11 11 100 0output121数位DP+组合数学题意:找到[l,r]符合条件[=d]的数字。[=d]定义为:当前数字中d出现的次数严格最大。e.g.111223为[*=1],112233为啥也不是思路:典型的数位dp虽然想到了,,,但没想到组合数学数位dp:dp[][][]三个维度分别表示当前还剩pos位,题意中的d,和一个长度为10的数组表示pos之前出现的每个数字的次数,这题不仅需要考虑limit还需

2020-07-31 00:31:01

牛客竞赛-NC13230

区间DP思路:区间DP思路:如果我们用f[i][j][k][l]表示前一个串(a串)的第 i 个字符到第 j 个字符后一个串(b串)的第 k 个字符到第 l 个字符能否组成一个回文串的话,有四种可能,四种当中任意一种为真f[i][j][k][l]就是真。往 a[i+1] 到 a[j−1] 和 b[k] 到 b[l] 构成的串的两端加上 a[i] 和 a[j] 两个字符:f[i][j][k][l] |= (f[i+1][j-1][k][l] & (a[i] == a[j]));往 a[

2020-07-09 22:56:32

牛客竞赛-NC50439

牛客竞赛-NC50439 每日一题3.25思路:如果没有每个士兵的人数限制,显而易见的我们会直接按照武力值大小排序,但是每个士兵对人数的加以了限制,如果我们还是按武力值大小加人的话,每次加人和删掉人都会导致队伍能容纳的人数的变化,而且还是跳跃的变化(完全有可能忽大忽小),更关键的是我们并不知道人数限制不满足了我们该删去谁——是删掉限制了我们人数的那个人扩充容量呢还是按现在的限制把多的人都删掉呢?但是想到这里,你应该能发现(也有可能你一开始就发现了),如果我们已知团队人数最多为k,那么我们的选择是可以

2020-07-09 19:14:27

Gym 101606L-计算几何+dp

Lizard Lounge (计算几何+dp)感受到了stl+c++17的强大题目大意:起始点sx,sy还有n个其余的点x,y问以sx,sy为起点的射线中的点的最长上升子序列的个数正常代码写过去了,但感觉不太美观,就整理了下思路,之后就玩了一些好玩的东西思路:【斜率,与sx,sy的相对关系相同】同时满足时,在一条射线上,之后dis近的在前面,跑最长上升子序列即可map的key 维护的是 斜率为二元组pii,与相对关系opval为set集合,存放pii按照第一关键字dis排序看起来很舒服#i

2020-05-25 01:39:00

int与long long效率问题

实验题ps:之前听过说long long的时间问题但是一直没有注意到过。直到遇见了他。。。。这是一个瞎搞题点这里思路:瞎搞证明:int快本着使劲优化的原则,,,加了4个优化。。但是在int数据类型其实这需要加2个多一点的优化就能过去。。。long long下需要加4个完整的优化才可以。优化1:质数ans=(1+n)/2优化2:因子只有2个质数组合优化3:因子只有3个质数组合优化4:因子只有4个质数组合每个优化都有对应的ans遍不需要暴力来处理。。。。但是在4种优化共同起作用时,in

2020-05-23 18:07:17

P1505 [国家集训队]旅游-树链剖分

P1505 [国家集训队]旅游-树链剖分码量惊人题意 如上思路1.板子2.边权转移到点权上,修改时不同链正常修改,相同链上if(x!=y) update(dfn[x]+1,dfn[y])。3.其余就是恶心的线段树了。十分恶心pushupvoid pushup(int o){ t[o].sum=t[ls].sum+t[rs].sum; t[o].max=max(t[ls].max,t[rs].max); t[o].min=min(t[ls].min,t[rs].mi

2020-05-21 20:54:01

[NOI2015]软件包管理器 树链剖分

[NOI2015]软件包管理器 树链剖分在水一道题意 如上思路1.版子2.线段树区间覆盖pushupvoid pushup(int o){ t[o].sum=t[o<<1].sum+t[o<<1|1].sum;}pushdownvoid pushdown(int o){ if(t[o].lazy!=-1){ t[o<<1].lazy=t[o<<1|1].lazy=t[o].lazy; t[

2020-05-21 17:10:36

VMware校园挑战赛E 树链剖分

小V和gcd树 树链剖分好题题意 如上题外话:1.树链剖分其实就是logn条链连接成,这条链满足头节点为轻儿子,之后均是重儿子相连。。。。1.轻-重-重-重-重-重-重 2.轻-重-重-重3.轻-重 这样的连在一起2.top[x]为轻儿子 ,也是重链头3.注意第二遍 为dfs2(1,1)思路:1.放入模板2.update 更改u->son[u] 与 u->fa[u] 的权值。3.query 时 记住top[x]为轻儿子,而轻儿子与father的权值肯定未被更改需要单独计算

2020-05-21 13:04:12

tarjin求割点 割边

tarjin求割点int dfn[maxn],low[maxn];bool pc[maxn];//pc-割点void tarjin(int u,int fa){ static int cnt=0; dfn[u]=low[u]=++cnt; int sum=0; for(auto v:edge[u]){ if(v==fa) continue; if(!dfn[v]){ tarjin(v,u);

2020-05-19 23:10:33

牛客算法周周练5-求幂

求幂——数学数学+数学+数学题意如上思路见大佬的博客好难好难==我好菜 数学题,没有数学思维的我只能到达能看懂题解的地步啦。至于怎么能想到,不会 。至于他为什么能优化到近似O(n),不会 。。。只会喊牛逼。。。。是我太菜了都是基础的数学知识,组合起来加点思维balabala的就没有思路了。我是fw#pragma GCC optimize(3,"Ofast","inline") //G++#include<bits/stdc++.h>#define mem(a,x

2020-05-14 18:40:30

牛客练习赛63---牛牛的树行棋

牛牛的树行棋 (树形sg函数)题意如上思路:很好的一道树上博弈。。。首先需要看出来是sg博弈(并且知道sg博弈)知道之后 如果能猜到sg函数的表示就差不多啦,结论是:sg[x]=到达子树中最深的叶子节点的长度。那么怎么猜呢???叶子节点无法在向下延伸,sg=0.那么叶子节点的father只能向下延伸一步,合理的猜想过后sg=1。之后balabala就能得出 这个结论:结论是:sg[x]=到达子树中最深的叶子节点的长度。虽然我是看题解猜出来的之后就是应有的套路,sg异或和xorsum。如果x

2020-05-14 13:42:33

牛客算法周周练5-A多彩的树

多彩的树(二进制压缩+容斥)题意如上思路k=10二进制压缩dp dfs即可以跑出来,符合相应点数的连通块为n。路径数即为n*(n-1)/2。累加即可,注意还需要加单点的情况即res+=ndp表示选包含相应颜色下路径数,即全部满足集合。比如1010,就包含1000,0010的情况所以需要容斥求b为a的子集,(a|b)^a==0表示为b为a的子集容斥 dp[i]减去dp[j] 当且仅当j为i的真子集且(a-b)的个数为奇数。。.dp[i]加上dp[j] 当且仅当j为i的真子集且(a-b

2020-05-13 18:53:30

动态中位数(对顶堆)

题意:动态求当前序列中的中位数思路:为了动态维护中位数,我们可以建立两个二叉堆:一个小跟堆、一个大根堆。在依次读入这个整数序列的过程中,设当前序列长度为M,我们始终保持:1.序列中从小到大排名为1-M/2的整数储存在大根堆中2.序列中从小到大排名为M/2-M的整数储存在小根堆中。任何时候,如果某一个堆中元素个数过多,打破了这个性质,就取出该堆的堆顶插入到另一个堆。这样一来,序列的中位数就...

2020-04-20 22:17:43

牛客算法周周练2

牛客算法周周练2B Music Problem题意:n个物品 01选法 能否凑成3600的整数倍。思路:dp(写麻烦了,不需要二进制优化其实也可以过,因为抽屉原理当n>=3600时肯定存在答案)很简单的一个dp,,,但是学到了bitset这种牛逼偷懒 的写法。dp[i] 表示当前容量是否可行 即dp[j]=(backup[j]|backup[((j-a[i])%3600+360...

2020-04-15 13:06:31

点分治 模板题

就明白了个模板题,先放个模板。多做一些题后在来整理下。#pragma GCC optimize(3,"Ofast","inline") //G++#include<bits/stdc++.h>#define mem(a,x) memset(a,x,sizeof(a))#define debug(x) cout << #x << ": " <...

2020-04-12 05:49:52

坐标变换

坐标变换#include<bits/stdc++.h>using namespace std;#define fcout cout<<setprecision(0)<<fixedtypedef long long ll;typedef pair<ll,ll> pii;pii calc(int n,ll m){ if(n==0...

2020-04-09 22:48:36

牛客OI周赛15-提高组 C回到过去

牛客OI周赛15-提高组 C回到过去双dp+2进制压缩题目描述n个物品,想要权值和为mm。当哪些种类的物品不选时,一定不能使权值和为mm。思路f[i][j]表示前i个物品权值和为j是否可行。g[i][j]表示后i个物品权值和为j是否可行。枚举不选的种类。然后将f数组和g数组合并一下即可。100%数据范围 做多只用450种物品,(因为权值和最大1e5+5)所以可以用类多重背包的二进制优...

2020-04-05 23:15:38

牛客OI周赛15-提高组 A 环球旅行(树形dp)

牛客OI周赛15-提高组 A 环球旅行树形dp+树的直径题目大意:删除一条边后剩下的子树中树的直径最大值最小.求此最小值现场赛差点搞出来 ,呜呜呜思路:可证删除的这条边肯定在原树的直径上,两遍dfs确定树的直径的起点和终点,这样问题转化为删除一条边剩下的求俩个子树中直径的,可以两遍dfs分别从st,en开始ans[u][0]表示从st开始向下遍历后 如果u为断点的直径的最大值ans...

2020-04-04 23:42:41

hdu4507(恨7不成妻)数位DP

hdu4507(恨7不成妻)数位DP+求平方和传送门题目大意:如果一个整数符合下面3个条件之一,那么我们就说这个整数和7有关——  1、整数中某一位是7;  2、整数的每一位加起来的和是7的整数倍;  3、这个整数是7的整数倍;询问区间[l,r]不符合条件数字的立方和思路如果求询问区间[l,r]不符合条件数字的个数就是普通的数位dp,但此题需要维护立方和。所以开个结构体{cn...

2020-03-21 15:44:07

hdu4352 (数位dp+状态压缩)

HDU 4352 XHXJ’s LIS传送门题目描述:给定一个区间中,将区间的每一个数看成一个字符串,求这个区间内每个字符串的最大上升子序列等于k的个数。思路:dp[pos][sta][k]pos:搜索到第几位sta:之前的最长上升子序列的状态。k:就是输入的那个k牛逼的地方:sta储存为0-9每个数字的状态 类似最长上升子序列更新方式。sta二进制下1的个数就是当前最长上升...

2020-03-20 17:08:48

查看更多

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