学步园

250p: 直接暴力搜出所有情况。。。

500p:

题意：

有n支队伍进行积分制联赛，每两支队伍可以相互比赛任意次（包括0次），赢得队伍得w分，输的不得分，平局各得d分，现在给你一个积分榜，问最小需要多少场次能达到这个积分榜，如果不能达到，返回-1。

解题思路：

对于一个积分f，有w x + d y = f,根据扩展欧几里得，对于所有的积分都能求出最小的x，因为y = (y0*f/gcd - d/gcd *t)，对y排个序，y0, y1, y2, y3..., ，所有的y的和如果是奇数，方案肯定不可行，如果是偶数，要确保最大的数不大于其他所有数的和。

250p:

/* **********************************************
Author      : JayYe
Created Time: 2013-8-13 9:15:42
File Name   : final.cpp
*********************************************** */

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <sstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;

//typedef __int64 LL;
typedef long long LL;
class TheBasketballDivOne { 
    public: 
    int find(int n, int m) ;
    
 
}; 

int ans, vis[11], a[11];
bool mp[111111];

void dfs(int x, int y, int m, int n) {
    int i;
    if(x == n) {
        for(i = 1;i <= n; i++) a[i] = vis[i];
        sort(a+1, a+n+1);
        if(a[n] == m) {
            int sum = 0;
            for(i = 1;i <= n; i++)  sum = sum*10+a[i];
            if(!mp[sum]) {
                mp[sum] = 1;ans++;
            }
        }
        return ;
    }
    if(y > n)   {
        dfs(x+1, x+2, m, n); return ;
    }
    vis[x] += 2;
    dfs(x, y+1, m, n);
    vis[x] --;
    vis[y] ++;
    dfs(x, y+1, m, n);
    vis[x] --;
    vis[y] ++;
    dfs(x, y+1, m, n);
    vis[y] -= 2;
}

int TheBasketballDivOne::find(int n, int m) {
    ans = 0;
    memset(vis, 0, sizeof(vis));
    memset(mp, 0, sizeof(mp));
    dfs(1, 2, m, n);
    return ans;
}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

500p:

/* **********************************************
Author      : JayYe
Created Time: 2013-8-13 15:22:44
File Name   : final.cpp
*********************************************** */

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <sstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;

class TheTournamentDivOne { 
    public: 
    int find(vector <int> points, int w, int d) ;
    
 
}; 

int exgcd(int a, int b, int &x ,int &y) {
    if(b == 0) {
        x = 1; y = 0;
        return a;
    }
    int ans = exgcd(b, a%b, y, x);
    y -= a/b*x;
    return ans;
}

int a[111111];

struct PP {
    int val;
    PP() {}
    PP(int val) : val(val) {}
    bool operator < (const PP &a) const  {
        return val < a.val;
    }
}cur;

priority_queue<PP> q;
int TheTournamentDivOne::find(vector <int> ps, int w, int d) {
    while(!q.empty()) q.pop();
    int x, y, i;
    int g = exgcd(w, d, x, y);
    int extr = 0;
    int sum = 0;
    for(i = 0;i < ps.size(); i++) {
        if(ps[i]%g != 0)    return -1;
        int xx = x*ps[i]/g;
        xx = (xx%(d/g) + d/g)%(d/g);
        int yy = (ps[i] - w*xx)/d;
        if(yy < 0)  return -1;
        sum += yy;
        extr += xx;
        cur = PP(yy);
        q.push( cur );
    //    printf("%d %d %d\n", ps[i], xx, yy);
    }
    int ret = -1;
  //  printf("sum = %d extr = %d\n", sum, extr);
    while(!q.empty()) {
        cur = q.top(); q.pop();
    //    printf("cur = %d\n", cur);
        int val = cur.val;
        if(sum %2 ==0 && val <= sum/2) {
            if(ret == -1)   ret = sum/2 + extr;
            else if(ret > sum/2+extr)
                ret = sum/2 + extr;
        }
        if(val >= w/g) {
            cur.val = val - w/g;
            extr += d/g;
            sum -= w/g;
            q.push(cur);
        }
        else    break;
    }
    return ret;
}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor