前言写在前面，线段树是一种用于区间处理的数据结构，本篇博客用来记录我学习线段树的刷题过程。 1.区间求和以及单点修改这里由于只是涉及单点修改操作，所以就不用lazy标记了hdu1166 #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = -1e9; const ll N =5e4+7; const ll mod=1e9+7; inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48...

单调栈 hdu1506 #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e9; const ll NUM =1e5+7; inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch >= 48 && ch <...

关于取数的题目（区间dp） 首先我们来看一道简单的取数问题： 取数游戏：有三个数字，把他们组成一个最大的三位数，暴力就行了代码如下： #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = -1e9; const ll N =80+7; const ll mod = 9999999967; inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { i...

hdu 2602滚动数组 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; int dp[1011]; int t,v,n; struct node{ int val; int vol; }bone[1011]; int solve(){ memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ for(int j=v;j>=bone[i].vo...

#include<bits/stdc++.h> using namespace std; const int maxn=2e6+5; typedef long long ll; const ll mod=1000000007; struct mat{ ll m[2][2]; }; mat mul(mat a,mat b){ mat c; memset(c.m,0,sizeof(c.m)); for(int i=0;i<2;i++) for(int j=0;j<2;j++){ for(int k=...

poj 2182二叉树实现 #include<stdio.h> const int maxn=1e4; struct { int l,r,len; }tree[maxn*4];//结构数组 int pre[maxn],ans[maxn]; void Buildtree(int left,int right,int u){ tree[u].l=left; tree[u].r=right; tree[u].len=right-left+1;//更新结点的值 if(left==right) return; Buildtree...

hdu2544 最短路 #include<bits/stdc++.h> using namespace std; const int INF = 1e6; const int NUM =105; struct edge{ int from,to,w;//from : 起点 to : 终点 w:权值 edge(int a,int b,int c){from = a;to = b;w = c;} }; vector<edge>e[NUM]; struct s_node{ int id,n_dis;//id:结点 n_dis:结点到起点的距离 ...

hdu1873看病排队：优先队列 #include<bits/stdc++.h> using namespace std; struct node{ int id,lev; friend bool operator<(const node x,const node y){ if(x.lev==y.lev) return x.id>y.id; return x.lev<y.lev; } }temp; int main(){ int t,a,b; string s1; while(cin&...

根据二叉树的前序,中序与后序序列构建二叉树 #include <stdio.h> #include <stdlib.h> #define MaxSize 100 typedef struct node /*二叉树结构定义*/ { char data; struct node *lchild,*rchild; }binnode; typedef binnode *bintree; bintree CreateBinTreebyPreIn(char *pre,char *in,int n){ bintree t; int k; c...

A.shooting Game 题目链接 题目描述成中文：n个人（n<=100)一起比赛,有三种目标给你射击，红色：1分，白色：2分，黑色：3分。已知每个人射中三种目标的数量，要你求出得分最高的选手，分数相同就取id较小的一个。输入描述：输入n。接下来n行是中，每行一个四个整数，分别是选手的id，以及红白黑各个目标数目。输出：选手的id以及总分。这就是一道签到题，我比较菜，搞了个结构体，代码如下。 #include <iostream> #include<bits/stdc++.h> #include<algorithm> #include<c...

A.夹娃娃 这题就是一个求前缀和的水题，不过要注意会卡快读，要用scanf输入才能过。 #include <iostream> #include<bits/stdc++.h> #include<algorithm> #pragma GCC optimize(2) #pragma GCC optimize(3) using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) typedef long long ll; const ll MOD = 1e5 ...

#include <stdio.h> #include <stdlib.h> #define max 1e9 typedef struct hnode{ int weight; int lchild; int rchild; int parent; char s[1000]; }huffNode; void select(huffNode huffmanTree[ ], int k, int *s1, int *s2); //从huffmanTree数组的0到up-1中找出father为-1的且权重最小的结点赋给s1,s2,（为了...

题目描述：有一群牛在花园里面，农夫需要一个个地把牛运送到牛舍，已知农夫把牛运到牛舍需要地时间（分钟）time以及牛每分钟破坏的花的数目destroy，给出一个数n，n头牛，下面有n行，每行两个数字分别使time,destroy.问如何搬运牛才能使花被破坏的数目最少。题目求解：我们可以看牛群中A，B两头牛，显然任意改变A，B两头牛的位置都对前面的搬运没有影响；1.假设A牛放在B牛的前面，对于后面的影响有：sum * A.destroy+(sum+2 * A.time) * B.destroy2.假设B牛在A牛的前面，对于后面的影响有：sum * B.destroy+(sum+ 2 * B.tim...

AVL树(平衡二叉树)：  AVL树本质上是一颗二叉查找树，但是它又具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为平衡二叉树。下面是平衡二叉树和非平衡二叉树对比的例图：AVL树的作用：  我们知道，对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化...