马拉车模板.因为不是很重要.加上原理经常忘记.这里贴一下,以备不时之需. void Manacher(char *s,int len){ int l=0; Ma[l++]='$'; Ma[l++]='#'; for (int i=0; i<len; i++){ Ma[l++]=s[i]; Ma[l++]='#'; } Ma[l]=0; int mx=0,id=0; for (int i=0; i<l; i++){ Mp[i]=mx>i ? min(Mp[2*id-i],mx-i) : 1; while (Ma[i+Mp[i]] == Ma[i-Mp[i]]) Mp[i]++;...

这题也是拖欠了几天的...emmm  题目大意:你有n头骆驼,他们要过桥,桥呢,有m座有两个属性l,v,l是它的长度,v表示在这个长度下,你不能超过v的载重,你呢,必须.让你安排下他们的过桥顺序.假如它们能够过桥,就要算出你安排的第一头骆驼和最后一头骆驼的间距,否则的话,输出-1.  思路是这样滴.先判断下无解的情况哈.假如说你的骆驼的体重的max>桥载重的min,那么以必然无解输出-1,有解的情况呢?注意到n的大小只有8,那么我们不妨全排列一下.(果然思路不是自己的写完就可能忘了...我又忘了...emmm所以划水不划水都那样哈哈哈).我们按长度进行一个排序,然后统计下长度排序完后载重...

对于本题而言,我们不妨可以直接贪心,每次尽可能多的把每一位的1消掉一个.如此在线性的复杂度内即可做出. #include <bits/stdc++.h> int cnt[8];//统计每位的个数. std::vector<int>v; int main() { int n,ans=0;std::cin>>n; int p=1000000;for(int i=1;i<=7;i++) {cnt[i]=n/p;if(cnt[i]) n-=cnt[i]*p;p/=10;ans=std::max(ans,cnt[i]);} std::cout<<an...

总体思路就是暴力,我们定义cost[i][j]表示第i天到第j天选择同一道路的花费(对于这个我们用起点跑个dij即可).好,下一步呢,我们不妨再设置一个状态f[i]表示到了第i天的最小花费是多少.它可以由<=的任何j转移过来.代码如下: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=105,M=25; struct vv{ int to,val; }; ll f[N]; bool vis[M]; ll cost[N][N];//预处理从i到j天走同一道路的minc...

emmm...我真的太懒了,老是拖欠,有些题写完就忘了,但尽管如此,我还是拖欠...这两天更是罪大恶极的打了两天LOL,呜呜呜.好了,废话就这么多. 这题是树状数组维护的dp,怎么维护呢.在维护dp前,我们必须要知道一个性质.什么性质呢,就是你选区间的时候鸭,区间的右端点一定是n(证明:因为假如不在最右边,那么右边的一段有些相对高度会降低,那么对于答案会产生不好的影响.),所以我们拿个树状数组,维护两种元素.1.这个点作为左端点选了多少次.2.这个点的高度有多高.维护这两个条件下的最长序列即可.对于这个树状数组的区间最值来说,你会发现,他只会在max更新,而不会把一个值更新到小的,如此,我们直...

可能就我写的比较麻烦...emmm菜的真实.我写了两个dfs,因为我不想写lca...acm带板子还是好..写完看了评论区,都比我短.思路就是dfs1找到第一个sum/3,dfs2找到第二个sum/3即可. //i<->ai ti a[i]=0的i为根节点 #include <bits/stdc++.h> using namespace std; const int N=1e6+5; int w[N];//i上面连着的点的权值是多少. vector<int>v[N]; vector<int>ans; int sum[N];//记录下i为根的子树的...

两次差分.第一次统计下某个操作要操作多少次,第二次差分就是直接统计答案了.注意要从后往前算. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; const int mod=1e9+7; ll op[N],l[N],r[N],ans[N],b[N]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=m;i++) { scanf("%lld%lld%lld",&op[i],&am...

CSP RP++！希望大家不要辜负自己的努力！

有手就行- 0 -.二分答案+排序ck即可.代码如下: #include <bits/stdc++.h> using namespace std; const int N=5e4+3; int x[N],n,R; bool ck(int k)//看下这个值是否可行. { int res=0;int jl=2*k; for(int i=1;i<=n;) { int j=i; while(x[j]-x[i]<=jl&&j!=n+1) { j++; } i=j; res++; } return R>=res; } int main() { cin>...

emmm..终于ac了,这里介绍一下标程做法,大佬的分治做法我也看不太懂,码风完全不一样.标程就是从后往前计算贡献,算出贡献的付出,最后保留的贡献就是f[n]. #include <bits/stdc++.h> typedef long long ll; const ll mod=998244353; const int N=5e5+5; struct vv{ ll h,id;//高度和位子. }w[N]; ll n,dis[N],g[N],f[N],sum[2][N];//第1维维护个数,第二维维护权值. ll qp(ll a,ll b) { ll res=1; while(b)...

所谓的动态的逆序对,就是要你按时间的顺序维护一下逆序对数量.我们不妨在原有的二维前提下增加一维time,那么题目就成了一个的三维偏序问题.我们把添加数,删除数都看成操作.然后进行分治处理,然后我们来看下咋算,对于每个操作id,我们都统计下答案,假定我现在要删除一个元素,那我们应该付出多少代价呢?对于这个数而言,假定我们是按值进行的排序,前面序号比它大的答案都得-,后面那些序号比它小的也得-.然后它自身是要删除的.即树状数组也得-.执行完这个以后,这个值对于后面的数一定是没有影响的,因为后面即+了这个值,又-了这个值.然后就没了. #include <bits/stdc++.h> u...

这是树状数组最后一个基础功能,更完树状数组在基础知识上就完结撒花了.  来看个很简单的模板题.https://www.luogu.com.cn/problem/P2880 贴一下这个题的代码,然后讲解.  #include <bits/stdc++.h> using namespace std; const int N=5e4+5; int h[N]; int n,q; int hmin[N],hmax[N]; int lowbit(int x) { return x&(-x); } void add(int pos,int val)//在点pos更新值为val. { h[...

代码注释很详细. #include <bits/stdc++.h> using namespace std; const int N=205; int vis[N];//-2表示前面有人,-1表示后面有人. bool f[N]; int main() { int n; scanf("%d",&n); bool flag=1; for(int i=1;i<=n;i++) { int a,b; scanf("%d%d",&a,&b); if (a>0&&vis[a]) flag=0;//直接和题意不符 if (b>0&&...

明天b站讲解,树状数组&递归.https://b23.tv/i9rN3k https://blog.nowcoder.net/n/65136c2a849140b69a3ccf380866d2dc 树状数组博客地址. #include <bits/stdc++.h> using namespace std; const int N=2e5+5; struct vv{ int a,b,c,cnt,ans; }tr[N],cp[N]; int n,m,k; int f[N],sum[N]; int lowbit(int x) { return x&(-x); } void...