#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;
}
活动打卡代码
AcWing 837. 连通块中点的数量
#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;
}
题目描述
一共有 $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
(并查集)
时间复杂度 $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)
时间复杂度 $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
(栈)
时间复杂度 $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;
}
