Pinguier

1005

sealt
Double_Leaf
._6495
incra

cloudsRise

Eureka_7

herry_01

violet_garden
CodeSlogan

Joyasa

Pinguier
15小时前

### 思维模拟题

[a/b] a除b上取整 = [a+b-1/b] a+b-1除以b下取整

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int main(){
int n;
cin>>n;
int k = 5,s=0;
while(s+k<n){
s+=k;
k*=2;
}
n-=s;
int len = k/5;
int t = (n+len-1)/len;
cout<<(char)(t-1+'a')<<endl;

return 0;
}


### 题目描述

#### 样例

输入样例：
(){}

yes


#### C++ 代码

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
const int N = 100010;
stack<char> c;

int main(){
string str;
cin>>str;
for(int i=0;i<str.size();i++){
//左边符号
if(str[i]=='<' || str[i]=='(' || str[i]=='{' ||str[i]=='['){
c.push(str[i]);
}
//右边符号
else{
if(c.empty()){
cout<<"no"<<endl;
return 0;
}
else if(  (str[i]=='>'&&c.top()=='<') ||
(str[i]==')'&&c.top()=='(' ) || (str[i]=='}'&&c.top()=='{') || (str[i]==']'&&c.top()=='[') ){
c.pop();
}
else {
cout<<"no"<<endl;
return 0;
}
}
}
if(c.empty()) cout<<"yes"<<endl;
else cout<<"no"<<endl;
return 0;
}



### 单调栈+二分

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int n;
int w[N];
int stk[N];
int ans[N];

int main(){
cin>>n;
//输入部分
for(int i=0;i<n;i++) cin>>w[i];
//定义栈顶
int top  =0;
//从后往前构造单调栈
for(int i=n-1;i>=0;i--){
//当栈为空或者当前的元素小于栈顶元素时 表示w[i]元素的右边不存在比他还小的数
if(!top || w[i]<=w[stk[top]]) {
ans[i] = -1;
//只有当该元素小于栈顶元素时 才会存入栈中 单调递增栈
stk[++top] = i;
}
else{
int l = 1,r = top;
while(l<r){
int mid = l + r>>1;
if(w[stk[mid]]<w[i]) r = mid;
else l = mid+1;
}
ans[i] = stk[r] - i -1;

}
//if(!top || w[i]<w[stk[top]]) stk[++top] = i;

}
for(int i=0;i<n;i++)
cout<<ans[i]<<" ";
return 0;
}


 #include<iostream>
using namespace std;
const int N = 100010;
int w[N];
int n;
int st[N];
int ans[N];
int top = 0;
int main(){
int n;
cin>>n;
//从左到右构造一个单调递增的栈
for(int i=0;i<n;i++){
cin>>w[i];
while(top>0 && w[i]<w[st[top]]){
top--;
}
st[++top] = i;//元素入栈
}

//在构造的单调栈中通过二分找出答案
for(int i=0;i<n;i++){
int l =0,r = top;
while(l<r){
int mid = l+r+1>>1;
//因为要找的答案是小于x的数 所以这里的判断语句只能是大于等于 取不到mid这个点
//所以要找的答案一定在mid左边 取不到mid这个点 r = mid-1
if(w[st[mid]]>=w[i]) r = mid-1;
else l = mid;
}
//要找到特定答案必须有两个条件 1.这个点在指定元素的右边 2.这个点的值小于指定元素
if(st[r]>i && w[st[r]]<w[i]) cout<< st[r] - i -1<<" ";
else cout<<"-1"<<" ";
}
return 0;
}



### 字符串直接操作 其思想还是栈的思想

#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
string str;
cin>>str;
string res;
//实质上是利用栈的思想存储 当进入的元素和res中的最后一个元素相等
//则删除栈中的这个元素 这样一定满足当前元素的前面的元素一定满足不是相同的元素连续的字母对
for(auto c:str){
if(res.size() && res.back()==c) res.pop_back();
else res+=c;
}
cout<<res<<endl;

}


### stl中的stack实现代码

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
stack<char> stk;
int main(){
string s;
cin>>s;
//利用栈的性质 当栈不为空且当前的元素和栈顶元素相同时 弹出栈顶元素
for(auto c:s){
if(!stk.empty()&&stk.top()==c) stk.pop();
else stk.push(c);
}
//定义答案
string res;
//将栈中的元素出栈 用res存储下来
while(!stk.empty()){
res+=stk.top();
stk.pop();
}
//注意这里栈的出栈顺序是先入栈的元素后出栈 所以最后的输出结果需要将ans倒序后再输出
reverse(res.begin(),res.end());
cout<<res;
}


### 字符串直接操作 其思想还是栈的思想

#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
string str;
cin>>str;
string res;
//实质上是利用栈的思想存储 当进入的元素和res中的最后一个元素相等
//则删除栈中的这个元素 这样一定满足当前元素的前面的元素一定满足不是相同的元素连续的字母对
for(auto c:str){
if(res.size() && res.back()==c) res.pop_back();
else res+=c;
}
cout<<res<<endl;

}


### stl中的stack实现代码


#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
stack<char> stk;
int main(){
string s;
cin>>s;
//利用栈的性质 当栈不为空且当前的元素和栈顶元素相同时 弹出栈顶元素
for(auto c:s){
if(!stk.empty()&&stk.top()==c) stk.pop();
else stk.push(c);
}
//定义答案
string res;
//将栈中的元素出栈 用res存储下来
while(!stk.empty()){
res+=stk.top();
stk.pop();
}
//注意这里栈的出栈顺序是先入栈的元素后出栈 所以最后的输出结果需要将ans倒序后再输出
reverse(res.begin(),res.end());
cout<<res;
}



### 利用哈希表中的元素不会有重复元素这一特性对元素进行去重

#### unordered_set中的元素不允许重复

#include<iostream>
#include<algorithm>
#include<unordered_set>
using namespace std;
int n;

int main(){
cin>>n;
unordered_set<string> hash;
for(int i=0;i<n;i++){
string a,b;
cin>>a>>b;
//unordered_set中的插入操作 这里插入的值不允许重复 unordered_map中的键值不允许重复
hash.insert(a +' '+b);
}
cout<<hash.size();
return 0;
}


#### unordered_map中的键值不允许重复

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
int n;
const int N = 110;

int main(){
cin>>n;
unordered_map<string,int> hash;
for(int i=0;i<n;i++){
string a,b;
cin>>a>>b;
hash[a+' '+b]++;
}
cout<<hash.size();
return 0;
}



Pinguier
11天前

### 因此 本题可以转换为排序+上升子序列的解法

#### C++ 代码

//朴素版本 时间复杂度O(n^2)

//朴素版本 时间复杂度O(n^2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;//因为题目中所给的友好城市是成对出现的 定义pair存储一对城市
const int N = 5010;
int f[N];//这里f[i]指的是以第i个元素结尾 构成的上升子序列中长度最大的值
int n;
PII q[N];
bool cmp(PII a,PII b){
return a.second<b.second;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>q[i].first>>q[i].second;
//对下游城市进行排序
sort(q+1,q+n+1,cmp);
//求最大上升子序列长度的方法
for(int i=1;i<=n;i++){
//刚开始的时候f[i]一定会包含只含有a[i]这种情况 此时的最大上升子序列长度为1
f[i] = 1;
//求倒数第二个值 当倒数第二个值小于a[i]时 此时的长度为f[j]+1
for(int j=1;j<i;j++){
if(q[i].first>q[j].first)
f[i] = max(f[i],f[j]+1);
}

}
//最大上升子序列的长度为f[i]中以a[i]结尾时长度最大的那个
int res = -0x3f3f3f3f;
for(int i =1;i<=n;i++) res = max(res,f[i]);
cout<<res<<endl;
return 0;

}
}


Pinguier
11天前

## 贪心思想的优化做法 O(nlogn)

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000010;
int n;
int a[N];
int q[N];

int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int len = 0;
//q[0] = -2e9;
for(int i=0;i<n;i++){
int l = 0,r = len;
//二分查找出序列中小于a[i]的最大值
//此时将a[i]接到这个值的后面 那么构成的上升子序列一定是最长的
while(l<r){
int mid = l+r+1>>1;
if(q[mid]<a[i]) l = mid;
else r = mid-1;
}
//这里直接将a[i]接到寻找到的r的后面即可
q[r+1] = a[i];
len = max(len,r+1);
}
cout<<len<<endl;
}


Pinguier
12天前

## 状态方程：f[i] = max(f[j]+1)

//这里f[i]表示以第i个元素结尾的上升序列的集合中长度最大值
//状态方程 f[i] = max(f[j]+1) 这里j表示第i个元素前面的一个数
// 时间复杂度为O(n^2)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int a[N],f[N];
int n;
int main(){
//正常输入的部分
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];

for(int i=1;i<=n;i++){
f[i] = 1;//这里表示上升序列中只包含a[i]一个元素 序列的长度为1
for(int j=1;j<i;j++)
//必须保证a[j]小于a[i]的时候 状态计算才成立 因为这是一个上升的子序列
if(a[j]<a[i]) f[i] = max(f[i],f[j]+1);
}
int res = 0;
//最后的结果对所有的f[i]遍历一遍取最大
for(int i=1;i<=n;i++) res = max(res,f[i]);

cout<<res<<endl;
return 0;
}



## 能够输出最大上升子序列中的元素的写法

//这里f[i]表示以第i个元素结尾的上升序列的集合中长度最大值
//状态方程 f[i] = max(f[j]+1) 这里j表示第i个元素前面的一个数
// 时间复杂度为O(n^2)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int a[N],f[N];
int g[N];//用于存储答案中的元素的下标
int n;
int main(){
//正常输入的部分
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];

for(int i=1;i<=n;i++){
f[i] = 1;//这里表示上升序列中只包含a[i]一个元素 序列的长度为1
g[i] = 0;
for(int j=1;j<i;j++)
//必须保证a[j]小于a[i]的时候 状态计算才成立 因为这是一个上升的子序列
if(a[j]<a[i]){
if(f[i]<f[j]+1){
f[i] = f[j]+1;
g[i] = j;//记录
}
}
}
int res = 0;
int k =1;
//最后的结果对所有的f[i]遍历一遍取最大
for(int i=1;i<=n;i++){
if(f[k]<f[i])
k = i;
}
cout<<f[k]<<endl;//f[k]就是最大的上升子序列的长度

for(int i =0,len = f[k];i<len;i++){
cout<<a[k]<<" ";
k = g[k];//g[k]中存储的为要输出的下标
}
return 0;
}



Pinguier
13天前

## dp入门题

//这里f[i][j]表示起点到第i行第j列的元素的路径的最大值
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510,INF = 0x3f3f3f3f;
int a[N][N];
int f[N][N];
int n;

int main(){
cin>>n;
//初始化三角形
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin>>a[i][j];
//初始化状态    从上往下遍历寻找的话 j的取值应该从0到j+1
//因为对于边界的点来说可能会访问到不存在的点
//比如左边界可能会访问到0列的元素
//右边界的点可能会访问到第i+1列的元素
for(int i=1;i<=n;i++)
for(int j=0;j<=i+1;j++){
f[i][j] = -INF;
}
//从上到下进行状态计算的话 第一行的元素的状态值f[1][1]直接为自身的值
f[1][1] = a[1][1];
//从第二行的元素开始进行状态计算
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++)
f[i][j] = max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);

int res = -INF;
//最大值为起点到最后一行的某个点的最大距离 需要遍历最后一行的元素 求最大值
for(int i=1;i<=n;i++) res = max(res,f[n][i]);

cout<<res<<endl;

return 0;
}