网站建设主,wordpress无域名ip访问,网站建设跟版网,平台开发需要什么技术目录
双指针算法
位运算
离散化
序列合并 双指针算法
题目描述#xff1a;1.输入n个单词#xff0c;每个单词在输入的时候按空格隔开#xff0c;之后打印出每个单词且换行
#includeiostream
#include stringusing namespace std;
int main()
{strin…目录
双指针算法
位运算
离散化
序列合并 双指针算法
题目描述1.输入n个单词每个单词在输入的时候按空格隔开之后打印出每个单词且换行
#includeiostream
#include stringusing namespace std;
int main()
{string arr;getline(cin, arr);int n arr.size();for (int i 0; i n; i){int j i;while (arr[j] ! jn){j;}for (; i j; i){cout arr[i];}cout endl;i j;}return 0;
} 习题2最长连续不重复的子序列 #includeiostream
#include string
#includemath.h
using namespace std;
const int N 100010;
int arr[N], s[N];
int main()
{int n;cin n;int res 0;int i, j;for (i 0; i n; i)cin arr[i];for (i 0,j 0; in; i){s[arr[i]];while (s[arr[i]]!1){s[arr[j]]--;j;}res max(res, i - j 1);}cout res;return 0;
}
位运算 lowbit(x)返回x的最后一位1起始就是x-xx(~x1) 习题:求二进制中1的个数 #includeiostream
#include string
#includemath.h
using namespace std;
int lowbit(int x)
{return x -x;
}
int main()
{int n;cin n;int x;while (n--){int res 0;cin x;while (x)//x若为0则说明没有1了每次减去一个1直到减把1减光为止{x x - lowbit(x);//每次减去一个1直到减把1减光为止res;//res统计一个个数}cout res ;}return 0;
} 也可这样计算
int main()
{int n;cin n;int x;while (n--){int res 0;cin x;for (int i 0; i 32; i){if ((x i) 1 1)res;}cout res ;}return 0;
}
离散化 unique函数本质是将重复的元素移动到数组的末尾最后再将迭代器指向第一个重复元素的下标。
离散化一般是在一个的数组中输入x下标将该值映射到从1开始对应的数组
如这里要给上面数组下标为2的值离散化离散化之后对应的下标为3 思路先用sort函数排序然后用unique去重再删除重复元素用二分查找找下标找到返回即可 一开始数字全是0下标为1的数2为3的数6为7的数5计算0-3的和4-6的和 。7-8的和
思路把所有加了 值的数映射到从一开始的数组即可
有n行所以是10的5次方个数对于m行要输入俩个整数lr这里又是2x10的5次方所以总共是3x10的5次方总共有2x10的9次方个数但是我们只用到了3x10的5次方个数
#includeiostream
#includevector
#includealgorithmtypedef pairint, int PII;
const int N 300010;
int n, m;//都代表行数n是xc的行数,m是区间函数l,r
int a[N], s[N];//a数组用来存离散后的数x对应数字c后的值但这个数组是从1开始与x相对应的若之前x是0在这个数组中就为1s是前缀和
vectorint alls;//存所有要离散化的值(这个数组里存的是下标)
vectorPII add,query;//add是给xc对应x,c的键值query存放要离散化的左右区间
using namespace std;
int find(int x)
{int l 0, r alls.size()-1;while (l r){int mid (l r) / 2;if (alls[mid] x){r mid;}elsel mid 1;}return r1;//由于映射的是从1开始映射,所以给r1。
}
int main(){cin n m;for (int i 0; i n; i){int x, c;cin x c;add.push_back({ x,c });alls.push_back(x);}for (int i 0; i m; i){int l, r;cin l r;query.push_back({l,r});//l,r是下标alls.push_back(l);//由于lr是下标所以也要离散化成对应的数字alls.push_back(r);}//给alls数组去重sort(alls.begin(), alls.end());alls.erase(unique(alls.begin(),alls.end()));//删除重复元素//处理插入:x下标对应数字c后具体的值for (auto item : add)//add中存的是x,c对应的键值{int x find(item.first);//先找到离散化之后的值a[x] item.second;//a是从下标1开始对应x}//预处理前缀和for (int i 1; i alls.size(); i){s[i] s[i - 1] a[i];}//处理询问for (auto item : query){int l find(item.first);//将l离散化后找到具体对应的数值int r find(item.second);cout s[r] - s[l - 1] endl;//计算区间和}return 0;
}序列合并
如果俩段区间有交集就将这俩段区间合并
绿色为合并后的区间 思路按区间左端点排序每个区间都有自己的左端点根据左端点的大小进行排序扫描整个区间扫描过程当中把有交集的区间进行合并。
不会出现红色这种情况因为我们对左端点按照从小到大的顺序进行了排列 当第一个区间合并完之后开始进行合并下一个区间更新start和end的位置 #includeiostream
#includevector
#includealgorithm
#includemath.h
using namespace std;
const int N 100010;
typedef pairint, int PII;
vectorPII segs;//存所有的区间
void merge(vectorPII segs)
{vectorPII res;//存放合并后的区间sort(segs.begin(), segs.end());//先把所有区间排序,pair排序优先以左端点排序再以又端点排序int st -2e9, ed -2e9;//刚开始区间的大小,2*10的-9次方for (auto seg : segs)//从前往后扫描所有的区间{if (seg.first ed)//如果这个区间左边的数大于上一个区间的最后一个数字说明没有交集{if (st ! -2e9)//这个区间如果不是最开始的初始区间就放入res中{res.push_back({ st,ed });}st seg.first, ed seg.second;//更新st和ed让st和ed跟下一个区间进行比较}else//此时有了交集,把右端点更新成最长的哪个{ed max(seg.second, ed);}}if (st ! -2e9)//防止输入一个空区间{res.push_back({ st, ed });//如果不是空区间就把最后一个区间放进去}segs res;
}
int main()
{int n;cin n;for (int i 0; i n; i){int l, r;cin l r;segs.push_back({ l,r });}merge(segs);//进行区间合并cout segs.size() endl;return 0;
}
