头像

静心寡欲




离线:11分钟前


最近来访(16)
用户头像
bxcXCX
用户头像
1只小牛马
用户头像
踏碎宴席
用户头像
carder
用户头像
仅冇旳坚持
用户头像
Yuniverse
用户头像
LcccY
用户头像
狐闹
用户头像
未蓝光途
用户头像
CSGOD2022
用户头像
前程似锦国
用户头像
wyzde18
用户头像
伞兵一号lubenwei
用户头像
balsamf
用户头像
yxc

活动打卡代码 AcWing 1875. 贝茜的报复

静心寡欲
26分钟前
#include<bits/stdc++.h>
using namespace std;

int ans;
//mp1存每一个字母奇数的个数,mp2存每一个字母偶数的个数,a存每一个字母的枚举为奇数还是偶数
map<char, int> mp1, mp2, a;
string s = "BESIGOM";//字母顺序无所谓,全部表示出来就行
void dfs(int u, int x){
    if(u == 7){
        if((a['B'] + a['I']) % 2 && (a['G'] + a['O'] + a['E'] + a['S']) % 2 && a['M'] % 2) return;
        ans += x;
        return;
    }
    char ch = s[u];
    a[ch] = 1, dfs(u + 1, x * mp1[ch]);//枚举ch为奇数的情况,累乘答案
    a[ch] = 2, dfs(u + 1, x * mp2[ch]);//枚举ch为偶数的情况,累乘答案
}
int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        char c; int x; cin >> c >> x;
        if(x % 2) mp1[c]++;//字母C中奇数的个数
        else mp2[c]++;//字母C中偶数的个数
    }
    dfs(0, 1);
    cout << ans;
    return 0;
}




静心寡欲
20小时前

堆就是一棵完全二叉树。

堆的常规操作(维护一堆数):

STL容器中:
1.插入一个数。
2.求数组中的最小值
3.删除最小值

手写堆还可以实现:
4.删除任意一个元素
5.修改任意一个元素。

堆的存储:

图片1.png
下标为先从上到下,再从左到右存储。

两种基本操作:down和up(越小越优秀hh)

down:大数向下走,与两个儿子比。
up:小数向上走,只与根节点比

怎样用两种基本操作来实现5种操作?

图片1.png

注意:

1.删掉堆尾元素只需size–,删掉堆头元素较困难。
2.down和up操作只会执行一个:,先写哪个都无所谓。
。证明:
如果先执行up[k],这个元素会往上走,换下来的新的heap[k]一定<任何一个下面的点,不会再down[k]了;
同理:如果先执行down[k],这个元素会往下走,换上来的新的heap[k]一定>任何一个上面的点,不会再up[k]了;

解体思路:

1.建小根堆:n个元素一个一个往里插o(nlogn),可以有一个o(n)的建堆方式,见代码。
2.每次取出堆顶元素
3.删除堆顶元素

C++代码:

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
const int N =100010;
int h[N];//堆
int cnt;//size会命名冲突,换成cnt,存储堆中元素下标(个数)
void down(int u)
{
    int t=u;//用t记录根节点和左右儿子最小值的下标
    if(u*2<=cnt&&h[u*2]<h[u]) t=u*2;
    if(u*2+1<=cnt&&h[u*2+1]<h[t]) t=u*2+1;
    if(t!=u)
    {
        swap(h[t],h[u]);
        down(t);//递归
    }
}
void up(int u)
{
    while(u/2&&h[u/2]>h[u])//越小越优秀
    {
        swap(h[u/2],h[u]);
        u/=2;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&h[++cnt]);
    }
    //o(n)的建堆方式
    for(int i=n/2;i;i--)
    down(i);

    while(m--)
    {
        printf("%d ",h[1]);
        //删除最小值
        h[1]=h[cnt];
        cnt--;
        down(1);
    }
    return 0;
}

时间复杂度:

取堆顶元素:o(1),down和up与堆的高度有关,都是o(logn);所以:O(mlogn)

图片来源:

AcWing 算法基础课




基本思想:

每一个集合用一个树表示,根节点的编号就是这个集合的编号。每个节点存储他的父节点,p[x]表示x的父节点
并查集思路.png
询问两个元素是否在一个集合当中。暴力做法十分耗时,不是O(1)的时间,并查集可以是近乎o(1)的时间完成
问题3:如何合并两个集合?假设Px是x的集合编号,py是y的集合编号:p[px]=py;
路径压缩优化:一旦搜到了某个点,就将这一路径上的所有点直接指向根节点。
递归过程:
图片1.jpg

#include<iostream>
using namespace std;
const int N=100010;
int p[N];
int n,m;
int find(int x)//查找祖宗节点并且实现路径压缩
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    int a,b;
    while(m--)
    {
        char op[2];
        cin>>op;
        if(*op=='M') 
        {
            cin>>a>>b;
            p[find(a)]=find(b);
        }
        else 
        {
            cin>>a>>b;
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

图片来源:AcWing算法基础课

时间复杂度:

建立n个集合o(n);
合并,查寻都是近似o(1)的



活动打卡代码 AcWing 3302. 表达式求值

#include<iostream>
#include<algorithm>
#include<cctype>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
int n;
const int N =200010;
char str[N];
stack <int> num;
stack<char> op;
unordered_map<char,int> h{{'+',1},{'-',1},{'*',2},{'/',2}};
void eval()
{
    int b=num.top();
    num.pop();
    int a=num.top();
    num.pop();
    char c=op.top();
    op.pop();
    int r=0;
    if(c=='+') r=a+b;
    if(c=='-') r=a-b;
    if(c=='*') r=a*b;
    if(c=='/') r=a/b;
    num.push(r);
}
int main()
{
    cin>>str;
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        if(isdigit(str[i])) 
        {
            int j=i,x=0;
            while(j<len&&isdigit(str[j]))
            {
                x=x*10+str[j]-'0';
                j++;
            }
            num.push(x);
            i=j-1;
        }
        else if(str[i]=='(')
        op.push('(');
        else if(str[i]==')')
        {
            while(op.top()!='(')
            {
                eval();
            }
            op.pop();
        }
        else
        {
            while(op.size()&&h[op.top()]>=h[str[i]])//为什么一定要加上op.size(),因为如果没有运算符,就无法进行运算
            eval();
            op.push(str[i]);
        }
    }
    while(op.size())
    eval();
    cout<<num.top()<<endl;
    return 0;
}



单调栈题型:

1.求一个数组中每一个元素左边(或右边)距离最近的小于(或大于)这个元素的数是多少;
如果每次将新的元素放入栈顶,并删掉不可能用到的元素,发现这个栈中元素是单调的,所以叫单调栈。

C++代码:

#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int N =100010;
int stk[N],tt;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        if(tt&&stk[tt]>=x) tt--;//如果stk[tt]>=x,则栈顶元素永远都用不到,删掉,删到栈空为止
        if(tt) cout<<stk[tt]<<" ";//如果栈不空,则栈顶元素即为所求
        else cout<<-1<<" ";//如果栈空,说明没找到比x小的元素。
        stk[++tt]=x;//新元素入栈
    }
    return 0;
}

时间复杂度分析:

每个元素最多进栈一次,最多出栈一次,时间复杂度o(2*n);
比暴力优化的地方:每个元素最多遍历两次,没用的元素不用多次遍历




用数组模拟队列:在队尾插入,从队头弹出

int q[N],hh=0,tt=-1;
//插入:
q[++tt]=x;
//弹出;
hh++;
//取出队头元素:
q[hh];
//判断是否为空:
if(hh<=tt) not empty;
else empty;

C++代码:

#include<iostream>
using namespace std;
const int N =100010;
int q[N],hh,tt=-1;
int m;
int main()
{
    scanf("%d",&m);
    string s;
    int x;
    while(m--)
    {
        cin>>s;
        if(s=="push")
        {
            cin>>x;
            q[++tt]=x;
        }
        else if(s=="empty")
        {
            if(hh<=tt) cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }
        else if(s=="query")
        {
            cout<<q[hh]<<endl;
        }
        else 
        hh++;
    }
    return 0;
}



用数组模拟栈:

int stk[N];
tt=0;//存放栈顶元素下标(只有tt,没有hh)
//插入元素x:
stk[++tt]=x;
//删除栈顶元素:
tt--;
//判断是否为空:
if(tt>0 ) 不空;
if(tt==0) 空;
//取出栈顶元素:
stk[tt];

C++代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N =100010;
int stk[N],tt;
int m;
int main()
{
    scanf("%d",&m);
    string s;
    int x;
    while(m--)
    {
        cin>>s;
        if(s=="push")
        {
            scanf("%d",&x);
            stk[++tt]=x;
        }
        else if(s=="query")
        {
            cout<<stk[tt]<<endl;
        }
        else if(s=="pop")
        {
            tt--;
        }
        else 
        {
            if(tt>0) cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 1884. COW

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n; string s;
    cin >> n >> s;

    long long c = 0, o = 0, w = 0;//分别代表C,CO,COW的数量
    for(auto ch : s){
        if(ch == 'C') c++;
        else if(ch == 'O') o += c;
        else w += o;
    }
    cout << w;
    return 0;
}



#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int N =100010;
int e[N],l[N],r[N],idx;
void init()
{
    //偷懒写法,不用再设head和tail
    r[0]=1;
    l[1]=0;
    idx=2;//下标从2开始
}
void add(int k,int x)//在下标是k的数的后面插入一个数。
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    //下面两行顺序不能变,否则r[k]的值会发生变化。
    l[r[k]]=idx;
    r[k]=idx++;
}
void remove(int k)
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}
int main()
{
    init();
    scanf("%d",&n);//n必须定义为全局变量,为什么?
    char op[2];
    int k,x;
    while(n--)
    {
        scanf("%s",op);
        if(op[0]=='R')
        {
            cin>>x;
            add(l[1],x);
        }
        else if(op[0]=='L')
        {
            cin>>x;
            add(0,x);
        }
        else if(op[0]=='D')
        {
            cin>>k;
            remove(k+1);//第1个插入的数下标是2,第k个插入的数的下标是k+1
        }
        else if(op[0]=='I'&&op[1]=='L')
        {
            cin>>k>>x;
            add(l[k+1],x);//注意是l[k+1],不是(k+1)-1
        }
        else 
        {
            cin>>k>>x;
            add(k+1,x);
        }
    }
    //输出链表
    for(int i=r[0];i!=1;i=r[i])
    printf("%d ",e[i]);
    return 0;
}



#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
int n;
vector<PII> segs;
void merge(vector<PII> &segs)//一定要传引用,否则不会改变segs
{
    vector<PII> res;
    sort(segs.begin(),segs.end());//按照左端点排序
    int st=-2e9,ed=-2e9;//可以将初始的区间设为假象的不存在的区间,由于所有区间按照左端点排序,所以初始值都为负无穷
    for(auto seg:segs)
    {
        if(seg.x>ed)
        {
            if(ed!=-2e9) res.push_back({st,ed});
            st=seg.x,ed=seg.y;
        }
        else 
        ed=max(ed,seg.y);
    }
    if(ed!=-2e9) res.push_back({st,ed});//加上最后一次处理的区间。由于区间数量>=1,不存在空区间的情况,去掉判断条件也可以。
    segs=res;//同种类的vector直接用=赋值
}
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        segs.push_back({l,r});
    }
    merge(segs);
    cout<<segs.size()<<endl;
    return 0;
}