P9077 [PA2018] Poddrzewo

Last_kiss_Snow_Dog6 · 2023-09-12 20:57:49 · 题解

题目

1. 修改序列中第 i 个数。
2. 删除序列中第 i 个数。
3. 交换序列中第 i,j 个数。

按照正常思路来想我们要建一个图，一个无环的图。

但是看样例一：读入了 6 个度，但是只输出了 4 条边和 5 个点，可以看出：有一个度没有用到，这是以简单方法切题的切入点，不妨大胆设想一下，如果只有两个点呢？可以直接用节点一连节点二。

好像题目中的每一个要求都符合了。

节点 1 和节点 2 的度都为 1 。

那现在题目要求就变成了怎样的条件才能满足直接用节点一连节点二呢？

很显然只要 n 个度中有 2 个是 1 就行了，不然就变里面随机一到两个为 1 。

#include <bits/stdc++.h>
using namespace std;

int n,jh;

int main ( ) {

    cin >> n ;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x ;
        if (x == 1) jh++;//统计1的个数
    }
    if (jh >= 2) cout << "0" << endl ;//满足情况直接输出
    else cout << 2 - jh << endl ;//不满足时计算所需的改变次数
    cout << "2" << endl << "1 2" << endl ;
}