cable cable cable

【2017 ACM/ICPC Asia Regional Shenyang Online】cable cable cable

Solution:

对于M个显示器,我们不如这样考虑:对于前K个【备注:题目保证了K不大于M】显示器,分别只与一个信号源连接,需要K根信号线;接下来断言,剩下的M-K个显示器每个都必要与K个信号源连接,也就是K*(M-K)根线,我们使用反证法证明,做如下思考,假如我们在选取K个显示器的时候,先将这K个显示器选定,之后任意从中去除一个显示器,再从剩下的M-K个显示器中选一个假如进来,如果这剩下的显示器中存在一个没有连接到K个信号源的显示器的话,假设它没有连接\(K_a\)信号源,那么,如果我们在选取时不选那个只连接着\(K_a\)信号源的显示器,而选择这个,就会导致不满足K个显示器有K个颜色,故断言必然成立。

因此公式为:

\(k + k * (m – k) = k * (m – k + 1)\)

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

int main(void) {
    ios::sync_with_stdio(false);
    ULL k, m;
    while (cin >> m >> k) {
        cout << k * (m - k + 1) << endl;
    }
    return 0;
}