NOI 2001 解題報告

NOI2001的題目是[反正切函數的應用][聰明的打字員][隕石的祕密][食物鏈][炮兵陣地][方程的解數]。

其中[反正切函數的應用][聰明的打字員]較爲簡單,[隕石的祕密][食物鏈][炮兵陣地][方程的解數]稍有難度。

[反正切函數的應用]是一個求函數最值的問題,要配合數學知識解決。[聰明的打字員]是廣度優先搜索問題。[隕石的祕密]是一個樹形動態規劃的問題,需要仔細思考。[食物鏈]用到了並差集。[ 炮兵陣地]是個不易看出的動態規劃問題。[方程的解數]是搜索問題,需要用哈希表來優化。

[反正切函數的應用]

根據題中公式,可以推出 a=(b*c-1)/(b+c)。由此得出c=(a*b+1)/(b-a)。因爲b,c均爲正整數,所以b>a。

我們要求b+c最小,設函數y=f(x),自變量x爲b的取值,但不限於正整數。則有

  • f(x) = (a*x+1)/(x-a) + x = a + ((1+a^2)/(x-a)) + x

對f(x)求導,得導數

  • f'(x)=1-(1+a^2)/(x-a)^2

f'(x)=0 得出 x = a+(a^2+1)^0.5 或 x = a-(a^2+1)^0.5,由於x>0,取 x = a+(a^2+1)^0.5

且x > a+(a^2+1)^0.5時,f'(x)>0,x < a+(a^2+1)^0.5時,f'(x)<0,所以當x = a+(a^2+1)^0.5時,f(x)取得最小值。

由於b和c都是正整數,只需在x一邊尋找距離x最近的整數b,c,b+c即要求的最小值。

/*
 * Problem: NOI2001 arctan
 * Author: Guo Jiabao
 * Time: 2009.3.21 14:18
 * State: Solved
 * Memo: 函數最值問題
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
int a,b,c,Ans=0x7FFFFFFF;
int main()
{
    freopen("arctan.in","r",stdin);
    freopen("arctan.out","w",stdout);
    scanf("%d",&a);
    double t=ceil(a+sqrt((double)a*a+1));
    for (;;t--)
    {
        b=(int)(t+0.1);
        long long q=a;
        q=q*b+1;
        if (q%(b-a)==0)
        {
            c=q/(b-a);
            Ans=b+c;
            break;
        }
    }
    printf("%d\n",Ans);
    return 0;
}

[聰明的打字員]

簡單的廣搜題,對於每個狀態,直接按照規則擴展6狀態,開一個哈希表判重,直到搜索到結果爲止。

/*
 * Problem: NOI2001 clever
 * Author: Guo Jiabao
 * Time: 2009.3.17 13:37
 * State: Solved
 * Memo: BFS
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int LIM=1000000;
using namespace std;
struct state
{
    int s,step,pos;
};
bool used[LIM][7];
int S,T;
int Q_size,Q_head,Q_tail;
state Q[LIM];
state start;
void init()
{
    freopen("clever.in","r",stdin);
    freopen("clever.out","w",stdout);
    scanf("%d%d",&S,&T);
    start.s=S;
    start.pos=1;
    start.step=0;
    Q_head=-1;Q_tail=0;Q_size=0;
}
void Answer(int ans)
{
    printf("%d\n",ans);
    exit(0);
}
void Q_ins(state p)
{
    if (used[p.s][p.pos]) return;
    used[p.s][p.pos]=true;
    if (p.s==T) Answer(p.step);
    Q_size++;
    if (++Q_head==LIM) Q_head=0;
    Q[Q_head]=p;
}
state Q_pop()
{
    state r=Q[Q_tail];
    Q_size--;
    if (++Q_tail==LIM) Q_tail=0;
    return r;
}
void BFS()
{
    state u,v;
    int pos[7],su,sv,tim,p,i;
    Q_ins(start);
    while (Q_size)
    {
        u=Q_pop();
        su=sv=u.s;
        p=u.pos;
        tim=LIM;
        for (i=1;i<=p;i++)
            tim/=10;
        for (i=6;i>=1;i--)
        {
            pos[i]=sv%10;
            sv/=10;
        }
        if (p>1) //swap0
        {
            sv=su;
            sv-=100000*pos[1] + tim*pos[p];
            sv+=tim*pos[1] + 100000*pos[p];
            v.pos=u.pos;
            v.step=u.step+1;
            v.s=sv;
            Q_ins(v);
        }
        if (p<6) //swap1
        {
            sv=su;
            sv-=pos[6] + tim*pos[p];
            sv+=tim*pos[6] + pos[p];
            v.pos=u.pos;
            v.step=u.step+1;
            v.s=sv;
            Q_ins(v);
        }
        if (pos[p]!=9) //up
        {
            sv=su;
            sv+=tim;
            v.pos=u.pos;
            v.step=u.step+1;
            v.s=sv;
            Q_ins(v);
        }
        if (pos[p]!=0) //down
        {
            sv=su;
            sv-=tim;
            v.pos=u.pos;
            v.step=u.step+1;
            v.s=sv;
            Q_ins(v);
        }
        if (p>1) //left
        {
            v.s=u.s;
            v.pos=u.pos-1;
            v.step=u.step+1;
            Q_ins(v);
        }
        if (p<6) //right
        {
            v.s=u.s;
            v.pos=u.pos+1;
            v.step=u.step+1;
            Q_ins(v);
        }
    }
}
int main()
{
    init();
    BFS();
    return 0;
}

[隕石的祕密]

容易看出是動態規劃,但是狀態轉移方程容易考慮不周全。

題目中樣例的8種方案爲{[]()} {()[]} {}[()] [()]{} []{()} {()}[] (){[]} {[]}() 可以看出每個SS表達式都可以看成由幾個小的SS組成,組成方式可能是嵌套或者連接。如果是嵌套(包括僅1層),我們把這個嵌套體看作一個整體部分,稱爲一個組。則每個SS表達式都是由幾個組連接而成了。

設定 F[p1,p2,p3,d]爲深度不超過d,包含p1個{},p2個[],p3個()的SS表達式的可能組成的方案數。S[p1,p2,p3,d]爲深度不超過d,包含p1個{},p2個[],p3個()的一個組的可能組成的方案數。

則狀態轉移方程爲

S[p1,p2,p3,d]=
{
    0 (p1==p2==p3==0)
    F[p1-1,p2,p3,d-1] (p1&gt;=1)
    F[p1,p2-1,p3,d-1] (p1==0 &amp;&amp; p2&gt;=1)
    F[p1,p2,p3-1,d-1] (p1==0 &amp;&amp; p2==0 &amp;&amp; p3&gt;=1)
}

F[p1,p2,p3,d]=Σ(S[x1,x2,x3,d]*F[p1-x1,p2-x2,p3-x3,d]) (0<=x1<=p1,0<=x2<=p2,0<=x3<=p3且x1,x2,x3不同時爲0)

初始條件

  • F[0,0,0,i]=1 (0<=i<=D)

最終的結果就是

  • F[L1,L2,L3,D]-F[L1,L2,L3,D-1]
/* 
 * Problem: NOI2001 secret
 * Author: Guo Jiabao
 * Time: 2009.3.18 13:54
 * State: Solved
 * Memo: 動態規劃
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXL=11,MAXD=31,MOD=11380;
using namespace std;
int L1,L2,L3,D,Ans;
int F[MAXL][MAXL][MAXL][MAXD];
int single(int p1,int p2,int p3,int d);
int dp(int p1,int p2,int p3,int d);
void init()
{
    freopen("secret.in","r",stdin);
    freopen("secret.out","w",stdout);
    scanf("%d%d%d%d",&L1,&L2,&L3,&D);
    int p1,p2,p3,d;
    for (d=0;d<=D;d++)
    {
        for (p1=0;p1<=L1;p1++)
            for (p2=0;p2<=L2;p2++)
                for (p3=0;p3<=L3;p3++)
                    F[p1][p2][p3][d]=-1;
        F[0][0][0][d]=1;
    }
}
int single(int p1,int p2,int p3,int d)
{
    if (p1>=1)
        return dp(p1-1,p2,p3,d-1);
    else if (p1==0 && p2>=1)
        return dp(p1,p2-1,p3,d-1);
    else
        return dp(p1,p2,p3-1,d-1);
}
int dp(int p1,int p2,int p3,int d)
{
    if (d<0) return 0;
    if (F[p1][p2][p3][d]==-1)
    {
        int x1,x2,x3,y1,y2,y3;
        F[p1][p2][p3][d]=0;
        for (x1=0;x1<=p1;x1++)
            for (x2=0;x2<=p2;x2++)
                for (x3=0;x3<=p3;x3++)
                {
                    y1=p1-x1;y2=p2-x2;y3=p3-x3;
                    if (x1+x2+x3==0) continue;
                    F[p1][p2][p3][d]+=single(x1,x2,x3,d)*dp(y1,y2,y3,d)%MOD;
                    F[p1][p2][p3][d]%=MOD;
                }
    }
    return F[p1][p2][p3][d];
}
int main()
{
    init();
    Ans=(dp(L1,L2,L3,D)-dp(L1,L2,L3,D-1)+MOD)%MOD;
    printf("%d\n",Ans);
    return 0;
}

[食物鏈]

這道題真是個並差集的典型應用問題。由於判斷真假總是根據前面得到的關係,在某時關係不是完全的,所以不能直接判斷a,b究竟是哪個物種,但是可以知道部分的關係。

很顯然,合法的關係都是三角形環,如果a,b同屬於一個環內,那麼它們的關係是可以直接判斷的。如果不屬於同一環,因爲不與前面矛盾,就認 爲是正確的,然後把a,b所在的兩個環合併。建立一個並差集,表示每個生物所屬的物種類型。對於物種i,定義prev[i]爲可以吃掉i的物種類 型,next[i]爲i可以吃掉的物種類型。初始時,每個物種i對應一個單獨的類型,並且引入兩個虛節點prev[i]和next[i],可分別爲一個單 獨的類型。

合併兩個環時,對於D=1,a與b爲同一物種,分別把(a,b),(prev[a],prev[b]),(next[a],next[b])依次合併。

對於D=2,a可以吃掉b,則分別把(next[a],b),(a,prev[b]),(prev[a],next[b])依次合併。

/* 
 * Problem: NOI2001
 * Author: Guo Jiabao
 * Time: 2009.3.13 13:28
 * State: Solved
 * Memo: 並差集 等價類判斷
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=50001;
struct UFS
{
    int f[MAXN*3];
    int getroot(int a)
    {
        int t,r=a;
        while (f[r]!=r) r=f[r];
        while (f[a]!=a) {t=f[a];f[a]=r;a=t;}
        return r;
    }
    bool judge(int a,int b){return getroot(a)==getroot(b);}
    void merge(int a,int b){f[getroot(b)]=getroot(a);}
}U;
using namespace std;
int N,M,Fake;
int prev[MAXN*3],next[MAXN*3];
void init()
{
    int i,p,n;
    freopen("eat.in","r",stdin);
    freopen("eat.out","w",stdout);
    scanf("%d%d",&N,&M);
    for (i=1;i<=N;i++)
    {
        p=N+i;n=p+N;
        U.f[i]=i;U.f[p]=p;U.f[n]=n;
        prev[i]=p;next[i]=n;prev[n]=i;
        next[n]=p;prev[p]=n;next[p]=i;
    }
}
bool relation(int d,int a,int b)
{
    if (d==1)
    {
        if (U.judge(a,b))
            return true;
        if (U.judge(prev[a],b) || U.judge(next[a],b))
            return false;
        U.merge(a,b);
        U.merge(prev[a],prev[b]);
        U.merge(next[a],next[b]);
    }
    else
    {
        if (U.judge(next[a],b))
            return true;
        if (U.judge(a,b) || U.judge(prev[a],b))
            return false;
        U.merge(next[a],b);
        U.merge(a,prev[b]);
        U.merge(prev[a],next[b]);
    }
    return true;
}
void solve()
{
    int i,d,a,b;
    for (i=1;i<=M;i++)
    {
        scanf("%d%d%d",&d,&a,&b);
        if (a>N || b>N || (d==2 && a==b) ||!relation(d,a,b))
            Fake++;
    }
}
int main()
{
    init();
    solve();
    printf("%d\n",Fake);
    return 0;
}

[炮兵陣地]

較難看出的動態規劃問題。注意到數據範圍N≤100;M≤10,發現每行的寬度都不大,所以可以考慮把一行看成一個狀態,表示該行的佈置方案。每行的佈置方案可以預先處理出,由數學知識可以算出,每行最多的佈置方案數也不過60個而已。

狀態設定

F[i,a,b]爲前i行,第i行的方案爲A[a],第i-1行的方案爲A[b]的最大炮兵數。

狀態轉移方程

  • F[i,a,b]=Max{ F[i-1,b,c] + P[a] }

其中c爲i-2行的佈置方案,a,b,c應保證互不衝突,即放置方案中炮兵都在平地上,且不會互相攻擊到。

目標結果

  • Ans=Max{F[N,a,b]}
/* 
 * Problem: NOI2001 cannon
 * Author: Guo Jiabao
 * Time: 2009.3.20 17:54
 * State: Solved
 * Memo: 動態規劃 位表示狀態
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=101,MAXM=11,MAXA=61;
using namespace std;
int N,M,Ans,AC;
bool used[MAXN];
int F[MAXN][MAXA][MAXA];
int A[MAXA],C[MAXA],Pla[MAXN];
void init()
{
    int i,j;
    char c;
    freopen("cannon.in","r",stdin);
    freopen("cannon.out","w",stdout);
    scanf("%d%d",&N,&M);
    for (i=1;i<=N;i++)
    {
        do c=getchar(); while(c==10 || c==13);
        ungetc(c,stdin);
        Pla[i]=0;
        for (j=1;j<=M;j++)
            if ((c=getchar())=='H')
                Pla[i]+=1<<(j-1);
    }
}
inline int Max(int a,int b)
{
    return a>b?a:b;
}
void dynamic()
{
    int i,j,k,l,x,y,z,p,q;
    for (i=2,j=1;j<=AC;j++)
    {
        x=A[j];
        p=C[j];
        if ((x&Pla[1])==0)
        for (k=1;k<=AC;k++)
        {
            y=A[k];
            q=C[k];
            if ((y&Pla[i])==0 && (x&y)==0)
                F[i][k][j]=p+q;
            if (F[i][j][k] > Ans)
                Ans = F[i][j][k];
        }
    }
    for (i=3;i<=N;i++)
    {
        for (j=1;j<=AC;j++)
        {
            x=A[j];    p=C[j];
            if ((x&Pla[i])==0)
                for (k=1;k<=AC;k++)
                {
                    y=A[k];
                    if ((y&Pla[i-1])==0 && (x&y)==0)
                        for (l=1;l<=AC;l++)
                        {
                            z=A[l];
                            if ((z&Pla[i-2])==0 && ((y|z)&x)==0)
                                F[i][j][k]=Max(F[i][j][k],F[i-1][k][l] + p);
                        }
                    if (F[i][j][k] > Ans)
                        Ans = F[i][j][k];
                }
        }
    }
}
void arrange(int p)
{
    if (p>M)
    {
        int r=0,c=0;
        for (int i=1;i<=M;i++)
            if (used[i])
            {
                c++;
                r+=1<<(i-1);
            }
        AC++;
        A[AC]=r;
        C[AC]=c;
        return ;
    }
    used[p]=true;
    arrange(p+3);
    used[p]=false;
    arrange(p+1);
}
void solve()
{
    arrange(1);
    dynamic();
}
int main()
{
    init();
    solve();
    printf("%d\n",Ans);
    return 0;
}

[方程的解數]

經典的搜索問題,方法是搜索每個x的所有可能值[1,M],判斷符合條件的解的個數。但是對於N=6,搜索量高達11390625000000,顯然會超時。

我們不妨把等式變形,對於N項,把後N/2項移到等式右邊,則移過去的項的k值全部取相反數。對於左邊剩下的N/2項,搜索x的所有可能 值,計算左邊式子的值,並插入到哈希表中。然後再對於右邊的N-2項,搜索x的所有可能值,計算左邊式子的值,然後再哈希表中查找與之相等的值的個數,加 到結果上。

插入到哈希表時先把絕對值Mod一個大質數,我選的是4000037,然後掛鏈解決衝突。爲了提高效率,在哈希表的每個位置上我都建立了一個Treap,這樣解決衝突時就能更快得找到了。

做這道題起初我試圖直接用一個Treap存儲所有的算式可能值,但是這樣做會超時。通過使用哈希表,使數據平均分佈了許多。哈希表和平衡樹,或者Trie樹混合使用不失爲一種解決衝突優秀的方法。

/* 
 * Problem: NOI2001 equation1
 * Author: Guo Jiabao
 * Time: 2009.3.21 16:15
 * State: Solved
 * Memo: 搜索 + Hash +Treap判重
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=7,MAXM=151,MAXP=7,MOD=4000037;
const bool LEFT=true,RIGHT=false;
using namespace std;
struct TTreap
{
    struct Treap_node
    {
        Treap_node *left,*right;
        int value,weight,fix;
        Treap_node(int v):value(v),weight(1)
        {
            left=right=0;
            fix=rand();
        }
    };
    Treap_node *root;
    TTreap():root(0){}
    inline void rotate_left(Treap_node *&p)
    {
        Treap_node *q=p->right;
        p->right=q->left;
        q->left=p;
        p=q;
    }
    inline void rotate_right(Treap_node *&p)
    {
        Treap_node *q=p->left;
        p->left=q->right;
        q->right=p;
        p=q;
    }
    void insert(Treap_node *&p,int value)
    {
        if (!p)
            p=new Treap_node(value);
        else if (value == p->value)
            p->weight++;
        else if (value < p->value)
        {
            insert(p->left,value);
            if (p->left->fix < p->fix)
                rotate_right(p);
        }
        else
        {
            insert(p->right,value);
            if (p->right->fix < p->fix)
                rotate_left(p);
        }
    }
    int find(Treap_node *p,int value)
    {
        if (!p)
            return 0;
        else if (value == p->value)
            return p->weight;
        else if (value < p->value)
            return find(p->left,value);
        else
            return find(p->right,value);
    }
};
struct item
{
    int k,p,x;
}I[MAXN];
int N,LIM,Mid,Ans;
int POW[MAXM][MAXP];
TTreap Hash[MOD];
bool L;
void init()
{
    freopen("equation1.in","r",stdin);
    freopen("equation1.out","w",stdout);
    scanf("%d%d",&N,&LIM);
    Mid=N/2;
    for (int i=1;i<=N;i++)
    {
        scanf("%d%d",&I[i].k,&I[i].p);
        if (i>Mid)
            I[i].k=-I[i].k;
    }
    srand(9112);
}
inline int power(int x,int p)
{
    if (!POW[x][p])
    {
        POW[x][p]=1;
        for (int i=1;i<=p;i++)
            POW[x][p]*=x;
    }
    return POW[x][p];
}
int compute(int a,int b)
{
    int rs=0,i;
    for (i=a;i<=b;i++)
        rs+=power(I[i].x,I[i].p)*I[i].k;
    return rs;
}
inline int Abs(int a) {return a<0?-a:a;}
void search(int e)
{
    int i,H;
    if (L && e>Mid )
    {
        i=compute(1,Mid);
        H=Abs(i)%MOD;
        Hash[H].insert(Hash[H].root,i);
    }
    else if (!L && e>N)
    {
        i=compute(Mid+1,N);
        H=Abs(i)%MOD;
        int a=Hash[H].find(Hash[H].root,i);
        Ans+=a;
    }
    else
        for (i=1;i<=LIM;i++)
        {
            I[e].x=i;
            search(e+1);
        }
}
void solve()
{
    L=LEFT;
    search(1);
    L=RIGHT;
    search(Mid+1);
}
int main()
{
    init();
    solve();
    printf("%d\n",Ans);
    return 0;
}
<h2><span class="mw-headline">反正切函數的應用 </span></h2>

<a class="image" title="Image:Arctan.gif" href="http://192.168.1.253/wiki/Image:Arctan.gif"><img src="http://192.168.1.253/mw/images/8/85/Arctan.gif" alt="Image:Arctan.gif" width="568" height="670" /></a>

輸入文件

輸入文件中只有一個正整數a ,其中1&lt;=a&lt;=60000 。

輸出文件

輸出文件中只有一個整數,爲b + c的值。
輸入樣例
<pre>1</pre>
輸出樣例
<pre>5</pre>

<h2><span class="mw-headline">聰明的打字員 </span></h2>

阿蘭是某機密部門的打字員,她現在接到一個任務:需要在一天之內輸入幾百個長度固定爲6的密碼。當然,她希望輸入的過程中敲擊鍵盤的總次數越少越好。

不幸的是,出於保密的需要,該部門用於輸入密碼的鍵盤是特殊設計的,鍵盤上沒有數字鍵,而只有以下六個鍵:Swap0, Swap1, Up, Down, Left, Right,爲了說明這6個鍵的作用,我們先定義錄入區的6個位置的編號,從左至右依次爲1,2,3,4,5,6。下面列出每個鍵的作用:
  • Swap0:按Swap0,光標位置不變,將光標所在位置的數字與錄入區的1號位置的數字(左起第一個數字)交換。如果光標已經處在錄入區的1號位置,則按Swap0鍵之後,錄入區的數字不變;
  • Swap1:按Swap1,光標位置不變,將光標所在位置的數字與錄入區的6號位置的數字(左起第六個數字)交換。如果光標已經處在錄入區的6號位置,則按Swap1鍵之後,錄入區的數字不變;
  • Up:按Up,光標位置不變,將光標所在位置的數字加1(除非該數字是9)。例如,如果光標所在位置的數字爲2,按Up之後,該處的數字變爲3;如果該處數字爲9,則按Up之後,數字不變,光標位置也不變;
  • Down:按Down,光標位置不變,將光標所在位置的數字減1(除非該數字是0),如果該處數字爲0,則按Down之後,數字不變,光標位置也不變;
  • Left:按Left,光標左移一個位置,如果光標已經在錄入區的1號位置(左起第一個位置)上,則光標不動;
  • Right:按Right,光標右移一個位置,如果光標已經在錄入區的6號位置(左起第六個位置)上,則光標不動。

    當然,爲了使這樣的鍵盤發揮作用,每次錄入密碼之前,錄入區總會隨機出現一個長度爲6的初始密碼,而且光標固定出現在1號位置上。當巧妙地使用上述六個特殊鍵之後,可以得到目標密碼,這時光標允許停在任何一個位置。 現在,阿蘭需要你的幫助,編寫一個程序,求出錄入一個密碼需要的最少的擊鍵次數。

    輸入文件

    文件僅一行,含有兩個長度爲6的數,前者爲初始密碼,後者爲目標密碼,兩個密碼之間用一個空格隔開。

    輸出文件

    文件僅一行,含有一個正整數,爲最少需要的擊鍵次數。

    輸入樣例

    123456 654321
    輸出樣例
    11
    樣例說明:

    初始密碼是123456,光標停在數字1上。對應上述最少擊鍵次數的擊鍵序列爲:

    Image:Clever.gif

    最少的擊鍵次數爲11。

    隕石的祕密

    公元11380年,一顆巨大的隕石墜落在南極。於是,災難降臨了,地球上出現了一系列反常的現象。當人們焦急萬分的時候,一支中國科學家組成的南極考察隊趕到了出事地點。經過一番偵察,科學家們發現隕石上刻有若干行密文,每一行都包含5個整數:

    1 1 1 1 6
      0 0 6 3 57
      8 0 11 3 2845
    著名的科學家SS發現,這些密文實際上是一種複雜運算的結果。爲了便於大家理解這種運算,他定義了一種SS表達式:

        <li>SS表達式是僅由‘{’,‘}’,‘[’,‘]’,‘(’,‘)’組成的字符串。</li>
        <li>一個空串是SS表達式。</li>
        <li>如果A是SS表達式,且A中不含字符‘{’,‘}’,‘[’,‘]’,則(A)是SS表達式。</li>
        <li>如果A是SS表達式,且A中不含字符‘{’,‘}’,則[A]是SS表達式。</li>
        <li>如果A是SS表達式,則{A}是SS表達式。</li>
        <li>如果A和B都是SS表達式,則AB也是SS表達式。</li>
      

    例如

  • ()(())[]

  • {()[()]}
  • {{[[(())]]}}

    都是SS表達式。

  • ()([])()

  • [()

    不是SS表達式。

    一個SS表達式E的深度D(E)定義如下:

    例如(){()}[]的深度爲2。

    密文中的複雜運算是這樣進行的:

    設密文中每行前4個數依次爲L1,L2,L3,D,求出所有深度爲D,含有L1對{},L2對[],L3對()的SS串的個數,並用這個數對當前的年份11380求餘數,這個餘數就是密文中每行的第5個數,我們稱之爲“神祕數”。

    密文中某些行的第五個數已經模糊不清,而這些數字正是揭開隕石祕密的鑰匙。現在科學家們聘請你來計算這個神祕數。

    輸入文件

    共一行,4個整數L1,L2,L3,D。相鄰兩個數之間用一個空格分隔。(0≤L1≤10,0≤L2≤10,0≤L3≤10,0≤D≤30)

    輸出文件

    共一行,包含一個整數,即神祕數。

    輸入樣例

    1 1 1 2
    輸出樣例
    8

    食物鏈

    動物王國中有三類動物A,B,C,這三類動物的食物鏈構成了有趣的環形。A吃B, B吃C,C吃A。

    現有N個動物,以1-N編號。每個動物都是A,B,C中的一種,但是我們並不知道它到底是哪一種。

    有人用兩種說法對這N個動物所構成的食物鏈關係進行描述:

  • 第一種說法是“1 X Y”,表示X和Y是同類。

  • 第二種說法是“2 X Y”,表示X吃Y。

    此人對N個動物,用上述兩種說法,一句接一句地說出K句話,這K句話有的是真的,有的是假的。當一句話滿足下列三條之一時,這句話就是假話,否則就是真話。

        <li>當前的話與前面的某些真的話衝突,就是假話;</li>
        <li>當前的話中X或Y比N大,就是假話;</li>
        <li>當前的話表示X吃X,就是假話。</li>
      

    你的任務是根據給定的N(1<=N<=50,000)和K句話(0<=K<=100,000),輸出假話的總數。

    輸入文件

    第一行是兩個整數N和K,以一個空格分隔。

    以下K行每行是三個正整數 D,X,Y,兩數之間用一個空格隔開,其中D表示說法的種類。

  • 若D=1,則表示X和Y是同類。

  • 若D=2,則表示X吃Y。

    輸出文件

    只有一個整數,表示假話的數目。

    輸入樣例

    輸入文件

    100 7
      1 101 1
      2 1 2
      2 2 3
      2 3 3
      1 1 3
      2 3 1
      1 5 5
    輸出樣例
    3
    樣例說明

    對7句話的分析

  • 1 101 1 假話

  • 2 1 2 真話
  • 2 2 3 真話
  • 2 3 3 假話
  • 1 1 3 假話
  • 2 3 1 真話
  • 1 5 5 真話
<h2><span class="mw-headline">炮兵陣地 </span></h2>

司令部的將軍們打算在N*M的網格地圖上部署他們的炮兵部隊。一個N*M的地圖由N行M列組成,地圖的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示),如下圖。在每一格平原地形上最多可以佈置一支炮兵部隊(山地上不能夠部署炮兵部隊);一支炮兵部隊在地圖上的攻擊 範圍如圖中黑色區域所示:

如果在地圖中的灰色所標識的平原上部署一支炮兵部隊,則圖中的黑色的網格表示它能夠攻擊到的區域:沿橫向左右各兩格,沿縱向上下各兩格。圖上其它白色網格均攻擊不到。從圖上可見炮兵的攻擊範圍不受地形的影響。

現在,將軍們規劃如何部署炮兵部隊,在防止誤傷的前提下(保證任何兩支炮兵部隊之間不能互相攻擊,即任何一支炮兵部隊都不在其他支炮兵部隊的攻擊範圍內),在整個地圖區域內最多能夠擺放多少我軍的炮兵部隊。

<a class="image" title="Image:Cannon.gif" href="http://192.168.1.253/wiki/Image:Cannon.gif"><img src="http://192.168.1.253/mw/images/0/08/Cannon.gif" alt="Image:Cannon.gif" width="257" height="184" /></a>

輸入文件

文件的第一行包含兩個由空格分割開的正整數,分別表示N和M;

接下來的N行,每一行含有連續的M個字符(‘P’或者‘H’),中間沒有空格。按順序表示地圖中每一行的數據。N≤100;M≤10。

輸出文件

文件僅在第一行包含一個整數K,表示最多能擺放的炮兵部隊的數量。

輸入樣例
<pre>5 4
PHPP
PPHH
PPPP
PHPP
PHHP</pre>
輸出樣例
<pre>6</pre>

<h2><span class="mw-headline">方程的解數 </span></h2>

問題描述

已知一個n元高次方程:

<a class="image" title="Image:Equation1.gif" href="http://192.168.1.253/wiki/Image:Equation1.gif"><img src="http://192.168.1.253/mw/images/f/fb/Equation1.gif" alt="Image:Equation1.gif" width="308" height="41" /></a>

其中:x1, x2, …,xn是未知數,k1,k2,…,kn是係數,p1,p2,…pn是指數。且方程中的所有數均爲整數。

假設未知數1≤ xi ≤M, i=1,,,n,求這個方程的整數解的個數。

輸入文件

文件的第1行包含一個整數n。第2行包含一個整數M。第3行到第n+2行,每行包含兩個整數,分別表示ki和pi。兩個整數之間用一個空格隔開。第3行的數據對應i=1,第n+2行的數據對應i=n。
輸出文件

文件僅一行,包含一個整數,表示方程的整數解的個數。

輸入樣例
<pre>3
150
1 2
-1 2
1 2</pre>
輸出樣例
<pre>178</pre>
約束條件

1&lt;=n&lt;=6;1&lt;=M&lt;=150;

<a class="image" title="Image:Equation2.gif" href="http://192.168.1.253/wiki/Image:Equation2.gif"><img src="http://192.168.1.253/mw/images/4/4a/Equation2.gif" alt="Image:Equation2.gif" width="300" height="36" /></a>

方程的整數解的個數小於2^31。

★本題中,指數Pi(i=1,2,……,n)均爲正整數。

相關日誌