C++Fraction - Trại hè hùng vương lần thứ XIII (tuyên quang 2017)

Trung tâm bồi dưỡng tài năng đã được thành lập, thầy Hòa là một giáo viên giỏi của trường CTQ đã được mời tham gia bồi dưỡng cho các tài năng. Một bài toán thú vị mà thầy Hòa giao cho các tài năng như sau:
Cho phân số:

hãy tìm dãy chỉ số sao cho

Các tài năng rất hào hứng và nhanh chóng tìm được hướng giải quyết cho bài toán. Thầy Hòa tiếp tục mở rộng bài toán, hãy tìm cách đảo lại một số phân số nếu muốn (phân số a/b đảo lại thành phân số b/a), sau đó lại tìm dãy chỉ số thỏa mãn đề bài mà K lớn nhất có thể.

Yêu cầu:

Cho n phân số và số nguyên w, trong đó w=0 nghĩa là không được phép đảo bất kỳ một phân số nào (bài toán ban đầu) hoặc w=1 nếu được phép đảo phân số (bài toán mở rộng), hãy đưa ra giá trị k lớn nhất có thể.

Dữ liệu vào:

- Dòng đầu ghi hai số nguyên n, w
- Dòng thứ i (i = 1,2,3,...,n) trong n dòng tiếp theo chứa hai số nguyên dương ai bi có giá trị không vượt quá 10^9 lần lượt là tử số và mẫu số của phân số thứ .

Dữ liệu ra:

Ghi ra một số nguyên là giá trị k lớn nhất tìm được.

VD:

Dữ liệu vào:

4 0
5 1
1 3
3 2
1 2

Dữ liệu ra:

2

Dữ liệu vào:

4 1
5 1
1 3
3 2
1 2

Dữ liệu ra:

4

Ràng buộc:

- Có 20% số test ứng với 20% số điểm của bài có n<=10 ; w=0
- Có 20% số test khác ứng với 20% số điểm của bài có n<=10 ; w=1
- Có 20% số test khác ứng với 20% số điểm của bài có n<=100 ; w=0
- Có 20% số test khác ứng với 20% số điểm của bài có n<=100 ; w=1
- Có 10% số test khác ứng với 10% số điểm của bài có n<=10^5 ; w=0
- Có 10% số test còn lại ứng với 10% số điểm của bài có n<=10^5 ; w=1

Hướng dẫn:

Thuât full đối với w = 0

Đối với w = 0 thì đơn giản rồi, khi đó ta đưa về bài dãy con không giảm dài nhất. Các bạn xem hướng dẫn chi tiết ở đây => QBMSEQ

Thuât n<=100 đối với w = 1

Để giải được với n=10^5 bạn cần tìm được công thức quy hoạch động. Công thức: dp[w][i] = max(dp[w][j]) trong đó w từ 0 -> 1, i từ 1 -> n, j từ 1 -> i.
Từ đó ta có thuật O(n^2)

Thuât n<=10^5 đối với w = 1

Ta thấy rằng dp[w][i] = max(dp[w][j]). Như vậy ta chỉ cần lấy max j từ 1 -> i, vì vậy ta dùng cây IT để giải quyết vấn đề trong O(logn)
Tổng thời gian là O(nlog(n))

Code mẫu:

// _____ _ _
// / ____| | | (_)
// | (___ ___ _ __ __| | ___ _ __ ______ _ _
// \___ \ / _ \| '_ \ / _ |/ _ \ '_ \ |_ / _ | |
// ____) | (_) | | | | | (_| | __/ |_) | / / (_| | |
// |_____/ \___/|_| |_| \__,_|\___| .__/ /___\__,_|_|
// | |
// |_|

#include <bits/stdc++.h>
#define nmax 100005
#define oo 10000000007
#define mod 1000000007
#define reset(x) memset(x, 0, sizeof x)
#define F first
#define S second
#define sonin cin
#define sonout cout
#define debug(x) cout << "Loli -> " << #x << " : " << x << "\n"
#define debugAry(x, a, b, y) for(int y = a; y<=b; y++) cout << #x << "[" << y << "]" << " -> " << x[y] << "\n"
#define filename ""
#define fileNX freopen(filename".inp", "r", stdin); freopen(filename".out", "w", stdout);
#define fileN freopen(filename".inp", "r", stdin);
#define fileX freopen(filename".out", "w", stdout);
#define toiuuhoa ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define SZ(a) (int) a.size()
#define FOU(x,a,b) for (lli x=a;x<=b;x++)
#define FOD(x,a,b) for (lli x=a;x>=b;x--)
#define FOA(a,b) for(auto &a:b)
#define ALLvec(a) a.begin(),a.end()
#define REU(x,a,b) for (lli x=a;x<b;x++)
#define RED(x,a,b) for (lli x=a;x>b;x--)
#define AutoCinAry(a,b,x) for(int a = 1; a<=b; a++) cin >> x[i];
#define dembit1(x) __builtin_popcount(x)
#define bit(x,i) ((x>>(i-1))&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))
#define EL cout << "\n";
#define EX exit(0);
#define Ary(x, i, j, a) x[(i - 1) a + j]
#define epsinon 1e-8
#define Son_onii_chan main
#define times double stime = clock();
#define gettime cerr << "Time executed: " << (clock() - stime) / CLOCKS_PER_SEC 1000 << "ms.\n";
using namespace std;
typedef long long lli;
typedef long double ldo;
typedef double dou;
typedef vector<lli> vi;
typedef vector<vi> vvi;
typedef pair<lli, lli> pii;
typedef vector<pii> vpi;
typedef deque<lli> dqll;

lli n, w, result;
dou ary[nmax], sary[nmax], saryf[nmax];
dou b[nmax];

void sub1(){
b[0] = -oo;
FOU(i,1,n)
b[i] = oo;
FOU(i,1,n){
lli k = lower_bound(b, b + n, ary[i]) - b;
b[k] = ary[i];
result = max(result, k);
}
}

lli dp[2];
struct IT {
lli n;
vi it;
IT(lli n) : n(n){
it = vi(4n, 0);
}
void update(lli i, lli l, lli r, lli u, lli detal){
if(l == r){
it[i] = max(it[i], detal);
return;
}
lli mid = (l+r)/2, li = i2;
if(u>= l && u <= mid){
update(li, l, mid, u, detal);
}
if(u >= mid + 1 && u <= r){
update(li + 1, mid + 1, r, u, detal);
}
it[i] = max(it[li], it[li + 1]);
}
lli query(lli i, lli l, lli r, lli u, lli v){
if(l > v || r < u) return -oo;
if(l>=u && r <= v) return it[i];
lli mid = (l+r)/2, li = i*2;
return max(query(li, l, mid, u, v), query(li + 1, mid + 1, r, u, v));
}
};
lli FindWhere(dou xx, lli tpey){
lli res = 0;
if(tpey == 0)
res = lower_bound(sary + 1, sary + 1 + n, xx) - sary;
else
res = lower_bound(saryf + 1, saryf + 1 + n, xx) - saryf;
return res;
}
void sub2(){
IT gg0(n);
IT gg1(n);
gg0.update(1, 1, n, FindWhere(ary[1], 0), 1);
gg1.update(1, 1, n, FindWhere(1.0/ary[1], 1), 1);
result = 1;
FOU(i, 2, n){
dp[0] = max(gg0.query(1,1,n,1,FindWhere(ary[i], 0)-1), gg1.query(1,1,n,1,FindWhere(ary[i], 1)-1)) + 1;
dp[1] = max(gg0.query(1,1,n,1,FindWhere(1.0/ary[i], 0)-1), gg1.query(1,1,n,1,FindWhere(1.0/ary[i], 1)-1)) + 1;
gg0.update(1, 1, n, FindWhere(ary[i], 0), dp[0]);
gg1.update(1, 1, n, FindWhere(1.0/ary[i], 1), dp[1]);
result = max(result, max(dp[0], dp[1]));
}
}
void InputType(){
FOU(i,1,n){
lli ggk;
sonin >> ary[i] >> ggk;
ary[i] /= ggk;
sary[i] = ary[i];
saryf[i] = 1.0/ary[i];
}
sort(sary + 1, sary + n + 1);
sort(saryf + 1, saryf + n + 1);
}
int Son_onii_chan(){
//fileNX
toiuuhoa
sonin >> n >> w;
InputType();
ary[n+1] = oo;
result = 0;
if(w == 0)
sub1();
else
sub2();
sonout << result;
return 0;
}

Chấm code: csloj.ddns.net/problem/808