一、P1055 [NOIP 2008 普及组] ISBN 号码 - 洛谷

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

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	string s;
	cin>>s;
	
	string digits;
	for(char c:s){
		if(c!='-') digits+=c;
	}
	
	int mod=0,sum=0;
	for(int i=0;i<9;i++){
		sum+=(digits[i]-'0')*(i+1);
	}
	mod=sum%11;
	
	char correct;
	if(mod==10) correct='X';
	else correct='0'+mod;
	
	if(correct==digits[9]) cout<<"Right"<<endl;
	else{
		string res=s; 
		res[12]=correct;
		cout<<res<<endl;
	}
	
	return 0;
}

1.使用string来提取纯数字，用字符来遍历字符串，而不是数组。

2.将字符数字-'0'转换为整数，整数+’0‘转换为字符数字。

二、P5723 【深基4.例13】质数口袋 - 洛谷

用于处理<1e12的质数的优解

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

#define ll long long

bool isPrime(ll n){
	if(n<=1) return false;
	if(n==2) return true;
	if(n%2==0) return false;
	for(ll i=3;i*i<=n;i+=2){
		if(n%i==0) return false;
	}
	return true;
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	ll l,cnt=0,sum=0;
	cin>>l;
	

	for(ll i=2;i<l;i++){
		if(l-sum<i)break; 
		if(isPrime(i))
		{
		cout<<i<<endl;
		cnt++;
		sum+=i;
		}
		
	}
	cout<<cnt<<endl;
	
	return 0;
}

更优解：埃氏筛法

// 埃氏筛法预筛[2, max_n]内的质数
vector<bool> sieve(ll max_n){
    vector<bool> is_prime(max_n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for(ll i=2; i*i <= max_n; i++){
        if(is_prime[i]){
            for(ll j=i*i; j <= max_n; j+=i){
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

// 主函数中替换质数收集逻辑：
ll max_n = b;
vector<bool> is_prime = sieve(max_n);
for(ll i=a; i <= b; i++){
    if(is_prime[i]){
        c.push_back(i);
    }
}

三、P1217 [USACO1.5] 回文质数 Prime Palindromes - 洛谷

当普通数组（存储在栈上）的长度达到1e5以上的时候使用vector（存储在堆上，不容易栈溢出）更优

1e+4为浮点数，不能直接int a[1e+5];需要

typedef long long ll;
const ll MAX=1e+4;
ll a[MAX];

优先判断回文数，再判断质数，提高效率。

其他注意点如下注释中：

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

typedef long long ll; 
const ll MAX = 1e8 + 5; 

bool isPrime(ll n){
    if(n <= 1) return false;
    if(n == 2) return true;
    if(n % 2 == 0) return false;
    for(ll i=3; i*i <= n; i+=2){
        if(n % i == 0) return false;
    }
    return true;
}

bool isHui(ll n){
    if(n < 0 || (n % 10 == 0 && n != 0)) return false;
    if(n < 10) return true;
    ll rev = 0;
    ll temp = n; //用 temp 副本存储 n，避免修改原参数
    while(temp > rev){ 
        rev = rev * 10 + temp % 10;
        temp /= 10;
    }
    return temp == rev || temp == rev / 10;
}
 
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 
    
    ll a, b;
    cin >> a >> b;
    
    vector<ll> c; // 存储区间内的质数
    vector<ll> res; // 存储既是质数又是回文数的结果
    
        for(ll i = a; i <= b; i++){
        if(isHui(i)){
            c.push_back(i); 
        }
    } 
    
	    for(ll num : c){ 
        if(isPrime(num)){
            res.push_back(num); 
        }
    }
    
    for(ll ans : res){
        cout << ans << '\n'; // 用'\n'代替endl，更快
    }
    
    return 0;
}

vector<int> vec = {1,2,3,4};
cout << vec.size() << endl; // 输出 4（元素个数）
cout << vec.capacity() << endl; // 输出 ≥4（如 4）
cout << vec.front() << endl; // 1（首元素）
cout << vec.back() << endl; //4（尾元素）
if (vec.empty()) {
    cout << "空数组";
} else {
    cout << "非空";
}

const ll MAX = 1e8 + 5;
vector<ll> c(MAX); // 长度 1e8+5，堆上分配，无栈溢出（只要内存足够）
vector<ll> res; // 动态收集结果，无需提前定义长度

// 方式 1：固定行数和列数（如 100 行 200 列，元素默认 0）
vector<vector<int>> dp(100, vector<int>(200)); // dp[100][200]

// 方式 2：动态行数（如邻接表，n 个节点，每个节点的邻接节点动态添加）
int n = 10;
vector<vector<int>> adj(n); // 10 个空数组
adj[0].emplace_back(1); // 节点 0 连接节点 1
adj[0].emplace_back(2); // 节点 0 连接节点 2

// 遍历二维 vector
for (int i = 0; i < adj.size(); i++) {
    for (int j = 0; j < adj[i].size(); j++) {
        cout << adj[i][j] << " ";
    }
    cout << endl;
}

P1138 American Heritage

题目描述

Farmer John takes the heritage of his cows very seriously. He is not, however, a truly fine bookkeeper. He keeps his cow genealogies as binary trees and, instead of writing them in graphic form, he records them in the more linear tree in-order" and tree pre-order" notations.

Your job is to create the `tree post-order" notation of a cow"s heritage after being given the in-order and pre-order notations. Each cow name is encoded as a unique letter. (You may already know that you can frequently reconstruct a tree from any two of the ordered traversals.) Obviously, the trees will have no more than 26 nodes.

Here is a graphical representation of the tree used in the sample input and output:

              C
            /   \
           /     \
          B       G
         / \     /
        A   D   H
           / \
          E   F

The in-order traversal of this tree prints the left sub-tree, the root, and the right sub-tree.

The pre-order traversal of this tree prints the root, the left sub-tree, and the right sub-tree.

The post-order traversal of this tree print the left sub-tree, the right sub-tree, and the root.

----------------------------------------------------------------------------------------------------------------------------

题目大意：

给出一棵二叉树的中序遍历 (inorder) 和前序遍历 (preorder)，求它的后序遍历 (postorder)。

输入描述

Line 1:

The in-order representation of a tree.

Line 2:

The pre-o rder representation of that same tree.

Only uppercase letter A-Z will appear in the input. You will get at least 1 and at most 26 nodes in the tree.

输出描述

A single line with the post-order representation of the tree.

样例输入

ABEDFCHG CBADEFGH 

样例输出

AEFDBHGC

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

void build(string in,string pre){
	if(in.empty()) return;
	
	char root=pre[0];
	
	int pos=in.find(root); 
	
	build(in.substr(0,pos),pre.substr(1,pos));
	build(in.substr(pos+1),pre.substr(pos+1));
	
	cout<<root; 
	
} 

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	string in,pre;
	cin>>in>>pre;
	
	build(in,pre);
	
	return 0;
} 

P1268 连续子段的最大和

题目描述

给定一个长度为 nn 的数组 aa，请你从数组 aa 中找到连续的一段数，使得这段数的和最大。

其中 1≤n≤100001≤n≤10000，−60000≤ai≤60000−60000≤ai​≤60000。

输入描述

第一行是一个正整数 nn，表示数数组 aa 的长度，从第二行开始是 nn 个数据，代表 aiai​。

输出描述

一行，子段的最大和。

样例输入

5 1 -3 4 1 -9 

样例输出

5

最大子段和算法（Kadane 算法 / 卡登算法）

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

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	int n;cin>>n;
	vector<int> a(n);
	
	for(int i=0;i<n;i++){
		cin>>a[i];
	} 
	
	int max_sum=INT_MIN;
	int current=0;
	
	for(int num:a){
		current=max(num,current+num);
		max_sum=max(max_sum,current);
	}
	
	cout<<max_sum<<endl;
	
	return 0; 
}

P1439 背包九讲(1)：简单的0-1背包

题目描述

有一个箱子容量为 V（正整数，0＜＝V＜＝1000），同时有 n 个物品（0＜n＜＝100），每个物品有一定的体积和价值。要求 n 个物品中，任取若干个装入箱内，在箱子能放得下的前提下，满足箱子内部的价值最大。

输入描述

一个正整数 V，表示箱子容量

一个正整数 n，表示有 n 个物品

接下来 n 行，每行两个不超过 1000 的正整数，分别表示这 n 个物品的各自体积和价值

输出描述

一个整数，表示箱子能装下的最大价值。

样例输入  3 2 2 100 4 200

样例输出  100

样例解释

输入：

3 // 箱子的总的容量为 3

2 // 一共有两个物品

2 100 // 第一个物品的体积为 2 价值为 100

4 200 // 第二个物品的体积为 4 价值为 200

输出:

100

在箱子能装下的前提下，应该选择第 1 个物品，最大的价值为 100

数据规模

对于前三个测试点，0<n,V≤100<n,V≤10

对于第四个测试点，0<n≤100,0<V≤10000<n≤100,0<V≤1000

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXV = 1005;
const int MAXN = 105;

int dp[MAXV];         
int w[MAXN], v[MAXN]; 

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

    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }

    memset(dp, 0, sizeof(dp)); 

    for (int i = 1; i <= n; i++) {        
        for (int j = V; j >= w[i]; j--) { 
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << dp[V] << endl;
    return 0;
}

B1631 [Usaco2007 Feb]Cow Party

题目描述

寒假到了，nn 头牛都要去参加一场在编号为 xx 的牛的农场举行的派对，农场之间有 mm 条有向路，每条路都有一定的长度。

每头牛参加完派对后都必须回家，无论是去参加派对还是回家，每头牛都会选择最短路径，求这 nn 头牛的最短路径（一个来回）中最长的一条路径长度。

输入格式

第一行有三个整数，分别表示牛的数量 nn，道路数 mm 和派对农场编号 xx。

接下来 mm 行，每行三个整数 uu, vv, ww 表示存在一条由 uu 通向 vv 的长度为 ww 的道路。

对于全部的测试点，保证 1≤x≤n≤1031≤x≤n≤103，1≤m≤1051≤m≤105，1≤u,v≤n1≤u,v≤n，1≤w≤1021≤w≤102，保证从任何一个结点出发都能到达 xx 号结点，且从 xx 出发可以到达其他所有节点。

输出格式

输出一行一个整数表示答案。

样例输入

4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3 

样例输出

10 

提示

样例说明:

共有 4 只奶牛参加聚会，有 8 条路，聚会位于第 2 个农场.

第 4 只奶牛可以直接到聚会所在地 (花费 3 时间), 然后返程路线经过第 1 和第 3 个农场 (花费 7 时间), 总共 10 时间.

题目来源

Silver

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1005;

vector<pair<int, int>> g[MAXN], rg[MAXN];
int d1[MAXN], d2[MAXN];
int n, m, x;

void dijkstra(int s, int dist[], vector<pair<int, int>> graph[]) {
    for (int i = 1; i <= 1005; i++) {
        dist[i] = INF;
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

    dist[s] = 0;
    q.push(make_pair(0, s));

    while (!q.empty()) {
        pair<int, int> p = q.top();
        q.pop();

        int d = p.first;
        int u = p.second;

        if (d > dist[u]) continue;

        for (int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i].first;
            int w = graph[u][i].second;

            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                q.push(make_pair(dist[v], v));
            }
        }
    }
}

int main() {
    cin >> n >> m >> x;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back(make_pair(v, w));
        rg[v].push_back(make_pair(u, w));
    }

    dijkstra(x, d1, g);
    dijkstra(x, d2, rg);

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, d1[i] + d2[i]);
    }

    cout << ans << endl;

    return 0;
}

P1719 Let's play a game!

题目描述

现有一包含nn 个数的序列A1,A2,A3,...,AnA1​,A2​,A3​,...,An​，给定一个定值kk.

每次我们可以选择数列中一个下标为 2 的次幂的元素（如A1,A2,A4,A8...A1​,A2​,A4​,A8​...) 将其删除出数列（删除后，其后的所有元素会自动前移一格）。

问最少进行多少次操作，能将序列中所有值为kk 的元素删除？

输入描述

第一行两个整数n,kn,k

第二行nn 个整数，A1,A2,...,AnA1​,A2​,...,An​.

输出描述

第一行一个整数，为最少操作次数。

样例输入 1

Copy to Clipboard

5 2 1 2 4 2 5 

样例输出 1

Copy to Clipboard

2 

样例输入 2

Copy to Clipboard

5 2 1 2 2 2 2 

样例输出 2

Copy to Clipboard

4 

样例解释

对于样例11，依次删除A4,A2A4​,A2​，即可。

对于样例22，连续删除44 次A2A2​，即可。

数据规模与约定

1≤n≤3×1051≤n≤3×105。

P1740 Ink on paper

题目描述

Bob accidentally spilled some drops of ink on the paper. The initial position of the i-th drop of ink is (xixi​, yiyi​), which expands outward by 0.5 centimeter per second, showing a circle. The curious Bob wants to know how long it will take for all the inks to become connected. In order to facilitate the output, please output the square of the time.

输入描述

The first line of input contains one integer TT (1≤T≤51≤T≤5), indicating the number of test cases. For each test case, the first line contains one integer nn (2≤n≤50002≤n≤5000), indicating the number of ink on the paper. Each of the next n lines contains 2 integers (xixi​, yiyi​)(∣xi∣≤109,∣yi∣≤109∣xi​∣≤109,∣yi​∣≤109), indicating that xx and yy coordinates of the ink.

输出描述

For each test case, output one line containing one decimal, denoting the answer.

样例输入

Copy to Clipboard

2 3 0 0 1 1 0 1 5 1 1 4 5 1 4 2 6 3 10 

样例输出

Copy to Clipboard

1 17

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 5005;
const ll INF = 1e18;

ll x[MAXN], y[MAXN];
ll dist[MAXN];  // 到生成树的最小距离
bool vis[MAXN];
ll cost[MAXN][MAXN];

// 计算距离平方（直接避免浮点数！）
ll dis2(int i, int j) {
    ll dx = x[i] - x[j];
    ll dy = y[i] - y[j];
    return dx*dx + dy*dy;
}

ll Prim(int n) {
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) dist[i] = cost[1][i];
    
    vis[1] = true;
    ll max_edge = 0;
    
    for (int i = 2; i <= n; i++) {
        // 找最小边
        ll min_d = INF;
        int pos = -1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && dist[j] < min_d) {
                min_d = dist[j];
                pos = j;
            }
        }
        
        vis[pos] = true;
        max_edge = max(max_edge, min_d); // 记录最长边
        
        // 更新
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && cost[pos][j] < dist[j]) {
                dist[j] = cost[pos][j];
            }
        }
    }
    return max_edge;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
        
        // 预处理所有点之间距离平方
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cost[i][j] = dis2(i, j);
            }
        }
        
        cout << Prim(n) << endl;
    }
    return 0;
}

P1679 夏日旅行

题目描述

夏天的时候，ThinkSpiritThinkSpirit 实验室去海边玩了。蒙起眼睛的 CrushCrush 举起了木棒，他要在大家的帮助下打西瓜。

沙滩可以被描述成一个N×MN×M 的网格，其中某些格子为不可移动的障碍物。CrushCrush 总是在格子上，始终在格子上移动，且不会走出边界。西瓜也处于一个格子上，当 CrushCrush 走到西瓜所在格子，他就会举起木棒，重重挥下 —— 啪！

好心的其它成员当然会说出提示，来帮助CrushCrush，每个提示都会让CrushCrush 走向相邻（上下左右四个方向，不可出界）的一个可走的格子。问最少需要多少条提示，才能让CrushCrush 打到西瓜？

输入描述

第一行两个正整数 NN, MM( NN, M⩽50M⩽50)，表示沙滩的大小。

接下来 N 行，每行 M 个用空格隔开的 0 或 1，表示沙滩的构造。其中，0 表示此格点无障碍，1 表示此格点为不可移动的障碍物。

最后一行输入 4 个整数，分别表示 Crush（起始点）和西瓜（目标点）所在网格的行号与列号。(行号和列号从 1 开始，行号从上往下递增，列号从左往右递增。)

数据确保起始点与目标点都在无障碍的格点上。

输出描述

一个整数，表示需要的最小提示数，如果无论接收多少提示 CrushCrush 都不能抵达西瓜，输出 −1−1。

样例输入

9 10 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 3 3 4 4 

样例输出

6

#include<bits/stdc++.h>  // 万能头文件，包含所有C++常用库
using namespace std;

const int MAX = 55;      // 棋盘最大大小为50x50，开55足够使用

// 方向数组：控制上下左右四个方向移动
// dx[i] 对应行的变化，dy[i] 对应列的变化
int dx[] = {-1, 1, 0, 0};  // 上、下、左、右 → 行号变化
int dy[] = {0, 0, -1, 1};  // 上、下、左、右 → 列号变化

int grid[MAX][MAX];   // 存储地图网格
                    // grid[x][y] = 0 → 可以走
                    // grid[x][y] = 1 → 障碍物，不能走
int dist[MAX][MAX];   // 距离数组
                    // dist[x][y] = 从起点到 (x,y) 的最短步数
                    // dist[x][y] = -1 → 表示该格子还没有访问过
int n, m;            // n = 地图行数，m = 地图列数

// BFS 函数
// 功能：从起点 (sx, sy) 出发，走到终点 (ex, ey)
// 返回值：最短步数，走不到则返回 -1
int bfs(int sx, int sy, int ex, int ey) {
    // 初始化 dist 数组全部为 -1
    // -1 表示：格子未被访问过
    memset(dist, -1, sizeof(dist));

    // 队列：存储格子坐标 (x,y)
    queue<pair<int, int>> q;

    // 把起点加入队列
    q.push({sx, sy});
    dist[sx][sy] = 0;  // 起点的步数 = 0

    // BFS 主循环：队列不为空就继续
    while (!q.empty()) {
        // 取出队首元素（当前走到的格子）
        auto now = q.front();
        q.pop();  // 弹出队首

        // 当前坐标
        int x = now.first;   // 当前行
        int y = now.second;  // 当前列

        // 如果当前位置 == 终点，直接返回最短步数
        if (x == ex && y == ey) {
            return dist[x][y];
        }

        // 遍历 上下左右 四个方向
        for (int i = 0; i < 4; i++) {
            // 计算下一个格子的坐标
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 判断条件（必须全部满足才能走）
            // 1. nx, ny 不越界（在地图内部）
            // 2. grid[nx][ny] == 0 → 不是障碍物
            // 3. dist[nx][ny] == -1 → 没访问过
            if (nx >= 1 && nx <= n && ny >=1 && ny <= m) {
                if (grid[nx][ny] == 0 && dist[nx][ny] == -1) {
                    // 更新步数：上一步 +1
                    dist[nx][ny] = dist[x][y] + 1;
                    // 把新格子加入队列
                    q.push({nx, ny});
                }
            }
        }
    }

    // 循环结束还没找到终点 → 无法到达
    return -1;
}

int main() {
    // 输入加速（大数据不超时）
    ios::sync_with_stdio(0), cin.tie(0);

    // 输入地图行数 n 和列数 m
    cin >> n >> m;

    // 输入地图
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }

    // 输入起点坐标 (sx, sy) 和终点坐标 (ex, ey)
    int sx, sy, ex, ey;
    cin >> sx >> sy >> ex >> ey;

    // 调用 BFS，输出答案
    cout << bfs(sx, sy, ex, ey) << endl;

    return 0;
}

P1848 编辑距离

题目描述

设 AA 和 BB 是两个字符串。我们要用最少的字符操作次数，将字符串 AA 转换为字符串 BB。这里所说的字符操作共有三种：

1. 删除一个字符；
2. 插入一个字符；
3. 将一个字符改为另一个字符。

A,BA,B 均只包含小写字母。

输入描述

第一行为字符串 AA , 第二行为字符串 BB , 字符串长度均小于等于 20002000。

输出描述

输出一个整数，为最少字符操作次数。

样例输入

Copy to Clipboard

sfdqxbw gfdgw 

样例输出

Copy to Clipboard

4

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;

const int MAXN = 2005;
int dp[MAXN][MAXN];
string a, b;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> a >> b;
    int n = a.size();
    int m = b.size();
    
    // 初始化
    for(int i=0; i<=n; i++) dp[i][0] = i;
    for(int j=0; j<=m; j++) dp[0][j] = j;
    
    // DP 核心
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = min( min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1] ) + 1;
        }
    }
    
    cout << dp[n][m] << endl;
    return 0;
}

P1748 a+b+c+d==0

求和问题可以被看做是以下的公式，给定 A，B，C，D 四个列表，计算有多少四元组满足 (a, b, c, d) ∈ A × B × C × D 且 a + b + c + d = 0。我们推测所有的列表都有 n 个数字。

注：不同的四元组是指元素位置不一样的四元组

样例输入

输入的第一个数字指明有 T 组。每一组这样描述，第一行是列表大小 n， 然后有 n 行。每一行都有四个整型数字，分别属于 A，B，C，D 四列。

对于 100% 的数据， 1≤T≤2000,1≤n≤2000,−200≤a,b,c,d≤2001≤T≤2000,1≤n≤2000,−200≤a,b,c,d≤200。确保所有数据中 n2n2 的和不超过 4⋅1064⋅106。

样例输出

对于每一个测试用例，统计有多少个四元组满足他们的和是 0 。每一组数据一行。

Sample Input

1 6 -45 22 42 -16 -41 -27 56 30 -36 53 -37 77 -36 30 -75 -46 26 -38 -10 62 -32 -54 -6 45 

Sample Output

5

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

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	int T;cin>>T;
	
	while(T--){
		int n;
		cin>>n;
		
		vector<int> A,B,C,D;
		
		for(int i=0;i<n;i++){
			int a,b,c,d;
			cin>>a>>b>>c>>d;
			A.push_back(a);
			B.push_back(b);
			C.push_back(c);
			D.push_back(d);
		}
		
		vector<int> sumAB;
		
		for(int a:A)
			for(int b:B)
				sumAB.push_back(a+b);
			
		sort(sumAB.begin(),sumAB.end());
		
		long long ans=0;
		
		for(int c:C)
			for(int d:D){
				int target=-(c+d);
				
				auto l=lower_bound(sumAB.begin(),sumAB.end(),target);
				auto r=upper_bound(sumAB.begin(),sumAB.end(),target);
				
				ans+=r-l;
			}
		cout<<ans<<endl;
	} 
	return 0;
}

P1859 单词接龙

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词S1,S2,...,SnS1​,S2​,...,Sn​，且给定一个开头的字母，要求出以这个字母开头的最长的 “龙”（每个单词SiSi​ 最多在 “龙” 中出现两次，如果存在SiSi​ 和SjSj​ 完全相同，则他们在 “龙” 中一共可以最多出现四次），在两个单词相连时，其重合的开头字母与结尾字母合为一个字母，例如 beast 和 tree ，如果接成一条龙则变为 beastree 。

输入描述

输入的第一行为一个单独的整数 nn 表示单词数，以下 nn 行每行有一个单词，输入的最后一行为一个单个字符，表示 "龙" 开头的字母。你可以假定以此字母开头的 “龙” 一定存在。(n≤20，但数据比较弱，暴力搜索可以过)(n≤20，但数据比较弱，暴力搜索可以过),

输出描述

输出以此字母开头的最长的 “龙” 的长度。

样例输入 1

Copy to Clipboard

3 abc cde efg a 

样例输出 1

7 

样例输入 2

Copy to Clipboard

3 aaaaaa aaaa aaaa a 

样例输出 2

Copy to Clipboard

23

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int n;
string word[25];
int use[25] = {0};  // 记录每个单词用了几次
int max_len = 0;

// 计算 a 后面接 b 能重叠多少（最小重叠，保证龙最长）
int overlap(string a, string b) {
    int len = min(a.size(), b.size());
    // 从 1 开始找最小重叠，找到立刻返回
    for (int k = 1; k < len; k++) {
        if (a.substr(a.size() - k) == b.substr(0, k)) {
            return k;
        }
    }
    return 0;
}

// 当前最后一个单词是 now，当前长度 len
void dfs(int now, int len) {
    if (len > max_len) max_len = len;

    for (int i = 0; i < n; i++) {
        // 每个单词最多用 2 次
        if (use[i] >= 2) continue;

        int k = overlap(word[now], word[i]);
        if (k == 0) continue;

        use[i]++;
        dfs(i, len + word[i].size() - k);
        use[i]--;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> word[i];
    }
    char st;
    cin >> st;

    // 枚举所有开头符合的单词作为起点
    for (int i = 0; i < n; i++) {
        if (word[i][0] == st) {
            use[i]++;
            dfs(i, word[i].size());
            use[i]--;
        }
    }

    cout << max_len << endl;
    return 0;
}

P1905 胖头鱼的找工作-简化版

题目描述

  wzywzy 要化简这道题，但他太累了所以就没写题面.

  给定一颗nn 个节点的树，树以11 为根节点，问有多少个叶子节点？.

输入描述

  第一行一个正整数nn. 代表树节点的个数.

  第22 至nn 行每行两个正整数xx,yy. 代表点xx 和点yy 之间有一条道路相连.

输出描述

  输出共一行，一个正整数ansans 代表叶子个数.

样例输入

Copy to Clipboard

5 1 2 1 3 1 4 2 5 

样例输出

Copy to Clipboard

3 

样例解释 & 数据规模

叶子节点为 3 4 5, 共 3 个.

对于部分数据，保证:

1≤n≤1001≤n≤100

对于全部数据，保证:

1≤n≤50001≤n≤5000

#include <iostream>
using namespace std;

const int MAXN = 5005;
int du[MAXN]; // 记录每个点的度数

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

    // 读入 n-1 条边
    for (int i = 1; i <= n-1; i++) {
        int x, y;
        cin >> x >> y;
        du[x]++;
        du[y]++;
    }

    int ans = 0;
    // 叶子：度数=1 且 不是根节点1
    for (int i = 2; i <= n; i++) {
        if (du[i] == 1) ans++;
    }

    cout << ans << endl;
    return 0;
}

Copy to Clipboard

Copy to Clipboard

#include <iostream>
using namespace std;

int main() {
    int x;
    cin >> x;
    int ten = x / 10;
    int one = x % 10;
    cout << ten + one << endl;
    return 0;
}

Copy to Clipboard

5 7 1 4 1 2 2 1 3 5 2 3 2 2 4 6 3 4 7 3 5 1 4 5 4 

Copy to Clipboard

NO 4 

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f; // 无穷大
int dis[MAXN][MAXN];       // 存两点间最短距离
int n, m, x, y;

void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dis[i][j] > dis[i][k] + dis[k][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
}

int main() {
    // 1. 初始化距离为无穷大
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= n; i++) dis[i][i] = 0;

    // 2. 读入数据
    cin >> n >> m >> x >> y;
    for (int i = 0; i < m; i++) {
        int a, b, d;
        cin >> a >> b >> d;
        // 双向边，保留最短的一条
        if (d < dis[a][b]) {
            dis[a][b] = d;
            dis[b][a] = d;
        }
    }

    // 3. 跑 Floyd 求全源最短路
    floyd();

    // 4. 取出两人到终点 n 的最短时间
    int lx = dis[x][n];
    int zs = dis[y][n];

    // 5. 判断输出
    if (lx <= zs) cout << "YES " << lx << endl;
    else cout << "NO " << zs << endl;

    return 0;
}

Copy to Clipboard

8 3 7 7 2 4 6 3 7 

Copy to Clipboard

3 

Copy to Clipboard

6 5 1 6 3 5 4 2 9 8 3 11 6 

Copy to Clipboard

5 

Copy to Clipboard

10 5 42 68 35 1 70 25 79 59 63 65 6 46 82 28 62 

Copy to Clipboard

8

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int M, N;
vector<int> A, B;

// 判断 D 是否满足条件
bool check(int D) {
    // 检查：A 中每个数都能在 B 找到匹配
    int j = 0;
    for (int a : A) {
        while (j < N && B[j] < a - D) j++;
        if (j >= N || B[j] > a + D) return false;
    }

    // 检查：B 中每个数都能在 A 找到匹配
    j = 0;
    for (int b : B) {
        while (j < M && A[j] < b - D) j++;
        if (j >= M || A[j] > b + D) return false;
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> M >> N;
    A.resize(M);
    B.resize(N);

    for (int i = 0; i < M; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> B[i];

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    // 二分答案
    int l = 0, r = 1e6, ans = 1e6;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    cout << ans << endl;
    return 0;
}

Copy to Clipboard

cin.tie(nullptr)->sync_with_stdio(false); 

Copy to Clipboard

7 1 2 4 6 3 5 7 

Copy to Clipboard

-1 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加速输入，适配1e6规模
    
    int n;
    long long W;
    cin >> n >> W;
    vector<long long> f(n);
    
    for(int i = 0; i < n; ++i)
    {
        cin >> f[i];
    }
    sort(f.begin(), f.end());
    
    int l = 0, r = n - 1;
    int table = 0;
    while(l <= r)
    {
        if(f[l] + f[r] <= W)
        {
            l++;
            r--;
        }
        else
        {
            r--;
        }
        table++;
    }
    cout << table << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, V;
    cin >> n >> V;
    vector<int> a(n);
    for(int i=0; i<n; i++)
    {
        cin >> a[i];
    }
    
    int l = 0;
    long long sum = 0;
    int ans = 0;
    for(int r=0; r<n; r++)
    {
        sum += a[r];
        // 窗口和超标，收缩左边界
        while(sum > V)
        {
            sum -= a[l];
            l++;
        }
        ans = max(ans, (int)sum);
    }
    cout << ans << endl;
    return 0;
}

P2137 乘2与乘3

题目描述

给出两组正整数 {a1,a2,...,an},{b1,b2,...,bn}{a1​,a2​,...,an​},{b1​,b2​,...,bn​}，请你分别判断一下，是否可以对数字 aiai​ 只进行若干次（包含 00 次）乘 22 操作，与若干次（包含 00 次）乘 33 操作，得到数字 bibi​。

输入描述

第一行输入一个正整数 n(1≤n≤10)n(1≤n≤10), 表示有 nn 个 case 需要判断。

接下来 nn 行，每行两个正整数 ai和biai​和bi​，用空格隔开，表示第 ii 组需要判断的数字。

输出描述

输出总共 nn 行，其中第 ii 行输出 Yes 如果 aiai​ 可以只通过乘 22 与乘 33 操作得到 bibi​。否则输出 No 。

数据规模

对于前两组测试数据，1≤ai≤bi≤101≤ai​≤bi​≤10

对于全部测试数据，1≤ai≤bi≤1051≤ai​≤bi​≤105

样例输入

4 1 1 1 10000 13 78 25 100 

样例输出

Yes No Yes Yes

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

bool isok(long long a, long long b) {
    if (b % a != 0) return false;
    long long t = b / a;
    while (t % 2 == 0) t /= 2;
    while (t % 3 == 0) t /= 3;
    return t == 1;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        long long x, y;
        cin >> x >> y;
        if (isok(x, y)) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

P2144 统计字符个数

题目描述

给你一个包含 nn 个英文字符的字符串，以及 qq 次询问，每次询问一个字符的出现次数。

输入描述

输入第一行包含两个正整数 nn 和 qq，用空格隔开，分别表示字符串中的字符个数和询问次数。

第二行是一个包含 nn 个英文小写字符的字符串。

加下来 qq 行，每行一个英文小写字符，表示 qq 次询问。

输出描述

输出 qq 行，每行一个整数，第 ii 行输出的是第 ii 次询问的字符在字符串中出现的次数。

数据规模

对于前两个测试点， 1≤q,n≤101≤q,n≤10。

对于全部测试点， 1≤q,n≤1051≤q,n≤105。

样例输入

10 3 abcdabcdef a f z 

样例输出

2 1 0

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


int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	int n,q,cnt[1000]={0}; 
	cin>>n>>q;
	
	string str;
	cin>>str;
	for (char c : str) {
        cnt[(int)c]++;
    }

    while (q--) {
        char ch;
        cin >> ch;
        cout << cnt[(int)ch] << '\n';
    }
	
	return 0;
} 

 P2174 动态星图（STL——Vector）

题目背景

在遥远的 30XX30XX 年，人类已经建立了遍布银河系的星际联邦。整个联邦由 NN 个空间站组成，编号从 11 到 NN。为了方便物资运输，联邦建设了 MM 条单向的超空间航道。

你是联邦星图局的一名初级数据员。你的上司给你下达了一项紧急任务：由于星际海盗的干扰，我们需要快速查询某个空间站能直接通往哪些其他空间站。

具体来说，上司会发来 QQ 次询问。每次询问给出一个空间站编号 uu 和一个整数 kk，你需要回答：从空间站 uu 出发，通过一条航道能到达的所有空间站中，编号第 kk 小的空间站是哪一个？

输入格式

第一行包含三个整数 N,M,QN,M,Q，分别表示空间站的数量、航道的数量和询问的次数。 接下来 MM 行，每行包含两个整数 u,vu,v，表示存在一条从空间站 uu 单向通往空间站 vv 的航道。（保证不出现自环，但可能存在重边，即两条航道的起点和终点相同，若存在重边，则在计算第 kk 小时视为多个目标）。 接下来 QQ 行，每行包含两个整数 u,ku,k，表示一次询问。

输出格式

对于每次询问，输出一行一个整数。 如果从空间站 uu 出发能到达的空间站数量少于 kk 个，或者 uu 根本无法到达任何空间站，请输出 -1 。 否则，输出第 kk 小的目标空间站编号。

样例输入

5 6 3
1 3
1 2
1 5
2 4
4 1
1 2
1 2
1 4
4 1

注：样例中 1->2 出现了两次（重边），1 的邻居为 {2, 2, 3, 5}

样例输出

2
5
1

解释： 询问 1 (u=1, k=2)：1 能到达 {2, 2, 3, 5}，排序后第 2 个是 2。 询问 2 (u=1, k=4)：1 能到达 {2, 2, 3, 5}，排序后第 4 个是 5。 询问 3 (u=4, k=1)：4 能到达 {1}，排序后第 1 个是 1。

数据范围与评分标准

本题共 10 个测试点，总分 100 分。

• 测试点 1-2 (20 分): 1≤N,M,Q≤1001≤N,M,Q≤100。
  • 提示：数据量很小，你可以使用二维数组 int map[105][105] (邻接矩阵) 来存储图，虽然浪费空间但可以通过。
• 测试点 3-5 (30 分): 1≤N,M,Q≤50001≤N,M,Q≤5000。
  • 提示：数据量中等，邻接矩阵可能导致内存紧张或遍历超时。
• 测试点 6-10 (50 分): 1≤N,M,Q≤2×1051≤N,M,Q≤2×105。
  • 提示：数据量较大，必须使用动态调整大小的存储方式，否则会超内存（MLE）或超时间（TLE）。

STL 容器小贴士：Vector

在本题中，推荐使用 std::vector 。

这是什么？ vector 是 C++ 标准模板库（STL）中最基本的容器，你可以把它理解为一个可以自动动态改变长度的数组。在数据结构课中，它常被用来实现邻接表。

为什么要用它？ 传统的数组（如 int a[100] ）大小是固定的。在图论问题中，有的节点连接了 10000 个点，有的节点只连接了 1 个点。如果用二维数组 adj[N][N] ，当 N=200000N=200000 时，你需要 400400 亿个整数的空间，内存会直接爆炸。 使用 vector<int> adj[N] ，我们可以为每个节点只分配它实际需要的空间。

常用方法举例：

#include <vector>
using namespace std;

// 1. 定义：创建一个存放整数的 vector
vector<int> v; 

// 2. 插入：在尾部添加元素
v.push_back(10); 
v.push_back(5);  // 现在 v 里面是 {10, 5}

// 3. 访问：像数组一样使用下标
int x = v[0]; // x = 10

// 4. 获取大小
int len = v.size(); // len = 2

// 5. 排序：vector 可以结合算法库排序
#include <algorithm>
sort(v.begin(), v.end()); // 现在 v 里面是 {5, 10}

// 6. 清空
v.clear();

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, Q;
    cin >> N >> M >> Q;

    vector<vector<int>> adj(N + 1); // 节点编号从1到N
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); // 重边直接加入
    }

    // 对每个节点的邻接表排序，方便直接取第k小
    for (int u = 1; u <= N; ++u) {
        sort(adj[u].begin(), adj[u].end());
    }

    // 处理查询
    while (Q--) {
        int u, k;
        cin >> u >> k;
        if (k > (int)adj[u].size()) {
            cout << "-1\n";
        } else {
            cout << adj[u][k - 1] << '\n';
        }
    }

    return 0;
}

P2175 能量共鸣（STL——Set）

题目背景

在魔法王国的中央实验室里，大魔法师们正在维护一个极其不稳定的 “能量共鸣场”。共鸣场中悬浮着若干枚具有特定频率的魔法晶体。

为了保证魔法阵的稳定，所有的晶体必须具有互不相同的频率值。

作为实验室的首席学徒，你需要操作控制台来响应 QQ 条指令。指令分为以下三种：

1. 注入 (Insert)：向共鸣场中投入一枚频率为 xx 的晶体。如果场内已经存在频率为 xx 的晶体，则由于排斥反应，投入无效（什么都不发生）。
2. 移除 (Delete)：从共鸣场中取出一枚频率为 xx 的晶体。如果场内不存在频率为 xx 的晶体，则操作无效。
3. 校准 (Query)：为了发动魔法，需要寻找场内频率大于等于 xx 的所有晶体中，频率最小的那一枚（即寻找 xx 的后继）。

输入格式

第一行包含一个整数 QQ，表示指令的总数。 接下来 QQ 行，每行包含两个整数 op,xop,x。

• op=1op=1：表示注入操作，投入频率 xx。
• op=2op=2：表示移除操作，移除频率 xx。
• op=3op=3：表示校准操作，寻找 ≥x≥x 的最小频率。

输出格式

对于每一次 op=3op=3 的操作，输出一行一个整数。 如果找到了符合条件的晶体，输出其频率值。 如果场内没有任何晶体的频率 ≥x≥x，或者场内为空，请输出 -1 。

样例输入

8
1 10
1 20
1 15
3 12
2 15
3 12
3 25
1 10

样例输出

15
20
-1

解释：

1. 插入 10, 20, 15。此时集合为 {10, 15, 20} (自动有序)
2. 查询 >= 12 的最小数 -> 15
3. 删除 15。此时集合为 {10, 20}
4. 查询 >= 12 的最小数 -> 20
5. 查询 >= 25 的最小数 -> 找不到，输出 -1
6. 插入 10。已存在，集合不变仍为 {10, 20}

数据范围与评分标准

本题共 10 个测试点，总分 100 分。

• 测试点 1-3 (30 分): 1≤Q≤10001≤Q≤1000，1≤x≤1091≤x≤109。
  • 提示：数据量较小，你可以使用数组或 vector，每次插入后排序，或者直接遍历查找。复杂度 O(Q2)O(Q2) 可以接受。
• 测试点 4-10 (70 分): 1≤Q≤2×1051≤Q≤2×105，1≤x≤1091≤x≤109。
  • 提示：数据量较大，频繁的插入、删除和查找操作要求每次操作的复杂度在 O(log⁡N)O(logN) 级别。线性扫描或反复排序会导致超时（TLE）。

STL 容器小贴士：Set

在本题中，推荐使用 std::set 。

这是什么？ set 是 C++ STL 中的一种关联容器，它维护了一个元素互不相同且自动排序的集合。 在底层实现上，它通常是一棵红黑树（Red-Black Tree），这是一种自平衡的二叉搜索树（BST）。

为什么要用它？ 如果使用 vector ，虽然查找第 kk 小很快，但在中间插入或删除一个元素的代价是 O(N)O(N)（因为要移动后面的元素），且保持有序需要频繁排序。 而 set 的插入、删除、查找操作的时间复杂度都是 O(log⁡N)O(logN)，非常适合需要动态维护有序序列的场景。

常用方法举例：

#include <set>
using namespace std;

// 1. 定义：创建一个存放整数的 set，默认从小到大排序
set<int> s;

// 2. 插入：插入元素，自动去重并排序
s.insert(10);
s.insert(5);
s.insert(10); // 重复插入无效，集合内仍为 {5, 10}

// 3. 删除
s.erase(5); // 集合变为 {10}

// 4. 查找是否存在
if (s.count(10)) { ... } // 返回 1 表示存在，0 表示不存在

// 5. 核心功能：二分查找（Lower Bound）
// lower_bound(x) 返回指向第一个 >= x 的元素的迭代器
// upper_bound(x) 则返回第一个 > x 的元素的迭代器
auto it = s.lower_bound(8); 
// auto的用法是根据赋值内容自动选择合适的数据类型
if (it != s.end()) {
    int val = *it; // 获取值
} else {
    // 没找到，说明所有元素都比 8 小
}

// 6. 遍历
for (auto x : s) { ... }

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

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    
    int q,op,x;
    cin>>q;
    
    set<int> s; //set自动升序排序
    
    for(int i=0;i<q;i++){
        cin>>op>>x;
        if(op==1){
            s.insert(x); // 插入x，自动去重+排序
        }else if(op==2){
            s.erase(x);  // 删除x（若不存在则无操作）
        }else if(op==3){
            // 核心：判断lower_bound返回的迭代器是否为end()
            auto it = s.lower_bound(x); 
            if(it != s.end()){ // 存在≥x的元素
                cout << *it << '\n'; // 解引用迭代器，输出元素值
            }else{ // 不存在≥x的元素
                cout << "-1\n";
            }
        }
    }
    
    return 0;
}

P2176 幻境拍卖行（STL——MultiSet）

题目背景

在连接现实与虚幻的缝隙中，存在着一座 “幻境拍卖行”。这里的拍品往往是稀有的记忆或梦境。

与普通拍卖行不同，这里的竞拍者互不可见，且经常会出现多人出价相同的情况。拍卖行的规则允许存在多个相同的出价（比如三个人都出价 100 金币，那么系统里就会记录 3 个 100）。

作为拍卖行的管理员，你需要维护当前的竞拍列表，并处理 QQ 次事务：

1. 出价 (Bid)：一名竞拍者提出了 xx 金币的出价。
2. 撤资 (Withdraw)：由于资金不足或改变主意，一名竞拍者撤回了 xx 金币的出价。
   • 注意：如果有多个人出价 xx，只撤回其中一个人的出价。如果当前没人出价 xx，则忽略此次操作。
3. 试探 (Query)：一名新来的土豪想要稳压某个价格一头。他询问：当前所有出价中，严格大于 xx 的最小出价是多少？

输入格式

第一行包含一个整数 QQ，表示事务处理的次数。 接下来 QQ 行，每行包含两个整数 op,xop,x。

• op=1op=1：表示有人出价 xx。
• op=2op=2：表示有人撤回一个 xx 的出价。
• op=3op=3：表示查询严格大于 xx 的最小出价。

输出格式

对于每一次 op=3op=3 的操作，输出一行一个整数。 如果找到了符合条件的出价，输出该价格。 如果当前没有任何出价严格大于 xx，或者拍卖列表为空，请输出 -1 。

样例输入

9
1 100
1 100
1 50
3 90
2 100
3 90
2 100
3 90
3 120

样例输出

100
100
-1
-1

解释：

1. 插入 100, 100, 50。当前列表：{50, 100, 100}。
2. 查询 > 90 的最小数。是 100。
3. 删除一个 100。当前列表：{50, 100}。
4. 查询 > 90 的最小数。仍然是 100（因为还有一个）。
5. 再删除一个 100。当前列表：{50}。
6. 查询 > 90 的最小数。找不到，输出 -1。
7. 查询 > 120 的最小数。找不到，输出 -1。

数据范围与评分标准

本题共 10 个测试点，总分 100 分。

• 测试点 1-3 (30 分): 1≤Q≤10001≤Q≤1000，1≤x≤1091≤x≤109。
  • 提示：数据量较小，可以使用数组或 list 暴力维护，删除时只删一个。
• 测试点 4-10 (70 分): 1≤Q≤2×1051≤Q≤2×105，1≤x≤1091≤x≤109。
  • 提示：数据量较大，需要使用支持 O(log⁡N)O(logN) 插入、删除、查找的数据结构，且必须支持重复元素。

STL 容器小贴士：Multiset

在本题中，推荐使用 std::multiset , 也可以思考如何使用 std::map 。

这是什么？ multiset 与 set 非常相似，底层也是红黑树（平衡二叉搜索树）。 唯一的、也是最重要的区别在于： set 会自动去重，而 multiset 允许存储重复的元素。

为什么要用它？ 本题中明确提到 “多人出价相同”，如果用 set ，第二次插入 100 时会被忽略，这会导致后续逻辑错误（比如删掉一个 100 后，应该还剩一个，但在 set 中就全没了）。 multiset 能够完美维护重复元素，且保持有序。

常用方法与陷阱（重点！）：

#include <set> // multiset 也包含在这里
using namespace std;

multiset<int> ms;

// 1. 插入
ms.insert(100);
ms.insert(100); // 现在集合里有 {100, 100}

// 2. 计数
int cnt = ms.count(100); // 返回 2

// 3. 删除（大坑预警！）
// 如果直接写 ms.erase(100)，它会把所有的 100 全部删掉！
// 题目要求只删一个，正确做法是先找到迭代器，再删迭代器：
auto it = ms.find(100); // 找到第一个 100 的位置
if (it != ms.end()) {
    ms.erase(it); // 只删除这个迭代器指向的那一个 100
}

// 4. 查找严格大于 x 的第一个元素 (Upper Bound)
// set/multiset 自带 upper_bound，效率 O(log N)
auto ub = ms.upper_bound(90); // 指向第一个 > 90 的元素
if (ub != ms.end()) {
    cout << *ub << endl;
}

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

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	int q,op,x;
	cin>>q;
	
	multiset<int> ms;
	
	for(int i=0;i<q;i++){
		cin>>op>>x;
		if(op==1) ms.insert(x);
		if(op==2){
			auto it =ms.find(x);
			if(it!=ms.end()){
				ms.erase(it);
			}
		}
		if(op==3){
			auto it =ms.upper_bound(x);
			if(it!=ms.end()){
				cout<<*it<<endl;
			}else{
				cout<<"-1"<<endl;
			}
		    }
	    }
	
	return 0;
}

P2177 记忆碎片（STL——Map）

题目背景

在名为 “阿卡夏” 的维度中，漂浮着无数的记忆碎片。每一片记忆都有一个独特的标签（由小写英文字母组成的字符串），以及它所蕴含的能量值。

你是一名记忆收藏家。你的背包是一个神奇的空间，可以容纳无限多的记忆碎片。由于记忆碎片的标签不是数字，而是字符串，普通的分类法（数组）完全失效了。你需要建立一个特殊的索引系统来管理它们。

你的背包系统需要支持 QQ 次操作：

1. 收集 (Collect)：发现了一批标签为 SS 的记忆碎片，数量为 xx 个。你需要将它们存入背包。
2. 融合 (Fuse)：为了炼制特殊道具，需要消耗标签为 SS 的记忆碎片 xx 个。
   • 如果背包中标签为 SS 的碎片数量不足 xx 个（或者根本不存在），则操作失败，不消耗任何碎片。
   • 如果数量足够，则扣除 xx 个。
3. 清点 (Check)：查询当前背包中，标签为 SS 的记忆碎片还有多少个。

输入格式

第一行包含一个整数 QQ，表示操作的次数。 接下来 QQ 行，每行格式如下：

• 1 S x : 表示收集标签为 SS 的碎片 xx 个。
• 2 S x : 表示尝试消耗标签为 SS 的碎片 xx 个。
• 3 S : 表示查询标签为 SS 的碎片数量。

其中，SS 是一个仅包含小写字母的字符串，xx 是一个正整数。

输出格式

• 对于操作 1，不需要输出。
• 对于操作 2，如果消耗成功（库存充足），输出剩余的碎片数量；如果消耗失败（库存不足），输出 -1 。
• 对于操作 3，输出当前标签为 SS 的碎片数量。如果背包里没有 SS，输出 0 。

样例输入

7
1 fire 10
1 ice 5
3 fire
2 fire 3
2 ice 10
3 water
2 water 1

样例输出

10
7
-1
0
-1

解释：

1. 存入 "fire" 10 个。
2. 存入 "ice" 5 个。
3. 查询 "fire" -> 10。
4. 消耗 "fire" 3 个 -> 够用 (10>=3)，剩余 7 个。输出 7。
5. 消耗 "ice" 10 个 -> 不够 (5<10)，失败。输出 -1。
6. 查询 "water" -> 不存在。输出 0。
7. 消耗 "water" 1 个 -> 不存在，失败。输出 -1。

数据范围与评分标准

本题共 10 个测试点，总分 100 分。

• 测试点 1-2 (20 分): 1≤Q≤1001≤Q≤100，字符串 SS 长度为 1（仅 a - z ）。
  • 提示：标签实际上等同于字符，可以用 int cnt[26] 来做。
• 测试点 3-4 (20 分): 1≤Q≤10001≤Q≤1000，字符串 SS 长度 ≤5≤5。
  • 提示：数据量较小，可以用结构体数组 {string name, int val} 并进行线性查找。
• 测试点 5-10 (60 分): 1≤Q≤1051≤Q≤105，字符串 SS 长度 ≤10≤10，1≤x≤1091≤x≤109。
  • 提示：需要高效的字符串查找与映射结构。

STL 容器小贴士：Map

在本题中，推荐使用 std::map 。

这是什么？ map 是一个关联容器，它存储的是键值对 (Key-Value Pair)。 你可以把它想象成一个超级数组，这个数组的下标（Key）不一定是整数，可以是字符串、结构体甚至是其他容器。 例如： map<string, int> backpack 就可以理解为 backpack["fire"] = 10 。

为什么要用它？ 在 C/C++ 中，普通的数组 a[100] 只能用整数下标访问。如果我们要统计 “单词出现的次数”，或者像本题一样通过 “名字” 找 “数量”，传统的做法是写一个哈希函数或者维护两个平行数组。 map 帮我们封装好了这一切。底层通常使用红黑树实现，因此查找和插入的时间复杂度为 O(Llog⁡N)O(LlogN)（LL 为字符串长度，NN 为元素个数）。

常用方法举例：

#include <map>
#include <string>
using namespace std;

// 1. 定义：Key是string，Value是int
map<string, int> mp;

// 2. 插入与修改：像数组一样直接使用 []
mp["apple"] = 5;
mp["banana"] = 10;
mp["apple"] += 3; // 现在 apple 是 8

// 3. 访问
cout << mp["apple"] << endl; 

// 4. 注意：[] 运算符的副作用
// 如果访问一个不存在的 Key，map 会自动创建它并赋值为 0 (默认构造值)
int x = mp["orange"]; // "orange" 被创建了，x = 0

// 5. 查找（如果不希望自动创建）
if (mp.find("orange") != mp.end()) {
    // 存在
} else {
    // 不存在
}

// 6. 遍历
for (auto& pair : mp) {
    cout << "Key: " << pair.first << ", Value: " << pair.second << endl;
}

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

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	map<string,long long> mp;
	
	int cnt,op,x;
	string s;
	cin>>cnt;
	
	for(int i=0;i<cnt;i++){
		cin>>op>>s;
		if(op==1){
			cin>>x;
		    mp[s]+=x;
		}
		else if(op==2){
			cin>>x;
			auto it=mp.find(s);
			if(it!=mp.end()&&it->second>=x){
			it->second-=x;
			cout<<it->second<<'\n';
		    }else{
		    	cout<<"-1\n";
			}

		}
		else if(op==3){
			auto it=mp.find(s);
			if(it!=mp.end()){
				cout<<it->second<<'\n';
			}else{
				cout<<"0\n";
			}
		}
		
	}
	return 0;
}

P2178 量子调度(STL——Queue)

题目背景

人类终于制造出了第一台通用量子计算机 ——“深蓝核心”。但这台计算机目前只有一个量子处理单元（QPU）。 这就意味着，尽管它算力无穷，但同一时刻只能处理一个任务。

为了公平起见，系统工程师设计了一套 “时间片轮转” 的调度协议：

1. 所有等待执行的任务按照到达顺序排成一个队列。
2. QPU 设定了一个标准的时间片长度 QQ（毫秒）。
3. 每次 QPU 从队列头部取出一个任务进行处理。
4. 如果该任务所需时间 T≤QT≤Q，则它能在本轮执行完毕。QPU 处理它 TT 毫秒，该任务结束，记录其完成时间。
5. 如果该任务所需时间 T>QT>Q，则 QPU 只会处理它 QQ 毫秒。处理完后，该任务的剩余所需时间变为 T−QT−Q，并被立刻重新放回队列的尾部等待下一轮。
6. 重复上述过程，直到队列为空。

现在给出了 NN 个任务的名称和所需时间，以及时间片 QQ。请你模拟这个过程，按任务完成的先后顺序输出每个任务的名称和它结束时的总耗时。

输入格式

第一行包含两个整数 NN 和 QQ，分别表示任务数量和时间片长度。 接下来 NN 行，每行包含一个字符串 NameName 和一个整数 TimeTime，表示任务名称和所需总时间。（字符串不含空格）。 初始时，任务按照输入的顺序进入队列。

输出格式

输出 NN 行。 每行包含两个信息：任务名称 NameName 和该任务结束时的系统总耗时（从 0 开始累计），中间用空格隔开。

样例输入

5 100
p1 150
p2 80
p3 200
p4 350
p5 20

样例输出

p2 180
p5 400
p1 450
p3 550
p4 800

解释： 初始队列: [p1 (150), p2 (80), p3 (200), p4 (350), p5 (20)]，当前时间 0

1. 取出 p1 (150)。需要 150 > 100。执行 100，剩余 50。时间变为 100。p1 放回队尾。 队列: [p2 (80), p3 (200), p4 (350), p5 (20), p1 (50)]
2. 取出 p2 (80)。80 <= 100。执行 80，结束。时间变为 100+80=180。输出 p2 180。 队列: [p3 (200), p4 (350), p5 (20), p1 (50)]
3. 取出 p3 (200)。200 > 100。执行 100，剩余 100。时间变为 280。p3 放回队尾。 队列: [p4 (350), p5 (20), p1 (50), p3 (100)]
4. 取出 p4 (350)。350 > 100。执行 100，剩余 250。时间变为 380。p4 放回队尾。 队列: [p5 (20), p1 (50), p3 (100), p4 (250)]
5. 取出 p5 (20)。20 <= 100。执行 20，结束。时间 400。输出 p5 400。 ... 以此类推。

数据范围与评分标准

本题共 10 个测试点，总分 100 分。

• 测试点 1-3 (30 分): 1≤N≤1001≤N≤100，所有任务总耗时之和 ≤10000≤10000。
  • 提示：数据非常小，可以手动模拟数组移动。
• 测试点 4-10 (70 分): 1≤N≤1051≤N≤105，1≤Q≤10001≤Q≤1000，单个任务所需时间 ≤109≤109。
  • 提示：为了保证不超时，题目保证所有任务被调度的总轮次（即出队次数）不超过 2×1062×106。请使用高效的队列操作，避免数组搬运带来的 O(N)O(N) 开销。

STL 容器小贴士：Queue

在本题中，推荐使用 std::queue 。

这是什么？ queue 是一种先进先出 (FIFO, First-In-First-Out) 的容器适配器。 它就像现实生活中的排队：新来的人只能站在队尾（push），办理业务的人只能从队头离开（pop）。

为什么要用它？ 本题的逻辑完全符合队列的特性。如果不使用 queue ，而使用数组 vector 模拟，每次删除头部元素会导致后面的 N−1N−1 个元素全部向前移动，复杂度是 O(N)O(N)。如果有 MM 次调度，总复杂度就是 O(M⋅N)O(M⋅N)，会超时。 使用 queue ，入队和出队都是 O(1)O(1) 的操作。

常用方法举例：

#include <queue>
using namespace std;

// 1. 定义
queue<int> q;

// 2. 入队 (push)：放到队尾
q.push(10);
q.push(20); // q: Front [10, 20] Back

// 3. 访问队头 (front)：查看队伍最前面是谁
int x = q.front(); // x = 10

// 4. 出队 (pop)：移除队头
q.pop(); // q: Front [20] Back

// 5. 判空
while (!q.empty()) {
    // ...
}

// 6. 获取大小
int len = q.size();

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

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	int n,q;
	cin>>n>>q;
	
	queue<pair<string,ll>> qu;
	
	for(int i=0;i<n;i++){
		string name;
		ll time;
		cin>>name>>time;
		qu.push({name,time});
	}
	
	ll sum=0;
	
	while(!qu.empty()){
		auto top=qu.front();
		qu.pop();
		
		string name=top.first;
		ll rtime=top.second;
		
		if(rtime<=q){
			sum+=rtime;
			cout<<name<<" "<<sum<<endl;
		}else{
			sum+=q;
			rtime-=q;
			qu.push({name,rtime});
		}
		
	}
	
	return 0;
}

P2180 远古守望塔（STL—Stack教学）（单调栈）

题目背景

在被遗忘的荒原上，矗立着一排古老的魔法守望塔。这些守望塔自西向东排列，编号依次为 11 到 NN。 每座塔都有一个特定的高度 HiHi​。

为了传递警报，每座守望塔都会向东方（即编号增大的方向）发射水平的魔法信号。 然而，魔法信号无法穿透实体。这意味着，从第 ii 号塔发出的信号，只能被位于其东侧、且高度严格大于 HiHi​ 的第一座塔所接收。 如果东侧不存在比它高的塔，信号就会消散在虚空中。

作为守望者军团的指挥官，你需要计算出每一座塔发出的信号最终会被哪一座塔接收。

输入格式

第一行包含一个整数 NN，表示守望塔的数量。 第二行包含 NN 个整数 H1,H2,…,HNH1​,H2​,…,HN​，依次表示每座塔的高度。

输出格式

输出一行 NN 个整数。 第 ii 个整数表示第 ii 号塔的信号接收塔的编号。 如果信号无法被接收（即东侧没有更高的塔），则输出 0 。 整数之间用空格分隔。

样例输入

5
4 2 3 5 1

样例输出

4 3 4 0 0

解释：

• 塔 1 (高度 4): 向东看，塔 2 (2)、塔 3 (3) 都比它矮，塔 4 (5) 比它高。接收者：4。
• 塔 2 (高度 2): 向东看，塔 3 (3) 比它高。接收者：3。
• 塔 3 (高度 3): 向东看，塔 4 (5) 比它高。接收者：4。
• 塔 4 (高度 5): 向东看，塔 5 (1) 比它矮。后面没了。接收者：0。
• 塔 5 (高度 1): 东面没有塔了。接收者：0。

数据范围与评分标准

本题共 10 个测试点，总分 100 分。

• 测试点 1-3 (30 分): 1≤N≤10001≤N≤1000。
  • 提示：数据量较小，可以对于每座塔 ii，遍历 j=i+1…Nj=i+1…N 寻找第一个满足条件的塔。复杂度 O(N2)O(N2)。
• 测试点 4-10 (70 分): 1≤N≤1061≤N≤106，1≤Hi≤1091≤Hi​≤109。
  • 提示：数据量很大，O(N2)O(N2) 会超时。请思考：如果你从左往右遍历，能不能利用某种数据结构记录下 “可能会成为答案” 的那些塔？如果塔 A 比塔 B 矮且塔 A 在塔 B 的左边，那么对于更左边的人来说，塔 A 还有意义吗？

STL 容器小贴士：Stack

在本题中，推荐使用 std::stack 。

这是什么？ stack 是一种后进先出 (LIFO, Last-In-First-Out) 的容器适配器。 它就像一个只能从顶部放书、只能从顶部取书的箱子。

为什么要用它？ 本题可以使用 单调栈 算法。 当我们从左向右遍历时，我们希望快速找到右边第一个比自己高的。 我们可以维护一个栈，栈里存放的是左边塔的下标。 关键点在于：如果栈里的某个塔比当前塔矮，那么这个矮塔对于更右边的塔来说，永远不可能是 “第一个比它高的” 了（因为当前塔既比它高，又比它靠左，完全挡住了它）。 所以，我们可以把这些矮塔统统 “弹出” 栈，保持栈内元素高度单调递减。

常用方法举例：

#include <stack>
using namespace std;

// 1. 定义
stack<int> s;

// 2. 入栈 (push)
s.push(10);
s.push(20); // 栈顶是 20

// 3. 访问栈顶 (top)
int x = s.top(); // x = 20

// 4. 出栈 (pop)
s.pop(); // 移除 20，现在栈顶是 10

// 5. 判空
if (s.empty()) { ... }

// 6. 大小
int len = s.size();

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

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	int n;
	cin>>n;
	vector<ll> H(n+1);//每个塔的高度 
	for(int i=1;i<=n;i++){
		cin>>H[i];
	}
	
	vector<int> ans(n+1,0);//每个塔的答案 
	stack<int> st;//存储每个塔的编号 
	
	//从右向左遍历 
	for(int i=n;i>=1;i--){
		while(!st.empty()&&H[st.top()]<=H[i]){
			st.pop();
		}
	
	    if(!st.empty()){
		    ans[i]=st.top();
	    }
	    st.push(i);
    } 
    
    for(int i=1;i<=n;i++){
    	cout<<ans[i]<<' ';
	}
	cout<<'\n';
	
	return 0;
}

P2181 信号过滤器（STL—Priority Queue教学）

题目背景

在探索未知的 “黑暗扇区” 时，你的飞船接收到了海量的宇宙背景辐射信号。 这些信号源源不断地到达，每一个信号都有一个强度值（整数）。 为了筛选出有价值的信息，舰载主机设置了一个过滤器：我们只关注当前接收到的所有信号中，强度第 KK 小的那个信号。

为什么是第 KK 小？因为强度太小的往往是噪音，强度太大的往往是恒星干扰，只有处于特定排位的信号才可能包含智慧生命的编码。

你需要编写一个程序，模拟信号的接收过程。 一开始，信号库是空的。接下来会有 NN 次事件，事件分为两种：

1. 接收 (Receive)：捕捉到一个强度为 xx 的新信号。
2. 分析 (Analyze)：输出当前已接收的所有信号中，强度第 KK 小的数值。

输入格式

第一行包含两个整数 NN 和 KK。NN 表示事件总数，KK 表示我们需要关注的排名。 接下来 NN 行，每行包含两个整数 op,xop,x。

• op=1op=1：表示接收到一个强度为 xx 的信号。
• op=2op=2：表示进行一次分析询问（此时忽略输入的 xx）。

输出格式

对于每一次 op=2op=2 的询问，输出一行一个整数。 如果当前接收到的信号不足 KK 个，无法确定第 KK 小，请输出 -1 。 否则，输出第 KK 小的信号强度。

样例输入

9 3
1 10
1 5
2 0
1 20
2 0
1 3
2 0
1 7
2 0

样例输出

-1
20
10
7

解释：

1. 接收 10。当前集合：{10}。
2. 接收 5。当前集合：{5, 10}。
3. 询问第 3 小。只有 2 个数，不足 3 个。输出 -1。
4. 接收 20。当前集合：{5, 10, 20}。
5. 询问第 3 小。排序后是 5, 10, 20。第 3 小是 20。（注意：如果不维护 Top K，直接排序是 20；这里稍微有点反直觉，通常 Top K 小是指最小的 K 个。题目定义是 “第 K 小”，即从小到大排在第 K 位的数）。
6. 接收 3。当前集合：{3, 5, 10, 20}。
7. 询问第 3 小。排序后 3, 5, 10, 20。第 3 小是 10。
8. 接收 7。当前集合：{3, 5, 7, 10, 20}。
9. 询问第 3 小。排序后 3, 5, 7, 10, 20。第 3 小是 7。

数据范围与评分标准

本题共 10 个测试点，总分 100 分。

• 测试点 1-3 (30 分): 1≤N≤10001≤N≤1000，1≤K≤10001≤K≤1000。
  • 提示：数据量较小，每次询问时把所有数字存入 vector 并 sort 一遍，复杂度 O(N2log⁡N)O(N2logN)，可以通过。
• 测试点 4-10 (70 分): 1≤N≤2×1051≤N≤2×105，1≤K≤N1≤K≤N，1≤x≤1091≤x≤109。
  • 提示：数据量较大，不能每次都全量排序。请利用优先队列（堆）的特性。想一想，如果我们只维护 “最小的 K 个数”，那么这 K 个数里最大的那个，是不是就是全局第 K 小？

STL 容器小贴士：Priority Queue

在本题中，推荐使用 std::priority_queue 。

这是什么？ priority_queue 是优先队列，它的底层通常是一个二叉堆 (Binary Heap)。 与普通队列（先进先出）不同，优先队列保证队头（top）永远是优先级最高的元素。 默认情况下，C++ 的 priority_queue 是大根堆 (Max-Heap)，即最大的元素在 top 。

为什么要用它？ 堆可以在 O(log⁡N)O(logN) 的时间内插入元素，并以 O(1)O(1) 的时间获取最值。 本题中，我们需要频繁地 “动态维护” 一部分数据。如果使用数组排序，插入新数据后重新排序代价太大。使用堆可以高效解决。

常用方法举例：

#include <queue>
#include <vector>
using namespace std;

// 1. 定义：默认是大根堆（最大的在上面）
priority_queue<int> pq; 

// 2. 插入
pq.push(10);
pq.push(5);
pq.push(20); 

// 3. 访问堆顶
int x = pq.top(); // x = 20 (因为是大根堆)

// 4. 删除堆顶
pq.pop(); // 移除 20，剩下的最大的是 10

// 5. 进阶：如何定义小根堆（最小的在上面）？
// 需要指定容器类型(vector<int>)和比较函数(greater<int>)
priority_queue<int, vector<int>, greater<int>> min_pq;
min_pq.push(10);
min_pq.push(5);
int y = min_pq.top(); // y = 5

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

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	int n,k,op,x;
	cin>>n>>k;
	
	priority_queue<int> pq;
	
	for(int i=0;i<n;i++){
		cin>>op>>x;
		if(op==1) pq.push(x);
		if(op==2){
			if(pq.size()<k){
				cout<<"-1"<<endl;
			}
			while(pq.size()>k){
				pq.pop();
			}
			cout<<pq.top()<<endl;
		}
	} 
	
	return 0;
} 

P2182 虚空石板（STL—List教学）

题目背景

你是一名考古学家，正在修复一块记录着远古魔法的 “虚空石板”。 石板上的文字是一行连续的字符序列。为了修复它，你需要使用一只魔法笔在石板上进行操作。 魔法笔有一个光标 (Cursor)，指示着当前的操作位置。

初始时，石板上有一串已有的字符序列（也可能为空），光标位于序列的最前端（即第一个字符之前）。 你需要根据指令移动光标，或者在光标处进行修改。

指令共有四种：

1. 右移 (Move Right)：将光标向右移动一个字符的位置。如果光标已经位于最右端（即最后一个字符之后），则忽略此操作。
2. 左移 (Move Left)：将光标向左移动一个字符的位置。如果光标已经位于最前端，则忽略此操作。
3. 刻写 (Insert)：在当前光标的左侧插入一个字符 cc。插入后，光标的位置保持在由该字符和它原来的后继字符之间（即光标相对位置不变，但在整个串中的下标增加了）。
4. 抹除 (Backspace)：删除当前光标左侧的一个字符。如果光标左侧没有字符（即光标在最前端），则忽略此操作。

请在完成所有 QQ 条指令后，输出石板上最终的字符序列。

输入格式

第一行包含一个字符串 SinitSinit​，表示石板初始的内容。如果 SinitSinit​ 为字符串 "EMPTY"（不含引号），则表示初始为空。 第二行包含一个整数 QQ，表示指令的数量。 接下来 QQ 行，每行描述一个指令，格式如下：

• > ：表示右移 (Move Right)。
• < ：表示左移 (Move Left)。
• I c ：表示刻写字符 cc（cc 是一个小写字母或数字）。
• D ：表示抹除 (Backspace)。

输出格式

输出一行，表示修复完成后的最终字符串。

样例输入

abc
6
>
>
I x
<
D
I y

样例输出

ayxc

解释：

• 初始： | a b c (光标在最前，| 表示光标)
• > : a | b c
• > : a b | c
• I x : a b x | c (在光标左侧插入 x)
• < : a b | x c
• D : a | x c (删除光标左侧的 b)
• I y : a y | x c (在光标左侧插入 y)
• 最终序列： ayxc

数据范围与评分标准

本题共 10 个测试点，总分 100 分。

• 测试点 1-3 (30 分): 指令数 Q≤2000Q≤2000，初始字符串长度 ≤2000≤2000。
  • 提示：数据量较小，你可以使用 std::vector 或 std::string 模拟。虽然插入删除是 O(N)O(N) 的，但 NN 很小，总耗时约 O(Q⋅N)≈4×106O(Q⋅N)≈4×106，可以接受。
• 测试点 4-10 (70 分): 指令数 Q≤2×105Q≤2×105，初始字符串长度 ≤105≤105，最终结果长度 ≤3×105≤3×105。
  • 提示：数据量较大，频繁在中间插入和删除。如果使用数组（vector/string），每次操作需要移动大量元素，总复杂度会达到 O(Q⋅N)≈1010O(Q⋅N)≈1010，会导致超时（TLE）。请使用能够 O(1)O(1) 进行局部插入删除的数据结构。

STL 容器小贴士：List

在本题中，推荐使用 std::list 。

这是什么？ list 是 双向链表 (Doubly Linked List)。 与 vector （连续内存数组）不同， list 的元素分散在内存中，通过指针相连。

为什么要用它？

• 优势：在链表的任意位置插入或删除元素，只需要修改指针，时间复杂度为 O(1)O(1)（前提是你已经有了指向该位置的迭代器）。
• 劣势：不支持随机访问。你不能像数组那样用 L[5] 直接访问第 5 个元素，必须从头遍历。

在本题中，我们只需要左右移动光标（迭代器 ++ 或 -- ），以及在光标处插入删除。这正是链表的强项。

常用方法举例：

#include <list>
using namespace std;

// 1. 定义
list<char> L;

// 2. 迭代器（光标）
list<char>::iterator it = L.begin();

// 3. 插入：在 it 指向的元素 *之前* 插入 'a'
// 插入后，it 仍然指向原来的那个元素（或者 end），
// 所以光标实际上是在新插入元素的 "右边"，符合题目要求。
L.insert(it, 'a'); 

// 4. 删除：删除 it 指向的元素
// erase 返回下一个有效元素的迭代器
// 注意：题目是“删除光标左侧”，所以要先 it-- 再 erase
it = L.erase(it);

// 5. 移动
it++;
it--;

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

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	list<char> l;
	int cnt;
	string str;
	cin>>str>>cnt;
	
	if(str!="EMPTY"){
		for(char c:str){
			l.push_back(c);
		}
	}
	
	list<char>::iterator it = l.begin();
	
	while(cnt--){
		string op;
		cin>>op;
		
		if(op==">"){
			if(it!=l.end()){
			it++;
		}
		}else if(op=="<"){
			if(it!=l.begin()){
			it--;
		}
		}else if(op=="I"){
			char c;cin>>c;
			l.insert(it,c);
		}else if(op=="D"){
			if(it!=l.begin()){
				auto d=--it;
				it=l.erase(d);
			}
		}
	}
	for (char c : l) {
        cout << c;
    }
    cout << '\n';
    
	return 0;
} 

四、P1075 [NOIP 2012 普及组] 质因数分解 - 洛谷

#include <iostream>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(0), cin.tie(0); // 输入输出优化，加快速度
    ll n;
    cin >> n;
    // 遍历到 sqrt(n)，找第一个能整除n的数（较小质数）
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            cout << n / i << endl; // 输出较大质数
            return 0; // 直接退出，无需继续遍历
        }
    }
    // 题目保证n是两个不同质数的乘积，此处不会执行
    return 0;
}

找8的个数

题目描述

你被要求写程序输出从 11 到 NN 的正整数，这很显然难不倒聪明的你。但当数字开始出现在屏幕上时，你突然发现，这个屏幕在输出数字 88 时出现了故障，显示成 66 了。

请你计算一下，你输出的这 nn 个数字中，有多少个数字含有至少一个 88 导致了输出结果错误。

输入描述

输入一个正整数 n(1≤n≤1,000)n(1≤n≤1,000)。

输出描述

输出 [1,n][1,n] 中有多少个数字含有至少一个 8。

样例输入 1   6

样例输出 1   0

样例输入 2  109

样例输出 2  20

#include <iostream>
using namespace std;

bool has8(int x) {
    while (x > 0) {
        if (x % 10 == 8) {  
            return true;
        }
        x /= 10;          
    }
    return false;
}

int main() {
    int n, ans = 0;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        if (has8(i)) {
            ans++;
        }
    }

    cout << ans << endl;
    return 0;
}

双指针

D - 超人与奥特曼

题目描述

有一排 NN 个怪兽，第 ii 个怪兽的战斗力为 aiai​，超人站在第一个怪兽的前面，奥特曼站在最后一个怪兽的后面。超人从前往后消灭怪兽，奥特曼从后往前消灭怪兽。因为他们是超人和奥特曼，所以可以秒杀怪兽，但是每打一个怪兽需要休息，休息的时间等于所消灭的怪兽的战斗力，休息结束后会立即消灭下一个怪兽。

请你帮忙计算一下，当所有怪兽都被消灭完的时候，超人和奥特曼各自消灭的怪兽的战斗力总和是多少。

注意：如果超人和奥特曼在同一时刻攻击同一个怪兽，认为怪兽是被超人所消灭。

输入描述

第一行输入一个正整数 N(1<=N<=100)N(1<=N<=100)，表示怪兽的数量。

第二行输入 NN 个不超过 100100 的正整数，用空格隔开，表示每个怪兽的战斗力。

输出描述

输出两个整数，用空格分开，分别表示超人所消灭的怪兽的战斗力总和，以及奥特曼所消灭的怪兽的战斗力总和。

样例输入 1    5 2 3 4 5 6

样例输出 1    9 11

样例输入 2    4 1 2 3 3

样例输出 2    6 3

#include <iostream>
using namespace std;


int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	int n;
	int a[105];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	
	//双指针
	int l=0,r=n-1;
	int x=0,y=0;
	
	while(l<=r){
		if(x<=y){
			x+=a[l];
			l++;
		}else{
			y+=a[r];
			r--;
		}
	} 
	cout<<x<<" "<<y<<endl;
	
    return 0;
}

未解决：P1009 [NOIP 1998 普及组] 阶乘之和 - 洛谷

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

const int MAX_LEN = 100; // 足够存储 50!+...+1!（最多 65 位）

// 高精度乘法：将当前阶乘数组 a（逆序）乘以 x，结果存回 a
void mul(int a[], int &len, int x) {
    int carry = 0; // 进位
    for (int i = 0; i < len; ++i) {
        int product = a[i] * x + carry;
        a[i] = product % 10; // 当前位数字
        carry = product / 10; // 新的进位
    }
    // 处理剩余进位（可能新增位数）
    while (carry) {
        a[len++] = carry % 10;
        carry /= 10;
    }
}

// 高精度加法：将阶乘数组 a（逆序，长度 len_a）累加到结果数组 sum（逆序，长度 &len_sum）
void add(int sum[], int &len_sum, int a[], int len_a) {
    int carry = 0; // 进位
    int max_len = max(len_sum, len_a);
    for (int i = 0; i < max_len; ++i) {
        int s = (i < len_sum ? sum[i] : 0) + (i < len_a ? a[i] : 0) + carry;
        sum[i] = s % 10; // 当前位数字
        carry = s / 10; // 新的进位
    }
    // 处理剩余进位
    while (carry) {
        sum[len_sum++] = carry % 10;
        carry /= 10;
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;

    int sum[MAX_LEN] = {0}; // 存储累加和（逆序）
    int len_sum = 1; // sum 的初始长度：1 位（数字 0）
    int fact[MAX_LEN] = {0}; // 存储当前阶乘 i!（逆序）
    int len_fact = 1;
    fact[0] = 1; // 初始：0! = 1（迭代计算 1! = 0!×1，2! = 1!×2...）

    for (int i = 1; i <= n; ++i) {
        mul(fact, len_fact, i); // 计算 i! = (i-1)! × i
        add(sum, len_sum, fact, len_fact); // 累加 i! 到 sum
    }

    // 逆序输出 sum（从最高位到最低位）
    for (int i = len_sum - 1; i >= 0; --i) {
        cout << sum[i];
    }
    cout << '\n';

    return 0;
}

long long 的最大值仅为 9.22×10^18（约 9e18）

1. 数组存储规则

• 用 int 数组存储数字，逆序排列（例如 123 存储为 [3,2,1]）：

  • 乘法时，从最低位（下标 0）开始计算，进位自然向高位（下标增大方向）传递，无需调整数组；

  • 加法时，同样从最低位对齐，避免高位补零的麻烦。

2. 高精度乘法（mul 函数）

• 输入：当前阶乘数组 a（逆序）、数组长度 len、乘数 x（当前的 i）；

• 逻辑：遍历数组每一位，计算 当前位×x + 进位，当前位存余数（%10），进位存商（/10）；

• 处理剩余进位：乘法可能新增位数（如 999×2=1998，从 3 位变 4 位），需将进位依次存入数组。

3. 高精度加法（add 函数）

• 输入：结果数组 sum（逆序）、sum 长度 len_sum、阶乘数组 a（逆序）、a 长度 len_a；

• 逻辑：遍历到两个数组的最大长度，计算 sum当前位 + a当前位 + 进位，当前位存余数，进位存商；

• 处理剩余进位：加法可能新增位数（如 999+2=1001），需将进位存入 sum 数组。

4. 迭代计算流程

• 初始：fact = [1]（表示 0! = 1），sum = [0]（累加和初始为 0）；

• 循环 i=1 到 n：

  • mul(fact, len_fact, i)：将 fact 从 (i-1)! 更新为 i!；

  • add(sum, len_sum, fact, len_fact)：将 i! 累加到 sum 中；

• 输出：逆序遍历 sum 数组，从最高位（下标 len_sum-1）到最低位（下标 0），输出结果。

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

// 全局变量：memo存储(x,y)到终点的路径数，避免重复计算
// 棋盘最大尺寸15，所以数组开16（下标1~15）
int memo[16][16];
int m, n; // m行，n列

// 递归函数：计算从(x,y)到(m,n)的路径数
int dfs(int x, int y) {
    // 终止条件1：超出棋盘范围，无路径
    if (x > m || y > n) {
        return 0;
    }
    // 终止条件2：到达终点，路径数+1
    if (x == m && y == n) {
        return 1;
    }
    // 记忆化：如果已经计算过(x,y)的路径数，直接返回
    if (memo[x][y] != -1) {
        return memo[x][y];
    }
    // 递推：两种走法的路径数之和
    int res = 0;
    res += dfs(x + 2, y + 1); // 走法1：x+2, y+1
    res += dfs(x + 1, y + 2); // 走法2：x+1, y+2
    // 存储结果到memo，避免重复计算
    memo[x][y] = res;
    return res;
}

int main() {
    // 输入n和m（注意输入顺序：先n后m）
    cin >> n >> m;
    // 初始化memo为-1（表示未计算）
    memset(memo, -1, sizeof(memo));
    // 从起点(1,1)开始递归
    cout << dfs(1, 1) << endl;
    return 0;
}