讨论详情 - QY code

图论，BFS

题目解析：

T1：CF520B Two Buttons

题意：给定一个红色按钮，蓝色按钮，数字 $n$ 和显示屏，

红色按钮：当前数字乘以2

蓝色按钮：当前数字减1

如果数字为负了，装置就损坏了,求数字从n到m最少要按多少次

思路： 1.判断首先比较 $n$ 和 $m$ 的大小，如果 $m < n$ ，由于乘 $2$ 只会让数字变得更大，此时唯一合法的操作就是连续减 $1$ ，因此，直接输出差值 $n - m$ 即可。

如果 $m > n$ ，我们需要不断将当前数字乘 $2$ ，并使用一个变量 $sum$ 来记录按红色按钮的次数, 一旦当前数字大于或等于 $m$ ，必须立即停止倍增操作。此时，剩余的差距只能通过连续按蓝色按钮（减 $1$ ）来弥补。

4.输出将之前记录的倍增次数与剩余的差值（当前数字 $- m$ ）相加，就是答案

代码：

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int n, m;
    cin >> n >> m;
    int ans = 0;
    if(n >= m) 
    {
        cout << n - m << endl;
        return 0;
    }
    while (m > n) 
    {
        if (m % 2 == 0) 
        {
            m /= 2;
            ans++;
        } 
        else 
        {
            m++;
            ans++;
        }
    }
    ans += (n - m);
    cout << ans << endl;
    return 0;
}

T2：CF35C Fire Again

题意：一个n*m棵树，初始时有 $k$ 棵树燃烧，如果相邻树有燃烧，那一分钟内这棵树也会燃烧，求最后燃烧树的坐标

思路：延伸，所以直接用BFS 代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
int n, m, k;
int d[N][N];
bool v[N][N];
int main() 
{
    cin >> n >> m >> k;
    queue<pair<int, int>> q;
    for (int i = 0; i < k; i++) 
    {
        int x, y;
        cin >> x >> y;
        q.push({x, y});
        v[x][y] = true;
        d[x][y] = 0;
    }
    int md = 0;
    int ax = q.front().first, ay = q.front().second;
    while (!q.empty()) 
    {
        auto c = q.front();
        q.pop();
        
        if (d[c.first][c.second] > md) 
        {
            md = d[c.first][c.second];
            ax = c.first;
            ay = c.second;
        }
        for (int i = 0; i < 4; i++) 
        {
            int nx = c.first + dx[i];
            int ny = c.second + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !v[nx][ny]) 
            {
                v[nx][ny] = true;
                d[nx][ny] = d[c.first][c.second] + 1;
                q.push({nx, ny});
            }
        }
    }
    cout << ax << " " << ay << endl;
    return 0;
}

T3：CF1106D Lunar New Year and a Wander

题意：小k 在公园散步，从节点 1 出发，每到一个新节点就记下来。目标是走遍所有节点，求记下来的字典序最小的序列。思路：

贪心+优先队列

每次优先选择当前能到达的、编号最小的未访问节点。用一个小顶堆来维护当前所有可达的未访问节点。每次从堆顶弹出最小节点，记录它，并把它的邻居加入堆中，直到记录满 $n$ 个节点。代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> g[N];
bool vis[N];
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) 
    {
        int u, v;
        cin >> u >> v;
        if (u != v) 
        { 
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }
    priority_queue<int, vector<int>, greater<int>> q;
    q.push(1);
    
    vector<int> res; 
    while (!q.empty()) 
    {
        int u = q.top();
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        res.push_back(u);
        for (int v : g[u]) 
        {
            if (!vis[v]) 
            {
                q.push(v); 
            }
        }
    }
    for (int i = 0; i < res.size(); i++) 
    {
        if (i > 0) cout << " ";
        cout << res[i];
    }
    cout << endl;
    
    return 0;
}

T4：CF954D Fight Against Traffic

题意：思路：代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
vector<int> g[N];
int d[2][N];
bool v[N];
void b(int s, int i) 
{
    memset(v, 0, sizeof(v));
    queue<int> q;
    q.push(s);
    v[s] = 1;
    d[i][s] = 0;
    while (!q.empty()) 
    {
        int u = q.front();
        q.pop();
        for (int x : g[u]) 
        {
            if (!v[x]) 
            {
                v[x] = 1;
                d[i][x] = d[i][u] + 1;
                q.push(x);
            }
        }
    }
}
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    for (int i = 0; i < m; i++) 
    {
        int u, x;
        cin >> u >> x;
        g[u].push_back(x);
        g[x].push_back(u);
    }
    b(s, 0);
    b(t, 1);
    int o = d[0][t];
    vector<vector<bool>> e(n + 1, vector<bool>(n + 1, 0));
    for (int i = 1; i <= n; i++) 
    {
        for (int x : g[i]) 
        {
            e[i][x] = 1;
        }
    }
    int a = 0;
    for (int i = 1; i <= n; i++) 
    {
        for (int j = i + 1; j <= n; j++) 
        {
            if (e[i][j]) continue;
            int p = d[0][i] + 1 + d[1][j];
            int c = d[0][j] + 1 + d[1][i];
            if (p >= o && c >= o) 
            {
                a++;
            }
        }
    }
    cout << a << endl;
    return 0;
}

T5：CF601A The Two Routes

题意：火车和巴士同时从 1 出发去 n，火车走铁路，巴士走公路，要求它们不能同时到达同一个中间城镇。求两车都到达 n 的最少时间思路： 1.火车经过的城镇没有公路，巴士绝对走不到；巴士经过的城镇没有铁路，火车绝对走不到。所以两车在中间节点天然互斥，不会碰撞。 2.分别对铁路图和公路图跑一次 BFS，求出火车和巴士各自的最短时间。 3. 答案就是 max(火车时间, 巴士时间)，若任一不可达则输出 -1 代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>a[410],b[410];
int c[410],d[410],x[410][410];
void bfs(int s,vector<int>g[],int f[])
{
	for(int i = 1;i <= n;i++)
    {
        f[i]=1e9;
    }
	queue<int>q;
	f[s] = 0;
	q.push(s);
	while(!q.empty())
    {
		int u = q.front();
        q.pop();
		for(int v:g[u])
        {
			if(f[v]==1e9)
            {
				f[v]=f[u]+1;
				q.push(v);
			}
		}
	}
}
int main()
{
	cin>> n >> m;
	for(int i = 1;i <= m;i++)
    {
		int u,v;
		cin>> u >> v;
		x[u][v] = x[v][u] = 1;
	}
	for(int i = 1;i <= n;i++) 
    {
		for(int j = i + 1;j <= n;j++)
        {
			if(x[i][j])
            {
				a[i].push_back(j);
				a[j].push_back(i);
			}
            else
            {
				b[i].push_back(j);
				b[j].push_back(i);
			}
		}
	}
	bfs(1,a,c);
	bfs(1,b,d);
	if(c[n] == 1e9 || d[n] == 1e9)
    {
        cout<<-1;
    }
	else cout<<max(c[n],d[n]);
	return 0;
}

T6：CF1037D Valid BFS?

题意：给定一棵包含 $n$ 个节点的树，以及一个长度为 $n$ 的节点序列。判断该序列是否可能是从节点 $1$ 开始进行合法 BFS遍历所得到的结果。

思路： 1.BFS 必须从节点 1 开始，因此序列的第一个元素必须是 1。 2.预处理：记录给定序列中每个节点出现的下标位置，以便快速比较节点间的先后顺序。 3. 按序列顺序遍历每个节点 $u$ ，找出它在树中所有 $u$ 的子节点。在合法的 BFS 序列中，同一个父节点 $u$ 的所有子节点在给定序列中必须是连续出现的。 4.指针：使用一个指针指向序列中下一个待验证的位置，将当前节点 $u$ 的子节点按序列中的位置排序后，依次与指针指向的元素比对。如果不匹配，则说明序列非法。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int> g[N]; 
int pos[N];      
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) 
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++) 
    {
        cin >> a[i];
        pos[a[i]] = i; 
    }
    if (a[0] != 1) 
    {
        cout << "No" << endl;
        return 0;
    }
    int t = 1; 
    for (int i = 0; i < n; i++) 
    {
        int u = a[i];
        vector<int> ch;
        for (int v : g[u]) 
        {
            if (pos[v] > pos[u]) 
            {
                ch.push_back(v);
            }
        }
        sort(ch.begin(), ch.end(), [](int x, int y) 
        {
            return pos[x] < pos[y];
        });
        for (int c : ch) 
        {
            if (t >= n || a[t] != c) 
            {
                cout << "No" << endl;
                return 0;
            }
            t++;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

7月day8

图论，BFS

题目解析：

T1：CF520B Two Buttons

T2：CF35C Fire Again

T3：CF1106D Lunar New Year and a Wander

贪心+优先队列

T4：CF954D Fight Against Traffic

T5：CF601A The Two Routes

T6：CF1037D Valid BFS?

0 条评论

目前还没有评论...

7月day8

图论，BFS

题目解析：

T1：CF520B Two Buttons

T2：CF35C Fire Again

T3：CF1106D Lunar New Year and a Wander

贪心+优先队列

T4：CF954D Fight Against Traffic

T5：CF601A The Two Routes

T6：CF1037D Valid BFS?

0 条评论

目前还没有评论...

还没有账户？

登录