2012年12月16日 星期日

SGU 182 Open the brackets

有啟發性的一題,建議各位想想後再看題解

給一邏輯式,轉成不含括號的等價邏輯式

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

精隨

因為只有十個變數,所以可以枚舉真值表

1024*跑過該式2048 = 2*10^6

如果是true,那就印出a&!b&c這樣

中間則用 || 串起來

長度為10*1024*3+1024 = 31XXX 這樣 < 32768

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

我把它想成是一塊一塊的東西,中間連接起來

所以就用有點像DFS的東西去遞迴

雖然co完後,bug一堆(寫了兩個小時==")

而且一塊一塊還要有等級的需別,才不會弄錯

大致上是用符號的priority分級,可以參考參考我的 code

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

char s[3000];
int app[10], ans[10], an, comb, p;

bool This();
bool dfs(int ty);

int main(){
    scanf("%s", s);
    for(int i = 0; s[i]; i++)
        if(s[i] >= 'a' && s[i] <= 'j') app[s[i]-'a'] = 1;
   
    for(int i = 0; i < 10; i++)
        if(app[i] != 0) ans[an] = i, app[i] = an++;
   
    bool fir = 1;
    for( ; comb < (1<<an); comb++){
        p = 0;
        if(!dfs(0)) continue;
        if(!fir) printf("||");
        for(int i = 0; i < an; i++){
            if(i != 0) printf("&");
            if((comb | (1<<i)) != comb) printf("!");
            printf("%c", ans[i]+'a');
        }
        fir = 0;
    }
    if(fir) printf("a<=>!a");
    puts("");
}

bool This(){
    bool fl = 0;
    while(s[p] == '!') fl ^= 1, p++; p++;
    if(s[p-1] == '(') return fl^dfs(1);
    else return fl ^ (1 & (comb >> app[s[p-1]-'a']));
}

bool dfs(int ty){
    bool now = This();
    while(1){
        if(s[p] == 0) return now;
        if(ty == 1){
            if(s[p] == ')'){
                p += 1;
                return now;
            }
        }
        if(ty == 2){
            if(s[p] == '<' || s[p] == '=' ||
               s[p] == '#' || s[p] == '|' || s[p] == ')')
                return now;
        }
        if(s[p] == '&'){
            p += 1;
            now = (now & This());
            continue;
        }
        if(s[p] == '|'){
            p += 2;
            now = (now | dfs(2));
            continue;
        }
        if(s[p] == '<'){
            p += 3;
            now = (now == dfs(2));
            continue;
        }
        if(s[p] == '='){
            p += 2;
            now = ((!now) | dfs(2));
            continue;
        }
        if(s[p] == '#'){
            p += 1;
            now = (now ^ dfs(2));
            continue;
        }
    }
}

2012年12月15日 星期六

SGU 164 Airlines

很神奇的題目。

題目敘述:

給一完全圖,每個邊有1~M其中一種顏色,選不超過(M+1)/2種顏色,使任意兩點只經過這些顏色時,最短路距離 <= 2
========================================

因為邊分成是你選的,跟你不選的兩種,所以可以把題目化簡成:

有一完全圖,邊只有兩種顏色,選一種顏色,使任兩點最短路距離<=2

可以證明,這兩種顏色,至少有一種會符合任兩點最短路距離<=2
========================================

我爸的證明:XD

設顏色為A, B,任一點都有A的度數 degA(u) 和B的度數 degB(u)

選一個點,使他的某顏色度數是所有點的某顏色度數當中,最大的

設該點為 u,且他連比較多條邊的顏色是A,於是你選擇 A 這個顏色

你可以把他看成兩群,一群是 u 連 A 過去的,一群是 u 連 B 過去的

連A的那群互相都可以相連(透過 u),所以先不理他

至於連B的那群,假設某點連到A的那群不存在一條A邊,也就是全部B邊

那麼加上他連到 u 的B邊,最少就有degA(u)+1條,也>degA(u)了,矛盾

所以所有B那群的點連到A的那群至少會有一條A邊

而透過-> A那群 -> u -> B那群 or -> A那群 -> u ->  A那群

所有的點都可以連到所有的點(距離 <= 2),QED
 ========================================

所以你可以隨便找一半的顏色作為一群,另一半顏色做另一群

判斷某一群是否皆<=2,若沒有,那就是另一群(用Floyd-Warshall)

//By momo
#include<cstdio>
#include<algorithm>
#define N 210
#define INF 999999999
using namespace std;
int n, m, G[N][N], st, en, fl;
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%d", &G[i][j]);
            if(i == j) continue;
            G[i][j] = (G[i][j] <= (m+1)/2)?1:INF;
        }
    }
   
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
   
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(G[i][j] > 3) fl = 1;

    if(fl) st = (m+1)/2+1, en = m;
    else st = 1, en = (m+1)/2;
    printf("%d\n", en-st+1);
    for(int i = st; i <= en; i++) printf("%d%c", i, i == en?'\n':' ');
}

2012年12月9日 星期日

中國郵遞員問題(參考poj 2404)

題目敘述:

有一張連通圖,找出經過所有的邊且回到原處的最小權重和

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

經過所有的邊且要回到原處,很顯然就是一個歐拉回路

但是跟歐拉回路不一樣的地方在於他沒有限制每個邊只能走一次

也就是說,只要是一張連通圖,就一定會有解

但其實你可以把它想成是歐拉回路的進階版本

歐拉迴路中,絕對不能有奇度的點(因為進出的數量相同)

只要有奇度的點,想要回到啟始點,就必定會重複

用重複的概念,可以把原本是奇度的點,修改成全部都是偶度的

至於要怎麼修呢?你可以想成我們對這張圖增加一些邊

原本偶度的點要增加偶數條,奇度的點要增加奇數條

換一種方式想,其實就是要在奇度點之間兩兩建立一條路徑,並使權重和最小

因為奇度點一定是偶數的(整張圖的度數必定是偶數),假設為2N

那就要建立N條路徑,使得這些奇度點兩兩配對,也就是所謂的一般配對

普通的題目N應該很小,所以可以直接用狀態壓縮DP(如本題)

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

算法描述:

1. 建出兩兩奇度點之間的距離(用Floyd或點太多用Dijkstra)

2. 將奇度點兩兩配對,並使權重和最小

3. 新增的邊權+原本圖上的邊權和 = 答案

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

#define N 17
#define INF 999999999
#define SZ(x) (int)((x).size())

using namespace std;

int n, dis[N][N], deg[N], dp[1<<N];
vector<int> odd;

void floyd()
{
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++) if(dis[i][k] != INF)
            for(int j = 0; j < n; j++) if(dis[k][j] != INF)
                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
}

int dfs(int cb)
{
    if(cb == 0) return 0;
    if(dp[cb] != INF) return dp[cb];

    for(int i = 0; i < n; i++)
    {
        if(!(cb & (1<<i))) continue;
        for(int j = 0; j < n; j++)
        {
            if(i == j || !(cb & (1<<j))) continue;
            int v = dfs(cb^(1<<i)^(1<<j));
            dp[cb] = min(dp[cb], v+dis[odd[i]][odd[j]]);
        }
    }
    return dp[cb];
}

int main()
{
    while(scanf("%d", &n), n != 0)
    {
        int ans = 0, m;
        fill(deg, deg+n, 0);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                dis[i][j] = INF;

        scanf("%d", &m);
        for(int i = 0; i < m; i++)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c); a--, b--;
            dis[a][b] = dis[b][a] = min(c, dis[a][b]);
            deg[a]++, deg[b]++, ans += c;
        }
       
        floyd();
       
        odd.clear();
        for(int i = 0; i < n; i++)
            if(deg[i]&1) odd.push_back(i);
        n = SZ(odd);

        for(int i = 0; i < (1<<n); i++) dp[i] = INF;
        printf("%d\n", ans + dfs((1<<n)-1));
    }
}

2012年12月7日 星期五

SGU 156 Strange Graph


很有趣的一個題目

我們來一步一步分析此題

題目把點都分成兩種:

1. deg = 2的點 x type
2. deg > 2的點 y type

我們可以推知,如果有一個 y 型點,連到超過兩個 x 型點
這個圖就暴了。因為第三個 x 型點,不具有其中一個端點

既然被判掉了,我們就假設目前遭遇到的圖 y 型點都連到不超過兩個的 x 型點

接著可以知道,如果有一個 y 型點,連到剛好兩個 x 型點
這個 y 型點可以視為是一個 x 型點。因為他一定要從 x 型點進入,而如果是從其中一個 x 型點進來,他就必定是從另一個 x 型點出去

所以這種情形也被我們弄掉了,所以我們現在的圖 y 型點都連到剛好一個 x 型點
(題目有保證至少會連到一個)

接著,透過題目的另一個條件:
『對於一個 y 型點,連到他的所有 y 型點,他們之間都有相連』

你可以知道 y 型點都會互相相連,形成一個完全圖
而每一個人又剛剛好會向外連出一個 x 型點(如圖所示)

這是什麼意思呢?你會發現不管從哪邊進來都可以出去

而且走過每一個點就會走過每一個邊(不包括裡面的那些)

所以其實我們可以把中間那一坨看成一個點,而外面那些鏈狀物視為一條邊

並把原先要求的哈密頓迴路,轉換成歐拉迴路去求

(我的code不是這樣寫的,所以就不放了,雖然是AC的)

2012年12月5日 星期三

SGU 148 B-Station

題目敘述:

有N層,每一層有該層目前水的體積及該層的容量,可以手動放水(但要付錢),水會放到下一層。如果水滿了則會自動放水,現在我們要使最後一層放水,問最少需要花費多少錢

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

一開始有兩種思緒:

1. 背包,因為只會需要水最多到N,且有N層,因此複雜度O(N^2)
2. 枚舉,從哪裡開始放,然後要讓他一路通暢(不然前面就白花錢了),複雜度O(N^2)

        其實常寫程式的人,很容易就想到第一種,但是因為這題N到100000,所以很明顯是行不通的,而且也很難去優化他,會讓你有種走錯路的感覺。

       至於第二種思路,倒是比較難想到(可能是因為太基礎了,或是太簡單了)不過若是想到了,便接近正解了。接下來你會發現從最後一層開始枚舉的話,其實前面的那些人越有可能可以自動放水,因為你可以用一個 heap 去維護,每一個人進入heap一次,出去一次。整體複雜度O(nlgn)

這麼說起來,把東西看簡單一點,還是比較好些~~~

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

#define N 15010
#define F first
#define S second
#define INF 999999999

using namespace std;

typedef pair<int,int> PII;
priority_queue<PII> que, ans;
int n, w[N], l[N], p[N], sum[N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d%d%d", &w[i], &l[i], &p[i]);
        sum[i] = sum[i-1]+w[i];
    }

    int bst = INF, mon = 0;
    for(int i = n; i >= 1; i--){
        mon += p[i];
        for(; !que.empty() && que.top().F > sum[i-1]; que.pop())
            mon -= p[que.top().S];
        que.push(make_pair(sum[i]-l[i], i));
        if(mon < bst) bst = mon, ans = que;
    }
    for(; !ans.empty(); ans.pop())
        printf("%d\n", ans.top().S);
}

2012年12月4日 星期二

SGU 147 Black-white king

題目看的懂就簡單了,但題目寫的真的不是很清楚

題目翻譯+注釋:

白王:走8格,但是要以最少的步數走到黑王
黑王:走8格,但是要以最少的步數走到黑王
黑白王:走8格,但是不能走到可以以較少步數走到的地方

走的順序:
白王先,黑王次,黑白王後

白王跟黑王要見面,黑白王要在他們碰面前走到某個人的所在位置並殺掉他
問有可能或不可能(白王跟黑王看不到黑白王)

==================以下是題解

枚舉走的步數,1步2步...

黑白王在第 i 步走到的一定是一個『正方形的外框』

而白王跟黑王,因為要走最少的,所以其中的一個方向

每次都必須要走至少一格,並避免無法跟對方相遇,會有另外的一個限制
      其實就是『他跟對方』走到這裡的兩條線段的交集
      因為他之後走到的一定會是另一個人的上面一層
      同層就代表多走了某些步數,且定義為面對面的範圍跟走的範圍是一樣的
      所以才可以直接算交集

所以其實他的所在位置都只會是某一條線(平行Y軸或X軸)

只要判斷這條線跟黑白王的框框有沒有相交即可

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

int n, bx, by, wx, wy, xx, xy, dis, ans = INF;
int check(int sx, int sy, int ex, int ey, int st){
    int dir = ex>sx?1:-1;
    for(int i = 1; i <= st; i++){
        int x = sx+dir*i, l, r;
        l = max(1, max(sy-i, ey-(dis-i)));
        r = min(n, min(sy+i, ey+(dis-i)));
        if((x == xx-i && !(r < xy-i || xy+i < l))
        || (x == xx+i && !(r < xy-i || xy+i < l))
        || (abs(xx-x)<i && l <= xy-i && xy-i <= r)
        || (abs(xx-x)<i && l <= xy+i && xy+i <= r))
            return i;
    }
    return INF;
}

int main(){
    scanf("%d%d%d", &n, &bx, &by);
    scanf("%d%d%d%d", &wx, &wy, &xx, &xy);
    if(abs(bx-wx) < abs(by-wy)){
        swap(bx, by);
        swap(wx, wy);
        swap(xx, xy);
    }
    dis = abs(bx-wx);
    ans = min(check(bx,by,wx,wy,dis/2-1), check(wx,wy,bx,by,dis/2-1));
    if(ans == INF) printf("NO\n%d\n", dis-1);
    else printf("YES\n%d\n", ans);
}

SGU 145 Strange People (recommended)

K短『簡單』路!!!!!!!! NPC問題,使用暴搜~

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

通常IDA*都是用在解一些奇怪的題目上面

像是8 puzzle, 加法鏈…等等

而且都是一層一層加深所謂的 step,藉此作為他的limit

但是這邊這題,卻是透過二分搜距離來創造他的limit

而H函數則是透過dijkstra做一次到終點的最短距離來的

這樣不會太慢嘛?因為在之前的step當中,只要小小的增加一次

可到達的種類數就會陡然的暴增

但是這一題,因為你只要走到終點K次

你就知道這是一個大於等於答案的解,於是便可以直接return回去

所以limit太大時,種類數並不會暴增,反而更可以加快return回去的速度

反而是太小的時候才較為糟糕(我一開始一直沒搞清楚)

而在太小的時候,又可以不斷的利用啟發式函數做減枝,綜合起來

整題速度還算挺可以的(但SGU說實在,測資貌似還挺水的)

//By momo
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define N 110
#define INF 999999999
#define MP make_pair
#define FOR(it, c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)
using namespace std;
typedef pair<int,int> PII;

int n, m, k, s, t, dis[N];
priority_queue<PII> que;

struct edge{
    int t, c;
    edge(){}
    edge(int _t,int _c){t=_t,c=_c;}
};
vector<edge> G[N];

int vst[N], cnt = 0, vs[N], vn, bomb, pnt;
void dfs(int p, int cst, int lmt)
{
    if(cst+dis[p] > lmt) return;
    if(p == t){
        cnt++;
        if(bomb && cst == lmt){
            pnt = 1;
            printf("%d %d\n", lmt, vn);
            for(int i = 0; i < vn; i++)
                printf("%d%c", vs[i], i == vn-1?'\n':' ');
        }
        return;
    }
    FOR(it, G[p]){
        if(!vst[it->t]){
            vst[it->t] = 1;
            vs[vn++] = it->t;
           
            dfs(it->t, cst+it->c, lmt);
           
            vst[it->t] = 0;
            vn--;
           
            if(pnt || cnt == k) return;
        }
    }
}

bool check(int lmt)
{
    fill(vst+1, vst+n+1, 0);
    vst[s] = 1; cnt = 0;
    vs[vn = 0] = s; vn++;
    dfs(s, 0, lmt);
    return cnt == k;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        G[a].push_back(edge(b, c));
        G[b].push_back(edge(a, c));
    }
    scanf("%d%d", &s, &t);

    //dijkstra
    for(int i = 1; i <= n; i++) dis[i] = INF;
    que.push(MP(dis[t] = 0, t));
    while(!que.empty()){
        PII now = que.top(); que.pop();
        int p = now.second;
        if(dis[p] < -now.first) continue;
        FOR(it, G[p]){
            if(dis[it->t] > dis[p]+it->c){
                dis[it->t] = dis[p]+it->c;
                que.push(MP(-dis[it->t], it->t));
            }
        }
    }

    int lb = -1, rb = INF;
    while(lb != rb-1){
        int mid = (lb+rb) >> 1;
        bomb = 1;
        if(check(mid)) rb = mid;
        else lb = mid;
    }
    bomb = 1;
    check(rb);
}

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);
}