考察线段树的区间最小和单点修改.因为树状数组还没学完,所以还是用线段树来写..其实线段树还没系统的学...但是这种题只是个模板而已.考虑我到了第i个,我包含的区间是(s[i],t[i]).这里面的区间都是可取的,我要做的就是问这个区间的最小值在哪里,然后我假如找到了这个区间的最小值,那么我只要更新右端点即可,因为下次询问假如它是要用这个区间,那么肯定是包含这个区间的右端点的,如此这个题就完美的解决了.代码如下: #include <stdio.h> const int N=2e6+4; int s[N],t[N],tmin[N]; int min(int a,int b) { if...

对于位运算来说,一般都是按位维护,题目要你求所有子段和的异或和,那么我们按位处理就好了.a[j]存的是在(1<<i)的情况下,小于第i位的sum[j]的值,然后就是讨论该位1是否发生变化了.第二题就写完了...emm #include <bits/stdc++.h> using namespace std; const int N=1e5+5,M=1e6+5; int a[N],sum[2][M],s[N]; int lowbit(int x) { return x&(-x); } void add(int pos,int val,int op) { while...

挺套路的一个题目.问最小的问题,一般就二分一下,且这个单调性真的显然.然后我们注意k只有2e5,完全可以贪心检测,1min..1min的检测嘛,贪心的策略就是ck时间,把我所坚持时间小的优先充电.貌似就么了..代码如下: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5; ll a[N]; int n,k,b[N]; struct vv{ ll p; int id; ll a1; int b1; friend bool operator<(struct v...

首先令f[i][j]为到了第j个值为i的贡献. 我们很容易想到没有问号时候的转移方程.  if(s[i]=='a') { f[0][i]=(f[0][i-1]+p[cnt])%mod; } if(s[i]=='b') { f[1][i]=(f[1][i-1]+f[0][i-1])%mod; } if(s[i]=='c') { f[2][i]=(f[2][i-1]+f[1][i-1])%mod; }那么有问号该怎么处理呢?其实也挺简单的,我们知道假如当前为?那么前面的贡献都得*3对吧?因为我?有三种选择'a','b','c'都是会被记录答案的,我们再来考虑第i位,第i位假如为a,那么它的贡献为3...

之前写树状数组只写了了单点修改区间查询以及区间修改单点查询.今天因为一个题目要用到树状数组区间修改区间查询,所以先更一下区间修改以及区间查询.  区间修改以及区间查询呢,简单的来说区间修改还是和以前一样用一个D[i]数组单点修改即可完成.如何进行区间查询呢?这里我们用到两个数组即可完成,c1[i]表示d[i]的前缀和,c2[i]表示d[i]*(i-1)的前缀和.如此我们就可以进行区间修改以及区间查询了.c1,c2类似之前的sum数组.   https://www.luogu.com.cn/problem/P6477  直接看这个题,其实树状数组这种数据结构大多数只是一种降低时间复杂度的工具,题...

可以私聊一下吗>?谢谢~   QQ:1070856563

b:直接模拟从左到右这个过程即可.空格操作和不进行空格操作进行一次比较. #include <bits/stdc++.h> using namespace std; vector<int>ans1,ans2; int main() { int T; scanf("%d",&T); while(T--) { ans1.clear(),ans2.clear(); string s1,s2;int num1=0,num2=0; cin>>s1>>s2; //不清0. for(int i=0;i<s1.size();i++) { if(nu...

题目太多做不完,意思下就好了...就1个hdu的模板题 1个蓝题 7个紫题 1个黑题结尾吧~https://www.luogu.com.cn/problem/P6477 (pass) https://www.luogu.com.cn/problem/P3760 (pass) https://www.luogu.com.cn/problem/P3157 (pass) https://www.luogu.com.cn/problem/P3810 (pass) https://www.luogu.com.cn/problem/P6375 (pass) https://www.luogu.com.cn...

A.直接二分长度ck一下区间是否有这些字母即可. #include <bits/stdc++.h> using namespace std; const int N=2e5,M=20; char s[N]; int pos[M][N]; int C(char c) { if(c=='p') return 1; if(c=='u') return 2; if(c=='l') return 3; if(c=='e') return 4; if(c=='y') return 5; if(c=='a') return 6; if(c=='k') return 7; if(c=='n') r...

100%的数据,满足1<=N,M<=30,0<=T<=30---来自洛谷的数据范围.简单来说就是暴力,暴力枚举一个点,然后再算到其他点的之间最少需要移除多少障碍物.然后就结束了. #include <bits/stdc++.h> using namespace std; const int N=32; char s[N][N]; int n,m,t,w[N][N],dis[N][N]; int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0}; void dfs(int x,int y,int cnt) { //cout<&l...

直接离线即可.对于每一步都存值即可.(凡是难做的题,都可以考虑离线.)代码如下: #include <bits/stdc++.h> using namespace std; const int N=1e6+5,M=5e5+5; int ans[M],p[N],v[N],l[M],sum[N],n; vector<int>r[N];//这个点是第几次查询的时候. vector<int>kind[N];//记录下种类有多少个了. int lowbit(int x) { return x&(-x); } void add(int pos,int val) ...

首先我们都会求[1,n]与给定的p互质的个数对吧?用容斥原理,拿n-1个p的质因子+2个p的质因子...这样容斥下去即可.题目是要求大于x第k个与p互质的数.很明显是有单调性的,我们来二分n然后ck一下,假定cnt[n]表示[1,n]与给定的p互质的个数,那么我们是要求大于x的第k个,那么我们直接拿cnt[n]-cnt[x]看他假如多了,我们就缩小r,少了就增加l...然后就没了..代码如下: #include <bits/stdc++.h> using namespace std; const int N=24; int id,pr[N],sum; int query(int x...

毒瘤题,注意下正数负数的取值就好了... #include <bits/stdc++.h> using namespace std; const int N=2e6+5,M=10,base=1e6+1; char s[M];int pos[N/10],sum[N],id,vis[N/10]; int lowbit(int x) { return x&(-x); } void add(int pos,int val) { while(pos<=N-1) { // if(f) cout<<pos<<endl; sum[pos]+=val; pos+...

讲真的看到题,我都没想容斥原理...是我太菜了吗.首先拿个完全背包进行预处理.然后我们来观察下完全背包的含义.什么含义呢,就是你每个物品都任意取,在容量为x的情况下的方案数.假定我们对于其中的一个做出了限制,那么方案数会不会减少呢>?显然是会的,因为有限制嘛~会减少多少呢...其实假设我们只能取d[i]个了,这个面值是c[i],我们假定选出来d[i]+1个.那么剩下的空间随便取,然后都是不合法的了,所以合法的就是种数就确定了 dp[n-(d[i]+1)*c[i]].同理哈,两个不合法就是 dp[n-(d[i]+1)*c[i]-(d[j]+1)*c[j]].三个四个同理.但是一个不合法中又...