题解 P6857 【梦中梦与不再有梦】

phil071128 · 2020-10-23 13:21:26 · 题解

这道题我们可以打表（逃）

打表程序：

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        switch (n){
            case 1:{
                cout<<0<<"\n";
                break;
            }
            case 2:{
                cout<<1<<"\n";
                break;
            }
            case 3:{
                cout<<3<<"\n";
                break;
            }
            case 4:{
                cout<<5<<"\n";
                break;
            }
            case 5:{
                cout<<"10\n";
                break;
            }
            case 6:{
                cout<<"13\n";
                break;
            }
            case 7:{
                cout<<"21\n";
                break;
            }
        }
    }
    return 0;
}

正确的解法是一笔画问题

如果你不知道什么是一笔画，你可以去百度

百度百科 一笔画问题

那么我们该怎么解决这道题呢？

有以下结论：

1. 凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。

2. 凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点则是终点。

3. 其他情况的图都不能一笔画出。(奇点数除以二便可算出此图需几笔画成。)

所以说：

• 一个图形判断能否被一笔画下来，关键是看奇点的个数：

• 当奇点为0个或者2个时（不可能为一个，奇点都是成对出现），可以被一笔画下来，反之则不能。

当点数个数为奇数时（%2==1），该图则一定可以一笔画。 否则（偶数），我们需要删掉n-2个点.

就是

100分代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long t;
    cin>>t;
    while(t--){
        long long n;
        cin>>n;
        if(n%2==1){
            cout<<n*(n-1)/2<<endl;
        }else{
            cout<<(n-1)*(n-2)/2+(n/2)<<endl;
        }

    }
    return 0;
}

话说，其实考场上列个表找规律就好了，毕竟这是月赛，多用点的时间去A一道题也无妨。