图论之欧拉路——梦中梦与不再有梦
写在前面的话
- 这道题作为月赛 T1 有点过分了，图论都上了；
- 这道题不是找规律，而是一道性质/结论题。
- 如果你没有学过图论，没关系。
由于我写不来逼格高的这篇题解绝对平易近人，让菜鸟都能一看就懂。
前置知识
如果您没有学过图论以及欧拉路相关的内容，请戳这里。
题意分析
-
每两个梦之间都有且仅有一条桥梁直接相连，不会有桥梁从一个梦连向自身；通过桥梁
e_{u,v} 可以从梦u\rightarrow v 或v \rightarrow u 。这是一个无向简单完全图；
-
对于每个桥梁
e_{u,v} ，它只能被经过一次。这是一个欧拉路问题；
-
获得一点休息值。
边权为
1 ；
正解
经过分析，题目想让我们删去最少的边使原图存在欧拉路。
根据
- 如果
n 是奇数，那么每个点都连接了偶数条边，原图没有奇点，存在欧拉路，直接输出\dfrac{n(n-1)}2 ； - 如果
n 是偶数，那么每个点都连接了奇数条边。显然，删去一条边会使两个点的度数各减一，也就是将两个奇点变成了两个偶点。显然，我们最多有2 个奇点，也就是最少有n-2 个偶点，需要删去\dfrac{n-2}2 条边。
代码
//十年 OI 一场空，不开 long long 见祖宗
#include <bits/stdc++.h>
using namespace std;
inline int read() {
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
int x=0;
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return x;
}
int main(void) {
int T=read();
while(T--) {
long long n=read();
if(n&1) printf("%lld\n",n*(n-1)/2);
else printf("%lld\n",n*(n-1)/2-((n-2)/2));
}
return 0;
}