其他

1、vector
- e.g.1 【深基15.例2】寄包柜
2、杂题
- e.g.5 String Minimization
- e.g.8 [NOIP1998 普及组] 幂次方

1、vector🧀

Tip

顺序容器，任意类型动态数组

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++) {
        cin>>v[i];
    }
    for(int i=0;i<n;i++) {
        cout<<v[i]+1<<" ";
    }
}

v.resize(2*n);
cout<<v.size()<<endl;

e.g.1 【深基15.例2】寄包柜🧀

题目描述

超市里有 $n(1\le n\le10^5)$ 个寄包柜。每个寄包柜格子数量不一，第 $i$ 个寄包柜有 $a_i(1\le a_i\le10^5)$ 个格子，不过我们并不知道各个 $a_i$ 的值。对于每个寄包柜，格子编号从 1 开始，一直到 $a_i$。现在有 $q(1 \le q\le10^5)$ 次操作：

1 i j k：在第 $i$ 个柜子的第 $j$ 个格子存入物品 $k(0\le k\le 10^9)$。当 $k=0$ 时说明清空该格子。
2 i j：查询第 $i$ 个柜子的第 $j$ 个格子中的物品是什么，保证查询的柜子有存过东西。

已知超市里共计不会超过 $10^7$ 个寄包格子，$a_i$ 是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。

输入格式

第一行 2 个整数 $n$ 和 $q$，寄包柜个数和询问次数。

接下来 $q$ 个行，每行有若干个整数，表示一次操作。

输出格式

对于查询操作时，输出答案，以换行隔开。

样例

样例输入

5 4
1 3 10000 118014
1 1 1 1
2 3 10000
2 1 1

样例输出

1 2	`118014 1`

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

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

    vector<vector<int> > A(n + 1);
    for (int i = 1; i <= q; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int I, j, k;
            cin >> I >> j >> k;
            if (A[I].size() < j + 1) {//in case there is no 'j'
                A[I].resize(j + 1);//resize the 'j'
            }
            A[I][j] = k;
        }
        if (op == 2) {
            int I, j;
            cin >> I >> j;
            cout << A[I][j] << endl;
        }
    }
}

2、杂题🧀

e.g.5 String Minimization🧀

题目描述

你有四个长 $n$ 的字符串 $a,b,c,d$。你可以执行任意多次如下操作：

选择一个 $i$，交换 $a_i,c_i$，然后交换 $b_i,d_i$。

求在 $a$ 的字典序尽量小的前提下，$b$ 字典序最小是什么。

如果你不知道什么是字典序，看这里：

对于两个字符串 $p,q$，称 $p$ 的字典序小于 $q$（记为 $p<q$），当且仅当存在自然数 $k$ 使 $p,q$ 的前 $k$ 个字符相同且 $p_{k+1}$ 的 ASCII 码小于 $q_{k+1}$ 的 ASCII 码。

例如： - $\texttt{abc}<\texttt{baa}$（当 $k=0$） - $\texttt{bae}<\texttt{bbb}$（当 $k=1$）

输入格式

输入的第一行有一个正整数 $n$，表示字符串 $a,b,c,d$ 长度。

之后四行，每行一个字符串，分别表示 $a,b,c,d$。

输出格式

输出一行一个字符串，表示题目要求的字符串 $b$。

样例

样例输入

8
westlake
yummyqaq
weabzzke
azazazaq

样例输出

1	`auazyqaq`

提示

【样例解释】

选择 $i$ 为 $1,3,4$ 可以让 $a$ 取到最小的字典序 $\texttt{weablake}$，此时字符串 $b$ 也得到满足题意最小的字典序 $\texttt{auazyqaq}$。

事实上如果 $i=1$ 时不操作 $a$ 的字典序也是最小的，但是此时字符串 $b$ 就是 $\texttt{yuazyqaq}$，不够小。

【数据范围】

本题共 $10$ 个测试点，每个测试点 $10$ 分。

测试点编号	$n\le$	特殊性质
$1\sim 2$	$15$
$3$	$10^5$	$a_i>c_i$
$4\sim 5$	$10^5$	$a_i\ne c_i$
$6\sim 7$	$10^5$	$b_i\ge d_i$
$8\sim 10$	$10^5$

对于全体数据，保证 $1\le n\le 10^5$，字符串所有字符都是小写字母。

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

int main() {
  int len;
  cin >> len;
  string a, b, c, d;
  cin >> a >> b >> c >> d;

  for(int i = 0; i < len; i++) {
    // 如果交换后能让a或b变得更小，就进行交换
    if(min(a[i], c[i]) != a[i] ||
       (a[i] == c[i] && min(b[i], d[i]) != b[i])) {
      swap(a[i], c[i]);
      swap(b[i], d[i]);
       }
  }

  cout << b << endl;
  return 0;
}
/*
    此题中，比较整体字典序：每位比较即可
    min(a[i], c[i]) != a[i]：检查是否可以让a变得更小
    (a[i] == c[i] && min(b[i], d[i]) != b[i])：当a不能再变小时，检查是否可以让b变得更小
*/

e.g.8 [NOIP1998 普及组] 幂次方🧀

题目描述

任何一个正整数都可以用 $2$ 的幂次方表示。例如 $137=2⁷⁺²3+2^0 $。

同时约定次方用括号来表示，即 $a^b$ 可表示为 $a(b)$。

由此可知，$137$ 可表示为 $2(7)+2(3)+2(0)$

进一步：

$7= 2^2+2+2^0$ ( $2^1$ 用 $2$ 表示)，并且 $3=2+2^0$。

所以最后 $137$ 可表示为 $2(2(2)+2+2(0))+2(2+2(0))+2(0)$。

又如 $1315=2^{10} +2^8 +2^5 +2+1$

所以 $1315$ 最后可表示为 $2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)$。

输入格式

一行一个正整数 $n$。

输出格式

符合约定的 $n$ 的 $0, 2$ 表示（在表示中不能有空格）。

样例

样例输入

样例输出

1	`2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)`

提示

【数据范围】

对于 $0100\%$ 的数据，$1 \le n \le 2 \times {10}^4$。

#include <bits/stdc++.h>
using namespace std;
void divide(int x)
{
    bool flag = false; 
    while (x != 0)
    {
        int t = int(log2(x));

        if (flag) cout << "+"; 
        if (t == 1) cout << "2"; 
        else if (t == 0) cout << "2(0)"; 
        else
        {
            cout << "2(";
            divide(t); 
            cout << ")";
        }
        x -= pow(2,t); 
        flag = true;
    }
}
int main() {
    int x;
    cin >> x;
    divide(x);
    return 0;
}

测试点编号	\(n\le\)	特殊性质
\(1\sim 2\)	\(15\)
\(3\)	\(10^5\)	\(a_i>c_i\)
\(4\sim 5\)	\(10^5\)	\(a_i\ne c_i\)
\(6\sim 7\)	\(10^5\)	\(b_i\ge d_i\)
\(8\sim 10\)	\(10^5\)