ACM训练问题实际代码操作

1.队列与栈的实际应用。

对于每一个样例，第一行是N和一个字符串“FIFO”或者“FILO”（FIFO表示先进先出，即队列;FILO表示先进后出，即栈，），N表示命令的个数，下面有N行，每一行表示一个命令。命令分为两种，IN a 表示进去一个a，OUT表示出一个队头元素或者栈顶元素。

输入格式

第一行是一个数字T，表示样例的个数，对于每一个样例，如题目所述。

输出格式

对于每一个OUT命令，你要根据“FIFO”和“FILO”单独一行输出一个数字，或者输出None如果没有整数了。

#include<vector>
#include <iostream>
#include<string>
#include <queue>
#include <stack>
using namespace std;
int main() {
int T,n;
string S;
cin >> T;

while (T--) {
cin >> n;
cin >> S;
if (S == "FIFO") {
queue<int>x;
for (int i = 1; i <= n; i++) {
string order;
cin >> order;
if (order == "IN") {
int number;
cin >> number;
x.push(number);

}
else {
if (!x.empty()) {
cout << x.front() << endl;
x.pop();
}
else cout << "None"<<endl;
}
}
}
if(S=="FILO") {
stack<int>y;
for (int i = 1; i <= n; i++) {
string order;
cin >> order;
if (order == "IN") {
int number;
cin >> number;
y.push(number);

}
else {
if (!y.empty()) {
cout << y.top() << endl;
y.pop();
}
else cout << "None"<<endl;
}
}
}
}
return 0;
}

2.哈希表的运用。

#include<vector>
#include <iostream>
#include<string>
#include <queue>
#include <stack>
#include<algorithm>
#include <cstring>
#include <unordered_map>
using namespace std;
long long a[1000005];
int main(){
int n;
long long m;
cin >> n >> m;
unordered_map<long long, int>outcome;
outcome[0] = 1;
vector<long long>pre(n+1,0);
long long count = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = a[i] + pre[i - 1];
long long goal = pre[i] - m;
if (outcome.count(goal)) {
count += outcome[goal];
}
outcome[pre[i]]++;
}
cout << count;
return 0;
}

3.图的建立/BFS/DFS

按照输入要求创建图，并分别用深度优先和广度优先两种方法遍历这张图。

输入格式

第一行包含两个整数 n,mn,m (1≤n≤80, n−1≤m≤1500)(1≤n≤80, n−1≤m≤1500)，分别表示图中点与边的数量。

其后 mm 行，每行包含两个整数 a,ba,b (0≤a,b<n)(0≤a,b<n)，表示 a,ba,b 这两个点之间是连通的。

输出格式

第一行输出按照深度优先搜索方法遍历的结果，第二行输出按照广度优先搜索方法遍历的结果(该题默认根据节点编号从小到大遍历该图)。

#include<vector>
#include <iostream>
#include<string>
#include <queue>
#include <stack>
#include<algorithm>
#include <cstring>
using namespace std;
vector<int> e[100];
vector<int> BFS, DFS;
bool vis[100];
void dfs(int x) {
vis[x] = true;
DFS.push_back(x);
for (int y : e[x])
{
if (!vis[y])
dfs(y);
}
}
void bfs(int x)
{
queue<int> q;
q.push(x);
vis[x] = true;
BFS.push_back(x);
while (q.size()){
int x= q.front();
q.pop();
for (int y : e[x]){
if (!vis[y])
{
q.push(y);
vis[y] = true;
BFS.push_back(y);
}

}
}
}

int main() {
int n, m;//点,边；
cin >> n >> m;

for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
}
for (int i = 0; i < n; i++)sort(e[i].begin(), e[i].end());

for (int i = 0; i < n; i++)
{
if (!vis[i])
{
dfs(i);
}
}
memset(vis, 0, sizeof vis);
for (int i = 0; i < n; i++) {
if (!vis[i])
{
bfs(i);
}
}
for (int a : DFS) {
cout << a << ' ';
}
cout << endl;
for (int a : BFS) {
cout << a << ' ';
}
cout << endl;


return 0;
}

4.字符串字母前缀统计

#include<vector>
#include <iostream>
#include<string>
#include <queue>
#include <stack>
#include<algorithm>
#include <cstring>
#include <unordered_map>
using namespace std;
int main() {
int n, k, t;
cin >> t;
while (t--) {
cin >> n >> k;
string str1;
string str2;
cin >> str1;
cin >> str2;
int l, r;
vector<vector<int>>pre1(n+1, vector<int>(26,0));
vector<vector<int>>pre2(n + 1, vector<int>(26, 0));
for(int i=0;i<n;i++){
pre1[i+1] = pre1[i];
pre2[i+1] = pre2[i];
pre1[i+1][ str1[i] - 'a']++;
pre2[i+1][ str2[i] - 'a']++;
}
while (k--) {
int count = 0;
cin >> l >> r;

for (int i = 0; i < 26; i++) {
int x1 = pre1[r][i] - pre1[l - 1][i];
int x2 = pre2[r][i] - pre2[l - 1][i];
if (x1 > x2)count += x1 - x2;
}
cout << count << endl;
}
}

5.树的直径

#include <vector> #include <iostream> #include <string> #include <queue> #include <stack> #include <algorithm> #include <cstring> using namespace std; const int N = 100000 + 10; // 定义最大节点数，+10 作为缓冲区 int n, c; // n: 节点数, c: 存储最远节点的临时变量 int count = 0; // 未使用的变量，可忽略 vector<int> e[N]; // 邻接表，e[u] 存储节点 u 的所有邻居 int DFS[N]; // 深度数组，DFS[u] 表示从起点到节点 u 的深度 // DFS 函数：递归遍历树，更新深度并记录最远节点 // u: 当前节点, fa: 父节点（避免回退） void dfs(int u, int fa) { for (int v : e[u]) { // 遍历 u 的所有邻居 v if (v == fa) continue; // 跳过父节点，防止循环 DFS[v] = DFS[u] + 1; // 更新节点 v 的深度（当前深度 +1） if (DFS[v] > DFS[c]) c = v; // 如果 v 的深度大于当前记录的最深节点，更新 c dfs(v, u); // 递归遍历子节点 v } } int main() { cin >> n; // 输入节点数 n // 构建树的邻接表：输入 n-1 条边 for (int i = 1; i <= n-1; i++) { int u, v; cin >> u >> v; // 输入一条边的两个端点 e[u].push_back(v); // 将 v 添加到 u 的邻居列表 e[v].push_back(u); // 将 u 添加到 v 的邻居列表（无向图） } // 第一次 DFS：从节点 1 开始，找到最远节点 c DFS[1] = 0; // 初始化起点深度为 0 c = 1; // 初始化 c 为起点（节点 1） dfs(1, 0); // 调用 DFS，fa=0 表示根节点无父节点 // 第二次 DFS：从第一次找到的最远节点 c 开始，找到直径的另一端点 DFS[c] = 0; // 重置 c 的深度为 0（作为新起点） dfs(c, 0); // 再次调用 DFS，此时 DFS[c] 将存储最大深度（即直径） printf("%d\n", DFS[c]); // 输出树的直径（DFS[c] 的值） return 0; }