NOI 2001 解题报告

This post is written in Chinese. Please consider using Google Translate

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)均为正整数。

Related posts