2012年11月23日 星期五

SGU 141 Jumping Joe

題目敘述:

給x1, x2, P, K,求:

P1*x1 - N1*x1 + P2*x2 - N2*x2 = P 
P1 + N1 + P2 + N2 = K

的可行解 P1, N1, P2, N2 其中一組。

x1, x2 <= 40000,P <= 40000,K <= 2000000000

======================================

很明顯的,這是一題特別的擴展歐幾里德題目

但需要一些很麻煩的運算及分析


最起先,要求得 P1-N1 跟 P2-N2 分別的可行解(分別設成A, B)

先求ax+by = gcd(a, b)的 x 和 y (或稱A或B)

可以知道兩個解都會分別小於 x2 和 x1
{
     pf: 用數學歸納法,而且用我所使用的ext_gcd較好證明
}

為了方便起見,可以將 P1, N1 調成 (t+abs(A), t) 或 (t, t+abs(A)),端看A的正負

而 P2, N2 調成 (abs(B), 0) 或 (0, abs(B)),端看B的正負

這麼調整的話,即可知道只要符合 2*t >= 0 時,便是一個這題的解,無需任何其他限制

而 t 即是 (K-abs(A)-abs(B)) / 2,所以我們想做的便是將abs(A)+abs(B)最小化且是偶數

有很多種作法可以讓abs(A)+abs(B)最小化(A跟B是變量可以不斷的分別+x2/gcd, -x1/gcd)

可以知道『abs(A)+abs(B)』對『改變量』呈現一個谷狀
{
     說明: 假設一開始兩個在零的異側,很明顯會呈現谷狀。若在同側,則要端看何者間隔大,將他不斷往零的方向移動,最後如果穿越零了,變成互相位於異側,則只會上升
}

所以可以直接用暴力去求得,剩下的就是調整奇偶即印出而已

但你可能覺得這樣跑太慢了,事實上重點就在於其與零的位置

因為 A <= x2*P/gcd 且 B <= x1*P/gcd,而間隔為x2/gcd和x1/gcd,所以最多改變約P次,for只會循環 P 次,時間複雜度O(P),是OK的

//By momo
#include<cstdio>
#include<algorithm>
using namespace std;

int ext_gcd(int a, int b, int& x, int& y){
    int v = a;
    if(b == 0){ x = 1, y = 0; }
    else{
        v = ext_gcd(b, a%b, y, x);
        y -= (a / b) * x;
    }
    return v;
}

int main()
{  
    int x1, x2, p, k, d1, d2, A, B;
    scanf("%d%d%d%d", &x1, &x2, &p, &k);
   
    int gcd = ext_gcd(x1, x2, A, B);
    if(abs(p) % gcd) return puts("NO"), 0;
   
    A *= p/gcd, B *= p/gcd; d1 = x2/gcd; d2 = x1/gcd;
   
    for( ; abs(A-d1) + abs(B+d2) < abs(A) + abs(B); A -= d1, B += d2);
    for( ; abs(A+d1) + abs(B-d2) < abs(A) + abs(B); A += d1, B -= d2);
    if(abs(A) + abs(B) > k) return puts("NO"), 0;

    if((k-abs(A)-abs(B)) % 2){
        if((d1+d2) % 2 == 0) return puts("NO"), 0;
        if(abs(A-d1)+abs(B+d2) < abs(A+d1)+abs(B-d2)) A -= d1, B += d2;
        else A += d1, B -= d2;
        if(abs(A)+abs(B) > k) return puts("NO"), 0;,
    }

    int t = (k-abs(A)-abs(B)) / 2;
    int p1, n1, p2, n2;
    if(A < 0) p1 = t, n1 = t-A;
    else p1 = t+A, n1 = t;
    if(B < 0) p2 = 0, n2 = -B;
    else p2 = B, n2 = 0;

    printf("YES\n%d %d %d %d\n", p1, n1, p2, n2);
}

2012年11月17日 星期六

Codeforces 243B Hydra

題目敘述:

給一個圖,沒有自環或重邊,問有沒有一隻多頭龍
有一個很簡單的作法可行:

『枚舉 u,然後枚舉 v,接著判斷可不可以』


也就是O(E)*一個不知道是多少但感覺很大的東西


感覺就會TLE,但這題神奇的地方就在於他的時間複雜度

先把可以當成頭的點記錄起來,接下來判斷可以當成尾巴的點的數量

作法如下:

如果head的數量夠多,且某個head可以當成tail,那就把它當成tail

如果他只能是tail,照樣把它當成tail

一直做到有足夠的tail了或是沒辦法再有其他tail了,就結束


for(int i = 0; cnt < t && i < SZ(G[v]); i++)
{
    int x = G[v][i];
    if(== u) continue;
    if(rem && vst[x]) rem--, tail[cnt++] = x;
    else if(!vst[x]) tail[cnt++] = x;
}


重點其實就是怕cnt不會變多(因為 t <= 100)

但如果cnt不會變多,其實也就是 rem == h

那麼最多跑 h 次,cnt便又會開始增加

因此時間複雜度為O(h+t),總時間複雜度O(E*(h+t)),2*10^7

//By momo
#include<cstdio>
#include<vector>
#include<algorithm>

#define N 100010
#define PB push_back
#define SZ(x) (int)((x).size())
#define FOR(it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)

using namespace std;

int n, m, h, t;
int vst[N], rev[N], che[N];
vector<int> G[N];

int main(){
    scanf("%d%d%d%d", &n, &m, &h, &t);
    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        G[a].PB(b); G[b].PB(a);
    }
   
    for(int u = 1; u <= n; u++)
    {
        if(SZ(G[u]) <= h) continue;
        FOR(it, G[u]) vst[*it] = 1;
        FOR(it, G[u])
        {
            if(SZ(G[*it]) <= t) continue;

            int v = *it;
            int cnt = 0;
            int rem = SZ(G[u])-h-1;

            for(int i = 0; cnt < t && i < SZ(G[v]); i++)
            {
                int x = G[v][i];
                if(x == u) continue;
                if(rem && vst[x]) rem--, che[x] = 1, rev[cnt++] = x;
                else if(!vst[x]) rev[cnt++] = x;
            }

            if(cnt == t)
            {
                printf("YES\n%d %d\n", u, v);
                int c = 0;
                FOR(it2, G[u])
                {
                    if(che[*it2] || *it2 == v) continue;
                    printf("%d ", *it2);
                    if((++c) == h) break;
                }puts("");
                for(int i = 0; i < cnt; i++) printf("%d ", rev[i]);
                puts("");

                return 0;
            }

            for(int i = 0; i < cnt; i++) che[rev[i]] = 0;
        }
        FOR(it, G[u]) vst[*it] = 0;
    }
    puts("NO");
}

SGU 132 Another Chocolate Maniac

題目敘述:

給你一塊M*N的蛋糕,有些地方有蠟燭

你要把沒有蠟燭的地方用1*2的巧克力塊覆蓋

而且如果有可以覆蓋的地方就一定要覆蓋

請用最少的巧克力,問最少要幾塊

M <= 70
N <= 7

一看到N好小,而且又發現因為是1*2的

所以當你要放在某一層時,最多影響到那前一層

所以無後效性,符合DP的原則,且是狀態壓縮DP

==========================

接下來比較麻煩的部份就是要怎麼去DP他

為了讓code便簡潔,我使用的方式是這樣:

對於某一層去放,放置的方式只有兩種-此格和下方格,此格和右方格

可以確定這樣便可以實現所有的可能

接著有些東西需要判斷,就是一定要放滿的這個規則

總之就寫成一個DFS

而因為那個規則,dp必須要包含上層及此層兩項

O(M*(2^(2N)*N) 約10^7


//By momo
#include<cstdio>
#include<algorithm>
#define N 100
#define INF 999999999
using namespace std;

int n, m, pos, tbl[N];
int dp[2][1<<7][1<<7];
int T(int x){ return 1<<x; }

void init();
void dfs();
void solve();
void output();

int main()
{
    init();
    solve();
    output();
}

void init()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        char cke[10];
        scanf("%s", cke);
        for(int j = 0; j < m; j++)
            tbl[i+1] = tbl[i+1]*2 + (cke[j]=='*');
    }

    tbl[0] = T(m)-1;
    for(int i = 0; i < T(m); i++)
        for(int j = 0; j < T(m); j++)
            dp[0][i][j] = dp[1][i][j] = INF;
}

void dfs(int x, int pv, int nw, int nx, int cnt)
{
    if(x == m)
    {
        dp[1-pos][nw][nx] = min(cnt, dp[1-pos][nw][nx]);
        return;
    }
    bool a = (pv & T(x));
    bool b = (nw & T(x));
    bool c = (nx & T(x));
    if(b) dfs(x+1, pv, nw, nx, cnt);
    else
    {
        if((x == 0 || (nw & T(x-1))) && a)
            dfs(x+1, pv, nw, nx, cnt);
        if(x != m-1 && (nw & T(x+1)) == 0)
            dfs(x+1, pv, nw+T(x)+T(x+1), nx, cnt+1);
        if(!c) dfs(x+1, pv, nw+T(x), nx+T(x), cnt+1);
    }
}

void solve()
{
    dp[pos = 0][T(m)-1][tbl[1]] = 0;
    for(int i = 0; i < n; i++, pos = 1-pos)
    {
        for(int j = 0; j < T(m); j++)
            for(int k = 0; k < T(m); k++)
                dp[1-pos][j][k] = INF;
       
        for(int j = 0; j < T(m); j++)
        {
            if((tbl[i]&j) != tbl[i]) continue;
            for(int k = 0; k < T(m); k++)
            {
                if(dp[pos][j][k] == INF) continue;
                dfs(0, j, k, tbl[i+2], dp[pos][j][k]);
            }
        }
    }
}

void output()
{
    int ans = INF;
    for(int i = 0; i < T(m); i++)
        if((tbl[n]&i) == tbl[n])
            ans = min(ans, dp[pos][i][0]);
    printf("%d\n", ans);
}