Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

洛谷10月月赛 T147643 梦中梦与不再有梦

keep/ 2020-10-19 00:55:00 阅读数:12 评论数:0 点赞数:0 收藏数:0

T1 梦中梦与不再有梦

思路分析

要求找可以一笔画的最大边数,考虑找欧拉路 当完全图的节点数为奇数个

时,奇度数点为0,存在欧拉路,最大经过变数就是完全图的边数,当节点

数为偶数时,所有节点为奇度数节点,考虑删边,删一条边最多可以把

两个节点变为欧度数点,所以删n/2 -1条边出现欧拉路

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
long long t;
int main(){
cin>>t;
int n;
while(t--){
cin>>n;
if(n&1){
cout<<1ll*n*(n-1)/2<<endl;
}
else{
cout<<(1ll*n*(n-1)/2)-(1ll*n/2-1)<<endl;
}
}
return 0;
}
版权声明
本文为[折翼的小鸟先生]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/rpup/p/13838061.html