Hướng dẫn giải của Trại hè Đà Lạt 2020 - Thi đấu vòng tròn
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
Biểu diễn quan hệ thắng thua bằng đồ thị: Mỗi đội là một đỉnh, có cung nối từ ~A~ tới ~B~ khi đội ~A~ thắng đội ~B~. Ta thấy tổng số cung vào và cung ra của mỗi đỉnh đều là ~n-1~. (do mỗi đội chỉ thi đấu ~1~ lần với ~n-1~ đội còn lại)
Nhận xét: Để cực đại số lượng TCIRCLE thì ta phải cực tiểu số chênh lệch cung vào và cung ra của mỗi đỉnh. Ta chia ~2~ trường hợp như sau:
Trường hợp 1: ~n~ lẻ
Khi đó ta có thể cho mỗi đỉnh có ~\frac{n-1}{2}~ cung vào và ~\frac{n-1}{2}~ cung ra.
Số TCIRCLE = số cách chọn ~3~ đỉnh có mối quan hệ tcircle.
Ta thấy việc tính trực tiếp quá khó, nên ta tính phần phủ định
Số TCIRCLE = số cách chọn ~3~ đỉnh bất kì - số cách chọn ~3~ đỉnh không có mối quan hệ tcircle.
Ta thấy với mọi cách chọn ~3~ đỉnh mà không có mỗi quan hệ tcircle, luôn tồn tại một đỉnh có ~2~ cung ra (và đồng thời có một đỉnh có ~2~ cung vào). Vì vậy ta sẽ tính số cách chọn ~3~ đỉnh mà trong đó có ~1~ đỉnh có ~2~ cung ra, vì mỗi đỉnh có ~\frac{n-1}{2}~ cung ra nên mỗi đỉnh có ~{\frac{n-1}{2} \choose 2}~ (tổ hợp) cách chọn
Như vậy, số TCIRCLE = ~{n \choose 3} - n \times {\frac{n-1}{2} \choose 2}~.
Trường hợp 2: ~n~ chẵn
Vì ~n~ chẵn, nên có ~\frac{n}{2}~ đỉnh có số cung ra nhiều hơn ~1~ so với số cung vào, và có ~\frac{n}{2}~ đỉnh có số cung vào nhiều hơn ~1~ so với số cung ra. Đỉnh có số cung ra nhiều hơn thì có ~{\frac{n}{2} \choose 2}~ cách chọn. Đỉnh có số cung ra ít hơn thì có ~{\frac{n-1}{2} \choose 2}~ cách chọn.
Như vậy, số TCIRCLE = ~{n \choose 3} - \frac{n}{2} \times {\frac{n-1}{2} \choose 2} - \frac{n}{2} \times {\frac{n}{2} \choose 2}~.
Code tham khảo:
#include <bits/stdc++.h>
using namespace std;
/***Crazy Macros***/
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define reu(i,a,b) for(ll i = (a); i <= (b); ++i)
#define red(i,a,b) for(ll i = (a); i >= (b); --i)
typedef int64_t ll;
typedef deque<int> di;
typedef deque<ll> dll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef tuple<ll,ll,ll> iii;
const ll inf = 2e9;
/***Common Functions***/
ll inp() {ll x; cin >> x; return x;}
string inp_str() {string x; cin >> x; return x;}
ll sqr(ll n) {return n*n;}
ll power(ll a, ll b, ll mod = inf) {
ll res = 1; a %= mod;
for(ll i = b; i > 0; i /= 2) {
if (i % 2) res = (res*a) % mod;
a = (a*a) % mod;
} return res;
}
ll gcd(ll a, ll b) {
while (b > 0) {ll tmp = a % b; a = b; b = tmp;}
return a;
}
bool is_pal(string s) {return equal(all(s), s.rbegin());}
void fast_io() {ios::sync_with_stdio(0); cin.tie(0);}
void file_io(char *in, char *out) {
freopen(in, "r", stdin);
freopen(out, "w", stdout);
}
void print_bool(bool a) {
if (a) cout << "YES\n";
else cout << "NO\n";
}
/***Main Code***/
ll n;
void Input() {
cin >> n;
}
ll nCr(ll n, ll r) {
ll ans = 1;
reu(i, n-r+1, n) ans *= i;
reu(i, 1, r) ans /= i;
return ans;
}
void Solve() {
ll ans;
if (n%2) {
ans = nCr(n, 3) - n*nCr((n-1)/2, 2);
} else {
ans = nCr(n, 3) - n/2*nCr((n-1)/2, 2) - n/2*nCr(n/2, 2);
}
cout << ans;
}
int main()
{
fast_io();
// file_io("TCIRCLE.INP", "TCIRCLE.OUT");
Input(), Solve();
return 0;
}
Bình luận