头像

kerman0411




离线:1小时前


最近来访(12)
用户头像
StkOvflow
用户头像
程点
用户头像
摆烂波比
用户头像
Lia_5
用户头像
Amaryllis_
用户头像
sprDream
用户头像
从黑夜走向白昼
用户头像
NZX
用户头像
Q1nghuan
用户头像
hutianshuo
用户头像
BlackAjactic


#include <bits/stdc++.h>

using namespace std;

int n;
int h[100005], ph[100005], hp[100005], cnt;

void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int x)
{
    int t = x;
    if ( x * 2 <= n && h[x * 2] < h[t] ) t = x * 2;
    if ( x * 2 + 1 <= n && h[x * 2 + 1] < h[t] ) t = x * 2 + 1;
    if ( x != t )
    {
        heap_swap(x, t);
        down(t);
    }
}

void up(int x)
{
    while ( x / 2 && h[x] < h[x / 2] )
    {
        heap_swap(x, x / 2);
        x /= 2;
    }
}

void add(int x)
{
    cnt ++;
    n ++;
    ph[cnt] = n;
    hp[n] = cnt;
    h[n] = x;
    up(n);
}

int query()
{
    return h[1];
}

void remove_root()
{
    heap_swap(1, n);
    n --;
    down(1);
}

void remove(int k)
{
    k = ph[k];
    heap_swap(k, n);
    n --;
    up(k);
    down(k);
}

void f(int k, int x)
{
    k = ph[k];
    h[k] = x;
    up(k);
    down(k);
}

int main()
{
    int q;
    cin >> q;

    while ( q -- )
    {
        string opr;
        cin >> opr;
        int k, x;
        if ( opr == "I" )
        {
            cin >> x;
            add(x);
        }else if ( opr == "PM" )
        {
            /*for ( int i = 1 ; i <= n ; ++ i )
            {
                cout << h[i] << ' ';
            }
            cout << endl;*/
            cout << query() << endl;
        }else if ( opr == "DM" )
        {
            remove_root();
        }else if ( opr == "D" )
        {
            cin >> k;
            remove(k);
        }else if ( opr == "C" )
        {
            cin >> k >> x;
            f(k, x);
        }
    }
    return 0;
}


活动打卡代码 AcWing 838. 堆排序

#include <bits/stdc++.h>

using namespace std;

int n;
int h[100005];

void down(int x)
{
    int t = x;
    if ( x * 2 <= n && h[x * 2] < h[t] ) t = x * 2;
    if ( x * 2 + 1 <= n && h[x * 2 + 1] < h[t] ) t = x * 2 + 1;
    if ( x != t )
    {
        swap(h[x], h[t]);
        down(t);
    }
}

void remove_root()
{
    h[1] = h[n];
    n --;
    down(1);
}

int main()
{
    int m;
    cin >> n >> m;
    for ( int i = 1 ; i <= n ; ++ i )
    {
        cin >> h[i];
    }
    for ( int i = n / 2 ; i ; -- i )
    {
        down(i);
    }
    for ( int i = 1 ; i <= m ; ++ i )
    {
        cout << h[1] << ' ';
        remove_root();
    }
    return 0;
}



题目描述

高桥买了个台钟。这个钟采用 $24$ 小时计时法,显示的时间为 $\overline{AB}:\overline{CD}$。
当且仅当 $0\leq \overline {AB}<24$ 且 $0\leq \overline {CD}<60$ 时我们称这个时间是合法的。

高桥决定将满足以下条件的时间叫做 “迷惑时间”:

如果把 $B$ 和 $C$ 交换,这个时间仍然是合法的。
比如说 $20:13$ 是“迷惑时间”,因为 $21:03$ 是合法的。

现在高桥的钟显示的时间是 $H:M$。请你求出离现在最近的“迷惑时间”(包括现在)。

样例

输入 #1
1 23

输出 #1
1 23

输入 #2
19 57

输出 #2
20 0

输入 #3
20 40

输出 #3
21 0

算法1

(暴力枚举)

直接暴力枚举每一个时间,判断是不是“迷惑时间”。

时间复杂度 $O(n)$

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int h, m;
int a1, a2, b1, b2;
bool check(int H, int M)
{
    if ( H >= 0 && H < 24 && M >= 0 && M < 60 )
    {
        return 1;
    }else
    {
        return 0;
    }
}
int main()
{
    cin >> h >> m;
    while ( h <= 23 && m <= 59 )
    {
        int h1 = h / 10 * 10 + m / 10;
        int m1 = h % 10 * 10 + m % 10;
        if ( check(h1, m1) )
        {
            break;
        }
        m ++;
        if ( m >= 60 )
        {
            h ++;
            m -= 60;
        }
        if ( h >= 24 )
        {
            h -= 24;
        }
    }
    cout << h << ' ' << m;
    return 0;
}



#include <bits/stdc++.h>
using namespace std;
int fa[100005];
int cnt[100005];
int n;
void init()
{
    for ( int i = 1 ; i <= n ; ++ i )
    {
        fa[i] = i;
        cnt[i] = 1;
    }
}
int ask(int k)
{
    if ( k == fa[k] )
    {
        return k;
    }else
    {
        fa[k] = ask(fa[k]);
        cnt[k] = cnt[fa[k]];
        return fa[k];
    }
}
void merge(int a, int b)
{
    if ( ask(a) != ask(b) )
    {
        cnt[ask(b)] += cnt[ask(a)];
        fa[ask(a)] = ask(b);
    }
}
int main()
{
    int m;
    cin >> n >> m;
    init();
    for ( int i = 1 ; i <= m ; ++ i )
    {
        string opr;
        int a, b;
        cin >> opr;
        if ( opr == "C" )
        {
            cin >> a >> b;
            merge(a, b);
        }else if ( opr == "Q1" )
        {
            cin >> a >> b;
            if ( ask(a) != ask(b) )
            {
                cout << "No\n";
            }else
            {
                cout << "Yes\n";
            }
        }else
        {
            cin >> a;
            cout << cnt[ask(a)] << endl;
        }
    }
    return 0;
}



数据结构笔记

1.链表:

屏幕截图_20230124_163536.png

屏幕截图_20230124_163623.png

2.栈

屏幕截图_20230124_163659.png

屏幕截图_20230124_163722.png

屏幕截图_20230124_163814.png

3.队列

屏幕截图_20230124_163752.png

屏幕截图_20230124_163845.png

屏幕截图_20230124_163907.png

4.Trie

屏幕截图_20230124_164006.png

屏幕截图_20230124_164013.png

5.KMP

屏幕截图_20230124_164058.png

屏幕截图_20230124_164107.png

6.并查集

屏幕截图_20230124_164206.png

屏幕截图_20230124_164216.png

屏幕截图_20230125_205207.png

更新中…




题目描述

一共有 $n$ 个数,编号是 $1∼n$,最开始每个数各自在一个集合中。

现在要进行 $m$ 个操作,操作共有两种:

M a b,将编号为 $a$ 和 $b$ 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;
Q a b,询问编号为 $a$ 和 $b$ 的两个数是否在同一个集合中;

样例

输入样例:
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例:
Yes
No
Yes

算法1

(并查集)

屏幕截图_20230124_161209.png

屏幕截图_20230124_161404.png

时间复杂度 $O(nlogn)$

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int fa[100005];
int n;
void init()
{
    for ( int i = 1 ; i <= n ; ++ i )
    {
        fa[i] = i;
    }
}
int ask(int k)
{
    if ( k == fa[k] )
    {
        return k;
    }else
    {
        fa[k] = ask(fa[k]);
        return fa[k];
    }
}
void merge(int a, int b)
{
    if ( ask(a) != ask(b) )
    {
        fa[ask(a)] = ask(b);
    }
}
int main()
{
    int m;
    cin >> n >> m;
    init();
    for ( int i = 1 ; i <= m ; ++ i )
    {
        string opr;
        int a, b;
        cin >> opr;
        if ( opr == "M" )
        {
            cin >> a >> b;
            merge(a, b);
        }else if ( opr == "Q" )
        {
            cin >> a >> b;
            if ( ask(a) != ask(b) )
            {
                cout << "No\n";
            }else
            {
                cout << "Yes\n";
            }
        }
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla


活动打卡代码 AcWing 836. 合并集合

#include <bits/stdc++.h>
using namespace std;
int fa[100005];
int n;
void init()
{
    for ( int i = 1 ; i <= n ; ++ i )
    {
        fa[i] = i;
    }
}
int ask(int k)
{
    if ( k == fa[k] )
    {
        return k;
    }else
    {
        fa[k] = ask(fa[k]);
        return fa[k];
    }
}
void merge(int a, int b)
{
    if ( ask(a) != ask(b) )
    {
        fa[ask(a)] = ask(b);
    }
}
int main()
{
    int m;
    cin >> n >> m;
    init();
    for ( int i = 1 ; i <= m ; ++ i )
    {
        string opr;
        int a, b;
        cin >> opr;
        if ( opr == "M" )
        {
            cin >> a >> b;
            merge(a, b);
        }else if ( opr == "Q" )
        {
            cin >> a >> b;
            if ( ask(a) != ask(b) )
            {
                cout << "No\n";
            }else
            {
                cout << "Yes\n";
            }
        }
    }
    return 0;
}



题目描述

维护一个字符串集合,支持两种操作:

I x 向集合中插入一个字符串 $x$;
Q x 询问一个字符串在集合中出现了多少次。
共有 $N$ 个操作,所有输入的字符串总长度不超过 $10^5$,字符串仅包含小写英文字母。

样例

输入样例:
5
I abc
Q abc
Q ab
I ab
Q ab

输出样例:
1
0
1

算法1

(STL map)

直接用一个 $map$ 记录每个字符串出现了几次。

时间复杂度 $O(n)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
map<string, int> cnt;
int main()
{
    int n;
    cin >> n;
    string s;
    while ( n -- )
    {
        string s;
        char op;
        cin >> op >> s;
        if ( op == 'I' )
        {
            cnt[s] ++;
        }else
        {
            cout << cnt[s] << endl;
        }
    }
    return 0;
}

算法2

(Trie)

屏幕截图_20230124_153008.png

屏幕截图_20230124_153313.png

时间复杂度 $O(n)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int sons[100005][26], cnt[100005], sz;
void insert(string s)
{
    int p = 0;
    for ( int i = 0 ; i < s.length() ; ++ i )
    {
        if ( !sons[p][s[i] - 'a'])
        {
            sons[p][s[i] - 'a'] = ++ sz;
        }
        p = sons[p][s[i] - 'a'];
    }
    cnt[p] ++;
}
int query(string s)
{
    int p = 0;
    for ( int i = 0 ; i < s.length() ; ++ i )
    {
        if ( !sons[p][s[i] - 'a'])
        {
            return 0;
        }
        p = sons[p][s[i] - 'a'];
    }
    return cnt[p];
}
int main()
{
    int n;
    cin >> n;
    string s;
    while ( n -- )
    {
        string s;
        char op;
        cin >> op >> s;
        if ( op == 'I' )
        {
            insert(s);
        }else
        {
            cout << query(s) << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 835. Trie字符串统计

#include <bits/stdc++.h>
using namespace std;
int sons[100005][26], cnt[100005], sz;
void insert(string s)
{
    int p = 0;
    for ( int i = 0 ; i < s.length() ; ++ i )
    {
        if ( !sons[p][s[i] - 'a'])
        {
            sons[p][s[i] - 'a'] = ++ sz;
        }
        p = sons[p][s[i] - 'a'];
    }
    cnt[p] ++;
}
int query(string s)
{
    int p = 0;
    for ( int i = 0 ; i < s.length() ; ++ i )
    {
        if ( !sons[p][s[i] - 'a'])
        {
            return 0;
        }
        p = sons[p][s[i] - 'a'];
    }
    return cnt[p];
}
int main()
{
    int n;
    cin >> n;
    string s;
    while ( n -- )
    {
        string s;
        char op;
        cin >> op >> s;
        if ( op == 'I' )
        {
            insert(s);
        }else
        {
            cout << query(s) << endl;
        }
    }
    return 0;
}



题目描述

请你将 $n$ 个中缀表达式转换为后缀表达式。

样例

输入
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

输出
abc*+
ab+zx+*
at+bac++cd+^*

算法1

(栈)

SPOJ 4 Transform the Expression.png

时间复杂度 $O(nt)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
stack<char> st;
int t;
string s;
int main()
{
    cin >> t;
    while ( t -- )
    {
        cin >> s;
        for ( int i = 0 ; i < s.length() ; ++ i )
        {
            if ( s[i] >= 'a' && s[i] <= 'z' )
            {
                cout << s[i];
            }else if ( s[i] == '(' )
            {
                st.push('(');
            }else if ( s[i] == ')' )
            {
                while ( !st.empty() && st.top() != '(')
                {
                    cout << st.top();
                    st.pop();
                }
                st.pop();
            }else
            {
                st.push(s[i]);
            }
        }
        cout << endl;
    }
    return 0;
}