头像

Pinguier

青岛大学




离线:15小时前


最近来访(75)
用户头像
sealt
用户头像
Double_Leaf
用户头像
._6495
用户头像
incra
用户头像
窦尊
用户头像
cloudsRise
用户头像
窦焕民
用户头像
Eureka_7
用户头像
懒回顾_3
用户头像
herry_01
用户头像
不高兴的兽奶
用户头像
需要时间
用户头像
嗨嗨害
用户头像
不要不听话
用户头像
violet_garden
用户头像
CodeSlogan
用户头像
又菜了
用户头像
文元每
用户头像
Joyasa
用户头像
反方向的钟

活动打卡代码 AcWing 4723. 队列

Pinguier
15小时前

思维模拟题

比赛的时候只想到暴力的小菜鸡
本题寻找规律 可以发现 第一次5 第二次10 第三次20 第四次40 每次将abcde全部弹出的个数每次变为之前的二倍 最后找到n位于的那一个区间 在那个区间里被分为5份 第一份为a 第二份为b 后面为 c d e 所以这里求出在本区间n位于哪一段即可

补充公式
[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,否则输出 no。

数据范围
输入字符串长度不超过 10000。

样例

输入样例:
(){}
输出样例:
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;
}




活动打卡代码 AcWing 4721. 排队

单调栈+二分

奇特的逆序构造单调栈

#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;
}


活动打卡代码 AcWing 4720. 字符串

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

#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;
}




活动打卡代码 AcWing 898. 数字三角形

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;
}