2016年12月13日 星期二

ACM Dhaka regional 2015 J. The Hypnotic Spirals

/* 
    題目連結 
    
    有些麻煩要注意一些 case
    1.沒有點 的話 答案是 0
    2.有點 但沒射線 答案是 -1
    
    為了方便 我們把 v[0]+2*pi 再丟進去
    這是為了確保每個點的角度都能被 兩條射線的角度給夾住
    我們將 < v[0] 的 ang += 2*pi 也是為了同樣的目的

    接著是簡易的面積積分
    算完得到 func = a*a*x*x*x/6
    考慮比較普遍的情況 可以得到該點所在的面積
    是四個角度的 func 相加減
    而有些特殊情況 角度不會有四個
    觀察知依原本的解法 那些"不存在的角度" 會解出負的角度
    使這些負的東西的 func 為 0 即可解決
*/
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cassert>
#include <vector>
#include <queue>
#include <cmath>
#include <set>

using namespace std;

typedef long long ll;

double const pi = acos(-1.0);
double r[10001], ang[10001];

double a;

double func(double x)
{
    if ( x < 0 ) return 0;
    return a*a/6*x*x*x;
}

int main()
{
    int T;
    scanf("%d", &T);

    for (int Ti = 1; Ti <= T; Ti++) {
        scanf("%lf", &a);

        int n;
        scanf("%d", &n);

        vector<double> v;
        for (int ni = 0; ni < n; ni++) {
            double t;
            scanf("%lf", &t);
            v.push_back(t);
        }

        sort(v.begin(), v.end());
        if ( n ) v.push_back(v[0]+pi*2 );

        int m;
        scanf("%d", &m);

        for (int mi = 0; mi < m; mi++) {
            scanf("%lf %lf", &r[mi], &ang[mi]);
            if ( n && ang[mi] < v[0] ) ang[mi] += 2*pi;
        }

        printf("Spiral %d: ", Ti);

        set<double> s;

        if ( m == 0 ) {
            puts("0.0000 liters");
        } else if ( n == 0 ) {
            puts("-1");
        } else {
            double ans = 0;

            for (int mi = 0; mi < m; mi++) {
                int t = -1;
                for (int ni = 0; ni < n; ni++) {
                    if ( v[ni] < ang[mi] && ang[mi] < v[ni+1] ) {
                        t = ni;
                        break;
                    }
                }

                double p = floor((r[mi]/a-ang[mi])/pi/2);

                if ( s.find(p*2*pi+v[t]) == s.end() ) {
                    s.insert(p*2*pi+v[t]);

                    ans -= func(p*2*pi+v[t+1])-func(p*2*pi+v[t]);
                    ans += func((p+1)*2*pi+v[t+1])-func((p+1)*2*pi+v[t]);
                }
            }

            printf("%.4f liters\n", (double)ans/10);
        }
    }
}

2016年9月12日 星期一

ACM ICPC Singapore Regional 2015 Association for the Country of Mububa

/*
    題目連結

    感覺就很簡單的一題DP
    可是隊友一開始寫了個爛 greedy
    (就一直拿拿到 比前一個人拿得多就停止)

    這 greedy 是錯的
    因為考慮到你現在在發東西給第i個人
    你可能會希望讓第i-1個人多拿一點 讓第i個人少拿一點
    這樣你發給 第i+1以後的人 可能可以發得比較少

    Ex:
    5
    7 1 8 8 8 
    Ans:
    4

    所以呢 正確的做法是DP
    DP[i][j] 紀錄 最後一個人拿 第i~j箱的話
    最多可以讓多少人拿

    那轉移 就是 DP[i][j] = max(DP[k][i-1] for all k satisfy sum k to i-1 <= sum i to j)+1; 
    雖然說 這邊有個對於所有的 k 但是你這樣枚舉 k 是顯然會超時的
    注意到 滿足的 k 會是個區間 所以你可以事先算出個 min[i][j] 之類的東西
    再加上 二分搜就能過了

    因為這題是我想丟給隊友寫
    所以就附上周逸風格怪異 的 code
*/
#include <bits/stdc++.h>
using namespace std;
long long int dp[3005][3005];
long long int ar[3005];
long long int pf[3005];
long long int mx[3005][3005];
long long int sum(int l,int r){
    return pf[r+1]-pf[l];
    }
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&ar[i]),pf[i+1]=pf[i]+ar[i];
    long long int ans=0;
    for(int j=0;j<n;j++){
        for(int i=0;i<=j;i++){
            if(i==0)dp[i][j]=1;
            else{
                int l=0,r=i-1;
                while(l<=r){
                    int mid=(l+r)/2;
                    if(sum(i,j)>=sum(mid,i-1))
                        r=mid-1;
                    else
                        l=mid+1;
                    }
                //printf("%d %d\n",l,i-1);
                if(l!=i&&mx[l][i-1])
                    dp[i][j]=mx[l][i-1]+1;
                }
            //printf("$%d %d %d\n",i,j,dp[i][j]);
            ans=max(ans,dp[i][j]);
            }
        for(int i=j;i>=0;i--){
            mx[i][j]=dp[i][j];
            if(i!=j)
                mx[i][j]=max(mx[i][j],mx[i+1][j]);
            //printf("~%d %d %d\n",i,j,mx[i][j]);
            }
        }
    printf("%lld\n",ans);
    }

2016年9月11日 星期日

2010-2011 ACM-ICPC, NEERC, Moscow Subregional Contest D. Distance

/*
    題目連結不知道怎麼附上
    所以就稍微口述一下吧

    題目:
    你有 N <= 100000 個點
    有的點對之間會有帶正權的邊
    然後其中又有一些點 會是特殊點
    問你距離最近的特殊點對 彼此的距離距離為何?

    題解:
    這一題 一看就會聯想到最短路
    一開始隊友想到一個錯的做法
    對所有特殊點 同時開始做 Dijkstra
    直到pop 出來的點是特殊點就結束
    這其實有保證正確性 但複雜度是爛的
    只是特殊點 彼此距離很遠
    而離非特殊點們很近 就會炸開變成 O(VE*logV)

    不過這確實給了一點靈感
    最後我想想這其實就是 多起點的最短路/次短路
    (雖然說多了一點限制 比方說兩條路不能來自於同一點)
    然後 答案就會是 所有點的 最短路+次短路 當中值最小的
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> e;
#define t first
#define d second

typedef long long ll;

bool hv[100001];
int S[100001];

vector<e> v[100001];

ll ans = 2e18;
ll dis[100001]; int fa[100001]; int cnt[100001];

struct s{
    int f, t, d;
    s(int _a, int _b, int _c):f(_a), t(_b), d(_c){}

    bool operator<(const s &p)const{
        return d > p.d;
    }
};

priority_queue<s> pri;

int main()
{
    int N, K, L;
    scanf("%d %d %d", &N, &K, &L);

    for (int Ni = 0; Ni < N; Ni++) {
        int x;
        scanf("%d", &x);
        S[Ni] = x;

        if ( hv[x] ) {
            puts("0");
            return 0;
        } else hv[x] = true;
    }

    for (int Ki = 1; Ki <= K; Ki++)
        dis[Ki] = 2e18;

    for (int Li = 0; Li < L; Li++) {
        int b, c, d;
        scanf("%d %d %d", &b, &c, &d);

        v[b].emplace_back(c, d);
        v[c].emplace_back(b, d);
    }

    for (int Ni = 0; Ni < N; Ni++)
        pri.emplace(S[Ni], S[Ni], 0);

    while ( !pri.empty() ) {
        s p = pri.top();
        pri.pop();

        int t = p.t, f = p.f, d = p.d;

        if ( f != t && f != fa[t] ) ans = min(ans, dis[t]+p.d);

        if ( fa[t] == f ) continue;

        if ( cnt[t] < 2 ) {

            if ( fa[t] == 0 ) {
                fa[t] = f;
                dis[t] = d;
            }

            for (auto x : v[t]) {
                pri.emplace(f, x.t, d+x.d);
            }

            cnt[t]++;
        }
    }

    printf("%lld\n", ans*3);
}

2016年8月30日 星期二

Codeforces 128B. String

/*
    題目連結

    字串題?! (誤
    我不太擅長字串啊(笑

    看到想拿來練習一下 Suffix Array
    但寫到一半 發現其實自己不會用SA來解這題
    外加 k 小的異常 就決定重新想

    注意到 p 的字典序一定比 p+q 小
    所以 s[i:i] 會比 s[i:i+j] 小
    於是想到一個做法 那就是把所有 s[i:i] push 到 priority_queue (pq) 裡
    每次 pop 出一個 s[i:j] 就把 s[i:j+1] (如果存在)再 push 進去
    那第k個 pop出來得即為答案

    接著來算算複雜度 設字串長為L
    O(k*log(L)*平均字串比大小時間)
    字串比大小時間 最差為L  乍看算出來 > 10^10
    似乎不可行 但考慮到多種情況發現 並不會那麼差
    傳上去 0.1s AC 毫無時間壓力

    另外注意到 
    我並沒有把字串真的丟到 pq裡而是放在外頭
    不然要構造出那些字串 就需要 L^2 的時間
    雖然有人這樣還是過了 OAO
    但我這樣比較快 XD
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

char c[100001];
int cn;

string s[100001];
int ed[100001];

struct Cmp{
    bool operator()(int a, int b) {
        return s[a] > s[b];
    }
};

typedef priority_queue<int, vector<int>, Cmp> pq;
pq pri;

int main() {

    while ( scanf("%s", c) != EOF ) {
        cn = strlen(c);
        pq().swap(pri);

        for (int ci = 0; ci < cn; ci++) {
            s[ci] = c[ci];
            ed[ci] = ci;
            pri.push(ci);
        }

        int k;
        scanf("%d", &k);

        for (int ki = 0; ki < k; ki++) {
            if ( pri.empty() ) {
                puts("No such line.");
                break;
            }

            int t = pri.top();
            pri.pop();

            if ( ki+1 == k ) puts(s[t].c_str() );

            ed[t]++;
            if ( ed[t] != cn ) {
                s[t].push_back(c[ed[t] ] );
                pri.push(t);
            }
        }
    }
}

2016年8月9日 星期二

樹鍊剖分模板

/*
    架構來自卦長的模板庫
*/
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int MAXN = 100001;
const int MAXM = 100001;
const int INF = 1e9;

typedef pair<int, int> E;
#define t first
#define d second

vector<E> v[MAXN], u[MAXN];
int sz[MAXN], max_son[MAXN], dep[MAXN], pa[MAXN];
int link_top[MAXN], link[MAXN], cnt;

void find_max_son(int x, int par) {
    sz[x] = 1;
    max_son[x] = -1;

    for (E e: v[x]) {
        int t = e.t;
        if ( t == par ) continue;

        dep[t] = dep[x]+1;
        pa[t] = x;
        find_max_son(t, x);
        sz[x] += sz[t];

        if ( max_son[x] == -1 || sz[t] > sz[max_son[x] ] )
            max_son[x] = t;
    }
}

void build_link(int x, int par, int top) {
    link[x] = ++cnt;
    link_top[x] = top;

    if (max_son[x] == -1) return;
    build_link(max_son[x], x, top);

    for (E e: v[x]) {
        int t = e.t;
        if ( t == max_son[x] || t == par ) continue;
        build_link(t, x, t);
    }
}

inline int find_lca(int a, int b) {
    int ta = link_top[a], tb = link_top[b];

    while (ta != tb) {
        if ( dep[ta] < dep[tb] ) {
            swap(ta, tb);
            swap(a, b);
        }

        ta = link_top[a=pa[ta]];
    }

    return dep[a]<dep[b]?a:b;
}

struct Node {
    Node *l, *r;
    int num;

    Node():l(NULL),r(NULL),num(INF){}
};

Node mem[MAXN*2]; int m;

Node *get_node() { return &(mem[m++] = Node()); }

Node *root;

Node *build(int L, int R) {
    Node *O = get_node();

    if ( L+1 != R ) {
        O->l = build(L, (L+R)/2);
        O->r = build((L+R)/2, R);
    }

    return O;
}

void add(Node *O, int L, int R, int A, int B, int x) {
    if ( B <= L || R <= A ) return;
    else if ( A <= L && R <= B ) O->num = min(O->num, x);
    else {
        add(O->l, L, (L+R)/2, A, B, x);
        add(O->r, (L+R)/2, R, A, B, x);
    }
}

int N, M;

inline void process(int a, int b, int x) {
    int ta = link_top[a], tb = link_top[b];

    while (ta != tb) {
        if ( dep[ta] < dep[tb] ) {
            swap(ta, tb);
            swap(a, b);
        }

        add(root, 1, N+1, link[ta], link[a]+1, x);
        ta = link_top[a=pa[ta]];
    }

    if ( dep[a] > dep[b] ) swap(a, b);

    add(root, 1, N+1, link[a]+1, link[b]+1, x);
}

int num[MAXN];

void DFS(int x, int par) {
    for (E e: v[x]) {
        int t = e.t, d = e.d;
        if ( t == par ) continue;
        num[t] = d;
        DFS(t, x);
    }
}

int ans;

void cal(Node *O, int L, int R, int x) {

    x = min(x, O->num);

    if ( L+1 == R ) {
        if ( x != INF ) ans += num[L]-x;
    } else {
        cal(O->l, L, (L+R)/2, x);
        cal(O->r, (L+R)/2, R, x);
    }
}

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        cnt = 0;
        m = 0;

        scanf("%d %d", &N, &M);

        root = build(1, N+1);

        for (int Mi = 0; Mi < M; Mi++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);

            if (Mi < N-1) {
                v[a].emplace_back(b, c);
                v[b].emplace_back(a, c);
            }

            u[a].emplace_back(b, c);
            u[b].emplace_back(a, c);
        }

        find_max_son(1, 1);
        build_link(1, 1, 1);



        for (int Ni = 1; Ni <= N; Ni++)
            for (E e: u[Ni]) {
                if ( Ni < e.t )
                    process(Ni, e.t, e.d);
            }

        ans = 0;

        DFS(1, 1);
        cal(root, 1, N+1, INF);

        printf("%d\n", ans);

        for (int Ni = 1; Ni <= N; Ni++)
            v[Ni].clear(), u[Ni].clear();
    }
}