Code Practice

一、STL
二、迭代
- e.g.8 [NOIP1998 普及组] 幂次方

📌

一、STL📌

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;

 insert /pushback

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.2 约瑟夫问题📌

题目描述

$n$ 个人围成一圈，从第一个人开始报数,数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

输入格式

输入两个整数 $n,m$。

输出格式

输出一行 $n$ 个整数，按顺序输出每个出圈人的编号。

样例

样例输入

10 3

样例输出

1	`3 6 9 2 7 1 8 5 10 4`

提示

$1 \le m, n \le 100$

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

int main() {
   int n, m;            // n是人数，m是报数到几出列
   cin >> n >> m;

   queue<int> q;        // 创建队列模拟圆圈中的人
   for (int i = 1; i <= n; i++) {  // 将1到n的数字放入队列
       q.push(i);       // 数字代表每个人的编号
   }

   for (int i = 1; i <= n; i++) {   // 一共要出列n个人
       for (int j = 1; j < m; j++) { // 每次报数到m-1
           int f = q.front();        // 取出队首的人
           q.pop();                  // 移除队首
           q.push(f);               // 将这个人放到队尾(因为没报到m，不用出列)
       }
       cout << q.front() << ' ';    // 输出报数为m的人(即出列的人)
       q.pop();                     // 移除这个人(出列)
   }
}

\[ 用数学方法\\ f(n,k)=(f(n−1,k)+k)\mod n \]

#include <iostream>
using namespace std;

int josephus(int n, int k) {
    if (n == 1) return 0;
    return (josephus(n - 1, k) + k) % n;
}

int main() {
    int n, k;
    cin >> n >> k;
    int result = josephus(n, k);
    cout << result + 1 << ' '; // 输出结果加1，因为题目中的位置是从1开始的
    return 0;
}

e.g.3 [NOIP2010 提高组] 机器翻译📌

题目背景

NOIP2010 提高组 T1

题目描述

小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。

这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

假设内存中有 $M$ 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 $M-1$，软件会将新单词存入一个未使用的内存单元；若内存中已存入 $M$ 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。

假设一篇英语文章的长度为 $N$ 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

输入格式

共 $2$ 行。每行中两个数之间用一个空格隔开。

第一行为两个正整数 $M,N$，代表内存容量和文章的长度。

第二行为 $N$ 个非负整数，按照文章的顺序，每个数（大小不超过 $1000$）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

输出格式

一个整数，为软件需要查词典的次数。

样例

样例输入

1 2	`3 7 1 2 1 5 4 4 1`

样例输出

提示

样例解释

整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：

1：查找单词 1 并调入内存。
1 2：查找单词 2 并调入内存。
1 2：在内存中找到单词 1。
1 2 5：查找单词 5 并调入内存。
2 5 4：查找单词 4 并调入内存替代单词 1。
2 5 4：在内存中找到单词 4。
5 4 1：查找单词 1 并调入内存替代单词 2。

共计查了 $5$ 次词典。

数据范围

对于 $10\%$ 的数据有 $M=1$，$N \leq 5$；
对于 $100\%$ 的数据有 $1 \leq M \leq 100$，$1 \leq N \leq 1000$。

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

int main() {
    int M, N;           
    cin >> M >> N;     
    int count = 0;     

    queue<int> Q;       // 创建队列Q
    set<int> seen;      // 创建集合seen，用于快速判断某个数是否在缓存中

    for (int i = 0; i < N; i++) {          
        if (seen.find(i) == seen.end()) {  // 如果数字i不在seen集合中
                                          // seen.find()返回迭代器，如果找不到返回seen.end()
            Q.push(i);                    // 将i加入队列
            seen.insert(i);               // 将i加入seen集合
            count++;                      // 缓存未命中次数加1
        }

        if (Q.size() > M) {              // 如果队列大小超过了限制M
            int removed = Q.front();      // 获取队列最前面的元素
            Q.pop();                      // 从队列中移除这个元素
            seen.erase(removed);          // 从seen集合中也移除这个元素
        }
    }

    cout << count;      
    return 0;
}

queue name	创建
push	队尾插入
pop	队首弹出
size()	返回元素个数
front()	队首元素
back()	队尾元素

3、Stack 栈📌

e.g.4括号序列📌

题目描述

定义如下规则：

空串是「平衡括号序列」
若字符串 $S$ 是「平衡括号序列」，那么 $\texttt{[}S\texttt]$ 和 $\texttt{(}S\texttt)$ 也都是「平衡括号序列」
若字符串 $A$ 和 $B$ 都是「平衡括号序列」，那么 $AB$（两字符串拼接起来）也是「平衡括号序列」。

例如，下面的字符串都是平衡括号序列：

()，[]，(())，([])，()[]，()[()]

而以下几个则不是：

(，[，]，)(，())，([()

现在，给定一个仅由 (，)，[，]构成的字符串 $s$，请你按照如下的方式给字符串中每个字符配对： 1. 从左到右扫描整个字符串。 2. 对于当前的字符，如果它是一个右括号，考察它与它左侧离它最近的未匹配的的左括号。如果该括号与之对应（即小括号匹配小括号，中括号匹配中括号），则将二者配对。如果左侧未匹配的左括号不存在或与之不对应，则其配对失败。

配对结束后，对于 $s$ 中全部未配对的括号，请你在其旁边添加一个字符，使得该括号和新加的括号匹配。

输入格式

输入只有一行一个字符串，表示 $s$。

输出格式

输出一行一个字符串表示你的答案。

样例

样例输入

([()

样例输出

()[]()

样例 #2

样例输入 #2

([)

样例输出 #2

()[]()

提示

数据规模与约定

对于全部的测试点，保证 $s$ 的长度不超过 $100$，且只含 (，)，[，] 四种字符。

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

int main() {
    string input;
    stack<int> st;  // Stack will store indices instead of characters
    vector<bool> matched;  // Track which positions are properly matched
    string answer;

    cin >> input;

    // Initialize matched vector with same size as input
    matched.resize(input.length(), false);

    // First pass: Find all matching pairs
    for (int i = 0; i < input.length(); ++i) {
        if (input[i] == '(' || input[i] == '[') {
            st.push(i);  // Push index onto stack
        } 
        else if (input[i] == ')' || input[i] == ']') {
            if (!st.empty()) {
                char opening = input[st.top()];
                // Check if brackets match
                if ((input[i] == ')' && opening == '(') ||
                    (input[i] == ']' && opening == '[')) {
                    // Mark both positions as matched
                    matched[i] = true;
                    matched[st.top()] = true;
                    st.pop();
                }
            }
        }
    }

    // Second pass: Build answer string
    for (int i = 0; i < input.length(); ++i) {
        if (!matched[i]) {
            // Replace unmatched brackets with their complete pairs
            if (input[i] == '(' || input[i] == ')') {
                answer += "()";
            } else {
                answer += "[]";
            }
        } else {
            // Keep matched brackets as they are
            answer += input[i];
        }
    }

    cout << answer << endl;
    return 0;
}

4、杂题（字典序）📌

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\)

Code Practice

📌

一、STL📌

1、vector📌

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

2、 队列📌

e.g.2 约瑟夫问题📌

e.g.3 [NOIP2010 提高组] 机器翻译📌

3、Stack 栈📌

e.g.4括号序列📌

4、杂题（字典序）📌

e.g.5 String Minimization📌

二、迭代📌

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

2、队列📌