时隔多月,终于对某些算法有了些了解.今天更一下树状数组.之所以能用树状数组解决快速的区间查询和修改问题主要还是因为二进制的特点.lowbit()函数很多博客都讲了,我也不说了. C[1] = A[1]; C[2] = A[1] + A[2]; C[3] = A[3]; C[4] = A[1] + A[2] + A[3] + A[4]; C[5] = A[5]; C[6] = A[5] + A[6]; C[7] = A[7]; C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];A是我们已知数组,我们不妨把C看成一个类前缀的形...

直接双指针模拟就好了,然后拿ans统计答案的min.注意变量之间别混淆. //orz代码构思太弱了... #include <bits/stdc++.h> using namespace std; const int N=1e6+5; typedef long long ll; struct vv{ ll col,pos; }a[N]; int cnt[N];//统计 bool cmp(vv x,vv y) { if(x.pos==y.pos) return x.col<y.col; else return x.pos<y.pos; } int main() { int...

前导0一定要处理... //进阶指南dp挺好的,经典又不难...先把最后一题写完吧orz. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int base=33; const int N=33,M=100; ll f[N][M];//到了第i位0与1的差值+base后面填的数没有限制有多少种方案. ll a[N];//存二进制数. ll dfs(int pos,int c,int limit,int is_zero)//到了哪一位,差值是多少,这一位填数有没有限制,前面是不是填了数...

邓老师题解写的十分的好.首先把完全二分图转化成一个二维的棋盘,因为完全二分图的连边可以把左边看成横坐标和右边看成纵坐标.如此题目就变成了,棋盘中同一横纵坐标不能存在相同颜色,且绿色根本不影响结果,我们不妨假设棋盘原本都是绿色,然后涂上红蓝两色...orz我们不妨设f[n]是一种颜色满足要求的所有涂法.然后这个可以递推.邓老师讲了.那么我们直接上方程: f[n]=f[n-1]*2*n-(n-1)*(n-1)*f[n-2];然后根据容斥原理.邓老师也讲了.是从i是从0到n.然后ac代码如下: #include <bits/stdc++.h> using namespace std; t...

这题不能二分...或许能二分也要讨论很多...所以可以直接贪心...直接算出平均的水温,再分类讨论一下即可,假如平均的水温比n个杯子里的都小,那么肯定大水缸是降温的.假如平均的水温比最大的要大,说明大水缸是升温的,不然我的大水缸的温度夹在两个max和min中间,那么一定是不能调节的.. #include <bits/stdc++.h> using namespace std; const int N=1e5+5; double t[N],c[N]; int main() { double T,C; int n; cin>>n; cin>>T>>C...

挺有价值的一个dp,记录一下.. //先分配最大的,然后枚举几个1dp即可 #include <bits/stdc++.h> using namespace std; const int N=5e3+5,M=35; int f[M][N];// int sum[N]; struct vv{ int id,val; }a[N]; bool cmp(vv x,vv y) { if(x.val==y.val) return x.id<y.id; else return x.val>y.val; } int ans[M]; int main() { int n,m; scanf...

有生之年,敲这么长的dp代码,记录一下~ //一题不会是真的. #include <bits/stdc++.h> using namespace std; //f(i,j,l,r,k1,k2)//到了第几行 选了几个数 选的数的左端点 右端点是什么 左端点是递增/递减 右端点是递增/递减 int f[16][16*16][16][16][2][2]; int sum[16][16],x; struct vv{ int a,b; }; struct node{ int aa,ab,ac,ad,ae,af; }pre[16][16*16][16][16][2][2]; node t; ...

dfs即可,代码有注释. #include <bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N],b[N],st[N],vis[N],flag=0,n; char ans[N]; //确认过眼神是一个难难的题目Hhhh bool dfs(int u,int step)//能不能用step步到第u个点. { if(u>n||u<1) return false;//假如不合法直接返回. if(u==n) { ans[step]='\0'; return true; } if(vis[u]) { st...

贪心就完事,1号点是小美,问max.那么就是每次都操作都对小美最有利.如何操作呢?首先呢,假如我是小美,我肯定是把这些数分成2组,一组是比我大的数,另外一组是比我小的数.我希望怎么比赛呢,肯定是我每次跟比我小的数进行比赛,然后比我大的人进行比赛,比我小的人进行比赛,这样子是最优的,然后代码就很好写了.代码如下: #include <bits/stdc++.h> using namespace std; const int N=(1<<21); int a[N]; int main() { int n; scanf("%d",&n); for(int i=1;i&...

#include <bits/stdc++.h> using namespace std; const int base=400; int f[205][25][805]; int p[205],d[205]; int main() { int n,m,T=1; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; for(int i=1;i<=n;i++) scanf("%d%d",&p[i],&d[i]); memset(f,-...

直接暴力n^2即可,好吧,还是少写这种题.. #include <bits/stdc++.h> using namespace std; const int N=1005; int a[N],b[N]; int main() { int n,m; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%d",&b[i]); int ans=2e9; for(int i=1;i<=m-n...

连续的子序列,emmm,难度瞬间下降...只要预处理出来两个数组,第一个是到i的时候,前面递增的最大数量,第二个是从后面往前递减的最大数量,然后假如a[i+1]-a[i-1]>2即可统计答案..代码如下: #include <bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N],l[N],r[N];//左边有多少连续比它小的 右边有多少连续比它大的 int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a...