1.并查集操作:
1 int father[10086]; 2 int find(int x){ 3 return father[x]=(father[x]==x?x:find(father[x]));//一般都是写这个模板,因为他快,不会超时!!! 4 } 5 void Union(int a,int b){ 6 int f1=find(a); 7 int f2=find(b); 8 if(f1<f2)swap(f1,f2);//意思是大的当小的父亲,有钦定的含义在里面,这是可以自定义的额 9 father[f2]=f1; 10 }
2.求解最大公约数:
1 inline int gcd(int a,int b){ 2 return b==0?a:gcd(b,a%b);//a一定是一直大于b的。。。 3 }
3.
1 //priority_queue默认使用的是大顶堆: 2 priority_queue<int>pq; 3 4 如果想使用priority_queue的小顶堆的特性,那么可以采用的是: 5 priority_queue<int,vector<int>,greater<int>()>pq;
4.优先队列,自定义大顶堆或者小顶堆:
那个排序大于是greater<>;所以大于是小顶堆
小于是less<>,所以小于是大顶堆,一定不能弄混了。
学习链接:
1 https://blog.csdn.net/c20182030/article/details/70757660?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
比较模板,以及习题:
787. K 站中转内最便宜的航班
1 // class Node{ 2 // public: 3 // Node(int _cost,int _name,int _dist):pay(_cost),name(_name),dist(_dist){} 4 5 // int pay; 6 // int name; 7 // int dist; 8 // }; 9 struct Node{ 10 int pay; 11 int name; 12 int dist; 13 }; 14 15 struct cmp{ 16 //下面的含义是重载小于号的含义 17 bool operator() (Node& a,Node& b){ 18 return a.pay>b.pay; 19 } 20 21 }; 22 struct edge{ 23 int to; 24 int cost; 25 }; 26 class Solution { 27 public: 28 //Djkstra算法,使用优先队列求解,首先写出Dijkstra算法的模板 29 int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) { 30 priority_queue<Node,vector<Node>,cmp>pq;//第一个参数是代价,第二个参数是到达结点位置。 31 vector<edge>g[n+1]; 32 for(auto v:flights){ 33 edge e; 34 e.to=v[1]; 35 e.cost=v[2]; 36 g[v[0]].push_back(e); 37 } 38 set<int>vis; 39 vis.clear(); 40 pq.push({0,src,-1}); 41 while(!pq.empty()){ 42 auto x=pq.top(); 43 pq.pop(); 44 cout<<x.name<<" "<<vis.count(x.name)<<endl; 45 //if(vis.count(x.name))continue; 46 if(x.name==dst)return x.pay; 47 //vis.insert(x.name); 48 int n=g[x.name].size(); 49 for(int i=0;i<n;i++){ 50 edge v=g[x.name][i]; 51 if(x.dist<K){ 52 pq.push({x.pay+v.cost,v.to,x.dist+1}); 53 } 54 55 } 56 } 57 return -1; 58 } 59 };
Trie树模板
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 //Trie 树 2 #include<iostream> 3 #include<vector> 4 #include<string> 5 #include<cstring> 6 using namespace std; 7 8 struct Node{ 9 Node *child[26]; 10 //bool flag; 11 Node(){//构造函数 12 for(int i=0;i<26;i++){ 13 child[i]=nullptr; 14 } 15 } 16 }; 17 void insert(Node *root,string word){ 18 Node *rt=root;//root是不能变化的,所以最初赋给一个新的值进行操作 19 for(int i=word.length()-1;i>=0;i--){ 20 int to=word[i]-'a'; 21 if(rt->child[to]==nullptr){ 22 rt->child[to]=new Node(); 23 } 24 rt=rt->child[to]; 25 } 26 } 27 void count(Node *root,int &res,int deep){ 28 bool flag=true;//这里涉及到递归的问题,所以需要首先设置一下,防止之后递归多加了。。。 29 for(int i=0;i<26;i++){ 30 if(root->child[i]!=nullptr){ 31 count(root->child[i],res,deep+1); 32 flag=false;//注意需要回溯,否则会出错。。。 33 } 34 } 35 if(flag){ 36 res+=deep;//注意这里的deep需要最初多加一个,因为#也算是一部份 37 //cout<<res<<endl; 38 } 39 } 40 41 int main(){ 42 Node *root=new Node(); 43 int n; 44 cin>>n; 45 string s; 46 vector<string>str; 47 for(int i=0;i<n;i++){ 48 cin>>s; 49 //str.push_back(s); 50 insert(root,s); 51 } 52 int res=0; 53 count(root,res,1); 54 cout<<res<<endl; 55 return 0; 56 }
Trie基本操作:
leetcode题目:
208. 实现 Trie (前缀树)
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Trie { 2 private: 3 bool is_str; 4 Trie* next[26]; 5 public: 6 //bool is_str;//是否是一个完整的字符串 7 /** Initialize your data structure here. */ 8 Trie() { 9 for(int i=0;i<26;i++){ 10 next[i]=nullptr; 11 } 12 is_str=false; 13 } 14 ~Trie(){//析构函数 15 for(int i=0;i<26;i++){ 16 if(next[i]==nullptr)continue; 17 delete(next[i]); 18 next[i]=nullptr; 19 } 20 } 21 22 /** Inserts a word into the trie. */ 23 void insert(string word) { 24 Trie *cur=this;//将根结点this赋给给node 25 for(auto v:word){ 26 if(cur->next[v-'a']==nullptr){ 27 cur->next[v-'a']=new Trie(); 28 } 29 cur=cur->next[v-'a']; 30 } 31 cur->is_str=true;//表示的是这个插入的字符串是完整的。 32 } 33 34 /** Returns if the word is in the trie. */ 35 bool search(string word) { 36 Trie *cur=this; 37 for(auto v:word){ 38 if(cur->next[v-'a']==nullptr)return false; 39 else cur=cur->next[v-'a']; 40 } 41 return cur->is_str; 42 } 43 44 /** Returns if there is any word in the trie that starts with the given prefix. */ 45 bool startsWith(string prefix) { 46 Trie *cur=this; 47 for(auto v:prefix){ 48 if(cur->next[v-'a']==nullptr)return false; 49 else cur=cur->next[v-'a']; 50 } 51 return true; 52 } 53 54 55 };
最短路径算法:
743. 网络延迟时间
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 struct edge{ 2 int to; 3 int cost; 4 }; 5 typedef pair<int,int>P; 6 7 class Solution { 8 public: 9 //dijkstra算法,采用的是优先队列的小顶堆的特性,因为每一次更新会有一个结点的最短路径会最终的确定。那么下一次优先更新的是最小路径的结点。 10 int networkDelayTime(vector<vector<int>>& times, int N, int K) { 11 priority_queue<P,vector<P>,greater<P>>pq; 12 vector<edge>g[N+1];//数组中的形式是edge的格式 13 memset(dist,0x3f,sizeof(dist)); 14 int n=times.size(); 15 for(int i=0;i<n;i++){ 16 edge e; 17 e.to=times[i][1]; 18 e.cost=times[i][2]; 19 g[times[i][0]].push_back(e); 20 } 21 set<int>vis; 22 pq.push({0,K}); 23 int res=0; 24 while(!pq.empty()){ 25 auto x=pq.top(); 26 pq.pop(); 27 if(vis.count(x.second))continue; 28 //vis[x.second]=true; 29 vis.insert(x.second); 30 res=max(x.first,res); 31 //cout<<res<<endl; 32 int n=g[x.second].size(); 33 for(int i=0;i<n;i++){ 34 edge v=g[x.second][i]; 35 if(vis.count(v.to))continue; 36 pq.push({v.cost+x.first,v.to}); 37 } 38 } 39 return vis.size()==N?res:-1; 40 } 41 };
快排手写代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 void Quick_sort(int arr[],int start,int end){ 2 int i=start; 3 int j=end; 4 int val=arr[start]; 5 while(i<j){ 6 while(i<j&&arr[j]>=val)j--; 7 if(i<j){ 8 arr[i]=arr[j]; 9 i++; 10 } 11 while(i<j&&arr[i]<=val)i++; 12 if(i<j){ 13 arr[j]=arr[i]; 14 j--; 15 } 16 } 17 arr[i]=val; 18 Quick_sort(arr,start,i-1); 19 Quick_sort(arr,i+1,end); 20 }
二分查找模板:
1095. 山脉数组中查找目标值
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Solution { 2 public://三次二分查找,第一次找峰,第二次左边,第三次右边 3 //不能使用暴力求解,因为get不能调用超过100次,所以只能采用二分查找的方法求解。。。。 4 int findInMountainArray(int target, MountainArray &a) { 5 //第一步找峰 6 int lo=0; 7 int hi=a.length()-1; 8 while(lo<hi){ 9 int mid=(lo+hi)/2; 10 if(a.get(mid)<a.get(mid+1)){ 11 lo=mid+1; 12 }else{ 13 hi=mid; 14 } 15 } 16 int peak=lo; 17 cout<<peak<<endl; 18 if(target>a.get(peak))return -1; 19 int l0=0; 20 hi=peak; 21 22 while(l0<=hi){ 23 int mid=(l0+hi)/2; 24 if(a.get(mid)==target)return mid; 25 else if(a.get(mid)<target){ 26 l0=mid+1; 27 }else{ 28 hi=mid-1; 29 } 30 } 31 l0=peak; 32 hi=a.length()-1; 33 while(l0<=hi){ 34 int mid=(l0+hi)/2; 35 if(a.get(mid)==target)return mid; 36 else if(a.get(mid)<target){ 37 hi=mid-1; 38 }else{ 39 l0=mid+1; 40 } 41 } 42 return -1; 43 } 44 };
KMP算法:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 namespace KMP{ 2 vector<int>next;//存放的是next数组 3 4 void build(const string &pattern){//构建next数组 5 int n=pattern.length(); 6 next.resize(n+1);//多构建一个位,在模式串的末尾加上一个永远不能操作的位置,方便下面匹配的操作 7 8 for(int i=0,j=next[0]=-1;i<n;next[++i]=++j){ 9 while(j!=-1&&pattern[j]!=pattern[i])j=next[j]; 10 } 11 } 12 vector<int>match(const string &pattern,const string &text){ 13 vector<int>res;//存放的是在text中符合条件的串的初始位置。。。 14 int n=pattern.length(),m=text.length(); 15 build(pattern); 16 for(int i=0,j=0;i<m;i++){ 17 while(j>0&&pattern[j]!=text[i])j=next[j];//kmp主操作 18 if(pattern[j]==text[i])j++; 19 if(j==n){//表示到达最后一个位置了,表示当前位置匹配成功了 20 res.push_back(i-n+1); 21 j=next[j];//表示j又变成0了。。。 22 } 23 } 24 } 25 }
快速幂模板:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 typedef double db; 2 typedef long long ll; 3 class Solution { 4 public: 5 double myPow(double x, int n) { 6 db ans=1.0; 7 ll k=n; 8 if(k<0){ 9 k=-k; 10 x=1/x; 11 } 12 while(k){ 13 if(k&1)ans*=x; 14 x*=x; 15 k=k>>1; 16 } 17 return ans; 18 } 19 };
最短路径相关的代码模板:
743. 网络延迟时间
Floyd:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Solution { 2 public: 3 int networkDelayTime(vector<vector<int>>& times, int N, int K) { 4 int res=0; 5 vector<vector<int>>edge(N+1,vector<int>(N+1,0x3f3f)); 6 for(int i=1;i<=N;i++){//注意这里是从1开始的,因为我们下标是结点的值,结点值最小是1 7 edge[i][i]=0; 8 } 9 for(auto v:times){ 10 edge[v[0]][v[1]]=v[2]; 11 } 12 for(int k=1;k<=N;k++){ 13 for(int i=1;i<=N;i++){ 14 for(int j=1;j<=N;j++){ 15 edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j]); 16 } 17 } 18 } 19 for(int i=1;i<=N;i++){ 20 if(edge[K][i]==0x3f3f)return -1;//如果不能使所有结点收到信号那么返回的是-1. 21 res=max(res,edge[K][i]); 22 } 23 return res; 24 25 } 26 }; 27 28 作者:zb121 29 链接:https://leetcode-cn.com/problems/network-delay-time/solution/cfloydspfa-by-zb121/ 30 来源:力扣(LeetCode) 31 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
SPFA:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Solution { 2 public: 3 //SPFA解法 4 int networkDelayTime(vector<vector<int>>& times, int N, int K) { 5 queue<int>que; 6 vector<vector<int>>edge(N+1,vector<int>(N+1,INT_MAX)); 7 vector<int>dist(N+1,INT_MAX);//表示的是K点到其他结点的最短距离 8 for(auto v:times){ 9 edge[v[0]][v[1]]=v[2]; 10 } 11 que.push(K); 12 dist[K]=0; 13 //SPFA使用的是队列的方式存放中间结点,方便下一次更新 14 while(!que.empty()){ 15 int x=que.front(); 16 que.pop(); 17 for(int i=1;i<=N;i++){//只要出现有边存在,同时边长度较小,那么更新边权值。同时将其放入队列中,下一次再更新一下,当没有边需要更新的时候,那么结束吧。。。 18 if(edge[x][i]!=INT_MAX&&dist[x]+edge[x][i]<dist[i]){ 19 dist[i]=dist[x]+edge[x][i]; 20 que.push(i); 21 } 22 } 23 } 24 int ans=0; 25 for(int i=1;i<=N;i++){ 26 if(dist[i]==INT_MAX)return -1; 27 ans=max(ans,dist[i]); 28 } 29 return ans; 30 } 31 }; 32 33 作者:zb121 34 链接:https://leetcode-cn.com/problems/network-delay-time/solution/cfloydspfa-by-zb121/ 35 来源:力扣(LeetCode) 36 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
Djkstra:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 struct edge{ 2 int to; 3 int cost; 4 }; 5 typedef pair<int,int>P; 6 7 class Solution { 8 public: 9 //dijkstra算法,采用的是优先队列的小顶堆的特性,因为每一次更新会有一个结点的最短路径会最终的确定。那么下一次优先更新的是最小路径的结点。不需要每一次更新不同结点的距离。。。 10 int networkDelayTime(vector<vector<int>>& times, int N, int K) { 11 priority_queue<P,vector<P>,greater<P>>pq; 12 vector<edge>g[N+1];//数组中的形式是edge的格式 13 int n=times.size(); 14 for(int i=0;i<n;i++){ 15 edge e; 16 e.to=times[i][1]; 17 e.cost=times[i][2]; 18 g[times[i][0]].push_back(e); 19 } 20 set<int>vis; 21 pq.push({0,K}); 22 int res=0; 23 while(!pq.empty()){ 24 auto x=pq.top(); 25 pq.pop(); 26 if(vis.count(x.second))continue; 27 vis.insert(x.second); 28 res=max(x.first,res); 29 int n=g[x.second].size(); 30 for(int i=0;i<n;i++){ 31 edge v=g[x.second][i]; 32 if(vis.count(v.to))continue; 33 pq.push({v.cost+x.first,v.to}); 34 } 35 } 36 return vis.size()==N?res:-1; 37 } 38 }; 39 40 作者:zb121 41 链接:https://leetcode-cn.com/problems/network-delay-time/solution/cfloydspfa-by-zb121/ 42 来源:力扣(LeetCode) 43 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
求解最长回文子串的长度:Manacher算法:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 //Mancher算法 ,O(n)时间复杂度解决,将奇数与偶数的回文串统一了起来!!! 2 //HDU 3068最长回文! 3 4 //核心思想: 5 6 #include<iostream> 7 #include<string> 8 #include<algorithm> 9 #include<cstring> 10 #include<map> 11 #include<cstdio> 12 #include<vector> 13 using namespace std; 14 const int maxn=3e5; 15 char s[maxn],str[maxn]; 16 int len1,len2,p[maxn],ans;//p[i]表示的是以i为中心的回文半径是多少。。。ans存放的是最终的结果。。。 17 void init(){//这是一个完成字符串翻倍的操作,加上#实现字符串翻倍的操作。。。 18 str[0]='$'; 19 str[1]='#'; 20 for(int i=0;i<len1;i++){//len1是s的长度 21 str[i*2+2]=s[i]; 22 str[i*2+3]='#'; 23 } 24 len2=len1*2+2;//加上的2是额外的$以及*。。。 25 str[len2]='*'; 26 } 27 void manacher(){ 28 int id=0,mx=0;//mx是以id为中心的最长回文子串的右边界。。。 29 for(int i=1;i<len2;i++){//这里下标是1,因为i-p[i]防止越界。。。 30 if(mx>i)p[i]=min(p[2*id-i],mx-i);//这里的解释在C++程序员面试宝典上面有写,在P3. 31 else p[i]=1; 32 for(;str[i+p[i]]==str[i-p[i]];p[i]++);//暴力的匹配。。。 33 if(p[i]+i>mx){//我的串加上我的回文半径大于mx,那么更新mx 34 mx=p[i]+i; 35 id=i;//更新id 36 } 37 } 38 39 } 40 int main(){ 41 while(cin>>s){ 42 //首先我们需要将string这个数组进行翻倍.init()函数完成这个功能 43 len1=strlen(s); 44 init(); 45 //下面就是进行manacher的操作了。。 46 manacher(); 47 ans=0; 48 for(int i=0;i<len2;i++){ 49 ans=max(ans,p[i]); 50 } 51 cout<<ans-1<<endl;//因为半径其实插入了字符,所以半径就是长度二倍,所以需要减一。。。 52 } 53 return 0; 54 }
C11特性,基本写代码模板:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<iostream> 2 #include<vector> 3 #include<algorithm> 4 #include<cstring> 5 #include<string> 6 using namespace std; 7 struct Point{ 8 int a,b; 9 Point(int a=0,int b=0):a(a),b(b){} 10 bool operator<(const Point &rhs)const{//这样就不用再写cmp函数,重载小于运算符。 11 return a<rhs.a; 12 } 13 } 14 template <typename T1,typename T2,typename T3>//模板的使用 15 bool solve(const T1 &a,cosnt T2 &b,const T3 &c){ 16 17 } 18 19 int main(){ 20 int n=100; 21 Point ts[n]; 22 sort(ts,ts+n,[](const Point& t1,cosnt Point& t2){ 23 if(t1.a!=t2.a)return t1.a<t2.a; 24 return t1.b<t2.b; 25 }); 26 return 0; 27 }
背包问题:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 //背包问题合集。 2 int 0-1(){//每一个物品只能被选择一次 3 //0-1背包 4 int n;//n表示的是有n件物品可以选择,每一件物品有其自己的重量以及价值。 5 int m;//m表示的是背包的总容量。 6 vector<int>dp(n,0);//dp表示的是可以在m容量的背包中装上最大的价值是多少。 7 vector<int>weight(n); 8 vector<int>value(n); 9 for(int i=1;i<=n;i++){//i表示的是物品编号。 10 for(int j=m;j>=weight[i];j--){//j表示的是容量,j从大到小就可以保证每一个物品只被选择一次。。。 11 dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);//这个j是从大到小,而j-weight[i]就是更小的,所以之后一定无法转移到大的上面。。。 12 } 13 } 14 return *max_element(dp.begin(),dp.end()); 15 } 16 17 //完全背包 18 int Wanquan(){ 19 //完全背包,每一个物品可以被多次的选择。。。 20 int n,m; 21 vector<int>dp; 22 vector<int>weight; 23 vector<int>value; 24 for(int i=1;i<=n;i++){ 25 for(int j=weight[i];j<=m;j++){ 26 dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);//这样同一件物品i就可以被多次的选择了。因为我当前的状态可以从之前的状态转移过来。这样转移的状态选的背包可能被多次的选择。 27 //原因是j从小到大遍历的,所以之后的j-weight[i]可能是之前的状态转移的结果 28 } 29 } 30 return *max_element(dp.begin(),dp.end()); 31 } 32 33 //多重背包,是0-1背包与完全背包的结合。 34 35 int Duochong(){ 36 int n,m; 37 vector<int>dp(n,0); 38 vector<int>value; 39 vector<int>weight; 40 vector<int>num;//这个表示每一个物品的个数,这个个数不是1,当然也不是无限个,是有限制的,个数是给出来的。 41 for(int i=1;i<=n;i++){ 42 for(int j=m;j>=weight[i];j--){//这样就可以保证,某一个物品是按照你的要求进行选择个数的,不会无缘无故的叠加之前的状态,从而不知道选择多少个物品。。 43 for(int k=0;k<=num[i];k++){//此时选择的个数是k个物品 44 dp[j]=max(dp[j],dp[j-k*weight[i]]+k*value[i]); 45 } 46 } 47 } 48 return *max_element(dp.begin(),dp.end()); 49 }
线段树模板:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 //树状数组主要处理的是一个数组中更新每一个区段数组的值,求每一个区段数组的和,或者某一段数组的最大值。。。 2 //线段树。。。 3 4 5 // const int maxn=1e6+5; 6 // typedef long long ll 7 // //vector<int>a(maxn,0); 8 // int n,q 9 // int sum[maxn<<2]; 10 // int a[maxn]; 11 // void push_up(int rt){ 12 // sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 13 // } 14 // void build(int l,int r,int rt){//首先建一颗线段树,rt表示的是当前的结点是多少。。。l,r是范围大小 15 // sum[rt]=0; 16 // if(l==r){ 17 // sum[rt]=a[l]; 18 // } 19 // int mid=(l+r)>>1; 20 // build(l,mid,rt<<1); 21 // build(mid+1,r,rt<<1|1); 22 // push_up(rt);//就是将两个叶子结点的值传上去。。。 23 // } 24 // void update(int pos,int val,int l,int r,int rt){//就是更新pos位置的结点值为val...l,r为范围,rt为当前的结点 25 26 27 // } 28 29 // int main(){ 30 31 // return 0; 32 // } 33 34 35 36 37 // const int maxn=1e5+5; 38 // int sum[maxn<<2]; 39 40 // int a[maxn];//表示当前结点存在的数组中。。。 41 42 // void push_up(int rt){ 43 // sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 44 // } 45 46 // void build(int l,int r,int rt){//rt当前结点位置,就是当前的根。。。 47 // sum[rt]=0; 48 // if(l==r){ 49 // sum[rt]=a[l];//表示到达最底下的叶子结点 50 // return; 51 // } 52 // int mid=(l+r)>>1; 53 // build(l,mid,rt<<1);//找根结点的左儿子 54 // build(mid+1,r,rt<<1|1); 55 // push_up(rt); 56 // } 57 58 // //求解一个区间的sum值,写一个函数query 59 // int query(int L,int R,int l,int r,int rt){//我需要查询的区间是[L,R],我当前的区间是(l,r),当前的结点是rt 60 // if(L<=l&&R>=r){ 61 // //这个含义是:我所递归到的区间,在我查询区间的里面,那么这个低估区间当前的结点的sum值直接返回,因为这个值一定是所需要的,不需要再往下做无用的查询了。。。 62 // return sum[rt]; 63 // } 64 // int ans=0; 65 // int mid=(l+r)>>1; 66 // if(L<=mid){ 67 // ans+=query(L,R,l,mid,rt<<1); 68 // } 69 // if(R>mid){ 70 // ans+=query(L,R,mid+1,r,rt<<1|1); 71 // } 72 // return ans; 73 // } 74 75 // void update(int L,int R,int val,int l,int r,int rt){//全部使用区间修改的方法,修改区间为[L,R] 76 // if(L<=l&&R>=r){ 77 // sum[rt]+=val; 78 // return; 79 // } 80 // int mid=(l+r)>>1; 81 // if(L<=mid){ 82 // update(L,R,val,l,mid,rt<<1); 83 // } 84 // if(R>mid){ 85 // update(L,R,val,mid+1,r,rt<<1|1); 86 // } 87 // push_up(rt); 88 // } 89 90 // int main(){ 91 // int n,q; 92 // cin>>n; 93 // for(int i=1;i<=n;i++){ 94 // cin>>a[i]; 95 // } 96 // build(1,n,1); 97 // int m; 98 // // int ans=query(1,n,1,n,1); 99 // // cout<<ans<<endl; 100 // cin>>m; 101 // for(int i=0;i<m;i++){ 102 // int l,r,v; 103 // cin>>l>>r>>v; 104 // update(l,r,v,1,n,1); 105 // cout<<"Ok"<<endl; 106 // int ans=query(1,n,1,n,1); 107 // cout<<ans<<endl; 108 // } 109 110 // } 111 //线段树模板: 112 #include<iostream> 113 #include<cstdio> 114 #include<algorithm> 115 #include<vector> 116 using namespace std; 117 118 const int maxn=1e5+10; 119 typedef long long ll; 120 121 int a[maxn]; 122 123 struct node{ 124 int l,r; 125 ll sum,lazy;//lazy的意思就是有的时候区间更改,只需要改需要修改的一段区间,eg.[1,3]只需修改范围为[1,3]的结点,下面的结点不需要修改,因为你之后不需要访问下面的结点内容的,下面的区间是不需要修改的。。。 126 void update(ll x){ 127 sum+=1ll*(r-l+1)*x; 128 lazy+=x; 129 } 130 }tree[maxn<<2]; 131 132 void push_up(int x){ 133 tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;//做儿子和与右儿子的和。。。 134 } 135 136 void push_down(int x){ 137 int lazyval=tree[x].lazy; 138 if(lazyval){ 139 tree[x<<1].update(lazyval); 140 tree[x<<1|1].update(lazyval); 141 tree[x].lazy=0; 142 } 143 } 144 145 void build(int x,int l,int r){//x是当前结点的编号。。。l,r是区间范围 146 tree[x].l=l; 147 tree[x].r=r; 148 tree[x].sum=tree[x].lazy=0; 149 if(l==r){ 150 tree[x].sum=a[l]; 151 return ; 152 }else{ 153 int mid=(l+r)>>1; 154 build(x<<1,l,mid); 155 build(x<<1|1,mid+1,r); 156 push_up(x); 157 } 158 } 159 160 void update(int x,int l,int r,ll val){//注意这里的l,r是需要更新的范围 161 int L=tree[x].l,R=tree[x].r;//这个L,R是结点当前的[L,R]管辖的范围 162 if(l<=L&&r>=R){//直接更新 163 tree[x].update(val); 164 return; 165 }else{ 166 //先将信息传下去 167 push_down(x); 168 int mid=(L+R)>>1; 169 if(mid>=l){ 170 update(x<<1,l,r,val);//注意这个是l,r表示的是需要查找的范围。。。这个需要查找的范围是不能够改变的。。。 171 } 172 if(r>mid){ 173 update(x<<1|1,l,r,val); 174 } 175 push_up(x); 176 } 177 } 178 179 ll query(int x,int l,int r){ 180 int L=tree[x].l,R=tree[x].r; 181 if(l<=L&&R<=r){//x的区间都是从到小的if 182 return tree[x].sum; 183 }else{ 184 push_down(x);//需要查询某一个区间先push_down一下,这一步一定要有,因为有肯能之前更新的时候,需要查询的这一段区间没有更新,但是现在需要查询这一段了,那么我们一定要先更新一下,然后再进行查询操作。。。 185 ll ans=0; 186 int mid=(L+R)>>1; 187 if(mid>=l){ 188 ans+=query(x<<1,l,r); 189 } 190 if(mid<r){ 191 ans+=query(x<<1|1,l,r); 192 } 193 push_up(x); 194 return ans; 195 } 196 } 197 198 int main(){ 199 int n; 200 scanf("%d",&n); 201 for(int i=1;i<=n;i++){ 202 scanf("%d",&a[i]); 203 } 204 build(1,1,n); 205 int m; 206 scanf("%d",&m); 207 for(int i=0;i<m;i++){ 208 int l,r,v; 209 scanf("%d%d%d",&l,&r,&v); 210 update(1,l,r,v); 211 printf("%lld ",query(1,l,r)); 212 } 213 return 0; 214 }
石子合并:virtual judge搜一下题目/洛谷P1880
直线问题:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 //直线问题: 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<string> 6 #include<vector> 7 #include<cmath> 8 #include<map> 9 #include<cstdlib> 10 #include<sstream> 11 #include<set> 12 #include<queue> 13 using namespace std; 14 typedef long long ll; 15 typedef pair<int,int>PII; 16 typedef pair<ll,ll>PLL; 17 #define make_pair mkp; 18 19 int dp1[400][400];//求解最小值的,,,, 20 int dp2[441][441];//求解最大值得。。。 21 int a[441]; 22 int sum[441]; 23 int main(){ 24 int n; 25 //while(cin>>n){ 26 cin>>n; 27 memset(dp1,0x3f,sizeof(dp1)); 28 memset(dp2,-1,sizeof(dp2)); 29 for(int i=1;i<=n;i++){ 30 cin>>a[i]; 31 } 32 memset(sum,0,sizeof(sum)); 33 //sum[0]=a[0]; 34 for(int i=1;i<=n;i++){ 35 sum[i]=sum[i-1]+a[i];//求解前缀和。。。 36 //cout<<sum[i]<<endl; 37 } 38 for(int i=1;i<=n;i++){ 39 dp1[i][i]=0; 40 dp2[i][i]=0; 41 } 42 for(int len=1;len<n;len++){ 43 for(int i=1;i+len<=n;i++){ 44 int j=i+len; 45 //dp1[i][j]=1e9; 46 for(int k=i;k<j;k++){ 47 dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]);//当前以k为分割点进行分割求解。。。 48 dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]); 49 } 50 } 51 } 52 cout<<dp1[1][n]<<endl; 53 cout<<dp2[1][n]<<endl; 54 //} 55 56 57 return 0; 58 }
曲线问题:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 //曲线问题石子合并 2 #include<iostream> 3 #include<algorithm> 4 #include<cstdio> 5 #include<string> 6 #include<cstring> 7 #include<numeric> 8 #include<vector> 9 #include<map> 10 #include<queue> 11 #include<set> 12 #include<cmath> 13 using namespace std; 14 typedef long long ll; 15 typedef pair<int,int>PII; 16 typedef pair<ll,ll>PLL; 17 18 //这一题是石子合并问题的延伸版本。。。注意一定不要忘记去环的情况。。。 19 20 //注意与直线是类似的,只不过是将环展开就完事了。。。 21 int dp1[450][450];//求解最小值 22 int dp2[400][450];//求解最大值 23 int sum[450];//维护一个前缀和。。。 24 int a[450]; 25 int main(){ 26 int n; 27 //while(cin>>n){ 28 cin>>n; 29 memset(dp1,0x3f,sizeof(dp1)); 30 memset(dp2,-1,sizeof(dp2)); 31 memset(sum,0,sizeof(sum)); 32 for(int i=1;i<=n;i++){ 33 cin>>a[i]; 34 } 35 for(int i=1;i<=n;i++){ 36 a[i+n]=a[i]; 37 } 38 for(int i=1;i<=n*2;i++){ 39 dp1[i][i]=0; 40 dp2[i][i]=0; 41 sum[i]=sum[i-1]+a[i];//求解前缀和。。。 42 } 43 for(int len=1;len<=n;len++){ 44 for(int i=1;i+len<=2*n;i++){ 45 int j=i+len; 46 for(int k=i;k<j;k++){ 47 dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]); 48 dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]); 49 } 50 } 51 } 52 int res1=1e9; 53 int res2=-1; 54 for(int i=1;i<=n;i++){ 55 res1=min(res1,dp1[i][i+n-1]); 56 res2=max(res2,dp2[i][i+n-1]); 57 } 58 cout<<res1<<endl; 59 //cout<<res2<<endl; 60 //} 61 return 0; 62 }