第十次CCF-CSP
第三题 Markdowm
原题链接：3244. Markdown - AcWing题库
思路分析：
这道大模拟题，对于我而言主要有下面几个难点：
输入数据不知道怎么处理
vector<string> str; while(getline(cin,s)) //只有遇到结束符 Ctrl z 或者 EOF才结束 str.push_back(s)怎么找到每一个区块？
for(int i = 0;i<str.size();i++) { if(str[i].empty()) //这里是把空行跳过 continue; int j = i + 1; //j 用来“测量” 这个区块有多少行 while(j<str.size() && !str[j].empty()) j++; solve(i,j-1); //i到j-1 就是区块的行数 i=j-1; }
处理完这两个问题之后，下面正式进入题目的分析：
对于每一个区块，有三种可能：
- 段落
- 标题
- 无序列表
而对于每一个区块，其中的每一行都可能会有
强调
超级链接
强调中 嵌套超级链接
超级链接中 嵌套强调
所以我们可以写两个函数，一个处理区块，一个处理区块中的每一行。
代码展示
#include<bits/stdc++.h>
using namespace std;
vector<string> str;
void solve_line(string s) //处理每行的具体细节
{
int i;
for (i = 0; i < s.size(); i++)
{
if (s[i] != ' ')
break;
}
for (i; i < s.size(); i++)
{
if (s[i] == '_') //处理强调
{
cout << "<em>";
for (i++; s[i] != '_'; i++)
{
if (s[i] == '[') //强调中嵌套超链接
{
string text, link;
for (i++; s[i] != ']'; i++) //text
{
text += s[i];
}
for (i++; s[i] != ')'; i++)
{
if (s[i] == '(')
continue;
link += s[i];
}
cout << "<a href=\"" << link << "\">" << text << "</a>";
}
else
{
cout << s[i];
}
}
cout << "</em>";
}
else if (s[i] == '[') //处理超链接
{
cout << "<a href=\"";
string text, link;
for (i++; s[i] != ']'; i++) //text
{
if (s[i] == '_') //超链接中嵌套强调
{
text += "<em>";
for (i++; s[i] != '_'; i++)
{
text += s[i];
}
text += "</em>";
}
else
{
text += s[i];
}
}
for (i++; s[i] != ')'; i++) //link
{
if (s[i] == '(')
continue;
//link += "<a href=";
if (s[i] == '_')
{
link += "<em>";
for (i++; s[i] != '_'; i++)
{
link += s[i];
}
link += "</em>";
}
else
{
link += s[i];
}
}
cout << link << "\"" << ">" << text << "</a>";
}
else //其他的 普通字符 直接输出
cout << s[i];
}
//cout << '\n';
}
void solve(int a, int b) //a,b表示区块开始的行号 结束的行号
{
if (str[a][0] == '#')
{
string s;
int k = 0;
for (int i = 0; i < str[a].size(); i++)
{
if (str[a][i] == '#')
k++;
}
cout << "<h" << k << ">";
solve_line(str[a].substr(k));
cout << "</h" << k << ">" << endl;
}
else if (str[a][0] == '*')
{
cout << "<ul>\n";
for (int i = a; i <= b; i++) //每一行
{
cout << "<li>";
solve_line(str[i].substr(1));
cout << "</li>\n";
}
cout << "</ul>\n";
}
else
{
cout << "<p>";
for (int i = a; i <= b; i++)
{
solve_line(str[i]);
if(i!=b)
cout << '\n';
}
cout << "</p>\n";
}
}
int main()
{
string s;
while (getline(cin, s))
{
str.push_back(s);
}
for (int i = 0; i < str.size(); i++)
{
if (str[i].empty())
continue;
int j = i + 1;
while (j < str.size() && !str[j].empty()) //找到区块
j++;
solve(i, j - 1); //处理区块
i = j - 1;
}
return 0;
}
踩坑
- 注意超链接要先存起来，再输出，不能一边遍历一边输出
- 注意每一行 换行时
</p>要放在最后一行的末尾
第四题：地铁修建
思路分析
题目描述有点复杂，把题目翻译一下就是：
给定一个无向图，有n个节点，m条边。要求最多选取n条边的前提下，使得节点1和节点n连通。求所用边最大的权重的最小值。
（最大的最小—可以联想到二分）
那么要怎么二分？
对于题意：假设修建地铁最少需要 mid 天，若在所有施工公司中修建天数小于 mid 天的公司中选取 1–n 个公司，可以使得节点1和节点n连通。那么此时的mid还可以再尝试变小。
翻译一下就是：
若从边权小于等于 mid 的边中选择边，找到节点1到节点n的最短路（每条路的长度是1），使得最短路的长度小于等于n。则此时的mid符合题意。
所以本题本质上是考察二分和BFS(最短路问题)。
难点
- 用数组模拟链表
//定义：
const int N = 1e6+10,M=4e6+10;
//h[i] 是以i为起点的链表的头指针, e[] 存放边的节点，w[] 存放边的权重, ne[] 存放下一个节点的索引（类似于指针
int h[N],e[M],w[M],ne[M],idx;
//初始化：
memset(h,-1,sizeof h);
//赋值：
void add(int a,int b,int c)
{
e[idx]=b; //是将节点b放在idx边上
w[idx]=c; //边idx 的权重
ne[idx]=h[a];//记住此时的头结点的索引
h[a]=idx++; //头指针移动（头插法）
}
//遍历：
for(int i = h[t];i!=-1;i=ne[i])
{
int j = e[i];
...
}
代码展示
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, M = 4e6 + 5;
int n, m;
int h[N], e[M], w[M], ne[M], idx; //注意这里的 N 和 M（简单起见也可以都用较大的M）
queue<int> q;
int dist[N]; //dist[i] 表示 1 到 i 的最短距离
void add(int a, int b, int c) //赋值
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
bool check(int mid)
{
memset(dist, 0x3f, sizeof dist); //路径初始化为最大值
dist[1] = 0;
q.push(1); //利用bfs
while (!q.empty())
{
int t = q.front();
q.pop();
for (int i = h[t]; i!=-1; i = ne[i]) //遍历
{
if (w[i] > mid) //由题目分析可知 只用权重小于mid 的
continue;
int j = e[i];
if (dist[j] > dist[t] + 1) //求最短路
{
dist[j] = dist[t] + 1;
q.push(j);
}
}
}
if (dist[n] <= n)
return true;
else
return false;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h); //初始化
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c); //无向边
add(b, a, c);
}
int l = 0, r = 1e6;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid))
r = mid;
else
l = mid + 1;
}
cout << r;
return 0;
}
