蓝桥杯 寒假备赛计划
lanqiao OJ 3226 宝藏排序 ||int main()ll n;cin>>n;ll a[N];in;ll x;i>n;ll sum=0;ll x;i
·
一: 竞赛编程基础
细节
#include<bits\stdc++.h> 万能头文件
const int N=1e5+10; //定义常量
typedef long long ll;//定义外号
输入输出：scanf("%d",s); %s遇到空格或回车会停下 scanf("%[^\n]",s);//排除回车 只要不是回车都可以读入
scanf printf 优势：格式化输入输出 效率高
cin>>s; 输入字符串遇到空格或回车就结束 cout<<s; cin cout 效率较低 数据量较大时候 应该加入取消同步流
取消同步流：ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
string:(迭代器)
string字符串 #include<string> 输入一整行字符串 可以采用getline(cin,s);
(如果头文件中没有加入 using namespace std 声明 应该在变量前加入 std::)
1>可以直接赋值 std::string str3=str2;
2>使用部分字符串初始化字符串 str4=str3.substr(0,5); substr(起始位置，长度)；
3>使用字符数组初始化字符串 char charArray[]="Hello"; std::string str5(charArray);
4>使用重复字符穿实话字符串 std::string str6(5,'A');="AAAAA";
进行printf输出时候 需要将String转换为C风格的进行输出 eg:printf("str=%s\n",str.c_str);
基本操作：
1>获取字符串长度 str.length() str.size()
2>拼接字符串 str1+","+str2 str1.append(",").append(str2)
3>字符串查找 str.find("World");//查找字符串的位置
4>字符串替换：replace str.replace(7,5,"Universe); str.replace(子串起始位置，长度，“替换子串”);
5>提取子字符串 str.substr(位置，长度);
6>字符串比较 str1.compare(str2)==0 相等
常用遍历String方式：
1.for循环直接遍历 2.auto枚举
eg:for(auto i:s){ i='a'; } 无法改变 for(auto &i:s){ i='a';}可以修改
lanqiao OJ 250
1. 反转字符串中的字符
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
getline(cin,s);
int n=s.size();
reverse(s.begin(),s.end());
cout<<s;
return 0;
return 0;
}二：竞赛常用库函数
1.排序 sort
包含在头文件#include<algorithm> sort算法思想快排
sort(起始位置，结束地址下一位，*比较函数)；默认升序函数
起始地址 ：迭代器.begin() 结束地址：迭代器.end()
自定义比较函数
降序排序
bool cmp(const int &u,const int &v){
return u>v;
}
sort(v.begin(),v.end(),cmp);lanqiao OJ 1265
#include <bits/stdc++.h>
using namespace std;
bool cmp(int u,int v){
return u>v;
}
int main()
{
int n;
cin>>n;
int a[500010];
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
sort(a,a+n);
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
cout<<endl;
sort(a,a+n,cmp);
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
return 0;
}2.最值查找
1.min和max函数
min(3,5)=3;
min({1,2,3,4})=1;
max(3,5)=5;
max({1,2,3,4})=4;
2.min_element 和 max_element
min_element(st,ed)返回地址[st,ed)中最小的那个值的下标（迭代器），传入参数为两个地址或迭代器
max_element(st,ed)返回地址[st,ed)中最大的那个值的下标（迭代器），传入参数为两个地址或迭代器
int min=*min_element(a,a+n);
int max=*max_element(a,a+n);
vector<int> v={5,4,2,7,9};
cout<<*max_element(v.begin(),v.end());//得到值而不是地址
3.nth_element
nth_element(st,k,ed) 进行部分排序
在第k个位置前都比其小 第k位置后都比其大 其他数无序
nth_element(v.begin(),v.begin()+3,v.end());
lanqiao OJ 497
3.二分查找
库函数只对数组进行二分查找 数组元素是单调
binary_search函数 通过二分算法来确定序列中是否存在目标元素 函数返回bool值 表示目标是否存在于序列中
bool found=binary_search(numbers.begin(),numbers.end(),target);(target目标)
采用lower_bound函数（数组升序）或upper_bound（数组降序）函数获取元素的位置
lower_bound(st,ed,x)返回地址[st,ed)第一个大于等于x的地址
upper_bound(st,ed,x)返回地址[st,ed)第一个大于x的地址
vector <int> v={8,5,1,7,6,8,9,8};
sort(v.begin(),v.end());
cout<<(lower_bound(v.begin(),v.end(),8)-v.begin());//地址减首地址等于下标
lanqiao OJ 1389
#include <bits/stdc++.h>
using namespace std;
int main()
{
int data[200];
for(int i=0;i<200;i++){
data[i]=4*i+6;
}
int n;
cin>>n;
int m=lower_bound(data,data+200,n)-data;
cout<<m<<endl;
return 0;
}4.大小写转换
islower/isupper函数 用于检查一个字符是否为小写字母或大写字母 函数返回类型为bool
包含#include<cctype>
tolower/toupper函数 tolower函数可以将大写字母转换为小写字母 toupper同理
ascii码大写编码范围65（'A'）-90('Z') 小写字母97('a')-122('z')
ch-'A'+'a' 大写转换为小写 ch-'a'+'A'小写转换为大写
5.全排列
next_permutation()函数 用于生成当前序列的下一个排序 按照字典序对序列进行重新排列 如果存在下一个序列返回true 如果当前序列已经是最后一个排列 则将序列更改为第一个排列
next_permutation(nums.begin(),nums.end());
pre_permutation()函数 用于生成当前上一个排列 按照字典序重新排列 如果存在上一个排列 则将当前序列更改为上一个排列 并返回true 如果当前序列已经是第一个序列 则将薛烈更改为最后一个排列 并返回false
prev_permutation(nums.begin(),nums.end());
6.其他库函数
memset(指针，要设置的值，设置的字节数)；
memset(arr,0,sizeof(arr)) 所有元素都设置为0
memset(arr,1,sizeof(arr)) 所有元素不全为1
swap(T&a,T&b);可以交换任意类型的变量 可以交换任意类型的变量 基本类型或者自定义类型
reverse(开始地址/迭代器，结束地址/迭代器)； 可以翻转各种类型的容器 #include<algorithm>
unique() 可以去除容器相邻重复元素的函数 #include<algorithm>
unique(v.begin(),v.end()) 在[first,end)范围内相邻重复元素去除 只保留第一个出现的元素 后续重复元素都被移除
三：STL
1.pair
位于<utility>头文件中
pair<T1，T2> pa(x,y) pair<int,string> p1(1,"Mike")
pair嵌套 pair<int ,pair<int,int>> pa;
pair自带排序规则是按照first成员进行升序排序 如果first成员相等，则按照second成员进行升序排序
std::vector<std::pair<int,int>>vec;
vec.push_back(std::make_pair(3,2));
vec.push_back(std::make_pair(3,4));
std::sort(vec.begin(),vec.end());2.vector
vector是一个动态数组 可以储存相同类型的元素 #include<vector>
std::vector<T> vec;
vector操作：
容器大小 vec.size()
元素访问 vec[i]
元素添加和删除 push_back()在末尾添加元素
使用insert()函数在指定位置插入元素 使用erase()函数指定位置删除元素
容器大小管理 使用empty()函数检查vector是否为空 还可以使用resize()函数调整vector大小
常用函数
vec.push_back(value);
vec.pop_back(value);
vector 的unique()去重
#include<algorithm>
std::vector<T> vec={....};
std::sort(vec.begin(),vec.end()); //unique去除相邻重复元素
auto last=std::unique(vec.begin(),vec.end());//将重复字母移到尾部
vec.erase(last,vec.end());//删除重复字母
//插入元素
numbers.insert(numbers.begin()+2,3);//插入位置 插入元素
//删除某个元素
numbers.erase(numbers.begin()+4);
//去除重复元素
numbers.erase(std::unique(numbers.begin(),numbers.end()),numbers.end());
//检查是否为空
numbers.empty();
//清空
numbers.clear();
3.list
首先创建一个list容器myList,然后使用push_back()和push_front()函数分别在链表尾部插入元素
std::list<int> myList;
myList.push_back(1);//在链表尾部插入元素
myList.push_front(2);//在链表头部插入元素
//遍历链表并输出元素
for(int num:myList){
std::cout<<num<<" ";
}4.stack
1.stack后进后出的数据结构 包含头文件<stack>
小tip：如果将一个数组元素一次存放入栈 在依次取出 则可以将数组进行翻转
#include<iostream>
#include<stack>
using namespace std;
int main(){
stack<int> myStack;
//向栈中插入元素
myStack.push(10);
myStack.push(20);
myStack.push(30);
myStack.push(40);
//获取栈顶元素
cout<<myStack.top()<<endl;
//弹出栈顶元素
myStack.pop();
//判断是否为空 myStack.empty();
//获取栈的大小 mystack.size();
}5.queue队列
queue先进先出
priority_queue优先队列:priority_queue中的元素按照一定优先级进行排列 默然情况下 按照元素从大到校进行排序 即最大元素位于队列前面
lanqiao OJ 1113 队列
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int m;
cin>>m;
queue<string>V,N;
while(m--){
string op;
cin>>op;
if(op=="IN"){
string name,q;
cin>>name>>q;
if(q=="V") V.push(name);
else N.push(name);
}else{
string q;
cin>>q;
if(q=="V") V.pop();
else N.pop();
}
}
while(V.size()){
cout<<V.front()<<'\n';
V.pop();
}
while(N.size()){
cout<<N.front()<<'\n';
N.pop();
}
return 0;
}lanqiao OJ 741 优先队列 合并果子（类似dp）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
priority_queue<ll,vector<ll>,greater<ll>> pq;//定义优先队列 greater<ll> 从小到大排列
for(int i=1;i<=n;i++){
ll x;
cin>>x;
pq.push(x);
}
ll ans=0;
while(pq.size()>=2){
ll x=pq.top();pq.pop();
ll y=pq.top();pq.pop();
ans+=x+y;
pq.push(x+y);
}
cout<<ans<<endl;
return 0;
}6.set集合
set是一种容器 用于存储一组唯一的元素 并按照一定排序序列进行排序 set中的元素是按照升序排序的 set元素是唯一的 即不允许重复的元素存在 当插入一个重复的元素时 set会自动忽略该元素
#include<iostream>
#include<set>
using namespace std;
struct MyCompare{
bool operator()(const int &a,const int &b) const{
return a>b;//改为降序
}
}
using namespace std;
int main(){
set<int,MyCompare<int>> mySet;
mySet.insert(25);
mySet.insert(17);
mySet.insert(42);
for(const auto& elem:mySet){
cout<<elem<<" ";
}
return 0;
}multiset多重集合 允许存储重复的元素
unordered_set无序集合 用于存储一组唯一的元素 并且没有特定顺序
7.map集合
map用于存储一组键值对 其中每个键（key）是唯一的
map根据键来自动进行排序 并且通过键可以快速查找对应的值
multimap 允许存储多个具有相同键的键值对
unordered_map是一种关联容器 其中每个键（key）都是唯一的 并且没有特定顺序
8.总结
lanqiao OJ 3226 宝藏排序 ||
#include <bits/stdc++.h>
typedef long long ll;
const int N=1e5+10;
using namespace std;
int main()
{
ll n;
cin>>n;
ll a[N];
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
for(int i=0;i<n;i++){
cout<<" "<<a[i];
}
return 0;
}lanqiao OJ 1624 小蓝吃糖果
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
ll n;
cin>>n;
ll x;
int sum=0,mx=0;
for(int i=0;i<n;i++){
cin>>x;
mx=max(mx,x);
sum+=x;
}
if(mx-1>=sum-mx) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n; cin>>n;
priority_queue<int> pq;
ll sum=0;
ll x;
for(int i=0;i<n;i++){
cin>>x;
pq.push(x);
sum+=x;
}
ll mx=pq.pop();
if(sum-mx>=mx-1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}小蓝的括号串
#include <bits/stdc++.h>
const int N=1e5;
using namespace std;
stack<char> stk;
char s[N];
int main()
{
int n;
cin>>n;
cin>>s+1;
bool ans=true;
for(int i=1;i<=n;i++){
if(s[i]=='(') stk.push('(');
else{
if(stk.size()&&stk.top()=='(') stk.pop();
else ans=false;
}
}
if(stk.size()) ans=false;
cout<<(ans?"Yes":"No")<<endl;
return 0;
}快递分拣
#include <bits/stdc++.h>
using namespace std;
map<string,vector<string>> mp;
vector<string> citys;//存放city
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
string a,b;
cin>>a>>b;
if(!mp.count(b)) citys.push_back(b);
mp[b].push_back(a);
}
for(const auto &city:citys){
cout<<city<<' '<<mp[city].size()<<endl;
for(const auto &i:mp[city]){
cout<<i<<endl;
}
}
return 0;
}四:基础算法
1.时间复杂度
2.枚举
基本思想：通过穷举所有可能得情况来解决问题 将问题的解空间的每个可能的解都枚举出来，并进行验证 找到满足问题条件的最优解 适用于规模较小 解空间可举
1.首先确定解空间的维度 即枚举变量个数
2.循环枚举某个范围的数字
3.对每个变量取值范围进行确定
lanqiao OJ 191
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int sum=0;
for(int i=1;i<=n;i++){
int a=i;
while(a){
int t=a%10;
a/=10;
if(t==2||t==0||t==1||t==9){
sum+=i;
break;
}
}
}
cout<<sum;
return 0;
}lanqiao OJ 152
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
int cnt=0;
cin>>n;
int a,b,c;
cin>>a>>b>>c;
for(int i=1;i<=n;i++){
if(i%a!=0&&i%b!=0&&i%c!=0){
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}lanqiao OJ 3227
#include <bits/stdc++.h>
using namespace std;
map<int,int> mp;
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int x;
cin>>x;
mp[x]++;
}
}
for(const auto&[x,y]:mp){
if(2*y>m*n) cout<<x;
}
return 0;
}#include<bits/stdc++.h>
using namespace std;
int main(){
int t=0;
cin>>t;
while(t--){
int m,k;
cin>>m>>k;
vector<int> arr(m);
set<int> s;
for(int i=0;i<m;i++){
cin>>arr[i];
s.insert(arr[i]);
}
int num=10000;
for(auto &x:s){//遍历元素
int sum=0;
for(int i=0;i<m;i++){//遍历墙数目
if(arr[i]==x) continue;//如果涂的颜色与此次颜色一致 跳过
sum+=1;//如果不一致则加一
i+=k-1;//因为每次涂k区间这么大
}
num=min(num,sum);
}
cout<<num<<endl;
}
return 0;
}小蓝的漆房
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main(){
int T=1;cin>>T;
while(T--){
int n,k,res=0x3f3f3f3f;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=60;i++){
int cnt=0;
for(int j=1;j<=n;j++) b[j]=a[j];
for(int j=1;j<=n;j++){
if(b[j]!=i){
for(int h=j;h<=j+k-1;h++) b[h]=i;
j=j+k-1;
cnt++;//记录涂漆天数cnt
}
}
res=min(res,cnt);//最少天数
}
cout<<res<<endl;
}
return 0;
}注意事项：
<1>枚举时要注意数据范围，列出所有可能情况，不能重复，不能遗漏
<2>枚举时要尽量缩小数据范围，提高计算效率，或者进行优化
<3>根据题目要求注意判断，挑选符合条件的解输出
3.模拟
通过模拟实际情况来解决问题
lanqiao OJ 549 扫雷
#include <iostream>
using namespace std;
const int N=150;
int mp[N][N],ans[N][N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]==1){
ans[i][j]=9;
continue;
}
//扫描四个方位
for(int _i=max(1,i-1);_i<=min(n,i+1);++_i){
for(int _j=max(1,j-1);_j<=min(m,j+1);++_j){
if(mp[_i][_j]) ans[i][j]++;
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
return 0;
}lanqiao OJ 551 花园浇水 用两个二维数组 分别表示当前和后一分钟的灌溉情况 持续按照题意更新数组即可
#include <iostream>
using namespace std;
const int N=120;
int a[N][N],b[N][N];
int main()
{
int n,m;
cin>>n>>m;
int cnt=0;
int t;
cin>>t;
for(int i=1;i<=t;i++){
int x,y;
cin>>x>>y;
a[x][y]=1;
}
int k;
cin>>k;
while(k--){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==1){
b[i][j]=1;
b[i-1][j]=1;
b[i+1][j]=1;
b[i][j+1]=1;
b[i][j-1]=1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]=b[i][j];
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==1){
cnt++;
}
}
}
cout<<cnt;
return 0;
}
lanqiao OJ 498
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int a[N];
int dfs(int dep){//dep表示当前深度
int res=1;
for(int i=a[dep-1]/2;i>=1;i--){
a[dep]=i;
res+=dfs(dep+1);
}
return res;
}
int main(){
int n;
cin>>n;
a[1]=n;
cout<<dfs(2)<<endl;
return 0;
}小蓝和小桥的挑战 标志位放在里面
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a[N],t,n;
int main(){
cin>>t;
while(t--){
cin>>n;
int sum=0,z=0;
for(int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];//看看和是否为0
if(!a[i]) z++;//0的个数有多少个 积改0的个数
}
sum+=z;
if(sum==0) cout<<z+1<<endl;//和为0 只需要改一个
else cout<<z<<endl;
}
return 0;
}
//利用数字来进行求和查看是不是匹配
#include<bits/stdc++.h>
using namespace std;
map<char,int>mp{//利用键值对
{'A',0},
{'C',1},
{'G',2},
{'T',3}
};
int main(){
int n;
cin>>n;
string a,b;
cin>>a>>b;
int cnt=0;
for(int i=0;i<n;i++){
if(mp[a[i]]+mp[b[i]]!=3){
for(int j=i+1;j<n;j++){
if(mp[a[i]]+mp[b[j]]==3&&mp[a[j]]+mp[b[i]]==3){
swap(b[i],b[j]);
break;
}
}
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}4.递归
关键要素： 递归终止条件：满足该条件递归终止 递归调用：用于解释规模更小的子问题 再将子问题的答案合并成当前问题的答案
实现过程：1.大问题->小问题 2.递归解决小问题3.递归终止结束递归
lanqiao OJ 760
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N];
int dfs(int dep){
int res=1;
for(int i=a[dep-1]/2;i>=1;i--){
a[dep]=i;
res+=dfs(dep+1);//
}
return res;
}
// 6 3 1 1走到头返回res res=1 res+=1 res=2 再return res res+=res=3
int main(){
int n;
cin>>n;
a[1]=n;
cout<<dfs(2)<<endl;
return 0;
}5.进制转换
1.将任意进制转换为十进制
ll x=0;
for(int i=1;i<=n;i++){
x=x*k+a[i];
}
cout<<x<<endl;2.将十进制转换为任意进制
ll x;
cin>>x;
while(x) a[++cnt]=x%k; x/=k;
reverse(a+1,a+1+cnt);lanqiao OJ2489
#include<bits/stdc++.h>
using namespace std;
int a[20];
int main()
{ int x=0;
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
string s="2021ABCD";
for(int i=0;i<s.size();i++)
{
if('0'<=s[i]&&s[i]<='9') a[i]=s[i]-'0';
else a[i]=s[i]-'A'+10;
}
for(int i=0;i<s.size();i++)
{
x=x*16+a[i];
}
cout<<x<<endl;
return 0;
}lanqiao OJ2095
#include<bits/stdc++.h>
using namespace std;
int main(){
string s="2022";
long long x=0;
for(int i=0;i<4;i++){
x=x*9+s[i]-'0';
}
cout<<x;
return 0;
}lanqiao OJ1230
6.前缀和
前缀和可以求数组的一段区间和：sum(l,r)=pre[r]-pre[l-1] 只适用于a数组为静态数组的情况 即a数组中的元素在区间和查询过程中不会进行修改
如果需要实现“先区间修改 再区间查询” 可以使用差分数组 “一边修改，一边查询” 需要使用树状数组或线段树等数据结构
//数组下标均从1开始 a[0]=0
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+a[i];
}lanqiao OJ 3382
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p=1e9+7;
const int N=1e5+10;
ll a[6][N],prefix[6][N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[1][i];
for(int i=2;i<=5;i++){
for(int j=1;j<=n;j++){
a[i][j]=a[i-1][j]*a[1][j]%p;
}
}
for(int i=1;i<=5;i++){
for(int j=1;j<=n;j++){
prefix[i][j]=(prefix[i][j-1]+a[i][j])%p;
}
}
while(m--){
int l,r,k;
cin>>l>>r>>k;
cout<<(prefix[k][r]-prefix[k][l-1]+p)%p<<endl;
}
return 0;
}lanqiao OJ 3419 平衡串 将L看成1 将Q看成-1 只有当某个区间的和为0 字符串是平衡的
#include<bits/stdc++.h>
using namespace std;
#define ll long long;
int a[1001];
string str;
int res[1001];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>str;
memset(a,0,sizeof(a));
memset(res,0,sizeof(res));
for(int i=0;i<str.size();++i)
{
if(str[i]=='L') a[i+1]=a[i]+1;//l加一P减一
else a[i+1]=a[i]-1;
}
a[0]=999;
for(int i=1;i<str.size();++i)//只需要到倒数第二位就行
{
for(int j=i+1;j<=str.size();++j)//要到最后一位
{
if(a[i-1]==a[j])//i到j之间字符数量相等
{
res[i]=j-i+1;//以i起始的平衡串的长度
}
}
}
cout<<*max_element(res,res+1002)<<endl;
return 0;
}#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e5+10;
int n;
PII q[N];
ll pre[N],nex[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>q[i].y>>q[i].x;//重量 初始位置
}
sort(q+1,q+n+1);//对初始位置进行排序
ll s=0;
//对重量和位置进行前缀和
for(int i=1;i<=n;i++){
pre[i]=pre[i-1];
pre[i]+=s*(q[i].x-q[i-1].x);
s+=q[i].y;//重量
}
s=0;
for(int i=n;i>=1;i--){
nex[i]=nex[i+1];
nex[i]+=s*(q[i+1].x-q[i].x);
s+=q[i].y;//重量
}
ll res=1e18;//开大
for(int i=1;i<=n;i++){
res=min(res,pre[i]+nex[i]);
}
cout<<res<<endl;
return 0;
}#include<bits/stdc++.h>
using namespace std;
int t,n,k;
const int N=2*10e5+10;
typedef long long ll;
ll a[N],sum[N];
int main(){
cin>>t;
while(t--){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
memset(sum,0,sizeof sum);
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i];
}
ll ans = 0;
int pos = 0;
while(k >= 0){//利用双指针 枚举所有情况 避免贪心
ans = max(ans, sum[n - k] - sum[pos]);
pos += 2;
k--;
}
cout << ans << "\n";
}
return 0;
}
7.差分
差分 diff[i]=a[i]-a[i-1] 对差分数组做前缀和可以还原为原数组
可以利用差分数组实现快速的区间修改
diff[l]+=x;
diff[r+1]-=x;在修改完成后，将前缀和恢复原数组
差分数组不可实现“边修改边查询”
lanqiao OJ 3291
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],diff[N];
int main(){
int n,m;
while(cin>>n>>m){
for(int i=1;i<=n;i++){
cin>>a[i];
}
a[0]=0;
for(int i=1;i<=n;i++){
diff[i]=a[i]-a[i-1];
}
while(m--){
int l,r,v;
cin>>l>>r>>v;
diff[l]+=v;
diff[r+1]-=v;
}
//前缀和还原
for(int i=1;i<=n;i++) a[i]=a[i-1]+diff[i];
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}lanqiao OJ 1276
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//1e9 开longlong
const int N=1e6;
int main(){
ll a[N],diff[N];
int n,q;
cin>>n>>q;
a[0]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
diff[i]=a[i]-a[i-1];
}
while(q--){
int l,r,x;
cin>>l>>r>>x;
diff[l]+=x;
diff[r+1]-=x;
}
for(int i=1;i<=n;i++){
a[i]=a[i-1]+diff[i];
}
for(int i=1;i<=n;i++){
if(a[i]<0){
a[i]=0;
}
cout<<a[i]<<" ";
}
return 0;
}#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
int n,q;
ll a[N],b[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=q;i++){
int l,r,c;
cin>>l>>r>>c;
b[l]+=c,b[r+1]-=c;
}
//利用前缀和进行求和 这样就能实现区域段的查询
for(int i=1;i<=n;i++) b[i]+=b[i-1];
for(int i=1;i<=n;i++) cout<<a[i]+b[i]<<" ";
return 0;
}//Sx1,y1+=c;
//Sx1,y2+1-=c;
//Sx2+1,y1-=c;
//Sx2+1,y2+1+=c;
//差分数组 s[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]
//恢复原矩阵 ai,j=ai-1,j+ai,j-1-ai-1,j-1+si,j
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
ll a[N][N],s[N][N];
int n,m,q;
void insert(int x1,int y1,int x2,int y2,int c){
s[x1][y1]+=c;
s[x1][y2+1]-=c;
s[x2+1][y1]-=c;
s[x2+1][y2+1]+=c;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
insert(i,j,i,j,a[i][j]);
}
}
while(q--){
int x1,y1,x2,y2,c;
cin>>x1>>y1>>x2>>y2>>c;
insert(x1,y1,x2,y2,c);
}
//求原数组
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+s[i][j];
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
//需要计算每一分钟需要消耗的热水量
//统计得到每一分钟需要的热水数量
//sl[i]+=p; sr[i]-=p;
//最后对数组S进行求前缀和 得到某一时刻X的热水使用量为Sx 检查是否超过M
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
int n,w;
const int N=200010;
void solve(){
cin>>n>>w;
vector<ll> s(N);
for(int i=0;i<n;i++){
int l,r,c;
cin>>l>>r>>c;
s[l]+=c;
s[r]-=c;
}
for(int i=1;i<N;i++) s[i]+=s[i-1];
for(int i=0;i<N;i++){
if(s[i]>w){
cout<<"No"<<endl;
return;
}
}
cout<<"Yes"<<endl;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
solve();
return 0;
}8.贪心
基本原理：达到局部最优解
贪心局限性：不能保证全局最优解 但在某些问题上具有高效性
贪心实现步骤：1.确定问题的最优子结构 2.构建贪心选择的策略 3.通过贪心选择逐步求解问题
lanqiao OJ3412 简单排序模型
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int main(){
int n;
cin>>n;
int w[N];
for(int i=1;i<=n;i++){
cin>>w[i];
}
sort(w+1,w+1+n);
int mn=w[2]-w[1];
for(int i=1;i<n;i++){
mn=min(mn,w[i+1]-w[i]);//min函数 中不可用long long
}
cout<<mn;
return 0;
}lanqiao OJ545 总操作数一定情况下最小代价模型 每次选择合并代价小的部落合并
类似于DP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll>> pq;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
ll x;
cin>>x;
pq.push(x);
}
ll ans=0;
while(pq.size()>1){
ll x=pq.top();pq.pop();
ll y=pq.top();pq.pop();
ans+=x+y;
pq.push(x+y);
}
cout<<ans<<endl;
return 0;
}lanqiao OJ532 最小数目贪心问题 挑最贵的和最便宜的在一组
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int main()
{
int w,n;
cin>>w>>n;
int a[N];
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
int l=1,r=n,ans=0;
while(l<=r){
ans++;
if(l==r){
break;
}
if(a[l]+a[r]<=w){
l++;
r--;
}else{
r--;
}
}
cout<<ans<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
bool cmp(int a,int b){
return a>b;
}
int n,k;
ll a[N],b[N],c[N],ans=0;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
ans+=a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
c[i]=b[i]-a[i];
}
sort(c+1,c+1+n,cmp);//降序
k=min(n,k);//细节 题目中没有告诉谁大谁小
while(k){
if(c[k]>=0) ans+=c[k];//必须大于0才能翻 还有k卡条件
k--;
}
cout<<ans<<endl;
return 0;
}//找两个数的最小差值
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,w[N];
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>w[i];
}
sort(w,w+n);//升序
int ans=1e9;
for(int i=1;i<n;i++) ans=min(ans,w[i]-w[i-1]);//注意i的起始位置
cout<<ans<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//多个1e9数相加 会爆int
#define all(s) s.begin(),s.end()
int n;
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
std::vector<int> a, b;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
x = abs(x);
if (i % 2) b.push_back(x);
else a.push_back(x);
}
if (n == 1) {
cout << abs(a[0]) << '\n';
return 0;
}
int mi = *min_element(all(a));
int mx = *max_element(all(b));
LL ans = accumulate(all(a), 0LL) - accumulate(all(b), 0LL);
if (mx >= mi)ans += 2 * mx - 2 * mi;//细节 主要是要减的最大数 大于 加的最小数 才是有效的
cout << ans << '\n';
return 0;
}//细节
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,k,a[N];
ll s[N];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;i++){
if((s[i-1]+(a[i]+1)/2)>k){
cout<<i-1<<endl;
return 0;
}
}
cout<<n<<endl;
return 0;
}
9.双指针
并非真正的指针 一般用两个变量来表示下标 往往和单调性和排序联系在一起
暴力打题时间复杂度O(n^2) 双指针利用“单调性” 可以优化到O(n)
常见双指针模型：对撞指针 快慢指针
1.对撞指针
对撞指针求解步骤
1.使用两个指针 left right ，left指向序列第一个元素，即left=1,right指向序列最后一个元素 right=n
2.在循环体中将左右指针相向移动 满足一定条件，left++,right--
3.直到两个指针相撞 left==right 或者满足其他要求的特殊要求 跳出循环体
2.快慢指针
快慢指针求解步骤：
1.使用两个指针l,r。l一般指向序列的第一个元素 l=1 r一般指向序列第零个元素 r=0
2.循环体将左右指针向右移动 满足一定条件 快指针右移 满足一定条件慢指针右移
3.当左右指针移动到数组尾端 或者两指针相交 或者满足其他特殊条件时候跳出循环体
lanqiao OJ 1372
lanqiao OJ 1621
10.二分法
将问题搜索范围一分为二
1.整数二分
//找到升序数组a中x第一次出现的位置
int l=0,r=1e9;
while(l+1!=r){
int mid=(l+r)/2;
if(a[mid]>=x) r=mid;
else l=mid;
}lanqiao OJ 1389
2.浮点二分
//浮点查找不再是在有序数组上进行查找 而是在某个实数范围内进行查找
double l=0,r=1e9,eps=1e-6;
while(r-l>=eps){
double mid=(l+r)/2;
if(f(mid)>=0) r=mid;
else l=mid;
}3.二分答案
bool check(int mid){
bool res=true;
return res;
}
int main(){
int l=0,r=1e9;
while(l+1!=r){
int mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
}//假设答案是x,那么我们需要的花朵是x*k朵 提供的有效花朵min(ai,k)
//统计出每个人可提供的有效花朵的和是否达到x*k 达到则说明可以凑出x束花束
//注意二分的上界不可开小 判断res>x*k x*k可能会爆long long 则修改为 res/x>=k
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
const int N = 200010;
int n, k;
void solve()
{
cin >> n >> k;
std::vector<LL> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
auto check = [&](LL x) {
LL res = 0;
for (int i = 0; i < n; ++i) {
res += min(a[i], x);
}
return res/x>=k;
};
LL l = 0, r = 2e14;
while (l < r) {
LL mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << r << '\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << setiosflags(ios::fixed) << setprecision(2);
int t = 1;
while (t--)
{
solve();
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=2e5+10;
int n,m,k;
ll a[N],b[N];
void solve(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]+=a[i-1];
}
for(int i=1;i<=m;i++){
cin>>b[i];
b[i]+=b[i-1];
}
int ans=0;
for(int i=0;i<=n;i++){
if(a[i]>k) break;
ll res=k-a[i];
int x=upper_bound(b,b+m+1,res)-b-1;//upper_bound 进行查找的是在[st,ed)第一个大于等于x的地址 -(b+1)等于下标
ans=max(ans,i+x);
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
solve();
return 0;
}
//二分题目好多都是 给出不同数目的某物=物体 要求分割相同数目的最大份数
//题目要求我们用N块原料 制作出K个高度完全相同的月饼 且这k个月饼高度要尽量高
//选定一个高度h 然后将每块原材料切割成高度为h的月饼 那么原材料最多可以分割成 [原材料/h]的月饼
//所有原材料切割完得到的月饼总数 cnt>=k则说明能切除成K个月饼
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,k;
cin>>n>>k;
vector<int> v(n);
for(int i=1;i<=n;i++){
cin>>v[i];
}
int l=1,r=1e9,res=-1;
while(l<=r){
int mid=(l+r)>>1;
int cnt=0;
for(int i=1;i<=n;i++){
cnt+=v[i]/mid;
}
if(cnt>=k){//已经切出来了 高度应该再高一些
l=mid+1,res=mid;
}else{
r=mid-1;//高度应该低一些
}
}
cout<<res<<endl;
}//二分搜索＋前缀和
//找到一个数组A的三元组数组的第K小元素 S=min(A[i],A[j],A[k])
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q,i,a[300005],cnt[300005],k;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
for(i=0;i<n;i++){
cnt[i]=(n-i-1)*(n-i-2)/2;
if(i>0){
cnt[i]+=cnt[i-1];
}
}
while(q--){
cin>>k;
cout<<a[lower_bound(cnt,cnt+n,k)-cnt]<<endl;
}
return 0;
}
11.构造
//X的最小值为2 若X=1必定无解
//如果X<=10的6次方+1 说明肯定存在一种构造方式是B=C=1，A=X-C满足题目要求 由于B C已经最小 即满足字典序最小
//如果X>=10的6次方+1 为了让B最小 让A为最大的10的6次方 因为C不会大于A 所以B的最小值肯定是 [X/A] 如果A可以整除X 则此时C=0不符合题意 C=A=10的6次方
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 1e9;
void solve(){
ll x;
cin >> x;
if(x == 1){
cout << -1 << '\n';
}else{
ll maxx = 1e6, a, b, c;
if(x <= maxx + 1){
a = x - 1, b = 1, c = 1;
}else{
a = maxx, c = x % maxx == 0 ? maxx : x % maxx, b = (x - c) / a;
}
cout << a << " " << b << " " << c << '\n';
}
}
int main(){
ios::sync_with_stdio,cin.tie(0),cout.tie(0);
int t = 1;
cin >> t;
while(t--){
solve();
}
return 0;
}
//有效序列和最小为2
//若序列和为偶数 用质数2 形成序列
//若序列和为奇数 用质数3 剩下和X-3必定为偶数 用质数2来表示
//gcd(a,b)>1 包含情况有ab都为偶数 ab都为奇数 但有公约数 相减直接为0
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t;
cin>>t;
while(t--){
ll a,b;
cin>>a>>b;
if(a<2||b<2){
cout<<-1<<endl;
}else{
if(__gcd(a,b)>1){
cout<<0<<endl;
}else{
cout<<1<<endl;
}
}
}
return 0;
}
//构造最小字符集 使得这n个字符串从小到大进行排序
//先假定字符集大小为k 那么可以将第i个字符串si看成一个长度的绝对值为si的k进制数 考虑两个相邻的字符串si和si+1
//考虑二分去找最小合法字符集的大小 并且考虑如何验证二分出来的k的大小是否合法
//1.若|si|<|si+1| 如果si是si+1的前缀 就可以满足si<si+1 只需要在si后面一直补充当前字符集中最小的字母直到长度等于|si+1|
//2.若|si|>|si+1| 如果si需要去掉长度为|si|-|si+1|的后缀 然后再将最后一位加1后 发现该位置上的字符大于当前字符集中最小字母加k之后的字母时 需要向前进位
//如果第一个位置发生了进位 则k不合法 如果到最后都没发生进位 那么这个k合法
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
struct node{
int pos,num;
}stk[maxn];
int top;
int n,s[maxn];
void insert(int v,int x){
while(top>1&&stk[top].pos>v)top--;
if(stk[top].pos==v)stk[top].num++;
else stk[++top]=(node){v,1};
if(top>1&&stk[top].num==x)insert(v-1,x);
}
bool check(int x){
stk[top=1]={0,0};
for(int i=2;i<=n;i++){
if(s[i]<=s[i-1])insert(s[i],x);
}
return stk[1].num==0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&s[i]);
int num=0;
for(int i=2;i<=n;i++)if(s[i]>s[i-1])num++;
if(num==n-1){
printf("1");
return 0;
}
int l=2,r=1e6;
int ans;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
printf("%d",ans);
return 0;
}12.位运算
位运算是一种对二进制数的位进行操作的运算方式
常见位运算：
- &按位与 只有两个位都为1时，结果位才为1，否则为0。
- |按位或 只要有两个位有一个为1，结果就为1，否则为0。
- ^按位异或 当两个位不同时，结果位为1，否则为0。 不会进位
- ~按位取反 对每个数进行取反操作
- <<左移 将一个数的二进制向左移动指定位数 低位补0 左移操作相当于对原数进行乘2的幂次方的操作
- >>右移 将一个数的二进制向右移动指定位数 高位补0 左移操作相当于对原数进行除2的幂次方的操作
技巧：
- 判断数字奇偶性 x&1结果为1说明为奇数 结果为0 说明是偶数
- 获取二进制数的某一位 x>>i&1 表示x的二进制表示中的第i位
- 修改二进制中某一位为1 x|(1<<i)
- 快速判断一个数字是否为2的幂次方 x&(x-1)
lanqiao OJ 1331
#include <iostream>
using namespace std;
const int N=1050;
int main()
{
unsigned int x;//无符号类型
cin>>x;
int ans=0;
while(x){
if(x&1) ans++;
x>>=1;//如果有符号 最高位为符号位时 会有无限的1
}
cout<<ans<<endl;
return 0;
}lanqiao OJ 3691 区间或
//拆位算贡献
//将整个问题划分为31个部分 分别表示数组元素二进制表示的第0位 第1位 ……
//计算每一个部分的前缀和 判断这一个位是否为1 如果是就算上这一位对答案的贡献
#include <iostream>
using namespace std;
const int N=1e5+9;
int a[N],prefix[35][N];//前缀和
int main()
{
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int w=0;w<=30;w++){//位 每个位扫描
for(int i=1;i<=n;i++) prefix[w][i]=prefix[w][i-1]+(a[i]>>w&1);
}
while(q--){
int l,r;
cin>>l>>r;
int ans=0;
for(int w=0;w<=30;w++){
ans+=(1<<w)*(prefix[w][r]-prefix[w][l-1]?1:0);
}
cout<<ans<<endl;
}
return 0;
}
//转化条件：因数个数为偶数个 =》不是完全平方数 试除法
//正难则反 计算有多少个数组的异或和为完全平方数 用总区间个数减
//先求前缀异或和 prexor（完全平方数） 枚举所有平方数sq 然后对于prexor[i]^prexor[j]=sq 于是统计有多少个j满足j<i,且prexor[j]=prexor[i]^sq
//总区间个数 n*(n+1)/2
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int a[N],prefix[35][N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
}//出现次数为偶数 连续偶数个异或之后 结果为0 不会影响结果 等于直接计算第l个数到第r个数的异或和即可
//前缀异或 s[i]表示第一个数到第i个数的前缀异或和
//对于每次访问 只需要计算s[r]^s[l-1]
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int a[N],s[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m,l,r;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]^a[i];
}
while(m--){
cin>>l>>r;
cout<<(s[r]^s[l-1])<<endl;
}
return 0;
}//第k次出列 队伍只剩下一个人 那么编号二进制一定为1000...00(k个0)
//问题转化为求不大于n的最大二次幂
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int v=0;
while((1<<v)<=n){//v此时不合适
v++;
}
cout<<(1<<(v-1))<<endl;//输出应该减1
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
if(n>8192){
cout<<0<<endl;
return 0;
}
vector<ll> a(n+1);
ll ans=1;
ll sum=1;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]^=a[i-1];
sum=sum*a[i]%mod;
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
ll now=a[i]^a[j];
sum=sum*now%mod;
}
}
cout<<sum<<endl;
return 0;
}
排序
冒泡排序：
时间复杂度O(n^2)
for(int i=1;i<=n;i++){
for(int j=1;j<=i-1;j++){
}
}lanqiao OJ 3225
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[1010];
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i-1;j++){
if(a[i]<a[j]){
swap(a[i],a[j]);
}
}
}
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
return 0;
}选择排序：
将a[1]-a[n]中最大值放到a[n] 时间复杂度O(n^2)
//i表示当前要确定的位置比
for(int i=n;i>=1;i--){
int max_id=1;
for(int j=1;j<=i;j++){
if(a[j]>a[max_id]) max_id=j;
}
swap(a[i],a[max_id]);
}插入排序：
时间复杂度O(n^2）
//i表示当前要确定的位置
for(int i=2;i<=n;i++){
//此时[1.i]已经为有序数组
int val=a[i],j;
for(j=i;j>1&&val<a[j-1];j--){
a[j]=a[j-1];
}
a[j]=val;
}快速排序：
分治法 原理：将一个数组分为两个子数组，其中一个子数组的所有元素都小于另一个子数组的元素，然后递归地对着两个数组进行排序
时间复杂度：O(nlogn)
解题思路：
1.确定分界点 随机两边界中间都可
2.调整区间：小于等于x的在分界点的左边，大于等于x的在分界点的右边
3.递归处理左右两段
#include<iostream>
using namespace std;
const int N = 100010;
int q[N];
void quick_sort(int q[] , int l , int r){
int i = l - 1,j = r + 1,x = q[l + r >>1];
if(l >= r) return;//排序完毕
while(i < j){
do i++;while(q[i] < x);
do j--;while(q[j] > x);
if(i < j) swap(q[i],q[j]);//i<j重点
}
quick_sort(q, l , j);
quick_sort(q, j+1, r);
}
int main(){
int n;
scanf("%d",&n);
for(int i = 0; i < n;i ++){
cin>>q[i];
}
quick_sort(q,0,n-1);
for(int j=0;j < n ;j ++){
cout<<q[j]<<' ';
}
return 0;
}归并排序：
解题步骤：
1.分界点：(l+r)/2
2.递归排序左右两段
3.归并合二为一
分成两段 从两头开始比较大小，将较小的数放入新开的数组
#include<iostream>
using namespace std;
const int N=1e5+10;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r){
int mid=l+r >>1;
if(l>=r) return;
merge_sort(q,l,mid),merge_sort(q,mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r){
if(q[i]<=q[j]) tmp[k++]=q[i++];//引入k,当i=mid,i++,i=mid+1,j还未循环完直接进去while
else tmp[k++]=q[j++];
}
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&q[i]);
}
merge_sort(q,0,n-1);
for(int i=0;i<n;i++){
printf("%d ",q[i]);
}
return 0;
}五：搜索
1.回溯法
回溯法：一般使用DFS实现，通过某种关系构造出来的搜索数，搜索树一般是排列型搜索树（每次枚举选哪个）和子集型搜索树（每个元素选或者是不选）
DFS从起始节点开始沿着一条路径尽可能深入探索（一条路走到黑），知道无法继续为止，然后回溯到前一个节点，继续探索其他路径，直到遍历完整个图或者树
DFS一般使用栈和递归来实现
模版
int a[N];
bool vis[N];
void dfs(int dep){
if(dep==n+1){
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
//排除不合法的路径
if(vis[i]) continue;
//修改状态
vis[i]=true;
a[dep]=i;
dfs(dep+1);
vis[i]=false;
a[dep]=0;//可以省略 下一次会遮盖
}
}lanqiao OJ 1508
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=15;
int n,ans;//方案数
int vis[N][N];//表示被多少个皇后占领了
void dfs(int dep){
if(dep==n+1){
ans++;
return;
}
for(int i=1;i<=n;i++){
if(vis[dep][i]) continue;
for(int _i=1;_i<=n;_i++) vis[_i][i]++;
for(int _i=dep,_j=i;_i>=1&&_j>=1;_i--,_j--) vis[_i][_j]++;
for(int _i=dep,_j=i;_i<=n&&_j>=1;_i++,_j--) vis[_i][_j]++;
for(int _i=dep,_j=i;_i<=n&&_j<=n;_i++,_j++) vis[_i][_j]++;
for(int _i=dep,_j=i;_i>=1&&_j<=n;_i--,_j++) vis[_i][_j]++;
dfs(dep+1);
for(int _i=1;_i<=n;_i++) vis[_i][i]--;
for(int _i=dep,_j=i;_i>=1&&_j>=1;_i--,_j--) vis[_i][_j]--;
for(int _i=dep,_j=i;_i<=n&&_j>=1;_i++,_j--) vis[_i][_j]--;
for(int _i=dep,_j=i;_i<=n&&_j<=n;_i++,_j++) vis[_i][_j]--;
for(int _i=dep,_j=i;_i>=1&&_j<=n;_i--,_j++) vis[_i][_j]--;
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
dfs(1);
cout<<ans<<endl;
return 0;
}lanqiao OJ 182时间戳
//采用时间戳来解题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+9;
int n,dfn[N],a[N],col[N],idx,mindfn;
//idx 表示当前的时间
int dfs(int x){
dfn[x]=++idx;//给一个新的时间戳
if(dfn[a[x]]){
if(dfn[a[x]]>=mindfn) return dfn[x]-dfn[a[x]]+1;
return 0;
}
return dfs(a[x]);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int ans=0;
for(int i=1;i<=n;i++){
if(!dfn[i]){//没有时间戳 没有被走过
mindfn=idx+1;//更新此时时间
ans=max(ans,dfs(i));
}
}
cout<<ans<<endl;
return 0;
}lanqiao OJ 178
全球气候
求多少岛屿被完全淹没
先用dfs将不同的岛屿染上不同的颜色 然后计算最后剩下岛屿的颜色有多少种
2.剪枝
找到某些特殊的数学关系或者逻辑关系 通过让搜索树尽可能浅而小 从而达到降低时间复杂度的目的
lanqiao OJ 2942
//最少可以分成几队
//由于n较小 队伍数从小到大进行枚举 “最少队伍数量” 然后判断在这个队伍数量的情况下 是否可以成功分组
//判断合法性的函数 可以用搜索来实现 确定总队伍数量 对于每个人枚举他所属的队伍 用回溯法解决
//剪枝策略:当某个人进入队伍时 直接检查是否存在倍数关系 如果存在直接跳过
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int a[N],n;
vector<int> v[N];
//cnt表示队伍数量 dfs返回在cnt个队伍下是否可以成功分组
bool dfs(int cnt,int dep){// bool 类型 不可return 返回上一步 只有void 可以
if(dep==n+1){
return true;
}
//枚举每个人所属的队伍
for(int i=1;i<=cnt;i++){
bool tag=true;
for(const auto&j:v[i]){//剪枝 减去倍数关系
if(a[dep]%j==0){
tag=false;
break;
}
}
if(!tag) continue;
v[i].push_back(a[dep]);//加入这个队伍
if(dfs(cnt,dep+1)) return true;
v[i].pop_back();
}
return false;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
if(dfs(i,1)){
cout<<i<<endl;
break;
}
}
return 0;
}lanqiao OJ 3008
lanqiao OJ 3075
3.记忆化
将搜索过程中会重复计算且结果相同的部分保存下来，作为一个状态，下次访问到这个状态直接将这个子搜索的结果返回 而不需要重新计算一遍
通常会使用数组或map来进行记忆化，下标一般和dfs参数表对应
01 斐波那契数列 （带备忘录的搜索）
lanqiao OJ 3820
lanqiao OJ 216
4.flood fill
1.池塘计数
#include<iostream>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=1010;
const int M=N*N;
int n,m;
char g[N][N];
PII q[M];
bool st[N][N];
void bfs(int sx,int sy){
int hh=0,tt=0;
q[0]={sx,sy};
st[sx][sy]=true;//打上标记
while(hh<=tt){
PII t=q[hh++];//先是0 再是1
for(int i=t.x-1;i<=t.x+1;i++){
for(int j=t.y-1;j<=t.y+1;j++){
if(i==t.x&&j==t.y) continue;
if(i<0||i>=n||j<0||j>=m) continue;
if(g[i][j]=='.'||st[i][j]) continue;
q[++tt]={i,j};//先是1
st[i][j]=true;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>g[i];
int cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(g[i][j]=='W'&&!st[i][j]){
bfs(i,j);
cnt++;
}
}
}
cout<<cnt<<endl;
return 0;
}#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=55,M=N*N;
int n,m;
int g[N][N];
PII q[M];
bool st[N][N];
int bfs(int sx,int sy){
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
q[0]={sx,sy};
st[sx][sy]=true;
int hh=0,tt=0;
int area=0;
while(hh<=tt){
PII t=q[hh++];
area++;
for(int i=0;i<4;i++){
int a=t.x+dx[i],b=t.y+dy[i];
if(a<0||a>=n||b<0||b>=m) continue;
if(st[a][b]) continue;
if(g[t.x][t.y]>>i&1) continue;
q[++tt]={a,b};
st[a][b]=true;
}
}
return area;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>g[i][j];
}
}
int cnt=0,area=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!st[i][j]){
area=max(area,bfs(i,j));
cnt++;
}
}
}
cout<<cnt<<endl;
cout<<area<<endl;
return 0;
}
//寻找最高处和最低处的联通块
#include <cstring>
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = N * N;
int n;
int h[N][N];
PII q[M];
bool st[N][N];
void bfs(int sx, int sy, bool& has_higher, bool& has_lower)//如果是判断两种不同数量 可以利用bool型传回main函数
{
int hh = 0, tt = 0;
q[0] = {sx, sy};
st[sx][sy] = true;
while (hh <= tt)
{
PII t = q[hh ++ ];
for (int i = t.x - 1; i <= t.x + 1; i ++ )
for (int j = t.y - 1; j <= t.y + 1; j ++ )
{
if (i == t.x && j == t.y) continue;
if (i < 0 || i >= n || j < 0 || j >= n) continue;
if (h[i][j] != h[t.x][t.y]) // 山脉的边界
{
if (h[i][j] > h[t.x][t.y]) has_higher = true;
else has_lower = true;
}else if (!st[i][j])
{
q[ ++ tt] = {i, j};
st[i][j] = true;
}
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
scanf("%d", &h[i][j]);
int peak = 0, valley = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
if (!st[i][j])
{
bool has_higher = false, has_lower = false;
bfs(i, j, has_higher, has_lower);
if (!has_higher) peak ++ ;
if (!has_lower) valley ++ ;
}
printf("%d %d\n", peak, valley);
return 0;
}
5. 最短路模型
//逆序输出经过的点
#include <cstring>
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = N * N;
int n;
int g[N][N];
PII q[M];
PII pre[N][N];
void bfs(int sx, int sy)
{
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int hh = 0, tt = 0;
q[0] = {sx, sy};
memset(pre, -1, sizeof pre);
pre[sx][sy] = {0, 0};
while (hh <= tt)
{
PII t = q[hh ++ ];
for (int i = 0; i < 4; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= n) continue;
if (g[a][b]) continue;
if (pre[a][b].x != -1) continue;
q[ ++ tt] = {a, b};
pre[a][b] = t;
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
scanf("%d", &g[i][j]);
bfs(n - 1, n - 1);
PII end(0, 0);
while (true)
{
printf("%d %d\n", end.x, end.y);
if (end.x == n - 1 && end.y == n - 1) break;
end = pre[end.x][end.y];
}
return 0;
}#include <cstring>
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 155, M = N * N;
int n, m;
char g[N][N];
PII q[M];
int dist[N][N];
int bfs()
{
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
int sx, sy;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == 'K')
sx = i, sy = j;
int hh = 0, tt = 0;
q[0] = {sx, sy};
memset(dist, -1, sizeof dist);
dist[sx][sy] = 0;
while (hh <= tt)
{
auto t = q[hh ++ ];
for (int i = 0; i < 8; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (g[a][b] == '*') continue;
if (dist[a][b] != -1) continue;
if (g[a][b] == 'H') return dist[t.x][t.y] + 1;
dist[a][b] = dist[t.x][t.y] + 1;
q[ ++ tt] = {a, b};
}
}
return -1;
}
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ ) cin >> g[i];
cout << bfs() << endl;
return 0;
}6. DFS之连通性模型
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int k,n;
int xa,ya,xb,yb;
char g[N][N];
bool st[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool dfs(int x,int y){
if(g[x][y]=='#') return false;//如果是一开始起点就是不能通过的
if(x==xb&&y==yb) return true;//可能是同一个点
st[x][y]=1;
for(int i=0;i<4;i++){
int a=x+dx[i],b=y+dy[i];
if(a<0||a>=n||b<0||b>=n) continue;
if(st[a][b]) continue;
//if(g[a][b]=='#') continue; 错误的
if(dfs(a,b)) return true;
}
return false;
}
int main(){
cin>>k;
while(k--){
cin>>n;
for(int i=0;i<n;i++) cin>>g[i];
cin>>xa>>ya>>xb>>yb;
memset(st,0,sizeof st);
if(dfs(xa,ya)) puts("YES");
else puts("NO");
}
return 0;
}
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 25;
int n, m;
char g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dfs(int x, int y)
{
int cnt = 1;
st[x][y] = true;
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (g[a][b] != '.') continue;
if (st[a][b]) continue;
cnt += dfs(a, b);
}
return cnt;
}
int main()
{
while (cin >> m >> n, n || m)
{
for (int i = 0; i < n; i ++ ) cin >> g[i];
int x, y;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == '@')
{
x = i;
y = j;
}
memset(st, 0, sizeof st);
cout << dfs(x, y) << endl;
}
return 0;
}
六:动态规划
动归分析步骤
1.确定状态 一般是“到第i个为止，xx为j的方案数/最小代价/最大价值”,可以根据数据范围和复杂度来推算
2.确定状态转移方程 从已知状态得到新状态的方法 并确保按照这个方向一定可以正确地得到最终状态（迭代法还是递归法）
3.确定最终状态输出
lanqiao OJ 1536 数字三角形模型
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n;
int a[N][N],dp[N][N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
for(int i=n;i>=1;i--){
for(int j=1;j<=i;j++){
dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
}
}
cout<<dp[1][1];
return 0;
}lanqiao OJ 3367
//设状态dp[i]表示走到第i级台阶的方案数
//状态转移方程：dp[i]=dp[i-1]+dp[i-2]; 如果是破损的 dp[i]=0;
//可以用一个桶来记录那些位置是破损的
//从前往后更新 最后输出dp[n];
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const ll p=1e9+7;
ll dp[N];
bool broken[N];
int main(){
ios::sync_with_stdio,cin.tie(0),cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x;
cin>>x;
broken[x]=true;
}
dp[0]=1;
if(!broken[1]) dp[1]=1;
for(int i=2;i<=n;i++){
if(broken[i]) continue;
dp[i]=(dp[i-1]+dp[i-2])%p;
}
cout<<dp[n]<<endl;
return 0;
}lanqiao OJ 3423
//设状态 dp[i]表示以位置i结尾的方案总数
//dp[i]=从j=1开始到i-k-1的dp[j]开始求和
//直接去求和会超时 n=1e6 开两个循环会1e12超时 所以利用前缀和来优化时间复杂度
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
const ll p=1e9+7;
ll dp[N],pre[N];
int main(){
int n,k;
cin>>n>>k;
dp[0]=pre[0]=1;
for(int i=1;i<=n;i++){
if(i-k-1<1) dp[i]=1;
else dp[i]=pre[i-k-1];
pre[i]=(pre[i-1]+dp[i])%p;//前缀和
}
cout<<pre[n]<<endl;
return 0;
}1.线性DP
//对于这个序列 假设下标k k 之前，要使这个序列非严格递增 ,k+1之后非严格递减 要求最少删除次数 即求它最大的长度
//考虑求原序列正向最长上升子序列 和反向最长下降子序列
#include<algorithm>
#include<iostream>
using namespace std;
const int N=110;
int n,m,a[N],dp1[N],dp2[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
dp1[i]=dp2[i]=1;
}
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
if(a[i]>=a[j]){
dp1[i]=max(dp1[i],dp1[j]+1);//最长上升子序列
}
}
}
for(int i=n-1;i>=1;i--){
for(int j=n;j>i;j--){
if(a[i]>=a[j]){
dp2[i]=max(dp2[i],dp2[j]+1);//最长下降子序列
}
}
}
for(int i=1;i<=n;i++){
m=max(m,dp1[i]+dp2[i]-1);
}
cout<<n-m<<endl;
return 0;
}//是否可以找到一个等于24的计算式
//并且计算式子必须是最小字典序
//暴力搜索 O(n!) 剪枝降低时间复杂度
//输出字典序最小的合法序列 所以可以升序排列抽出卡牌的点数
#include<bits/stdc++.h>
using namespace std;
int n,pd;
double a[50];
int tap[50];
double b[50];
char c[50];
string ans;
string q;
double sum;
//四则运算模拟 检测系列是否合法
//*/优先级比+-优先级高 应该先顺序遍历字符串cc中*-并且计算该运算符两边的数字
bool check(){
sum=0;
int pd=1;
char cc[15];
double bb[15];
for(int i=1;i<=n;i++){
cc[i]=c[i];
bb[i]=b[i];
}
for(int i=2;i<=n;i++){
if(cc[i]=='*'){
bb[i]=bb[i]*bb[i-1];
bb[i-1]=0;
}else if(cc[i]=='/'){
bb[i]=bb[i-1]/bb[i];
bb[i-1]=0;
}
}
sum=bb[1];
for(int i=2;i<=n;i++){
if(cc[i]=='-'){//符号从2开始
pd=2;
}else if(cc[i]=='+'){
pd=1;
}
if(pd==1){
sum+=bb[i];
}else{
sum-=bb[i];
}
}
if(sum==24) return 1;
else return 0;
}
void dfs(int num){
if(pd==1) return;
if(num==n){
if(check()==1){
pd=1;
cout<<"YES"<<endl;
cout<<b[1];
for(int i=2;i<=n;i++){
cout<<c[i]<<b[i];
}
cout<<"="<<sum;
}
return;
}
double sum=0;
for(int i=1;i<=n;i++){
if(tap[i]==1) continue;//如果这个数使用过 跳过
tap[i]=1;
b[num+1]=a[i];
c[num+1]='*';
dfs(num+1);
c[num+1]='+';
dfs(num+1);
c[num+1]='-';
dfs(num+1);
c[num+1]='\\';
dfs(num+1);
tap[i]=0;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n);
pd=0;
for(int i=0;i<=n;i++){
b[1]=a[i];
tap[i]=1;
dfs(1);
memset(b,0,sizeof b);
memset(c,0,sizeof c);
if(pd==1){
return 0;
}
tap[i]=0;
}
cout<<"NO"<<endl;
}
//1.判断连通性2.打破墙壁后 起点和终点之间有合法连通性
//遇到障碍物问题可以使用染色法 染色算法基本思路是 将起点和终点分别染成不同的颜色 枚举所有的障碍物 若某个障碍物连接着颜色1和颜色2那么可以破坏墙壁 使终点和起点具有联通性
//将起点可以到达的地方都染成1 将终点可以到达的地方全部染成2 染色操作
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3 + 10;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m;
int A, B, C, D;
char g[N][N];
int color[N][N];
void dfs(int x, int y, int c)
{
color[x][y] = c;
for (int i = 0; i < 4; ++ i )
{
int tx = x + dx[i], ty = y + dy[i];
if (tx < 0 || ty < 0 || tx >= n || ty >= m || g[tx][ty] == '#' || color[tx][ty])
continue;
dfs(tx, ty, c);
}
}
bool check(int x, int y)
{
int u = 0;
for (int i = 0; i < 4; ++ i )
{
int tx = x + dx[i], ty = y + dy[i];
if (tx < 0 || ty < 0 || tx >= n || ty >= m)
continue;
u |= color[tx][ty];
}
return u == 3;
}
int main()
{
cin >> n >> m;
cin >> A >> B >> C >> D;
A --, B --, C --, D --;
for (int i = 0; i < n; ++ i )
cin >> g[i];
dfs(A, B, 1);
if (color[C][D] == 1)
{
puts("Yes");
return 0;
}
dfs(C, D, 2);
for (int i = 0; i < n; ++ i )
for (int j = 0; j < m; ++ j )
if (g[i][j] == '#')
if (check(i, j))
{
puts("Yes");
return 0;
}
puts("No");
return 0;
}//第一步:第一次深度优先搜索 找到不依靠喷气包就可以到达的地方
//第二步：使用喷气背包并进行第二次深度搜索
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int n,m,k;
int A,B,C,D;
int h[N][N];
bool st[N][N];
void dfs(int x,int y){
st[x][y]=true;
for(int i=0;i<4;i++){
int tx=x+dx[i],ty=y+dy[i];
if(tx<0||ty<0||tx>=n||ty>=m){
continue;
}
if(h[tx][ty]>=h[x][y]){
continue;
}
dfs(tx,ty);
}
}
int main(){
cin>>n>>m>>k;
cin>>A>>B>>C>>D;
A--;B--;C--;D--;
for(int i=1;i<n;i++){
for(int j=0;j<m;j++){
cin>>h[i][j];
}
}
dfs(A,B);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(st[i][j]){
h[i][j]+=k;//将可以走到的点都加k 相当于模拟在这些点任意一个点使用了喷气包 反向思维
}
}
}
memset(st,0,sizeof st);
dfs(A,B);//进行第二次搜索
cout<<(st[C][D]?"Yes":"No")<<endl;
return 0;
}2.背包问题
1.01背包
拿或者不拿
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v) 表示到第i个物品有没有被拿 拿的物品总体积为j的情况下的最大价值
01背包优化
首先有dp[i][j]=dp[i-1][j]，相当于将dp[i-1]复制给dp[i],然后dp[i][j]=max(dp[i][j],dp[i-1][j-w]+v),每次下标都是从小的转移到大的，于是我们可以将第一维度给优化掉每次更新从前向后更新
dp[j]=max(dp[j],dp[j-w]+v) dp[j]表示此时物品总重量为j的情况下的最大价值
lanqiao OJ 1174
#include<bits/stdc++.h>
using namespace std;
const int N=110;
const int M=1010;
typedef long long ll;
ll dp[M];
int main(){
int n,V;
cin>>n>>V;
for(int i=1;i<=n;i++){
ll w,v;
cin>>w>>v;
for(int j=V;j>=w;j--){
dp[j]=max(dp[j],dp[j-w]+v);
}
}
cout<<dp[V];
return 0;
}lanqiao OJ 2223
//设状态dp[i][j]表示物品总重量为i 且使用了j次魔法的情况下的最大价值
//对于每个物品有三种选择 可以不选 选但不使用魔法 选且用魔法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+9;
ll dp[N][2];
int main(){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
ll w,v;
cin>>w>>v;
for(int j=m;j>=0;j--){
if(j>=w){
dp[j][0]=max(dp[j][0],dp[j-w][0]+v);
dp[j][1]=max(dp[j][1],dp[j-w][1]+v);
}
if(j>=w+k){
dp[j][1]=max(dp[j][1],dp[j-w-k][0]+2*v);
}
}
}
cout<<max(dp[m][0],dp[m][1])<<endl;
return 0;
}注意：1.先写转移方程 2.再写if判断条件
2.完全背包
即每种物品有无穷种状态即拿0个，1个，2个，，，，无穷个
我们并不关心某个物品拿了几个 只关心当前体积下的最大价值
dp[i]=max(dp[i],dp[i-w]+v)必须用新数据来更新新数据
因为新数据中包括了拿当前这个物品的状态 而这个物品可以被拿无数次
3.多重背包
商店有n种物品，每种物品有一个价值v和体积w，每种物品有s个，问能够装下物品的最大价值
只有s+1种状态即“拿0个，1个....s个”
多重背包就是每种物品的s个摊开，变成s种相同的物品，从而退化成01背包处理
只需要在01背包的基础上稍加改动， 对每个物品循环更新s次即可
当s较大，容易超时
“拆分”操作时进行一些优化，我们不再拆分成均为1个物品的组，而是每一组的物品个数为1,2,4,8...，最后剩下的单独为一组，这样一定存在一种方案来表示0-s的所有情况。
对拆分后的物品跑一遍01背包
include<bits/stdc++.h>
using namespace std;
const int N=205;
int dp[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
int w,v,s;
cin>>w>>v>>s;
while(s--){
for(int j=m;j>=w;j--){
dp[j]=max(dp[j],dp[j-w]+v);
}
}
}
cout<<dp[m]<<endl;
return 0;
}#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+7,M=2e4+7;
ll dp[M];
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
ll v,w,s;
cin>>v>>w>>s;
//s=14
for(int k=1;k<=s;s-=k,k+=k){
//k=1 2 4...
//k=8>s=7
for(int j=m;j>=k*v;j--){
dp[j]=max(dp[j],dp[j-k*v]+k*w);
}
}
//s=7 还有剩余
for(int j=m;j>=s*v;j--) dp[j]=max(dp[j],dp[j-s*v]+s*w);
}
cout<<dp[m]<<endl;
}3.区间DP
区间DP特点：以将一个大区间的问题拆分成若干个子区间合并的问题
多个连续的子区间可以进行整合,合并成一个大区间
区间DP遵循方法：1.从小到大枚举区间长度。2.对于每一个区间长度，枚举该长度的每个区间.
3.对于每个子区间，枚举可能出现的两个子区间的组合。
4.对于每个子区间的组合计算合并所需的代价。
5.求出当前区间的最优值。
lanqiao OJ 1233 石子合并区别于贪心：石子合并只能合并相邻的石子
4 5 9 4
9 9 4 总花费9
9 13 总花费13+9=22
21 总花费22+22=44
每次只能合并相邻的两堆石子。
那么如果现在想要将区间[l,r]的所有石子合并为一堆，那么一定是将[l,r]中的两堆石子合并成整个区间[l,r]。
可以考虑区间DP。
石子合并:令f[i][j]为将区间[i,j]合并为一堆的最小花费，那么枚举所有的中间点k将区间[i,j]分成[i,k]和[k+1,j]两部分 f[i][k]+f[k+1][j]+sum(i,k)+sum(k+1,j)就是先将[i,k]合并为一堆，再将[k+1,r]合并为一堆，最后将这两堆合并成[i,j]的最小花费，在所有合并中选择一个总价值最小的作为合并[i,j]的答案，即f[i][j]
转移方程f[i][j]=min(f[i][k]+f[k+1][j]+sum(i,j));
//对于区间[i,j]，其子区间长度一定小于该区间长度，而区间长度len由小到大枚举就保证了[i,j]的每个子区间都被计算过
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
for(int k=i;k<j;k++){
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum(i,j);
}
}
}#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int main(){
int n,a[MAXN],f[MAXN][MAXN];
cin>>n;
memset(f,127,sizeof f);//将f初始化为无穷大
for(int i=1;i<=n;i++){
cin>>a[i];
f[i][i]=0;//长度为1的区间不需要合并 代价是0
a[i]+=a[i-1];//计算前缀和 sum(i,j)=a[j]-a[i-1]
}
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
for(int k=i;k<j;k++){
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]);
}
}
}
cout<<f[1][n]<<endl;
return 0;
}遥远的北国雪车
//状态转移 dp[i][j]为i与j之间的列车数量
//对于dp[L][R]它们之间的列车数量肯定包含dp[L+1][R]之间列车的数量，同时也包含dp[L][R+1]的列车数量 这样确保dp数组扩大不会导致同一辆列车在多个区间相加
//转移方程 dp[L][R]=dp[L+1][R]+dp[L][R-1]-dp[L+1][R-1]+a[L][R];
#include<bits/stdc++.h>
using namespace std;
int n,m,t,i,j,p,q,l,r,f[525][525],a[525][525];
int main(){
cin>>n>>m>>t;
for(int i=1;i<=m;i++){
cin>>l>>r;
a[l][r]+=1;
}
//要确保f[i][j]都是从前面的式子中推出
for(int i=n;i>=1;i--){
for(int j=i;j<=n;j++){
f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1]+a[i][j];
}
}
while(t){
cin>>p>>q;
cout<<f[p][q]<<endl;
t--;
}
return 0;
}课上小游戏
//首先考虑非环状DP
//定义f[i][j][k]代表合并完区间[i,j]最后剩下的数为k所能获得的最大贡献
//将[i,j]分割成两个 枚举分割点为p 转移方程f[i][j][k]=max(f[i][p][k1]+f[p+1][j][k2]+[k1*k2/10]);
//考虑环状问题 实际上最后一步肯定是环上两个区间合并完成后再进行合并
//环拆成链 区间扩大一倍 [a1,a2,a3,a4,a5,a1,a2,a3,a4,a5]
//小技巧：转移过程中包含大量的除法和取模 考虑预处理出来 之后直接读取数组即可
#include<bits/stdc++.h>
using namespace std;
const int N=220;
typedef long long ll;
int dp[N][N][10],R[10][10],F[10][10];
int a[N];
int n;
void DP(){
for(int i=0;i<10;i++){//预处理除法和取模
for(int j=0;j<10;j++){
R[i][j]=i*j%10;
F[i][j]=i*j/10;
}
}
for(int len=2;len<=n;len++){
for(int l=1,r=l+len-1;r<=n*2;l++,++r){
for(int p=l;p<r;p++){
for(int k1=0;k1<10;k1++){
if(dp[l][p][k1]>=0){//优化 判断k1是否合法 小于0即为不合法表示这个数组空没有装入a[i]
for(int k2=0;k2<10;k2++){
dp[l][r][R[k1][k2]]=max(dp[l][r][R[k1][k2]],dp[l][p][k1]+dp[p+1][r][k2]+F[k1][k2]);
}
}
}
}
}
}
}
void sol(){
memset(dp,-0x3f,sizeof(dp));//预处理无穷小
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];//扩充两倍
dp[i][i][a[i]]=dp[i+n][i+n][a[i]]=0;//处理初值
}
DP();
int ans=0;
for(int i=1;i<n;i++){
for(int k=0;k<10;k++){
ans=max(ans,dp[i][i+n-1][k]);
}
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio,cin.tie(0),cout.tie(0);
int T=1;
while(T--){
sol();
}
exit(0);
return 0;
}
//首先考虑非环状DP
//定义f[i][j][k]代表合并完区间[i,j]最后剩下的数为k所能获得的最大贡献
//将[i,j]分割成两个 枚举分割点为p 转移方程f[i][j][k]=max(f[i][p][k1]+f[p+1][j][k2]+[k1*k2/10]);
//考虑环状问题 实际上最后一步肯定是环上两个区间合并完成后再进行合并
//环拆成链 区间扩大一倍 [a1,a2,a3,a4,a5,a1,a2,a3,a4,a5]
//小技巧：转移过程中包含大量的除法和取模 考虑预处理出来 之后直接读取数组即可
#include<bits/stdc++.h>
using namespace std;
const int N=220;
typedef long long ll;
int dp[N][N][10],R[10][10],F[10][10];
int a[N];
int n;
void DP(){
for(int i=0;i<10;i++){//预处理除法和取模
for(int j=0;j<10;j++){
R[i][j]=i*j%10;
F[i][j]=i*j/10;
}
}
for(int len=2;len<=n;len++){
for(int l=1;l+len-1<=2*n;l++){
int r=l+len-1;
for(int p=l;p<r;p++){
for(int k1=0;k1<10;k1++){
if(dp[l][p][k1]>=0){//优化 判断k1是否合法 小于0即为不合法表示这个数组空没有装入a[i]
for(int k2=0;k2<10;k2++){
dp[l][r][R[k1][k2]]=max(dp[l][r][R[k1][k2]],dp[l][p][k1]+dp[p+1][r][k2]+F[k1][k2]);
}
}
}
}
}
}
}
void sol(){
memset(dp,-0x3f,sizeof(dp));//预处理无穷小
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];//扩充两倍
dp[i][i][a[i]]=dp[i+n][i+n][a[i]]=0;//处理初值
}
DP();
int ans=0;
for(int i=1;i<n;i++){
for(int k=0;k<10;k++){
ans=max(ans,dp[i][i+n-1][k]);
}
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio,cin.tie(0),cout.tie(0);
int T=1;
while(T--){
sol();
}
exit(0);
return 0;
}
小飞打地鼠
//区间DP处理问题是将区间一点一点扩大先把小区间求解好，然后利用求解好的小区间去 求解更大一点的区间
//任一点除法 然后每一步往左或往右拓展一个点过程很像一个区间在不断拓展将己打过的地鼠位置构成一个区间打完下一个地鼠后区间就扩大
//设dp[i][j][0]是完整经过区间[1,j]且人处于左端点时的总得分
//设dp[i][j][1]是完整经过区间[i,j]且人处于右端点时的总得分
//对于dp[i][j][0]可能是由dp[i+1][j][0]和dp[i+1][j][1]
//考虑到 dp[i][j][0]=max(dp[i+1][j][0]+[ai/2]-18,dp[i+1][j][1]+a[i]-(j-i)*10)
#include <bits/stdc++.h>
using namespace std;
int n;
int a[505];
int dp[505][505][2];
int main () {
scanf ("%d", &n);
for (int i = 1; i <= n; i++)
scanf ("%d", a + i);
for (int i = 1; i <= n; i++)
dp[i][i][0] = dp[i][i][1] = a[i];
for (int len = 1; len <= n; len++)
for (int i = 1, j = len; j <= n; i++, j++) {
dp[i][j][0] = max (dp[i + 1][j][0] + a[i] / 2 - 10, dp[i + 1][j][1] + a[i] - (j - i) * 10);
dp[i][j][1] = max (dp[i][j - 1][1] + a[j] / 2 - 10, dp[i][j - 1][0] + a[j] - (j - i) * 10);
}
printf ("%d", max (dp[1][n][0], dp[1][n][1]));
return 0;
}//区间DP处理问题是将区间一点一点扩大先把小区间求解好，然后利用求解好的小区间去 求解更大一点的区间
//任一点除法 然后每一步往左或往右拓展一个点过程很像一个区间在不断拓展将己打过的地鼠位置构成一个区间打完下一个地鼠后区间就扩大
//设dp[i][j][0]是完整经过区间[1,j]且人处于左端点时的总得分
//设dp[i][j][1]是完整经过区间[i,j]且人处于右端点时的总得分
//对于dp[i][j][0]可能是由dp[i+1][j][0]和dp[i+1][j][1]
//考虑到 dp[i][j][0]=max(dp[i+1][j][0]+[ai/2]-18,dp[i+1][j][1]+a[i]-(j-i)*10)
#include <bits/stdc++.h>
using namespace std;
int n;
int a[505];
int dp[505][505][2];
int main () {
scanf ("%d", &n);
for (int i = 1; i <= n; i++)
scanf ("%d", a + i);
for (int i = 1; i <= n; i++)
dp[i][i][0] = dp[i][i][1] = a[i];
for (int len = 1; len <= n; len++)
for (int i = 1; i+len-1<= n; i++) {
int j=i+len-1;
dp[i][j][0] = max (dp[i + 1][j][0] + a[i] / 2 - 10, dp[i + 1][j][1] + a[i] - (j - i) * 10);
dp[i][j][1] = max (dp[i][j - 1][1] + a[j] / 2 - 10, dp[i][j - 1][0] + a[j] - (j - i) * 10);
}
printf ("%d", max (dp[1][n][0], dp[1][n][1]));
return 0;
}
//对于区间[l,r]考虑其端点处的颜色，只有端点颜色相同和不同的两种情况
//如果两端颜色相同 操作次数上和区间[l+1,r][l,r-1]相同 f[l][r]=min(f[l+1][r],f[l][r-1]); 无论两端颜色是啥 涂多少格子 都是1次 看次数
//两端颜色不同 将整个区间拆分成[l,k]和[k+1,r]
//l==r f[l][r]=1
#include<bits/stdc++.h>
using namespace std;
const int MAXN=55;
int main(){
string s;
int f[MAXN][MAXN];
cin>>s;
int n=s.size();
memset(f,127,sizeof f);
for(int i=0;i<n;i++){
f[i][i]=1;
}
for(int len=2;len<=n;len++){
for(int i=0;i+len-1<n;i++){
int j=i+len-1;
if(s[i]==s[j]){
f[i][j]=min(f[i+1][j],f[i][j-1]);
}else{
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
}
}
}
cout<<f[0][n-1]<<endl;
return 0;
}4.状态DP
1.状态压缩：是使用某种方法来表示某种状态，通常是一串01数字（二进制数）来表示各个状态。这就是要求状态压缩对象的状态必须只有两种0或1,当然如果有三种状态用三进制也可以
2.题目特征：解法需要保存一定的状态数据
状态DP数组有一维数量较小
acwing相关题目
//f[i][j][s]状态表示 集合：所有只排在前i行，已经摆了j个国王，并且第i行摆放状态是s的所有方案的集合
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=12,M=1<<10,k=110;
int n,m;
vector<int> state;//所有合法状态
vector<int> head[M];//每个状态可以转移到的状态
int cnt[M];//存的每个状态的1的个数
ll f[N][k][M];
bool check(int state){//是否存在连续1
for(int i=0;i<n;i++){
if((state>>i&1)&&(state>>(i+1)&1)){
return false;
}
}
return true;
}
int count(int state){//1的个数
int res=0;
for(int i=0;i<n;i++){
res+=state>>i&1;
}
return res;
}
int main(){
cin>>n>>m;
for(int i=0;i<1<<n;i++){
if(check(i)){//自身这一行不包含连续的1
state.push_back(i);
cnt[i]=count(i);//此行1的个数
}
}
for(int i=0;i<state.size();i++){
for(int j=0;j<state.size();j++){
int a=state[i],b=state[j];
if((a&b)==0&&check(a|b)){//两行上下不可有相对的1 两行上下不可有交错的1
head[i].push_back(j);//用的是下标并非是状态值
}
}
}
//动态规划
f[0][0][0]=1;
for(int i=1;i<=n+1;i++){
for(int j=0;j<=m;j++){
for(int a=0;a<state.size();a++){
for(int b:head[a]){
int c=cnt[state[a]];
if(j>=c){//摆放的国王必须小于整个上限
f[i][j][a]+=f[i-1][j-c][b];
}
}
}
}
}
cout<<f[n+1][m][0]<<endl;
return 0;
}玉米地
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 14, M = 1 << 12, mod = 1e8;
int n, m;
int w[N];
vector<int> state;
vector<int> head[M];
int f[N][M];
bool check(int state)
{
for (int i = 0; i + 1 < m; i ++ )
if ((state >> i & 1) && (state >> i + 1 & 1))
return false;
return true;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < m; j ++ )
{
int t;
cin >> t;
w[i] += !t * (1 << j);
}
for (int i = 0; i < 1 << m; i ++ )
if (check(i))
state.push_back(i);
for (int i = 0; i < state.size(); i ++ )
for (int j = 0; j < state.size(); j ++ )
{
int a = state[i], b = state[j];
if (!(a & b))
head[i].push_back(j);
}
f[0][0] = 1;
for (int i = 1; i <= n + 1; i ++ )
for (int j = 0; j < state.size(); j ++ )
if (!(state[j] & w[i]))
for (int k : head[j])
f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
cout << f[n + 1][0] << endl;
return 0;
}//f[i][j][k]表示所有已经摆完前i行，且第i-1行为j 第i行状态为k 摆放的最大值
//连续三行不可有炮
//意大利炮不可放山地 只可放平地
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 10, M = 1 << 10;
int n, m;
int g[1010];
int f[2][M][M];
vector<int> state;
int cnt[M];
bool check(int state)
{
for (int i = 0; i < m; i ++ )
if ((state >> i & 1) && ((state >> i + 1 & 1) || (state >> i + 2 & 1)))
return false;
return true;
}
int count(int state)
{
int res = 0;
for (int i = 0; i < m; i ++ )
if (state >> i & 1)
res ++ ;
return res;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < m; j ++ )
{
char c;
cin >> c;
g[i] += (c == 'H') << j;
}
for (int i = 0; i < 1 << m; i ++ )
if (check(i))
{
state.push_back(i);
cnt[i] = count(i);
}
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < state.size(); j ++ )
for (int k = 0; k < state.size(); k ++ )
for (int u = 0; u < state.size(); u ++ )
{
int a = state[j], b = state[k], c = state[u];
if (a & b | a & c | b & c) continue;
if (g[i] & b | g[i - 1] & a) continue;
f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[b]);
}
int res = 0;
for (int i = 0; i < state.size(); i ++ )
for (int j = 0; j < state.size(); j ++ )
res = max(res, f[n & 1][i][j]);
cout << res << endl;
return 0;
}
小蓝的灯
//f[i]定义为从初始状态到状态i的时候小号的最小体力值
//默认二进制位都是从0下标开始的 初始化所有f[i]为无穷大
//打开选项 假设f[j]转移到f[i] 可以枚举i的每个二进制位k 若找到i的第k位为1 则令j=i-2的k次方 f[i]=min(f[i],f[j]+xk);
//关闭选项 假设f[j]转移到f[i] 可以枚举i的每个二进制位k 若找到i的第k位为0 则令j=i+2的k次方 f[i]=min(f[i],f[j]+yk);
//交换选项 假设f[j]转移到f[i] 可以用两个指针枚举i的两个不同二进制p与q 若i的第p位为1且第q位为0交换 则令j=i-2的p次方+2的q次方
//f[i]=min(f[i],f[j]+z);
//通过图论的思路去优化DP 令0到2的n次方-1为2的n次方个的顶点 让初始的状态S为起点 最终的状态E为起点 每次转移都是对两个顶点间建边
//边权都是正的 利用Dijkstra算法跑S到E的最短路 可以求出答案
/*
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,z;
cin>>n>>z;
vector<int>x(n),y(n);
for(int i=0;i<n;i++) cin>>x[i];
for(int i=0;i<n;i++) cin>>y[i];
int st=0,ed=0;
for(int i=0;i<n;i++){
int t;cin>>t;
st|=t<<i;//灯初始状态
}
for(int i=0;i<n;i++){
int t;cin>>t;
ed|=t<<i;//灯最终状态
}
vector<int>vis((1<<n),0),dis((1<<n),1e18);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
dis[st]=0;
q.push({0,st});
while(!q.empty()){
auto [l,r]=q.top();
q.pop();
if(vis[r]) continue;
vis[r]=1;
for(int i=0;i<n;i++){
if((r>>i)&1){
if(l+y[i]<dis[r^(1<<i)]){
dis[r^(1<<i)]=l+y[i];
q.push({dis[r^(1<<i)],r^(1<<i)});//1变0
}
}else{
if(l+x[i]<dis[r^(1<<i)]){
dis[r^(1<<i)]=l+x[i];
q.push({dis[r^(1<<i)],r^(1<<i)});//0变1
}
}
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(((r<<i)^(r<<j))&1){
if(l+z<dis[r^(1<<i)^(i<<j)]){
dis[r^(1<<i)^(1<<j)]=l+z;
q.push({dis[r^(1<<i)^(1<<j)],r^(1<<i)^(1<<j)});
}
}
}
}
}
cout<<dis[ed]<<endl;
}
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,z;
cin>>n>>z;
vector<int>x(n),y(n);
for(int i=0;i<n;++i) cin>>x[i];
for(int i=0;i<n;++i) cin>>y[i];
int st=0,ed=0;
for(int i=0;i<n;++i){
int t;cin>>t;
st|=t<<i;
}
for(int i=0;i<n;++i){
int t;cin>>t;
ed|=t<<i;
}
vector<int>vis((1<<n),0),dis((1<<n),1e18);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
dis[st]=0;
q.push({0,st});
while(!q.empty()){
auto [l,r]=q.top();q.pop();
if(vis[r]) continue;
vis[r]=1;
for(int i=0;i<n;++i){
if((r>>i)&1){
if(l+y[i]<dis[r^(1<<i)]){
dis[r^(1<<i)]=l+y[i];
q.push({dis[r^(1<<i)],r^(1<<i)});
}
}
else{
if(l+x[i]<dis[r^(1<<i)]){
dis[r^(1<<i)]=l+x[i];
q.push({dis[r^(1<<i)],r^(1<<i)});
}
}
}
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j){
if(((r>>i)^(r>>j))&1){
if(l+z<dis[r^(1<<i)^(1<<j)]){
dis[r^(1<<i)^(1<<j)]=l+z;
q.push({dis[r^(1<<i)^(1<<j)],r^(1<<i)^(1<<j)});
}
}
}
}
cout<<dis[ed]<<endl;
}//挑出任意个字符串并以任意顺序组成一段字符串数数量最多的关联文本
//若不改变其顺序 本题状态可以定义为dp[i][c]表示从word[0]到word[i]这一闭区间内组成以c结尾的关联文本所能使用的最多字符串数
//类似与01背包 对于word[i]有“选”与“不选”两种选择 不选：dp[i][c]=dp[i-1][c] 选：dp[i][last]=dp[i-1][first]+1 first为word[i]的首字母 last为word[i]的末尾字母
//但对于last以外的c 其状态不会改变 dp[i][c]=dp[i-1][c]
//若改变其顺序 使用状态压缩来丰富dp数组所表示的信息
//可以利用二进制数bits代替原本的i来表示可以选择的字符串范围，再枚举bits中1的位数，如果第k位为1，就可以把word[k]作为最后一个选择的字符串
//dp[bits][last]=max(dp[bits][last],dp[bits异或(1<<k)][first]+1);
//状态方程中first为word[k]的首字母，last为word[k]末尾字母
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<string> word(n);
vector<int> first(n),last(n);
vector<vector<int>> dp(1<<n,vector<int>(26,0));//表示二维数组
for(int i=0;i<n;i++){
cin>>word[i];
first[i]=word[i][0]-'a';
last[i]=word[i].back()-'a';
}
for(int bits=0;bits<(1<<n);bits++){
for(int i=0;i<n;i++){
if(bits&(1<<i)){
dp[bits][last[i]]=max(dp[bits][last[i]],dp[bits^(1<<i)][first[i]]+1);
}
}
}
int res=0;
for(int i=0;i<26;i++){
res=max(res,dp[(1<<n)-1][i]);
}
cout<<res<<endl;
return 0;
}#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a[N],dp[N];
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
if(a[j]<a[i]){
dp[i]=max(dp[i],dp[j]+1);
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
ans=max(dp[i],ans);
}
cout<<ans<<endl;
return 0;
}
//由于本题数据量较大，使用常规的O(n^2)的LIS算法会超时
//故本题采用二分+贪心的算法求解：
//维护一个low数组，low[i]表示长度为i的最长上升子序列的末尾元素
//使用贪心思想来对low数组进行更新，核心思想是末尾元素越小，越容易凑出最长的子序列
//遍历每一个元素，若当前元素比low[i]更大，则直接加入low数组的末尾
//若当前元素小于low[i],则从low数组中找到一个大于等于它的最小值将其替换
//由于low数组是递增的，故使用二分算法进行搜索和替换
//最终输出low数组的长度即为答案
//例1:对于序列arr[8]={3,1,2,6,4,5,10,7}
//扫描arr[1],low[1]=3;扫描arr[2],low[1]替换为1;扫描arr[3],low[2]=2;扫描arr[4],low[3]=6
//扫描arr[5],low[3]替换为4;扫描arr[6],low[4]=5;扫描arr[7],low[5]=10;扫描arr[8],low[5]替换为7
//最终low数组长度为5，即为答案，此时low[5]={1,2,4,5,7}
//例2：对于序列arr[8]={1,4,7,2,5,9,10,3}
//扫描arr[1],low[1]=1;扫描arr[2],low[2]=4;扫描arr[3]，low[3]=7;扫描arr[4],low[2]替换为2
//扫描arr[5],low[3]替换为5;扫描arr[6],low[4]=9;扫描arr[7],low[5]=10;扫描arr[8],low[3]替换为3
//最终low数组长度为5，即为答案，此时low[5]={1,2,3,9,10};
//注意此算法的缺陷：low数组只有长度是有意义的，其保存的元素是无意义的
//比如上例中的low={1,2,3,9,10}，原序列中不存在此子序列
//实际上low数组中每个元素只代表一种排列可能性，不代表最终的排列结果
#include <bits/stdc++.h>
using namespace std;
int arr[300009];
int low[300009];
int main()
{
int N;
int length=1;
cin>>N;
for(int i=1;i<=N;i++)cin>>arr[i];
low[1]=arr[1];//初始化，长度为1的子序列初始化为第一个元素
for(int i=2;i<=N;i++)//依次遍历后面的元素，更新low数组
{
if(arr[i]>low[length])//若当前元素大于low数组末尾元素，直接插入
{
low[++length]=arr[i];
}
else//若小于，则用low数组中刚好大于等于它的元素替换之
{
int index=lower_bound(low+1,low+1+length,arr[i])-low;//获取插入位置下标
low[index]=arr[i];//替换
}
}
cout<<length<<endl;//输出low数组长度即为答案
return 0;
}
七：字符串
1.kmp算法
next数组表示此模式串下标失配时应该移动到的位置，也表示最长的相同真前后缀的长度
计算next数组（next数组仅与模式串P有关）的方式是用P自己去匹配自己
//计算nex数组
char s[N],p[M];
int nex[M];
int n=strlen(s+1),m=strlen(p+1);//字符串下标都是从1开始
nex[0]=nex[1]=0;
for(int i=2,j=0;i<m;i++){
//不断匹配p[i]和p[j+1]
while(j&&p[i]!=p[j+1]) j=nex[i];
if(p[i]==p[j+1]) j++;
nex[i]=j;
}
//通过next数组进行匹配
for(int i=1,j=0;i<=n;i++){
while(j&&s[i]!=p[j+1]) j=nex[i];
if(p[i]==p[j+1]) j++;
if(j==m){
//成功匹配一次
}
}//斤斤计较的小z
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int p[N],s[N];
int nex[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
scanf("%s",p+1);
int m=strlen(p+1);
scanf("%s",s+1);
int n=strlen(s+1);
//计算nex数组
nex[0]=nex[1]=0;
for(int i=2,j=0;i<=m;i++){
while(j&&p[i]!=p[j+1]) j=nex[i];
if(p[i]==p[j+1]) j++;
nex[i]=j;
}
//进行匹配
int ans=0;
for(int i=1,j=0;i<=n;i++){
while(j&&p[i]!=p[j+1]) j=nex[i];
if(s[i]==p[j+1]) j++;
if(j==m) ans++;
}
cout<<ans<<endl;
return 0;
}2.字符串Hash
本质是利用一个数字表示一段字符串，从而降低字符串的处理的复杂度
采用unsigned long long 类型 可以自然溢出
还需要一个进制数base 用于规定这个数字的进制
Hash数组h[i]表示字符串s[1-i]的Hash值 采用类似前缀和的形式以便求出任意一个字串的Hash值
//字符串Hash初始化
typedef unsigned long long ull;
const ull base=131;
ull h[N];//h[i]表示s[i-n]的Hash(类似前缀和)
char s[N];
for(int i=1;i<=n;i++){
h[i]=h[i-1]*base+s[i]-'a'+1;
}
//获取子串s[l]-s[r]的Hash
ull getHash(int l,int r){
return h[r]-h[l-1]*b[r-l+1];//b[i]表示base的i次方（预处理）
}
Manacher回文串
/*int C=0,R=0;
for(int i=1;i<=2*n+1;i++){
p[i]=i<R?min(R-i,p[2*C-i]):1;
//如果p[i]可以更大 就持续更新
while(s[i+p[i]]==s[i-p[i]]) p[i]++;
//如果此时i可以作为一个更好的C，就替换
if(i+p[i]>R) C=i,R=i+p[i];
}
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
char s[N];
int p[N];
int main(){
cin>>s+1;
int n=strlen(s+1);
for(int i=2*n+1;i>=1;i--)//开两倍空间
{
s[i]=(i&1)?'#':s[i>>1];//奇数位放无效字符 偶数位放有效数字
}
s[0]='^',s[2*n+2]='$';
int C=0,R=0;
for(int i=1;i<2*n+1;i++){
p[i]=i<R?min(R-i,p[2*C-i]):1;
while(s[i+p[i]]==s[i-p[i]]) p[i]++;
if(i+p[i]>R) C=i,R=i+p[i];
}
int ans=0;
for(int i=1;i<=2*n+1;i++) ans=max(ans,p[i]-1);
cout<<ans;
return 0;
}01-tire
01字典树(01-trie)是一种特殊的字典树，字符集只有{0,1}，主要用来解决一些关于二进制上的问题，例如异或问题和子集问题。
七：数论
矩阵乘法&整除&同余&GCD&LCM
矩阵乘法
只有当相乘的两个矩阵的左矩阵的列数等于右矩阵的行数时，才可相乘
N*M的矩阵和M*K的矩阵做乘法后的矩阵大小为N*K
规则：第一个矩阵A的第i行和第二个矩阵B的第j列的各M个元素对应相乘再相加得到新矩阵C[i][j]的值
A*B≠B*A
八：数据结构
1.手写堆
优先队列就是一个堆
维护集合的一个最大值和最小值
堆是一个二叉树 对于每个节点满足：儿子的权值都比自己的权值小或相等
这个相纸不断向上传递直到根 就可以保证根的权值是整棵树中最大的
手写堆需要实现的几个函数
- pushup()将某个点向上更新 一般是将最后一个点向上更新
- push()插入一个点堆内
- Pop()将根节点删除
我们采用数组的方式来存储数据，利用二叉树的性质：2x表示x的左编号 2x+1表示x的右儿子编号。sz表示结点数量 a[x]表示结点
所有中间结点，一定比它孩子大（大根堆），或者一定比它的孩子小（小根堆）
如何构建大根堆
初始化：
1:按照给出的数组，首先按照层次优先（逐层摆放）构造一棵二叉树
2:从该二叉排序树的最后一个叶子结点的根结点出发，比较该结点的左右孩子，选取最大的置换到根结点上
3:整理倒数第二非叶子结点，比较并选择一个最大的置换到根结点…
4:依次类推，直到整理完整棵树，此时树的根结点一定是该大根堆中最大值
5:在把大数往上顶的过程中，也要看互换位置的数是否比左右孩子都大，如果不是，则又要选择一个最大的换到该子树根结点。
//优先队列
#include <iostream>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e5+9;
priority_queue<ll> pq;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,q;
cin>>n>>q;
ll sum=0;
for(int i=1;i<=n;i++){
ll x; cin>>x;
pq.push(x);
}
for(int i=1;i<=q;i++){//q次询问
ll x;cin>>x;
while(pq.top()>=x){
ll y=pq.top();pq.pop();
sum+=y%x-y;
pq.push(y%x);
}
cout<<sum<<' ';
}
return 0;
}//1.pushup()将某个点向上更新，一般是将最后一个点向上更新
void pushup(int x){
while(x!=1){//只要不是根节点 就一直跟父节点比较 并更新
if(a[x]>a[x>>1]) swap(a[x],a[x>>1]),x>>1;
else break;
}
}
//2.pushdown()将某个点向下更新
void pushdown(int x){
//如果没有儿子
if((x<<1)>sz) return;
//如果只有左儿子
if((x<<1|1)>sz){
if(a[x<<1]>a[x]){
swap(a[x],a[x<<1]);
pushdown(x<<1);
}
}else{
//左右儿子都有
if(a[x]==max({a[x],a[x<<1],a[x<<1|1]})) return;
if(a[x<<1]>a[x<<1|1]){
swap(a[x],a[x<<1]);
pushdown(x<<1);
}else{
swap(a[x],a[x<<1|1]);
pushdown(x<<1|1);
}
}
}
//3.push()插入一个点到堆
void push(int x){
a[++sz]=x;
pushup(sz);
}
//4.pop()将根节点删除
void pop(){
a[1]=a[sz--];
pushdown(1);
}//有插入 删除 修改操作 如果直接上暴力的在数组上操作 复杂度较高
//采用优先队列 大根堆 需要维护一个偏移量offset 偏移量的作用
//1.当执行增加工作的时候 偏移量加上x,减少工作的时候，偏移量减上x
//2.执行插入操作的时候 我们只需要修改插入仅优先队列的变量即可
//3.当执行删除操作的时候，我们需要将堆顶变量加偏移量后直接输出
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll q,x;
cin>>q>>x;
priority_queue<ll> qu;//递增的优先队列 压入元素之后，自动根据优先级进行排序 top() 是当前优先队列的最大值
qu.push(x);
ll sum=0;//累加差值
while(q--){
ll f,x;
cin>>f;
if(f==1){
cin>>x;
qu.push(x-sum);//插入x-sum
}else if(f==2){
cin>>x;
sum+=x;//差值累计在sum
}else if(f==4){
cout<<qu.top()+sum<<endl;
qu.pop();
}else{
cin>>x;
sum-=x;
}
}
return 0;
}//如果本题直接暴力 会爆掉
//采用小根堆来维护前k大的数 堆顶即是我们需要的答案
//对于一个元素 直接想要插入heap中 有以下的情况
//1.大于堆顶，需要将堆顶删除，再将元素插入堆中
//2.小于等于堆顶 我们无需处理
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
priority_queue<int, vector<int>, greater<int>> q;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
q.push(x);
}
for (int i = 0; i < k; i++) {
int x;
cin >> x;
if (x > q.top()) {
q.pop();
q.push(x);
}
cout << q.top() << " ";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t = 1;
for (int zu = 1; zu <= t; zu++) {
solve();
}
return 0;
}2.ST表
RMQ问题指的是对于数组，每次给一个区间[l,r]，要求返回区间内的最大值或最小值的下标
如果暴力直接解题，会导致算法较慢
可以利用倍增和动态规划的思想，利用“ST表”数据结构解决
“静态求区间最值”的数据结构，本质是dp
如果求区间最大值，设状态st[i][j]表示从i开始，大小为2^j的长度的区间的最大值，即区间[i,i+2^j-1]的最大值
状态转移方程为st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);(从i开始的长度为j的区间)
区间查询[l,r]的最大值 可以分解为两个小区间的最大值
在区间[l,r]，需要找到一个k，使得2^k<=r-l+1，k<=log2(r-l+1),可以分解为max(st[l][k],st[r-2^k+1][k])
3.并查集
图形数据结构 用于存储结点的连通关系
每个结点有一个父亲，可以理解为“伸出去的手”，会指向另外一个点，初始时指向自己
一个点的根节点是该点的父亲的父亲...的父亲，直到某一个的父亲是自己（根）
当两个点的根相同时，我们就说他们属于同一个类，或者说是连通的
int root(int x){
if(pre[x]==x) return x;//如果指向自己 自己就是根
return root(pre[x]);
}在并查集中，所有操作都在根上，假如我要使得x和y两个点合并，只需要root(x)指向root(y)，或使得root(y)指向root(x)
pre[root(x)]=root(y);//将x的根指向y的根
路径压缩
找根的过程中，将父亲直接指向根，从而实现路径压缩。
int root(int x){
return pre[x]=pre[x]==x?x:root(pre[x]);//将父亲直接指向根
}基本并查集
1.合并两个集合
2.查询某个元素的祖宗节点
1》记录每个集合的大小 绑定到根节点上
2》每个点到根节点的距离 绑定到元素身上
食物链并查集维护相对距离
拓展域并查集使用枚举
4.数的基础和树的遍历
边也可以存储权值 树中的条数严格是点数-1
结点的度：儿子结点的个数
四种遍历方法：
DFS:前序遍历 中序遍历 后序遍历 二叉树中前中后序遍历
遍历过程中可以维护结点与父亲的关系，经常用于树形dp,并且DFS序在算法中应用
前序遍历：dfs过程中 保持根左右顺序
1 2 4 8 5 9 3 6 7 10
后序遍历： 左根右
8 4 2 5 9 1 6 3 10 7
后序遍历：左右根
8 4 9 5 2 6 10 7 3 1
层序遍历 ：1 2 3 4 5 6 9 8 9 10
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int ls[N],rs[N];
//先序遍历
void dfs1(int x){
cout<<x<<' ';
if(ls[x]) dfs1(ls[x]);
if(rs[x]) dfs1(rs[x]);
}
//中序遍历
void dfs2(int x){
if(ls[x]) dfs2(ls[x]);
cout<<x<<' ';
if(rs[x]) dfs2(rs[x]);
}
//后序遍历
void dfs3(int x){
if(ls[x]) dfs3(ls[x]);
if(rs[x]) dfs3(rs[x]);
cout<<x<<' ';
}
//层序遍历
void bfs(){
queue<int> q;
q.push(1);
while(q.size()){
int x=q.front();
q.pop();
cout<<x<<" ";
if(ls[x]) q.push(ls[x]);
if(rs[x]) q.push(rs[x]);
}
}
int main(){
}5.数的直径与重心
树的直径和重心
树的直径：是数上最长的一条链 链不唯一 一棵树可能有很多直径
直径是由两个顶点u v决定的 若有一条直径(u,v) 则满足以下性质：
1》u v度数均为1
2》在以任意一个点为根的树上,u,v中必然存在一个点作为最深的叶子结点
深度就是点距离根节点的距离
树的直径求法：“跑两遍dfs”
由于直径端点u v必然存在一个是深度最深的点 那么我们可以在以任意结点为根的树上跑一遍dfs求所有点的深度，选取深度最大的点作为u,然后以u为根再跑一次dfs，此时深度最大的点就是v。
于是就可以得到两个端点u v，从而确定树的直径，其长度就是路径上点的个数，也就是等于以u为根的树中的dep[v]。
lanqiao Oj 3029
九：字符串
1.kmp
2.Manacher
Manacher算法
回文串：对于每个s[i]=s[n+1-i]的字符串
回文半径：对于一个回文中心，如果其半径为r,如果它为奇数长度的回文串的中心，则说明[i-r+1,i+r-1]为一个回文串。如果i为偶数长度的回文中心，则回文半径没有意义。
回文的递归性质：某个点的回文半径相比某个回文中心的点的回文半径一定相等或更大
Manacher算法是一种O(n)复杂度计算字符串中每个位置作为回文中心的回文半径的算法
转换后的字符串中回文半径为p[i]，说明在转换前的回文串长度为p[i]-1
转换后的字符串的有效区间为[1,2*n+1]，所以我们从1到2*n+1去遍历所有的点
如果i<R,说明i存在关于C(C是此时最右侧的R多对应的对称中心)的对称点2*C-i,那么p[i]就可以等于p[2C-i]。
3.01-tire
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
35
0- 0
已为社区贡献1条内容
所有评论(0)