CodeForces 367 C Sereja and the Arrangement of Numbers 欧拉回路

题解：

ummm。

在一副图中，如果全部点的度数是偶数/只有2个点是奇数，则能一笔画。

考虑图的点数k为奇数的时候，那么每个点的度数都是偶数点，所以就是可以一笔画，答案为 1 +k * (i - kll) / 2;

k为偶数的时候，所有的点是奇数点，我们保留2个点是奇数点，将其他的点改为偶数点，就可以一笔画了。 1 +k * (i - kll) / 2 + k/2 - 1.

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 1e5 + ;

int n, m;

int a[N], b[N];

LL dp[N];

int main(){

    scanf("%d%d", &n, &m);

    for(int i = ; i <= m; ++i){

        scanf("%d%d", &a[i], &b[i]);

        if(i&) dp[i] =  + i * (i - 1ll) / ;

        else dp[i] =  + i * (i-1ll)/ + i/ - ;

    }

    int k = m;

    while(dp[k] > n) --k;

    sort(b+, b++m, greater<int>());

    LL ans = ;

    for(int i = ; i <= k; ++i)

        ans += b[i];

    cout << ans << endl;

    return ;

}