Error:NAN-CSDN博客

原创正则表达式匹配

正则表达式匹配给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。‘.’ 匹配任意单个字符 ‘*’ 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。dp[i][j] i,j分别代表s[i-1] p[j-1],表式两个前缀是否匹配当 p[j-1]=='*' 时dp[i][j]=dp[i][j-2](取消*匹配)|dp[i-1][j] s去掉字符串尾部再进行*匹配p[j-1]!=*dp[i][j]=dp..

2021-11-03 23:13:56 218

原创寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。归并排序时间复杂度O(n+m)class Solution {public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int pre=-0x3f3f3f3f,now=-0x3f3f3f3f;

2021-10-28 22:27:39 96

原创 Gardener and Tree

A tree is an undirected connected graph in which there are no cycles. This problem is about non-rooted trees. A leaf of a tree is a vertex that is connected to at most one vertex.The gardener Vitaly grew a tree from n vertices. He decided to trim the tree

2021-10-20 13:09:28 196

原创 The Number of Imposters

D. The Number of Imposters time limit per test3 seconds memory limitper test256 megabytes inputstandard input outputstandard outputTheofanis started playing the new online game called “Among them”.However, he always plays with Cypriot players, and they.

2021-10-09 20:58:48 251

原创 D. Lowbit

Lucida has a sequence of n integers a1,a2,…,an. He asks you to perform two types of operations for him, which aredescribed as follows:1 L R, add lowbit(ai) to each ai in the interval [L,R].2 L R, query the sum of the numbers in the interval [L,R].

2021-09-04 19:34:32 314

原创 2021-06-07

放假之前报了牛客的多校，放假之后做了几场牛客多校不理想。时间过得比较快，重新组队后,我们开始打hdu多校，联系了一些常用的数据结构的题目，我还是负责数据结构和dp,考虑到现在的水平，做题的重心放在了铜牌题上。做hdu多校,尽量理解思考。不会则去看题解理解。下月主要做一些vj思维题题目和在洛谷上解决一些数据结构的题目,hdu多校题目比较困难，继续加油吧。...

2021-08-02 22:39:05 50

原创 E.String reversal

题意：将一个字符串通过交换相邻的字符变为反转的字符串的最小次数。将反转后的字符串每个字符视为离原字符串最近的字符转移的。从后向前遍历，如果一个字符在已经进入树状字符的后面则必定于其交换一次，用树状数组维护。#include <iostream>#include <algorithm>#include <cstdio>#include <queue>#include <cstring>#include <vector&g..

2021-06-07 00:05:38 137 1

原创省赛总结

这场省赛我们打的很不好，刚开始我们先捡的题目短的做，很快队友就发现了签到题然后就把签到题AC了，另一道题意思我没读懂暂时不明白就跳过了，然后分头找题，我发现一个01背包问题，但是很久没做背包题目了出了差错，跟队友讨论后成功从WR到MemoryLimited了，然后很快想到了滚动数组，但是出了差错改错了，最后耗费了很长时间Wr了好几次才AC。然后我们跟榜做M题，队友发现是构造类型的题目，但是发现没有啥思路也WR了好几次最后放弃了，最后lcy根据做题情况让我们做c,d题，明显d题比较简单但是也是想了很长时间外加

2021-05-10 18:02:16 130

原创五一总结

这一个五一假期，我参与了五一训练不久之后就是省赛感觉自己的水平不够，在这几场比赛中，队友比较给力，我感觉我比较拖后腿了，尤其是代码水平的下滑，让我出现了许多次的错误提交，做题进度上也落后了。除了简单题外，能做出的比较难的题目甚少。最近想题目耗费的时间比较多，这次训练的J题我们想了2个小时一直没有想出来，一直在推公式，这一题实际上是找规律，在这方面我比较缺乏思路的转换。还有时间复杂度估计的不好，容易超时。我在数据结构方面也处理的不好。做题思路上我没有大体的规划因为我比较菜，基本上在跟榜。现在的步骤就是整理数据

2021-05-06 00:22:23 139 2

原创 leeing Sunlight(二分)

Klee's definition of playing is throwing explosives all over the place; she is particularly fond of "fish blasting'' --- throwing bombs in lakes full of fish. Today, Klee also plans to blast fish in Starfell Lake. There are n fish in Starfell Lake. Klee .

2021-04-27 01:05:33 260

原创 venile Galant(简单dp+逆元)

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 524288K，其他语言1048576K 64bit IO Format: %lld题目描述As a self-proclaimed practitioner of the Guhua Clan (Aka. Kokaha)'s arts, Xingqiu (Aka. Yukuaki) is planning to forge a longsword with length n. The following p...

2021-04-26 23:58:21 241

原创周训练总结

这一周,我们队打了四场比赛，比赛的效果并不好，周末的联盟赛让我清楚了我现在的水平不够，这几场比赛有两场遇到了差不多的数据结构题目类型，但是没能及时做出总是有偏差，这是我的失误，还有一些dp类型的题目，感觉做题还是少了没有快速看出题目的用意，这周做题疏忽了，下周要加紧补充题目。...

2021-04-26 09:11:35 90

原创 P2198 杀蚂蚁

1.放射塔和辐射塔都是经过后才起作用，所以最后那位一定是激光塔。2.因为放射塔和辐射塔的效果可以累加所以激光塔最后放最优。3.枚举激光塔的长度，剩下的区间放置辐射塔和放射塔int n,r,g,b,t; 激光塔辐射塔放射塔dp[i][j] i为放射塔数量,j为辐射塔的数量动态转移方程dp[i][j]=max(dp[i-1][j]+(n-i-j)(j * g)b,dp[i][j-1]+(n-i-j)(ib+t)*g);__int128挺好用#include<iostream&gt..

2021-04-06 21:32:23 102

原创杠杆数

…#include<iostream>#include<cstring>using namespace std;#define ll long longconst int maxn=25;ll pos[maxn];ll dp[maxn][maxn][maxn*100];ll i;ll dfs(int ps,int pt,int st,int fn)//数的位数支点的位置力矩和{ if(!ps) return st==0; i.

2021-04-06 20:41:04 92

原创 Philosopher‘s Walk(分治)

Philosopher‘s Walk画几遍图，你会发现有四种形态而且相互转化。#include<iostream>#include<cstdio>using namespace std;int block[4][4]={{1,0,0,3},{2,1,1,0},{3,2,2,1},{0,3,3,2}};int rectu[4][4]={{0,1,2,3},{1,2,3,0},{2,3,0,1},{3,0,1,2}};bool sx=true;int init=0;v.

2021-03-29 22:54:33 113

原创 P1285 队员分组(二分图+背包)

P1285 队员分组#include <iostream>#include <string>#include <complex>#include <vector>#include <stack>#include <cstdio>#include<functional>#include<cmath>#include<ctime>#include<cstring>#in

2021-03-28 01:36:52 213

原创 CF865C Gotta Go Fast

CF865C Gotta Go Fastf[i][j]表示在进行关卡i时的时间。1.在关卡i前重新开始，期望值为mid2.关卡i最快方式通过，时间为(dp[i+1][j+a[i]]+a[i])p[i]/1003.关卡i最慢方式通过，时间为(dp[i+1][j+b[i]+b[i]])(1-p[i]/100)#include <iostream>#include <string>#include <complex>#include<functional.

2021-03-27 23:19:15 122

原创 CF321E Ciel and Gondolas（决策单调性）

Ciel and Gondolas动态规划方程是dp[i][j]=min{dp[i-1][j]+cal(k+1,j)},cal(i,j)=cal(i-1,j)+cal(i,j-1)-cal(i-1,i-1)+ch[j][j]。做题时，没有注意策略点的范围，超时了好几次。#include<cstdio>#include<cstring>#include<iostream>#include<fstream>using namespace std;c.

2021-03-24 12:57:54 243

原创 CF868F Yet Another Minimization Problem(决策单调性)

Yet Another Minimization Problem题意：将序列划分为k段，每段的代价为这段所有重复数n(n-1)/2的和，求怎么分段使得，所有段的代价之和最小。思路:容易知道动态规划方程式为dp[i][j]=max(dp[i-1][k]+cal(k+1,j)){i为分段数,j为序列总长度}但是这样做时间复杂度为O(n3)，所以要对动态规划进行优化。决策单调性若序列总长度分别为i,m,i>m则最优决策点iu>=mu,根据决策点单调的性质分治优化，cal(i,j)则用莫队。#..

2021-03-21 13:22:24 386

原创 Early Orders

题意:给出一段数字序列，找出序列中字典序最小的子序列。思路：维护一个递增的单调栈，特殊考虑下末位的数情况，如果在栈中不抛出，如果不在栈中直接加入。#include<iostream>using namespace std;int l=1,r=0;const int maxn=2e5+5;int q[maxn];int st[maxn];int tt[maxn];int main(){ int n,k; cin>>n>>k; f.

2021-03-15 00:09:54 55

原创 2021-02-6总结

这几天继续做了状压dp，学习到了Ac自动尝试写了一下,原理是字典树+Kmp算法(fail指针失败匹配指向)，省选的状压题目感觉有点难做，感觉最近状态不是多么好，题目有点刷不动，我要调整一下做的题目的难度。...

2021-02-07 00:09:31 48

原创 2020-1-30

最近有些事情没有参加比赛，比赛后做了一场CF的题目，前两个觉得没有问题，第三个有些难但是能够想出来，第四题感觉与数论有关但是没有想出来，发现是忽略的知识点。之后做了几道数位动态规划的题目和一些状压的题目。感觉这一部分思路还行，继续练习动态规划的题目。...

2021-01-31 00:31:23 85

原创 2021-1-27总结

这些天做了比较多的CF提高+省选-的DP题目，动态规划有较多的题目是与贪心思想相结合，在这方面我还没有贯通，剩下的是状态的转移感觉比之前好点了。但是有时，题目中的某些概念与自己的想法混淆，想了半天被自己带偏了。看了几道省选的题目感觉难度比较大，没有思路，只能之后继续理解下去了。...

2021-01-27 23:36:06 65

原创 2021-01-23

这三天，继续练习了动态规划，主要做了区间动态规划和压缩压缩方面的几道题，做题时感觉掌握的不是太好，不容易看出来到底是用哪一个，题目上作为状态转移的一些细节没有想出来，题目做出来的比较少。之后我要总结一下做题时思路出现的问题。...

2021-01-23 23:08:27 410

原创 2021-01-20

之前了解了四大平衡树，这三天主要练习了Treap树，做了相关的题目，感觉代码比较冗长。之后复习动态规划，找了几个洛谷的题目，发现这一块还不行，状态转移方面还是不能自然地从题目中看出来，思考的不是很详细，之后的时间继续复习dp....

2021-01-20 21:33:57 621

原创学期总结

不知不觉一个学期结束了，这一个学期过得比较快。刚开始我先从动态规划开始学习，本来以为动态规划种类比较多，大概有区间dp,状压dp,树形dp,单调队列优化dp,斜率优化dp，数位优化dp,做题时还遇到插头DP,看了许多博客没懂，最后在B站找了个视频才看懂的前前后后大约花了近一个星期才看懂的，动态规划方面学习也不是很快但感觉比数论容易。然后学习了数论，主要学习了质数，同余，快速幂，线性筛，博弈问题，矩阵乘法，组合数学，还新学了许多新的算法，BSGS,ExBSGS,Lucas,exlucas,原根,还做了一些关于

2020-12-22 23:12:53 74

原创 2020-12-20

这一周我复习了树状数组和线段树二部分，对比上次做题时，感觉理解更加深入了。然后学习了倍增法求LCA，了解了一下SBT。LCA,在一个根树下，找两个节点u,v最近的父节点。倍增法求LCA,设F[x,k]是距离x节点2^k距离的父节点，则f[x,k+ 1] = f[f[x][k]][i],利用二进制拆分思想将深度较少的节点移到与较大点相同的深度，然后继续拆分逼近父节点，最后的得到距离父节点一位置的点。void deal_first(int u,int father){ Dep[u]=Dep[...

2020-12-20 22:11:43 69

原创 2020-12-06

这一周做了组合数学和博弈方面的题目。组合数学方面比较熟悉，博弈方面比较难懂。新学到了Lucas和Exlucaslucas(模是质数)lucas(x,y)=C(x%p,y%p)∗lucas(x/p,y/p)lucas(x,y)=C(x\%p,y\%p)*lucas(x/p,y/p)lucas(x,y)=C(x%p,y%p)∗lucas(x/p,y/p)Exlucas（模不一定是质数）主要利用了唯一分解定理，中国剩余定理下面是模板ll fac(ll n,ll p,ll pk)//n...

2020-12-06 22:02:54 60

原创 1657：序列统计(lucas)

1657：序列统计时间限制: 1000 ms 内存限制: 524288 KB提交数: 178 通过数: 92【题目描述】原题来自：BZOJ 4403给定三个正整数 N,L 和 R，统计长度在 1 到 N 之间，元素大小都在 L 到 R 之间的单调不降序列的数量。输出答案对 106+3 取模的结果。【输入】输入第一行包含一个整数 T，表示数据组数。第二到第 T+1 行每行包含三个整数 N,L 和 R，N,L 和 R 的意义如题所述。【输出】输出包含 T 行，每行有一

2020-12-03 12:12:40 282

原创 P1350 车的放置

#include <iostream>using namespace std;#define ll long long const ll mod=1e5+3;const ll maxn=1e3+1;ll list[maxn];ll revs[maxn];inline ll ext_gcd(ll a,ll b,ll &x,ll &y){ if(b==0) { x=1;y=0; return a; } ll r=ext_gcd(b,a%b,y,.

2020-12-02 22:02:05 67

原创 2020-11-29

这一个星期做了信息奥赛一本通上的数论模块，做了约数，同余，乘法三部分。新奥一本通题目多数题目独立完成的，但还是有几道题目参考了一下题解，一些地方的思维还是不够，有的地方对算法的理解不够深。下一星期做洛谷和新奥上的组合数学和博弈论方面。...

2020-11-30 09:34:56 57

原创 1647：迷路(矩阵快速幂+矩阵点的拆分)

1647：迷路时间限制: 1000 ms 内存限制: 524288 KB提交数: 97 通过数: 69【题目描述】原题来自：SCOI 2009Windy 在有向图中迷路了。该有向图有 N 个节点，Windy 从节点 0 出发，他必须恰好在 T 时刻到达节点 N−1。现在给出该有向图，你能告诉 Windy 总共有多少种不同的路径吗？注意：Windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。【输入】第一行包含两个整数，N,T；接下来有 N 行，每行

2020-11-25 20:03:51 227

原创 2020-11-22

数学分块int l=0,r=0;for(int i=1;i<maxn;i++){ l=r+1; int value=m/l; int r=m/value;//数值的终点 if(r>maxn)r=maxn; //区间操作(l.....r)}时间复杂度为O(logn)欧拉函数欧拉筛利用欧拉函数积性函数性质。bool nop[maxn];int pri[maxn],oular[maxn];for(int i=2; i<maxn; i++){ ...

2020-11-22 21:21:02 78

原创 P2504洗牌(扩欧)

洗牌根据题目模拟了几次洗牌过程，得到了第一层逻辑，if(x<=(n/2))x1=2∗x else if(x>(n/2))x1=(x−(n/2)−1)∗2+1;−>x1=(2∗x−n−2)+1−>x1=(2∗x−(n+1))因为2∗x−（n+1）<n所以x1=2∗x(mod n+1),总式子也是x1=2∗x(mod n+1)题目变为2m∗x=L(mod n+1)−>2m∗x+(n+1)∗Y=Lif

2020-11-21 22:00:04 80

原创 2020-11-15总结

本周练习了同余，逆元方面，新学了几个模板题，感觉对数学的理解提升了。最近感觉比其他同学落下了比较多的一部分。做题时常常用简单暴力的方法，导致了不少题目超时,int相乘要比longlong相乘快得多，如果数据范围还可以要用int,龟速乘要慎用。...

2020-11-15 21:30:13 84

原创 2020-11-08周总结

学了多项式的相乘的优化算法-----fft,感觉有点迷糊，剩下的都是素数和矩阵快速幂的题目了。数学这科目，难搞，我天赋一般，搞个几个小时都容易搞不出来。理解快速傅里叶，一直没有完全搞懂，于是就做了几道模板题。于是我打算先巩固素数的知识。做题时碰着了几个矩阵快速幂的，一起做了。中途遇到一个字符串变化辅助的题，一直WRONG,跳了过去，到了周末时才发现题目读错了。数论这方面感觉很广，初高中，大学数学的知识都有，用的差不多是遗忘或忽略的那一块。现在发现初高中的数学忘得比较多了，没有忘的知识感觉也很难与题目联想起来

2020-11-09 12:10:06 54

原创 2020-11-01总结

这一周打了一场cf比赛，主要做出来的是三道水题吧，还是有一道题也比较水，但是没有想到点子上去，浪费了挺长时间我的思路比较偏向贪心，这道题让我意识到思路的不足，做题中思考过程比较慢，还是靠没出大的错误才上分,cf感觉进步很小。本周主要做了剩余定理和快速幂的的模板和应用。做题速度太慢了，弄懂一道题目采用的的原理时间比较长，做出一道题的时间长而且题目的细节比较多不能保证AC。这一周也是完成了基本的任务，但是感觉不足。这周末听了蔡同学的演讲，我明白我掌握的数论知识太少了，现在的目标是把数论的部分题目模板搞清楚，然后

2020-11-01 20:23:56 138 2

空空如也

空空如也