【C++】 —— 笔试刷题day

一、kotori和气球

题目解析

这道题，有n中气球，每一种气球有无数多个；现在我们需要将这些气球摆成一排，但是，如果相邻的气球是相同的就会发生爆炸（也就是说，相同的气球相邻的摆法是不合法的）；

现在我们要求将气球摆成一排m个一共有多少种摆法；最终结果可能数据过大，我们输出最终结果对于109取模的结果即可。

算法思路

这道题整体来说还是比较简单的：

我们摆放第一个气球时，我们可以随便选取一个气球，那也就有n中可能；

当我们摆放第二个以及后面的气球时，我们不能摆放与上一个气球相同的气球，那也就有n-1种可能。

所以，我们最终结果就等于：n * (n-1)^(m-1)。

代码实现

这里通过查看数据范围我们可以发现：在运算的时候数据就看超出范围，所以在运算的过程中就进行%109操作。

#include 
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    long long ret = n;
    for(int i = 1;i > m;
    cin >> x1 >> y1 >> x2 >> y2;
    for (int i = 1; i 
        for (int j = 1; j 
            cin  arr[i][j];
        }
    }
    cout 
  public:
    int minmumNumberOfHost(int n, vector
        sort(startEnd.begin(), startEnd.end());
        priority_queue
            if (startEnd[i][0] = heap.top()) {
                heap.pop();
                heap.push(startEnd[i][1]);
            } else {
                heap.push(startEnd[i][1]);
            }
        }
        return heap.size();
    }
};