Editorial for Bedao Mini Contest 12 - MUSCULAR
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Ta biết được rằng khi chọn các số trong dãy ~a~ cùng lúc thì ta chỉ được chọn nhiều nhất ~3~ số. Bên cạnh đó, với giới hạn lớn nhất là ~n = 300~, ta có thể duyệt chọn cùng lúc ~3~ số bằng ~3~ vòng lặp lồng nhau.
Sau khi lần lượt thu được các giá trị từ việc chọn ~1~ số, chọn ~2~ số cùng lúc và chọn ~3~ số cùng lúc, ta sẽ lọc đi các giá trị trùng nhau và số lượng các giá trị còn lại sẽ là đáp án.
Độ phức tạp: ~O(n^3)~
Code mẫu
#include <iostream> #include <stdio.h> #include <vector> #include <cmath> #include <math.h> #include <map> #include <algorithm> #include <set> #include <bitset> #include <queue> #include <cstring> #include <stack> #include <iomanip> #include <assert.h> #define BIT(x,pos) (((x)>>(pos)) & 1LL) #define _(x) (1LL<<(x)) #define bitCnt(x) __builtin_popcountll(x) #define turnOn(x,pos) ((x) = (_(pos))) #define turnOff(x,pos) ((x) &= ~(_(pos))) #define flipBit(x,pos) ((x) ^= (_(pos))) #define lowBit(x) ((x) & (-x)) #define turnAll(x) (_(x)-1LL) #define name "test" #define nameTask "" #define fastIO ios::sync_with_stdio(false); cin.tie(0); using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<int,ll> pil; typedef pair<ll, int> pli; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; const int N = 300; int a[N+9]; int n,W; int main() { if (fopen(name".INP","r")) freopen(name".INP","r",stdin), freopen(name".OUT","w",stdout); fastIO cin>>n>>W; vector<int> v; for (int i = 1;i <= n; ++i) { cin>>a[i]; if (a[i] <= W) v.push_back(a[i]); } if (n >= 2) { for (int i = 1;i <= n; ++i) for (int j = i + 1; j <= n; ++j) if (a[i] + a[j] <= W) v.push_back(a[i] + a[j]); } if (n >= 3) { for (int i = 1;i <= n; ++i) for (int j = i + 1; j <= n; ++j) for (int k = j + 1; k <= n; ++k) if (a[i] + a[j] + a[k] <= W) v.push_back(a[i] + a[j] + a[k]); } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); cout<<(int)v.size(); }
Comments