APIO10A – spoj

Đề bài: http://www.spoj.com/problems/APIO10A/


Cho 1 dãy N số nguyên. Một hàm số bậc 2 : f(x) = a * x ^ 2 + b * x + c. Phân dãy trên thành các đoạn liên tiếp sao cho tổng các hàm f trên các dãy là lớn nhất (giá trị f của 1 dãy là f(x) với x là tổng của dãy đó).

Input format :

  • Dòng đầu là số test case T
  • Mỗi test case gồm 3 dòng :
    • Dòng đầu là số nguyên dương N – số phần tử của dãy.
    • Dòng 2 là 3 số nguyên a, b, c.
    • Dòng còn lại gồm n số x1, x2, …, xn là n phần tử của dãy.

Output format :

  • Mỗi test case gồm 1 dòng, là kết quả của bài toán.

Giới hạn :

T<=3

n ≤ 1, 000, 000,

−5 ≤ a ≤ −1

b <= 10,000,000

c <= 10,000,000

1 ≤ xi ≤ 100.

Thuật toán:


Gọi f(x) = a * x ^ 2 + b * x + c

Thuật O(n^2):

Gọi dp(i) là chi phí lớn nhất khi phân hoạch đoạn từ 1 -> i.

sum(i) là tổng các phần tử từ 1 -> i.

dp(i) = max(dp(j) + f(sum(i) – sum(j)) (1 <= i <= n; 0 <= j < i)

 

Thuật O(n): dùng Convex Hull Trick

dp(i) = max(dp(j) + f(sum(i) – sum(j)) (1 <= i <= n; 0 <= j < i)

⇔ dp(i) = dp(j) + a * (sum(i) – sum(j))^ 2 + b * (sum(i) – sum(j)) + c

⇔ dp(i) = (a * sum(i) ^ 2 + b * sum(i) + c) + (-2 * a * sum(i) * sum(j)) + a * sum(j) ^ 2 – b * sum(j) ^ 2

Đặt A = -2 * a * sum(j), X = sum(i), B = a * sum(j) ^ 2 – b * sum(j) ^ 2

⇔ ta được đường thẳng y = A * X + B.

Vì mảng sum tăng dần -> ta có thể dùng two-pointer để giảm đpt xuống O(n)

Code:


#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e6 + 10;
 
class ConvexHull {
private:
    int head, tail;
    long long A[N], B[N];
public:
    void init() { head = tail = 0; }
    bool bad(int l1, int l2, int l3) {
        return (long double) (B[l3] - B[l1]) / (A[l1] - A[l3]) < (long double) (B[l2] - B[l1]) / (A[l1] - A[l2]);
    }
    void add(long long a, long long b) {
        A[tail] = a; B[tail++] = b;
        while (tail > 2 && bad(tail - 3, tail - 2, tail - 1)) {
            A[tail - 2] = A[tail - 1];
            B[tail - 2] = B[tail - 1];
            tail--;
        }
    }
    long long query(long long x) {
        if (head >= tail) head = tail - 1;
        while (head < tail - 1
               && A[head + 1] * x + B[head + 1] >= A[head] * x + B[head]) head++;
        return A[head] * x + B[head];
    }
} hull;
 
int n, a, b, c;
long long sum[N];
 
long long f(long long x) { return a * x * x + b * x + c; }
 
void load() {
    scanf("%d%d%d%d", &n, &a, &b, &c);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", sum + i);
        sum[i] += sum[i - 1];
    }
}
 
void process() {
    hull.init();
    long long cost = f(sum[1]);
    hull.add(-2 * a * sum[1], cost + a * sum[1] * sum[1] - b * sum[1]);
 
    for (int i = 2; i <= n; ++i) {
        cost = f(sum[i]) + max(0ll, hull.query(sum[i]));
        hull.add(-2 * a * sum[i], cost + a * sum[i] * sum[i] - b * sum[i]);
    }
    printf("%lld\n", cost);
}
 
int main() {
  //  freopen("input.in", "r", stdin);
 //   freopen("output.out", "w", stdout);
 
    int test; scanf("%d", &test);
    while (test--) {
        load();
        process();
    }
 
    return 0;
}

C11TRCNT – spoj

Đề bài:

Thuật toán:

  • Bài toán đưa về: kiểm tra 3 điểm có thẳng hàng hay không

Code:

const   fi='';
        fo='';
type    dinh=record
                x,y:longint;
                end;
var     i,j,k:integer;
        d,max,min:int64;
        kq,n:byte;
        p:array[1..200] of dinh;
        dem:array[1..200] of int64;
        f:text;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n);
    for i:=1 to n do readln(f,p[i].x,p[i].y);
    close(f);
end;
function kt(x1,y1,x2,y2,x3,y3:longint):boolean;
begin
        if x1*y3-x1*y2+x2*y1-x2*y3+x3*y2-x3*y1=0
        then exit(false) else exit(true);
end;
procedure xuly;
begin
    d:=0; min:=1000000000000000;
    for i:=1 to n do
    begin
        for j:=1 to n do
        if i<>j then
                for k:=1 to n do
                if (i<>k) and (j<>k) then
                                if kt(p[i].x,p[i].y,p[j].x,p[j].y,p[k].x,p[k].y)  then
                                begin
                                        inc(dem[i]);
                                        if (i<j) and (k>j) then inc(d);
                                end;
        if dem[i]<min then begin min:=dem[i]; kq:=i; end;
    end;
end;
procedure inkq;
begin
    assign(f,fo);
    rewrite(f);
    writeln(f,d,' ',kq);
    close(f);
end;
begin
    nhap;
    xuly;
    inkq;
end.

QBPOINT – SPOJ

Đề bài: http://vn.spoj.com/problems/QBPOINT/

Thuật toán:

  • Duyệt n điểm, với mỗi điểm i ta:
    • Duyệt các điểm j <> i rồi tính vector ij lưu lại vào 1 mảng ss[]
    • Sort lại mảng ss[]
    • 3 điểm i,j,k thẳng hàng nếu vector ij = vector ik

Code:

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;
 
using namespace std;
int n,x[2001],y[2001];
long long res;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("tripoint.inp", "r", stdin);
    freopen("tripoint.out", "w", stdout);
    #endif //
    cin>>n;
    FORE(i,1,n) cin>>x[i]>>y[i];
    FORE(i,1,n)
    {
        vector <double> ss; int cc=0;
        FORE(j,1,n)
        if (x[j]!=x[i])
            ss.push_back((double) (y[j]-y[i])/(x[j]-x[i]));
        else ++cc;
        sort(ss.begin(),ss.end());
        int sl=(cc-2)*(cc-1);
        if (ss.size())
        {
            int dem=1;
            FORE(j,1,ss.size()-1)
            if (ss[j]==ss[j-1]) ++dem;
            else
            {
                sl+=dem*(dem-1);
                dem=1;
            }
            sl+=dem*(dem-1);
        }
        res+=sl;
    }
    cout<<res/6;
    return 0;
}

TFIELD – SPOJ

Đề bài:


Thuật toán:


    Ngay từ đầu đề bài đã đề cập đến phần hình học.

    – Ta cần biết vị trí của các khoang theo đúng thứ tự (ví dụ từ trong ra ngoài). Ta có nhận xét là đa giác của khoang trong luôn có diện tích nhỏ hơn đa giác của khoang ngoài. Vì thế, ta chỉ cần sắp xếp các đa giác theo diện tích của chúng. Công thức tính diện tích 1 đa giác bất kì:

    S=1/2 ∑(x[i]-x[i+1])*(y[i]+y[i+1]) (với i=[1..n], quy ước điểm thứ n+1 chính là điểm 1).

    – Sau khi sắp xếp, ta có thể tính được diện tích từng khoang (diện tích khoang thứ i=s[i]-s[i-1]).

    – Bài toán đặt ra bây giờ là tìm đoạn khoang có diện tích lớn nhất nằm giữa 2 đa giác. Ta dùng đếm phân phối để giải quyết. Đầu tiên, ta cố định điểm trái của vùng cần xét O(m). Từ điểm này, tìm điểm phải nhất có số khoang cần đổi màu không quá k (nói cách khác là c-st<=k, với c là tổng số khoang của vùng, st là số khoang cùng màu của vùng) O(m). – Kết quả bài toán là kết quả tối ưu trong các giá trị đã xét. Độ phức tạp ~O(m^2).

Code:


uses    math;
const   fi='';
        fo='';
        maxn=1000+3;
type
        dinh    =record
                        x,y:longint;
                        end;
        arr1    =array[1..maxn] of dinh;
var     a       :array[1..maxn,1..maxn] of dinh;
        s       :array[1..maxn] of int64;
        i,j,n,m,k       :longint;
        c       :array[1..maxn] of longint;
        sodinh  :array[1..maxn] of longint;
        khoang  :array[1..maxn] of int64;
        res     :int64;
        dem     :array[1..maxn] of longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        read(m,k);
        for i:=1 to m do
                begin
                        read(sodinh[i],c[i]);
                        for j:=1 to sodinh[i] do read(a[i,j].x,a[i,j].y);
                end;
        close(input);
end;
procedure swap(var x,y:int64);
var     tg      :int64;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure swap2(var x,y:longint);
var     tg      :longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r:longint);
var     x:extended;
        i,j:longint;
begin
        i:=l;j:=r;
        x:=s[(l+r) div 2];
        repeat
                while x<s[i] do inc(i);
                while x>s[j] do dec(j);
                if i<=j then
                        begin
                                swap(s[i],s[j]);
                                swap2(c[i],c[j]);
                                inc(i);dec(j);
                        end;
        until i>j;
        if i<r then qs(i,r);
        if j>l then qs(l,j);
end;
function dientich(p:arr1;n:longint):int64;
var     i       :longint;
begin
        dientich := 0;
        p[n+1] := p[1];
        for i:=1 to n do
                dientich:= dientich + int64( (p[i+1].x-p[i].x) )*(p[i+1].y+p[i].y);
        dientich:= abs(dientich){/2};
end;
procedure tinhs;
var     i:longint;
begin
        for i:=1 to m do
                s[i]:=dientich(a[i],sodinh[i]);
end;
procedure chuanbi;
begin
        sodinh[n+1]:=4;
        a[n+1,1].x:=1;
        a[n+1,1].y:=1;
        a[n+1,2].x:=1;
        a[n+1,2].y:=1;
        a[n+1,3].x:=1;
        a[n+1,3].y:=1;
        a[n+1,4].x:=1;
        a[n+1,4].y:=1;
end;
procedure process;
var     maxc,sokhoang        :longint;
        dientich        :int64;
begin
        tinhs;
        s[m+1]:=0;
        qs(1,m+1);
        for i:=1 to m do
                khoang[i]:=s[i]-s[i+1];
        for i:=1 to m do
                begin
                        fillchar(dem,sizeof(dem),0); dientich := 0; maxc :=1; sokhoang :=1;
                        inc(dem[c[i]]);
                        dientich := dientich + khoang[i]; if dientich>res then res := dientich;
                        for j := i+1 to m do
                        begin
                                inc(dem[c[j]]); inc(sokhoang);
                                maxc := max(maxc,dem[c[j]]);
                                if sokhoang-maxc<=k then
                                        begin
                                                dientich := dientich + khoang[j];
                                                if dientich>res then res := dientich;
                                        end else break;
                        end;
                end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        write(res{:0:1} div 2);
        if odd(res) then
                write('.5') else write('.0');
        close(output);
end;
begin
        enter;
        process;
        print;
end.
#include<bits/stdc++.h>
#define db double
#define fs first
#define sc second
#define maxn 1005
#define ll long long
using namespace std;
int n,k,d[maxn],sum[maxn];
struct data
{
            ll s;
            int c;
};
data a[maxn];
ll res;
typedef pair<int,int> II;
II c[maxn][maxn];
void tinh(int k)
{
            d[k]++;
            c[k][d[k]].fs=c[k][1].fs;
            c[k][d[k]].sc=c[k][1].sc;
            for (int i=2; i<=d[k]; ++i)
            {
                        a[k].s+=((ll)(c[k][i].fs-c[k][i-1].fs)*(c[k][i].sc+c[k][i-1].sc));
            }
            if (a[k].s<0) a[k].s=-a[k].s;
}
bool cmp(const data &a,const data &b)
{
            return a.s<b.s;
}
int main()
{
            //freopen("TFIELD.inp","r",stdin);
            ios::sync_with_stdio(0);
            cin.tie(0);
            cout.tie(0);
            cin>>n>>k;
            for (int i=1; i<=n; ++i)
            {
                        cin>>d[i]>>a[i].c;
                        for (int j=1; j<=d[i]; ++j)
                                    cin>>c[i][j].fs>>c[i][j].sc;
            }
            for (int i=1; i<=n; ++i) tinh(i);
            sort(a+1,a+n+1,cmp);
            sum[n+1]=1000000000;
            for (int i=1; i<=n; ++i)
            {
                        sum[0]=0;
                        for (int j=1; j<=n; ++j)
                                    if (a[j].c!=i) sum[j]=sum[j-1]+1;
                                    else sum[j]=sum[j-1];
                        int r=1;
                        for (int l=1;l<=n;++l)
                        {
                                    while(sum[r+1]-sum[l-1]<=k)
                                                ++r;
                                    res=max(res,a[r].s-a[l-1].s);
                        }
            }
            cout<<res/2;
            if (res%2) cout<<".5";
            else cout<<".0";
            return 0;
}