清北學堂比賽 Q1 解題報告

昨天晚上做了清北學堂的比賽“首屆信息學在線測評大賽Q1”,名字很響亮。今天寫了一份題解,發出來。

第一題:低價購買

要求求出方案數的最長單調序列(LIS)問題。我把序列先倒轉了過來,然後求最長上升序列。由於需要去除重複序列,可以增加一個域Next[i],定義Next[i]=min{ k | k>i 且 A[k]=A[i] },表示大於i且離i最近的Next[i],使得第Next[i]個數與第i個數相同。如果不存在這樣的數則Next[i]=無窮大。這樣的話如果出現Next[i]不爲0且Next[j]<i可直接跳過。

狀態設定 F[i]爲以第i個元素爲結尾的最長上升序列的長度 G[i]爲以第i個元素爲結尾的最長上升序列的方案數

狀態轉移方程

F[i] = Max{ F[j] + 1 | A[j] < A[i] 且 Next[j] > i } G[i] = Sum{ G[j] | F[j] + 1 = F[i] }

邊界條件

G[0]=1

爲了方便,增加一個極大的元素到序列結尾。這樣目標狀態爲 最長長度 F[N+1]-1 方案數 G[N+1]

第二題:連續串之和

相鄰元素絕對值之差必須爲1,所以顯然構造出的和最大的序列一定爲0,1,2,3,...,N-1,和爲(N-1)N/2,最小和同理爲-(N-1)N/2。於是如果給定的S不在最大值與最小值的區間內,一定無解。

我們先生成一個和最大的序列,0,1,2,3,...,N-1,然後再考慮調整使得滿足條件。假設當前的和與S的差爲D,可以發現,無論怎樣變換序列,D的奇偶性的不改變的。因爲無論改變那個元素,都只能從比前一個元素多1變成少1,或者從比前一個元素少1變成多1,調整多個也是一樣的,變化量爲偶數。所以說,如果初始的D爲奇數,則一定不可能有解。

餘下來的情況一定爲有解的情況了。把序列順序做差,初始化每項差值都爲1,則對應了0,1,2,3,...,N-1。可以發現,修改一個差值從1到-1會引起後面所有項的值減少2,總的減少量就是後面項的個數*2。這時就可以設計出算法了,從第一個差值開始嘗試從1變成-1,更新當前和,直到等於S爲止。最後再根據差值序列還原出原序列。時間複雜度爲O(N)。

第三題:決鬥

觀察發現,如果第i個人想與第j個人決鬥(i<j),i,j必須相鄰,也就是i,j之間的人必須全部被打敗。換句話說,如果i,j相鄰,一定存在一個k(i<k<j),使得i,k相鄰,k與j相鄰,而且i可以打敗k或者j可以打敗k。這樣就把問題縮小了,可以以此進行動態規劃。考慮到是一個環,我們可以把N個人複製一遍,接在後面。

設定狀態 F[i,j] 表示第i個人是否可以與第j個人相鄰 (1<=i<j<=N*2),第i個人在環上另一面的映射爲i+N

狀態轉移方程 F[i,j]= Or { F[i,k]=F[k,j]=true | i可以打敗k或j可以打敗k }

邊界條件 由於i和i+1兩個一定是相鄰的,所以有 F[i,i+1]=true

判斷第i個人可以勝出的條件就是F[i,i+N]=true,此時i兩邊的人全部敗了,i獲勝。

時間複雜度O(N^3)。

第四題:最小費用多米諾

把棋盤上每個非障礙格子看作一個頂點,相鄰兩個非障礙格子對應的頂點連接一條邊,權值爲在這兩個格子上放上多米諾方塊的費用。判斷是否能放滿只需求出該圖的最大匹配,並判斷是否每個頂點都有匹配。如何求最大匹配?帶花樹?不,這是一個二分圖!

爲什麼是二分圖?因爲棋盤是可以2染色的,之間有邊的頂點都是相鄰的,而相鄰的格子必然是顏色不同的,所以這是一個二分圖。

接下來就容易了,首先求出最大匹配,如果存在完美匹配(每個頂點都有匹配),再求最佳匹配(最小權值完備匹配)即可。

下面是四個題的程序

第一題:低價購買

/* 
 * Problem: RQN Q1 低價購買
 * Author: Guo Jiabao
 * Time: 2009.5.2 21:48
 * State: Solved
 * Memo: 動態規劃 LIS
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=50001,INF=0x7FFFFFFF;
using namespace std;
int F[MAXN],G[MAXN],A[MAXN],Next[MAXN];
int N,Ans=-INF,Ans2;
void init()
{
    int i,j;
    freopen("low.in","r",stdin);
    freopen("low.out","w",stdout);
    scanf("%d",&N);
    for (i=N;i>=1;i--)
        scanf("%d",&A[i]);
    Next[0]=INF;
    for (i=1;i<=N;i++)
    {
        Next[i]=INF;
        for (j=i+1;j<=N;j++)
            if (A[j]==A[i])
            {
                Next[i]=j;
                break;
            }
    }
    A[++N]=INF;
}
void dynamic()
{
    int i,j;
    memset(G,0,sizeof(G));
    G[0]=1;
    for (i=1;i<=N;i++)
    {
        F[i]=0;
        for (j=0;j<=i-1;j++)
        {
            if (Next[j]>i && A[j] < A[i])
            {
                if (F[j] > F[i])
                {
                    F[i] = F[j];
                    G[i] = G[j];
                }
                else if (F[j] == F[i])
                    G[i] += G[j];
            }
        }
        F[i]++;
    }
    Ans=F[N]-1;
    Ans2=G[N];
}
int main()
{
    init();
    dynamic();
    printf("%d %d",Ans,Ans2);
    return 0;
}

第二題:連續串之和

/* 
 * Problem: RQN Q1 連續串之和
 * Author: Guo Jiabao
 * Time: 2009.5.1 20:01
 * State: Done
 * Memo: 構造
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=10001;
using namespace std;
int A[MAXN],N,S;
void init()
{
    freopen("sum.in","r",stdin);
    freopen("sum.out","w",stdout);
    scanf("%d%d",&N,&S);
}
void construct()
{
    int i,Lim,Dif,k,d;
    Lim=N*(N-1)/2;
    Dif=Lim-S;
    if (S>Lim || S<-Lim || Dif%2==1)
    {
        printf("NIE");
        return;
    }
    for (i=2;i<=N;i++)
        A[i]=1;
    for (i=2;i<=N && Dif;i++)
    {
        k=(N-i+1)*2;
        if (Dif >= k)
        {
            A[i] = -1;
            Dif -= k;
        }
    }
    k=0;d=0;
    for (i=1;i<N;i++)
    {
        k += A[i];
        d+=k;
        printf("%dn",k);
    }
    k += A[i];
    d+=k;
    printf("%d",k);
}
int main()
{
    init();
    construct();
    return 0;
}

第三題:決鬥

/* 
 * Problem: RQN Q1 決鬥
 * Author: Guo Jiabao
 * Time: 2009.5.1 20:24
 * State: Done
 * Memo: 動態規劃
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN=1001;

bool F[MAXN][MAXN];
bool Beat[MAXN][MAXN];
int N,N2,Wcnt;
int Win[MAXN];

void init()
{
    int i,j,c;
    freopen("mus.in","r",stdin);
    freopen("mus.out","w",stdout);
    scanf("%d",&N);
    N2=N*2;
    for (i=1;i<=N;i++)
    {
        for (j=1;j<=N;j++)
        {
            scanf("%d",&c);
            Beat[i][j]=Beat[i][j+N]=Beat[i+N][j]=Beat[i+N][j+N]= c==1;
        }
    }
}

void dynamic()
{
    int i,j,k,l;
    for (i=1;i<N2;i++)
    {
        F[i][i+1]=true;
    }
    for (l=3;l<=N+1;l++)
    {
        for (i=1;i<=N2;i++)
        {
            if ((j=i+l-1)>N2)
                break;
            for (k=i+1;k<=j-1;k++)
            {
                if (F[i][k] && F[k][j] && (Beat[i][k] || Beat[j][k]))
                {
                    F[i][j]=true;
                    break;
                }
            }
        }
    }
    for (i=1;i<=N;i++)
    {
        if (F[i][i+N])
        {
            Wcnt++;
            Win[ Wcnt ]=i;
        }
    }
    printf("%dn",Wcnt);
    for (i=1;i<Wcnt;i++)
    {
        printf("%dn",Win[i]);
    }
    printf("%d",Win[i]);
}

int main()
{
    init();
    dynamic();
    return 0;
}

第四題:最小費用多米諾

/* 
 * Problem: RQN Q1 最小費用多米諾
 * Author: Guo Jiabao
 * Time: 2009.5.2 19:40
 * State: Solved
 * Memo: 棋盤2染色 二分圖匹配 匈牙利 費用流
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=41,MAXV=MAXN*MAXN,MAXE=MAXV*8,INF=0x7FFFFFFF;
const int dx[4]={0,1,-1,0},dy[4]={1,0,0,-1};
using namespace std;
struct Queue
{
    int Q[MAXV],head,tail,size;
    bool inq[MAXV];
    Queue(){head=size=0,tail=-1;memset(inq,0,sizeof(inq));}
    void ins(int p)
    {
        size++;
        if (++tail>=MAXV)
            tail=0;
        Q[tail]=p;
        inq[p]=true;
    }
    int pop()
    {
        int r=Q[head];
        size--;
        if (++head>=MAXV)
            head=0;
        inq[r]=false;
        return r;
    }
}Q;
struct edge
{
    edge *next,*op;
    int t,c,v;
}ES[MAXE],*V[MAXV],*fe[MAXV];
struct point
{
    int vx,vy,id,put;
}P[MAXN][MAXN];
int N,M,S,T,MatchCnt,MaxCostFlow,EC,Number;
int color[MAXV],Match[MAXV],sp[MAXV],fp[MAXV],PX[MAXV],PY[MAXV];
bool vis[MAXV];
void init()
{
    int i,j;
    freopen("domino.in","r",stdin);
    freopen("domino.out","w",stdout);
    scanf("%d%d",&N,&M);
    for (i=1;i<=N;i++)
        for (j=1;j<=M;j++)
        {
            scanf("%d",&P[i][j].vx);
            if (P[i][j].vx)
                Number++;
        }
    for (i=1;i<=N;i++)
        for (j=1;j<=M;j++)
            scanf("%d",&P[i][j].vy);
}
inline bool inrange(int x,int y)
{
    return x>=1 && x<=N && y>=1 && y<=M;
}
void dye(int x,int y,int c)
{
    P[x][y].id=++T;
    PX[T]=x; PY[T]=y;
    color[T]=c;
    for (int k=0;k<4;k++)
    {
        int px=x+dx[k],py=y+dy[k];
        if (inrange(px,py) && P[px][py].vx && !P[px][py].id)
        {
            dye(px,py,3-c);
        }
    }
}
inline void addedge(int a,int b,int c,int v)
{
    ES[++EC].next=V[a];
    V[a]=ES+EC; V[a]->t=b; V[a]->c=c; V[a]->v=v;
    ES[++EC].next=V[b];
    V[b]=ES+EC; V[b]->t=a; V[b]->c=0; V[b]->v=-v;
    V[a]->op=V[b]; V[b]->op=V[a];
}
void makegraph()
{
    int i,j,k,px,py,a,b,v;
    for (i=1;i<=N;i++)
        for (j=1;j<=M;j++)
            if (P[i][j].vx && !P[i][j].id)
                dye(i,j,1);
    for (i=1;i<=N;i++)
        for (j=1;j<=M;j++)
            for (k=0;k<2;k++)
            {
                px=i+dx[k],py=j+dy[k];
                if (inrange(px,py))
                {
                    a=P[i][j].id;
                    b=P[px][py].id;
                    if (a==0 || b==0) continue;
                    if (color[b]==1)
                    {
                        v=a; a=b; b=v;
                    }
                    if (k==0)
                        v = P[i][j].vx + P[px][py].vx;
                    else
                        v = P[i][j].vy + P[px][py].vy;
                    addedge(a,b,1,v);
                }
            }
    S=0;T++;
    for (i=1;i<T;i++)
    {
        if (color[i]==1)
            addedge(S,i,1,0);
        else
            addedge(i,T,1,0);
    }
}
bool path(int i)
{
    for (edge *e=V[i];e;e=e->next)
    {
        int j=e->t;
        if (!vis[j] && e->c>0)
        {
            vis[j]=true;
            if (Match[j]==0 || path(Match[j]))
            {
                Match[j]=i;
                return true;
            }
        }
    }
    return false;
}
bool hungary()
{
    for (int i=1;i<T;i++)
    {
        if (color[i]==1 && !Match[i])
        {
            memset(vis,0,sizeof(vis));
            if (path(i))
                MatchCnt++;
        }
    }
    return MatchCnt*2==Number;
}
bool spfa()
{
    int i,j;
    for (i=S;i<=T;i++)
        sp[i]=INF;
    sp[S]=0;
    Q.ins(S);
    while (Q.size)
    {
        i=Q.pop();
        for (edge *e=V[i];e;e=e->next)
        {
            j=e->t;
            if (e->c && sp[i] + e->v < sp[j])
            {
                sp[j] = sp[i] + e->v;
                fp[j] = i;
                fe[j] = e;
                if (!Q.inq[j])
                    Q.ins(j);
            }
        }
    }
    return sp[T]!=INF;
}
void CostFlow()
{
    int i,delta;
    while (spfa())
    {
        delta=INF;
        for (i=T;fp[i];i=fp[i])
            if (fe[i]->c < delta)
                delta = fe[i]->c;
        for (i=T;fe[i];i=fp[i])
        {
            fe[i]->c -= delta;
            fe[i]->op->c +=delta;
        }
        MaxCostFlow += delta * sp[T];
    }
    for (i=1;i<T;i++)
    {
        if (color[i]==1)
        {
            for (edge *e=V[i];e;e=e->next)
            {
                if (e->c==0)
                {
                    Match[e->t] = i;
                    break;
                }
            }
        }
    }
}
void print(int Ans)
{
    int i,j;
    printf("%dn",Ans);
    for (i=1;i<T;i++)
    {
        if (color[i]==2)
        {
            j=Match[i];
            if (PX[i]==PX[j])
                P[ PX[i] ][ PY[i] ].put = P[ PX[j] ][ PY[j] ].put = 1;
            else
                P[ PX[i] ][ PY[i] ].put = P[ PX[j] ][ PY[j] ].put = 2;
        }
    }
    for (i=1;i<=N;i++)
    {
        for (j=1;j<M;j++)
            printf("%d ",P[i][j].put);
        printf("%d",P[i][j].put);
        if (i!=N)
            printf("n");
    }
}
void solve()
{
    makegraph();
    if (hungary())
    {
        CostFlow();
        print(MaxCostFlow);
    }
    else
        print(MatchCnt);
}
int main()
{
    init();
    solve();
    return 0;
}
低價購買

<table>
<tbody>
<tr>
<td class="Text0" height="28" bgcolor="#84c1ff">描述</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">“ 低價購買”這條建議是在奶牛股票市場取得成功的一半規則。要想被認爲是偉大的投資者,你必須遵循以下的問題建議:“低價購買;再低價購買”。每次你購買一 支股票,你必須用低於你上次購買它的價格購買它。買的次數越多越好!你的目標是在遵循以上建議的前提下,求你最多能購買股票的次數。你將被給出一段時間內 一支股票每天的出售價(2^16範圍內的正整數),你可以選擇在哪些天購買這支股票。每次購買都必須遵循“低價購買;再低價購買”的原則。寫一個程序計算 最大購買次數。

這裏是某支股票的價格清單:
日期  1  2  3  4  5  6  7  8  9 10 11 12
價格 68 69 54 64 68 64 70 67 78 62 98 87

最優秀的投資者可以購買最多4次股票,可行方案中的一種是:
日期    2  5  6 10
價格   69 68 64 62

數據規模
對於100%的數據,1 &lt;= N &lt;= 5000。

</span></td>
</tr>
<tr>
<td class="Text0" height="24" bgcolor="#84c1ff">輸入格式</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">第1行: N,股票發行天數。
第2行: N個數,是每天的股票價格。
</span></td>
</tr>
<tr>
<td class="Text0" bgcolor="#84c1ff">輸出格式</td>
</tr>
<tr class="TextN">
<td class="Text0"><span class="Text4">輸出僅一行包含兩個數:最大購買次數和擁有最大購買次數的方案數(&lt;=2^31)當二種方案“看起來一樣”時(就是說它們構成的價格隊列一樣的時候),這2種方案被認爲是相同的。</span></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">樣例輸入</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea" readonly="readonly">12 68 69 54 64 68 64 70 67 78 62 98 87 </textarea></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">樣例輸出</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea2" readonly="readonly">4 2</textarea></td>
</tr>
</tbody></table>

連續串之和

<table>
<tbody>
<tr>
<td class="Text0" height="28" bgcolor="#84c1ff">描述</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">我們定義連續串爲一串整數,它的第一個元素爲0,並且任兩個相鄰元素之差的絕對值爲1。更精確的說,如果[a1, a2, …, an]爲一個連續串,那麼有:
    對於任意的1&lt;k&lt;n,|ak - ak+1|=1
    a1=0
任務:
寫一個程序:
    讀入連續串的長度和連續串中所有元素的和;
    找出一個給定長度的連續串,使其所有元素的和與給定的和相等,或者指出這樣的連續串不存在。

數據規模
對於100%的數據,1 &lt;= n &lt;= 10000,|S| &lt;= 50000000。
輸出任意一個可行解即可,本題的Special Judge已經由RenQing編寫完畢.
最新更新[RQ剛剛出完數據...所以來透露一下]:
對於30%的數據 n&lt;=12 s&lt;=30
對於60%的數據 n&lt;=1000 s&lt;=1500
對於100%的數據 n&lt;=10000 s&lt;=50000000

</span></td>
</tr>
<tr>
<td class="Text0" height="24" bgcolor="#84c1ff">輸入格式</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">輸入的第一行有一個整數n,表示連續串中元素的個數。第二行爲一個整數S,表示連續串中所有元素之和。</span></td>
</tr>
<tr>
<td class="Text0" bgcolor="#84c1ff">輸出格式</td>
</tr>
<tr class="TextN">
<td class="Text0"><span class="Text4">如果能夠找到滿足條件的連續串,你應當輸出n個整數(每行一個),表示連續串中的各個元素(第k個元素輸出在第k行)。否則,文件應該只包含一個單詞NIE。</span></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">樣例輸入</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea" readonly="readonly">8 4 </textarea></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">樣例輸出</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea2" readonly="readonly">0 1 2 1 0 -1 0 1</textarea></td>
</tr>
</tbody></table>

決鬥

<table>
<tbody>
<tr>
<td class="Text0" height="28" bgcolor="#84c1ff">描述</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">Michel最近迷上了買彩票。現在,某賭場就一輪決鬥的結果開設了賭局。這個賭局同樣被Michel盯上了,他決定購買這個彩票。
當然,身爲有教養有文化的人,Michel買彩票並不是胡亂買的。他在買之前進行了詳盡的市場調查,並拿到了任意兩個選手對決後的勝敗情況。可以假定正式比賽的時候決鬥後果也是一樣的。
同時決鬥的規則是這樣的:
首先,選手們圍成一個圈。每一回合隨機抽出一個選手的號碼,讓他和他右邊的選手決鬥。開始時,1號右邊的是2號,2號右邊的試三號,依此類推。特別的,n號右邊的是1號。戰敗的選手則退出戰場。例如2號戰敗,則1號右邊的就變成了3號。
現在,他找到了你,希望你能告訴他哪些選手可能贏。

數據範圍:
對於30%的數據,n=5
對於100%的數據,1&lt;=n&lt;=500

[感謝:陳啓峯出題,清北學堂提供]

</span></td>
</tr>
<tr>
<td class="Text0" height="24" bgcolor="#84c1ff">輸入格式</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">輸入數據的第一行爲一個整數n,表示有n個選手。
接下來n行,每行n個整數,第I+1行第J列表示第I個選手與第J個選手對決後的勝敗情況,0表示選手I失敗,1表示選手I獲勝。</span></td>
</tr>
<tr>
<td class="Text0" bgcolor="#84c1ff">輸出格式</td>
</tr>
<tr class="TextN">
<td class="Text0"><span class="Text4">輸出數據的第一行爲一個整數k,表示有多少選手可能贏。
接下來k行,每行一個整數,從小到大輸出這些選手的編號。</span></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">樣例輸入</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea" readonly="readonly">2 0 0 1 0</textarea></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">樣例輸出</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea2" readonly="readonly">1 2</textarea></td>
</tr>
</tbody></table>

最小費用多米諾

<table>
<tbody>
<tr>
<td class="Text0" height="28" bgcolor="#84c1ff">描述</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">在 N*M 的棋盤上互不覆蓋地放置 1*2 和 2*1 的多米諾方塊,有一些格子上有障礙,這些格子不能放置多米諾方塊。在每個沒有障礙的格子上有兩個費用值,分別表示這個格子上橫放和豎放多米諾方塊所需的費 用。試問存不存在一種放置多米諾的方案,能放滿所有無障礙的格子。若存在,求出完成放置的最小費用;若不存在,求出最多能放置多少個多米諾。

數據規模
保證第一行的答案不超過 2^30。
對於 30% 的數據,N, M &lt;= 5。
對於 80% 的數據,N, M 中至少有一個不超過8。
對於 100% 的數據,N, M &lt;= 40。

備註
本題設有部分分,對於每種情況,如果你的程序只輸出了第一行且答案正確,可以得到該測試點 70% 的分數。但是如果你的程序輸出了放置方案而方案不正確,該測試點得0分。
[感謝題目作者wish]

</span></td>
</tr>
<tr>
<td class="Text0" height="24" bgcolor="#84c1ff">輸入格式</td>
</tr>
<tr class="TextN">
<td class="Text0" height="24"><span class="Text4">第一行兩個正整數 N 和 M,表示棋盤共 N 行 M 列。
後爲兩個 N*M 的矩陣,分別表示棋盤每個格子橫放和豎放多米諾的費用。費用爲正整數,若費用爲0,則格子是障礙格(保證障礙格兩個費用均爲0)。
</span></td>
</tr>
<tr>
<td class="Text0" bgcolor="#84c1ff">輸出格式</td>
</tr>
<tr class="TextN">
<td class="Text0"><span class="Text4">若存在至少一種放置方案,則第一行輸出最小費用,後跟一個 N*M 的矩陣,表示最小費用方案。
若不存在滿足要求的放置方案,則第一行輸出最多能夠放置多少個多米諾,後跟一個 N*M 的矩陣,輸出一種放置方案。
方案可能有很多種,只需輸出任意一種即可。
輸出的方案中,0表示這個格子不放置多米諾,1表示這個格子的多米諾橫放,2 表示這個格子的多米諾豎放。
</span></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">樣例輸入</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea" readonly="readonly">3 4 3 5 3 2 3 0 0 3 9 8 2 3 2 8 4 4 8 0 0 2 1 4 3 8 </textarea></td>
</tr>
<tr>
<td class="Text0" align="left" valign="top" bgcolor="#84c1ff">樣例輸出</td>
</tr>
<tr>
<td class="Text0" align="left" valign="top"><textarea cols="80" rows="4" name="textarea2" readonly="readonly">42 1 1 1 1 2 0 0 2 2 1 1 2 </textarea></td>
</tr>
</tbody></table>

相關日誌