QYcode QYcode
编程

7月day10

· 2026-7-20 16:17:59

题目解析

T1:CF1020B Badge

题意：有nn个学生在恶作剧，于是老师每抓住一个学生，就在他的徽章上打一个洞，到最后一定会有一个同学的徽章上有两个洞，求哪个学生徽章上有两个洞。 思路： 这道题本质是一道找环问题， 如果按照顺序一直走，必定会走进一个死循环。当再次遇到之前抓过的学生时，他就会被打上第二个洞。因此，对每个起点直接暴力模拟即可。 代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int p[N];
bool vis[N];
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) 
    {
        cin >> p[i];
    }
    for (int a = 1; a <= n; a++) 
    {
        memset(vis, false, sizeof(vis));
        int cur = a;
        while (true) 
        {
            if (vis[cur]) 
            {
                cout << cur << " ";
                break;
            }
            vis[cur] = true; 
            cur = p[cur];    
        }
    }
    cout << endl;
    return 0;
}

T2:CF1851E Nastya and Potions

题意：有nn种药剂，获取方式有两种：1.直接花钱购买2.用其他药剂混合起来合成这种药剂。注意不可以将自己和自己混合，kk种药剂是无限且免费的，求获取这种药剂的最小花费。 思路：使用记忆化搜索 先处理免费药剂：将题目给出的kk种免费药剂标记为已访问，DFS 遇到它们时直接返回0。 再处理叶子节点：如果某种药剂没有合成配方，它只能直接购买，返回其购买价格c[i]。 状态转移与记忆化：对于普通药剂，递归计算其所有材料的最小花费之和。将合成总花费与直接购买花费取最小值，存入记忆化数组f[i]中并返回，避免重复计算。 代码：

#include <bits/stdc++.h>
using namespace std;
vector<long long> f;
vector<long long> co;
vector<int> vis;
vector<vector<int>> a;
long long dfs(int u) 
{
	if (vis[u]) return 0;
	if (f[u] != -1) return f[u];
	if (a[u].empty()) 
    {
		return f[u] = co[u];
	}
	long long sum = 0;
	for (int v : a[u]) 
    {
		sum += dfs(v);
	}
	return f[u] = min(co[u], sum);
}
int main() 
{
	int t;
	cin >> t;
	while (t--) 
    {
		int n, k;
		cin >> n >> k;
		co= vector<long long>(n + 1, 0);
		f = vector<long long>(n + 1, -1);
		vis = vector<int>(n + 1, 0);
		a = vector<vector<int>>(n + 1);
		for (int i = 1;i <= n;i++) 
        {
			cin >> co[i];
		}
		for (int i = 0;i < k;i++) 
        {
			int p;
			cin >> p;
			vis[p] = 1;
		}
		for (int i = 1;i <= n;i++) 
        {
			int m;
			cin >> m;
			for (int j = 0;j < m;j++) 
            {
				int x;
				cin >> x;
				a[i].push_back(x);
			}
		}
		for (int i = 1;i <= n;i++) 
        {
			cout << dfs(i) << ' ';
		}
		cout << endl;
	}
	return 0;
}

T3:CF510C Fox And Names

题意： 给定n个字符串，问是否存在一种自定义的字母表顺序，使得这 n 个字符串按字典序严格递增。如果存在，输出任意一种合法的字母表排列，如果不存在，输出 Impossible。

思路：拓扑排序 提取字母间的先后关系。依次比较相邻的两个字符串，找到它们第一个不同的字符。为了保证字典序成立，前一个字符串中的该字符在自定义字母表中必须排在后一个字符串对应字符的前面。据此建立有向边并统计入度。 如果相邻字符串在较短字符串的长度内所有字符都相同，但前一个字符串更长，则违反字典序规则，那就是无解。此外，如果提取出的字母依赖关系中存在环，导致拓扑排序无法排满26个字母，同样判定无解。 拓扑排序求解。将所有入度为零的字母加入队列，依次取出并拼接到结果字符串中，同时将其指向的后继字母入度减一。若后继字母入度减为零则将其加入队列。最终若结果字符串长度等于26，则输出该序列作为合法的字母表顺序。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
string s[N];
vector<int> g[26];
int in[26];     
void so() 
{
    cin >> n;
    for (int i = 0; i < n; i++) 
    {
        cin >> s[i];
    }
    for (int i = 0; i < 26; i++) 
    {
        g[i].clear();
        in[i] = 0;
    }
    for (int i = 0; i < n - 1; i++) 
    {
        string a = s[i];
        string b = s[i + 1];
        bool f = false;
        for (int j = 0; j < min(a.size(), b.size()); j++) 
        {
            if (a[j] != b[j])
            {
                int u = a[j] - 'a', v = b[j] - 'a';
                g[u].push_back(v);
                in[v]++;
                f = true;
                break; 
            }
        }
        if (!f && a.size() > b.size()) 
        {
            cout << "Impossible" << endl;
            return;
        }
    }
    queue<int> q;
    for (int i = 0; i < 26; i++) 
    {
        if (in[i] == 0) 
        {
            q.push(i);
        }
    }
    string ans = "";
    while (!q.empty()) 
    {
        int u = q.front();
        q.pop();
        char c = u + 'a';
        ans += c;
        for (int v : g[u]) 
        {
            in[v]--;
            if (in[v] == 0) 
            {
                q.push(v);
            }
        }
    }
    if (ans.size() != 26) 
    {
        cout << "Impossible" << endl;
    } 
    else 
    {
        cout << ans << endl;
    }
}
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    so();
    return 0;
}

T4:CF1027D Mouse Hunt

题意：有nn个房间，老鼠每秒会从第ii个房间移动到第aia_i 个房间。老鼠初始可能在任意房间。已知在第ii个房间放置捕鼠器的花费为cic_i 求保证无论老鼠初始在哪个房间，最终都能被抓到的最小花费。 思路：每个点只有一条出边，图的结构是基环树森林。老鼠无论从哪里出发，最终都会走进一个环里打转。因此只需在每个环上放捕鼠器，树枝部分不用管。为了让花费最少，在每个环上选花费最小的点放捕鼠器即可。 把叶子节点删去，只留下环，然后选价钱最少的就行。 代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
int c[N];    
int a[N];     
int in[N];  
bool vis[N];//标记
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> c[i];
    } 
    for (int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        in[a[i]]++; 
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) 
    {
        if (in[i] == 0) 
        { 
            q.push(i);
        }
    }
    while (!q.empty()) 
    {
        int u = q.front();
        q.pop();
        int v = a[u];
        in[v]--; 
        if (in[v] == 0) 
        { 
            q.push(v);
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) 
    {
        if (in[i] > 0 && !vis[i]) 
        {
            int m = INT_MAX;
            int u = i;
            while (!vis[u]) 
            {
                vis[u] = true;
                m = min(m, c[u]);
                u = a[u];
            }
            ans += m;
        }
    }
    cout << ans << endl;
    return 0;
}

T5:CF919D Substring

题意： 给定一个有向图，每个节点有一个小写字母。一条路径的权值定义为路径上出现次数最多的字母的次数。求最大权值。若存在环导致权值可无限大，输出 -1。 思路：DP+拓扑排序 1.判断是否有环：如果图中存在环，且环上包含某个字母，那么可以绕着环无限走，该字母的出现次数可以无限增大，直接输出 -1。 2.状态定义：用 dp[u][c] 表示到达节点 u 时，字母 c 出现的最大次数。 3.状态转移：利用拓扑排序保证无后效性。每次从队列中取出一个节点 u，遍历它的后继节点 v，将 u 的所有字母计数传递给 v（即 dp[v][c] = max(dp[v][c], dp[u][c])）。 4.更新当前节点：在处理节点 u 时，先将 u 自身字母的计数加 1，然后更新全局答案。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
vector<int> g[N];
int dp[N][30];
int du[N];
int main()
{
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    for(int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        du[v] ++;
    }
    queue<int> q;
    for(int i = 1; i <= n; i++)
    {
        if(du[i] == 0) q.push(i);
    }
    int ans = 0, cnt = 0;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        cnt ++;
        dp[u][s[u - 1] - 'a'] ++;
        for(int ch = 0; ch < 26; ch++)
        {
            ans = max(dp[u][ch], ans);
        } 
        for(auto v : g[u])
        {
            for(int ch = 0; ch  < 26; ch ++)
            {
                dp[v][ch] = max(dp[v][ch], dp[u][ch]);
            }
            if(--du[v] == 0) q.push(v);
        }
    }
    if(cnt < n) cout << -1 << endl;
    else cout << ans << endl;
}

T6:CF1572A Book

题意： 思路： 代码：

已修改 1 次查看 举报

0 条评论

目前还没有评论...

Be the first to comment!

返回讨论列表
温张鑫
161
通过题目
6
发帖数