河工院首届工业设计大赛程序组（挑战赛）题解

$更好的阅读体验$

寻找ACMer

思想：

• 签到题
• 按照题意遍历字符串，不断向后寻找包含 ACMer 完整字符串的数量即可

std标程：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

void solve(){
   

    string s; cin >> s;
    int idx = 0;
    int ans = 0;
    while(s.find("ACMer", idx) != -1) {
   
        ans ++; idx = s.find("ACMer", idx) + 1;
    }
    cout << ans << endl;

}

int main(){
   

    IOS;

    int _ = 1;

    // cin >> _;

    while(_ --){
   
        solve();
    }

    return 0;

}

欧拉幻树苗

思想：

• 树形DP
• 始化每一个节点为独立的连通分量，即每个节点自身就是一个树的根。
• 读取树的结构，确保我们可以通过 g 数组访问到每个节点的孩子节点。
• 读取特殊边，并使用并查集合并特殊边的两个端点。由于题目保证特殊边的两个端点深度相同，合并这些端点不会导致环的出现。
• 然后开始广度优先搜索。从根节点（节点1）开始，用队列来记录接下来需要访问的节点。
• 对于当前节点 t，如果它是叶子，将 find(t) 的路径数加到答案中（即cnt[find(t)]），因为从叶子节点可以直接走到根节点。
• 遍历当前节点t的所有孩子节点，将父节点到当前节点的路径数累加到孩子节点上（需要通过find函数找到孩子节点所在的连通分量），然后将这些孩子节点加入队列中以进行下一轮搜索。
• 当队列为空时，所有节点都被访问过，搜索结束。最后输出计算的答案 ans。

std标程：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<