NOIP2003题解

传送门

考查题型搜索字符串模拟 dp

T1 神经网络

题目背景

人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。

题目描述

在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：

神经元〔编号为1）

图中，X1―X3是信息输入渠道，Y1－Y2是信息输出渠道，C1表示神经元目前的状态，Ui是阈值，可视为神经元的一个内在参数。

神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。

兰兰规定，Ci服从公式：（其中n是网络中所有神经元的数目）

公式中的Wji（可能为负值）表示连接j号神经元和 i号神经元的边的权值。当 Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为Ci。

如此．在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态（Ci），要求你的程序运算出最后网络输出层的状态。

输入输出格式

输入格式：

输入文件第一行是两个整数n（1≤n≤100）和p。接下来n行，每行两个整数，第i＋1行是神经元i最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为0。再下面P行，每行由两个整数i，j及一个整数Wij，表示连接神经元i、j的边权值为Wij。

输出格式：

输出文件包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状态，两个整数间以空格分隔。仅输出最后状态大于零的输出层神经元状态，并且按照编号由小到大顺序输出！

若输出层的神经元最后状态均为 0，则输出 NULL。

输入输出样例

输入样例#1：

(1)正向建边dfs每一层的点

反向建边从第二层开始推每个点的状态

这样做完美避过所有坑点一次AC

#include<iostream>

#include<cstdio>

#define N 101

using namespace std;

int n,p,x,cc,y,zz,cnt,flag,zsumedge,fsumedge;

int c[N],u[N],rd[N],cd[N],ceng[N],z[N][N],fa[N],zhead[N],fhead[N];

struct E1{

    int x,y,z,nxt;

    E1(int x=,int y=,int z=,int nxt=):

        x(x),y(y),z(z),nxt(nxt){}

}zedge[N<<];

struct E2{

    int x,y,z,nxt;

    E2(int x=,int y=,int z=,int nxt=):

        x(x),y(y),z(z),nxt(nxt){}

}fedge[N<<];

void zadd(int x,int y,int z){

    zedge[++zsumedge]=E1(x,y,z,zhead[x]);

    zhead[x]=zsumedge;

}

void fadd(int x,int y,int z){

    fedge[++fsumedge]=E2(x,y,z,fhead[x]);

    fhead[x]=fsumedge;

}

void dfs(int k){

    ceng[k]=ceng[fa[k]]+;

    z[ceng[k]][++z[ceng[k]][]]=k;

    cc=max(cc,ceng[k]);

    for(int i=zhead[k];i;i=zedge[i].nxt){

        int v=zedge[i].y;

        if(fa[k]!=v){

            fa[v]=k;

            dfs(v);

        }

    }

}

int main(){

    scanf("%d%d",&n,&p);

    for(int i=;i<=n;i++){

        scanf("%d%d",&c[i],&u[i]);

    }

    for(int i=;i<=p;i++){

        scanf("%d%d%d",&x,&y,&zz);

        cd[x]++;rd[y]++;

        zadd(x,y,zz);fadd(y,x,zz);

    }

    for(int i=;i<=n;i++)

    if(!rd[i])dfs(i);

    for(int s=;s<=cc;s++){

        for(int i=;i<=z[s][];i++){

        int v=z[s][i];cnt=;

        for(int j=fhead[v];j;j=fedge[j].nxt){

            int vv=fedge[j].y;

            if(c[vv]>)cnt+=(fedge[j].z*c[vv]);

        }

        c[v]=cnt-u[v];

        }

    }

    for(int i=;i<=n;i++){

        if(cd[i]==&&c[i]>){

            flag=;printf("%d %d\n",i,c[i]);

        }

    }

    if(flag==)printf("NULL\n");

    return ;

}

（2）宽搜+模拟

#include<iostream>

#include<cstdio>

#define mx 103

using namespace std;

int n,p,x,y,z,sumedge,hed=,tail,flag;

int head[mx],h[mx],q[mx],c[mx],u[mx],inq[mx];

struct Edge{

    int x,y,z,nxt;

    Edge(int x=,int y=,int z=,int nxt=):

        x(x),y(y),z(z),nxt(nxt){}

}edge[mx];

void add(int x,int y,int z){

    edge[++sumedge]=Edge(x,y,z,head[x]);

    h[x]=sumedge;

    head[x]=sumedge;

}

void bfs(){

    while(hed<=tail){

        int now=q[hed++];

        if(c[now]<=)continue;

        for(int i=head[now];i;i=edge[i].nxt){

            int v=edge[i].y;

            c[v]+=(c[now]*edge[i].z);

            if(!inq[v]){q[++tail]=v;c[v]-=u[v];inq[v]=;}

        }

    }

}

int main(){

    scanf("%d%d",&n,&p);

    for(int i=;i<=n;i++){

        scanf("%d%d",&c[i],&u[i]);

        if(c[i])q[++tail]=i,inq[i]=;

    }

    for(int i=;i<=p;i++){

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);

    }

    bfs();

    for(int i=;i<=n;i++)

    if(h[i]==)if(c[i]>){printf("%d %d\n",i,c[i]);flag=;}

    if(flag==)printf("NULL\n");

    return ;

}

T2 侦探推理

题目描述

明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：

证词中出现的其他话，都不列入逻辑推理的内容。

明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。

现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！

输入输出格式

输入格式：

输入由若干行组成，第一行有三个整数，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）；M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证言的总数。接下来M行，

每行是明明的一个同学的名字（英文字母组成，没有主格，全部大写）。

往后有P行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过250个字符。

输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。

输出格式：

如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出 Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出 Impossible。

输入输出样例

输入样例#1：

3 1 5

MIKE

CHARLES

KATE

MIKE: I am guilty.

MIKE: Today is Sunday.

CHARLES: MIKE is guilty.

KATE: I am guilty.

KATE: How are you??

题解 字符串+模拟

#include<cstdio>

#include<map>

#include<iostream>

#include<string>

using namespace std;

int n,m,p,s[][],l[],d[][],day[][],gu[];

map<string,int>t;

map<int,string>h;

string u,v[],g[],q[],bb;

int main()

{

    scanf("%d%d%d",&m,&n,&p);

    for (int i=;i<m;i++)

    {cin>>u;t[u]=i+;h[i+]=u;}

    for (int i=;i<p;i++)

    {

        int y,ll=;u="";while(u[ll-]!='.' && u[ll-]!='?' && u[ll-]!='!')

        {cin>>bb;if (ll>)u+=' ';u+=bb;ll=u.length();}

        for (int j=;j<ll&&u[j]!=':';j++)

        {v[i]+=u[j];y=j;}

        int jj=t[v[i]],b=-,nn=,uu=;

        for (int j=y+;j<ll;j++)

        {

            if (!uu)g[i]+=u[j];else q[i]+=u[j];

            if (!nn && !uu && u[j+]==' ')for (int k=;k<=m;k++)if (h[k]==g[i]){b=k;break;}

            if (b!=- && !nn && !uu){g[i]=u[j+];j+=;nn=;}

            if (g[i]=="Today is ")uu=;

        }

        if (g[i]=="I am guilty.")s[jj][l[jj]++]=;

        if (g[i]=="I am not guilty.")s[jj][l[jj]++]=;

        if (g[i]=="is guilty."){s[jj][l[jj]]=;d[jj][l[jj]++]=b;}

        if (g[i]=="is not guilty."){s[jj][l[jj]]=;d[jj][l[jj]++]=b;}

        if (g[i]=="Today is ")

        {

            s[jj][l[jj]]=;

            if (q[i]=="Monday.")day[jj][l[jj]++]=;

            if (q[i]=="Tuesday.")day[jj][l[jj]++]=;

            if (q[i]=="Wednesday.")day[jj][l[jj]++]=;

            if (q[i]=="Thursday.")day[jj][l[jj]++]=;

            if (q[i]=="Friday.")day[jj][l[jj]++]=;

            if (q[i]=="Saturday.")day[jj][l[jj]++]=;

            if (q[i]=="Sunday.")day[jj][l[jj]++]=;

        }

    }

    for (int i=;i<=m;i++)

    for (int j=;j<=;j++)

    {

        int fa=,T,F,abc=;

        for (int k=;k<=m;k++)

        {

            T=F=;

            for (int kk=;kk<l[k];kk++)

            {

                if (s[k][kk]==)

                {

                    if (i==k)T=;else F=;

                }

                if (s[k][kk]==)

                {

                    if (i!=k)T=;else F=;

                }

                if (s[k][kk]==)

                {

                    if (i==d[k][kk])T=;else F=;

                }

                if (s[k][kk]==)

                {

                    if (i!=d[k][kk])T=;else F=;

                }

                if (s[k][kk]==)

                {

                    if (j==day[k][kk])T=;else F=;

                }

            }

            if (T && F)break;

            if (F)fa++;

            if (!T && !F)abc++;

        }

        if (T && F)continue;

        if (fa==n || fa<=n && fa+abc>=n)gu[i]=;

    }

    int ans=;

    for (int i=;i<=m;i++)

    if (gu[i])ans++;

    if (!ans)printf("Impossible");

    else if (ans>)printf("Cannot Determine");

    else for (int i=;i<=m;i++)if (gu[i]){cout<<h[i];break;}

    return ;

}

（这不是我的code我的还没调试完会补上的

T3 加分二叉树

题目描述

设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：

subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数。

若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；

（1）tree的最高加分

（2）tree的前序遍历

输入输出格式

输入格式：

第1行：一个整数n（n＜30），为节点个数。

第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。

输出格式：

第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。

第2行：n个用空格隔开的整数，为该树的前序遍历。

输入输出样例

输入样例#1：

5

5 7 1 2 10

输出样例#1：

145

3 1 2 4 5

题解

这个题可以用动态规划或者记忆化搜索来做。因为如果要求加分最大的话，必须要求它的儿子结点

加分最大，所以就有了最优子阶段。我们可以枚举根来更新最大值。中序遍历有个特点，在中序遍

历这个序列上，某个点左边的序列一定是这个点的左子树，右边的序列，一定在这个点的右子树。

root[i,j]表示[i,j]这段序列的根，递归输出先序遍历。注意初始化，f[i][i]=v[i]，当序列只有I一个元素时，f[i][i]等于这个点本身

的权值，当l==r-1时，此时是空树设为1。

啦啦啦啦代码来啦两种方法

code

动态规划区间dp

#include<iostream>

#include<cstdio>

using namespace std;

int n,v[],f[][],i,j,k,root[][];

void print(int l,int r){

    if(l>r)return;

    if(l==r){printf("%d ",l);return;}

    printf("%d ",root[l][r]);

    print(l,root[l][r]-);

    print(root[l][r]+,r);

}

int main() {

    scanf("%d",&n);

    for( i=; i<=n; i++) scanf("%d",&v[i]);

    for(i=; i<=n; i++) {f[i][i]=v[i];f[i][i-]=;}

    for(i=n; i>=; i--)

        for(j=i+; j<=n; j++)

            for(k=i; k<=j; k++) {

                if(f[i][j]<(f[i][k-]*f[k+][j]+f[k][k])) {

                    f[i][j]=f[i][k-]*f[k+][j]+f[k][k];

                    root[i][j]=k;

                }

            }

    printf("%d\n",f[][n]);

    print(,n);

    return ;

}

记忆化搜索

#include<iostream>

#include<cstdio>

using namespace std;

int n,v[],dp[][],root[][];

int ser(int l,int r){

    if(dp[l][r]>)return dp[l][r];

    if(l==r)return v[l];

    if(r<l)return ;

    for(int i=l;i<=r;i++){

        int p=ser(l,i-)*ser(i+,r)+dp[i][i];

        if(p>dp[l][r]){

            dp[l][r]=p;root[l][r]=i;

        }

    }

    return dp[l][r];

}

void print(int l,int r){

    if(r<l)return;

    if(l==r){printf("%d ",l);return;}

    printf("%d ",root[l][r]);

    print(l,root[l][r]-);

    print(root[l][r]+,r);

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&v[i]),dp[i][i]=v[i];

    printf("%d\n",ser(,n));

    print(,n);

    return ;

}

T4传染病控制

题目背景

近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国大范围流行，该国政府决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚未完全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。于是，蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO（世界卫生组织）以及全球各国科研部门的努力，这种新兴传染病的传播途径和控制方法已经研究清楚，剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。

题目描述

研究表明，这种传染病的传播具有两种很特殊的性质；

第一是它的传播途径是树型的，一个人X只可能被某个特定的人Y感染，只要Y不得病，或者是XY之间的传播途径被切断，则X就不会得病。

第二是，这种疾病的传播有周期性，在一个疾病传播周期之内，传染病将只会感染一代患者，而不会再传播给下一代。

这些性质大大减轻了蓬莱国疾病防控的压力，并且他们已经得到了国内部分易感人群的潜在传播途径图（一棵树）。但是，麻烦还没有结束。由于蓬莱国疾控中心人手不够，同时也缺乏强大的技术，以致他们在一个疾病传播周期内，只能设法切断一条传播途径，而没有被控制的传播途径就会引起更多的易感人群被感染（也就是与当前已经被感染的人有传播途径相连，且连接途径没有被切断的人群）。当不可能有健康人被感染时，疾病就中止传播。所以，蓬莱国疾控中心要制定出一个切断传播途径的顺序，以使尽量少的人被感染。

你的程序要针对给定的树，找出合适的切断顺序。

输入输出格式

输入格式：

输入格式的第一行是两个整数n（1≤n≤300）和p。接下来p行，每一行有两个整数i和j，表示节点i和j间有边相连（意即，第i人和第j人之间有传播途径相连）。其中节点1是已经被感染的患者。

输出格式：

只有一行，输出总共被感染的人数。

输入输出样例

输入样例#1：

输出样例#1：

３

题解 枚举+搜索
贪心了半天 每次切掉重儿子竟然是错了 详情画菊花图自行脑补
贪心90

#include<iostream>

#include<cstdio>

#include<queue>

#include<algorithm>

using namespace std;

queue<int>q,qq;

int n,p,x,y,ans=,sumedge;

int head[],siz[];

struct Edge{

    int x,y,nxt;

    Edge(int x=,int y=,int nxt=):

        x(x),y(y),nxt(nxt){}

}edge[];

void add(int x,int y){

    edge[++sumedge]=Edge(x,y,head[x]);

    head[x]=sumedge;

}

void dfs(int x){

    siz[x]=;

    for(int i=head[x];i;i=edge[i].nxt){

        int v=edge[i].y;

        dfs(v);

        siz[x]+=siz[v];

    }

}

void slove(){

    int u=;

    if(q.size()==)return;

    while(q.size()){

        int now=q.front();q.pop();qq.push(now);

        for(int i=head[now];i;i=edge[i].nxt){

            int v=edge[i].y;

            if(siz[v]>siz[u])u=v;

        }

    }

    while(qq.size()){

        int now=qq.front();qq.pop();

        for(int i=head[now];i;i=edge[i].nxt){

            int v=edge[i].y;

            if(v!=u){

                q.push(v);ans++;

            //    cout<<v<<endl;

            }

        }

    }

    slove();

}

int main(){

    //freopen("epidemic.in","r",stdin);

//    freopen("epidemic.out","w",stdout);

    scanf("%d%d",&n,&p);

    for(int i=;i<=p;i++){

        scanf("%d%d",&x,&y);

        if(x>y)swap(x,y);

        add(x,y);

    }

    dfs();q.push();

    slove();

    printf("%d\n",ans);

    return ;

}

#include<iostream>

#include<cmath>

#include<cstdio>

#define mx 313

using namespace std;

int n,p,x,y,sumedge,ans=,flag,cut[mx],head[mx],dep[mx],fa[mx],deep[mx][mx];

struct Edge{

    int x,y,nxt;

    Edge(int x=,int y=,int nxt=):

        x(x),y(y),nxt(nxt){}

}edge[mx];

void add(int x,int y){

    edge[++sumedge]=Edge(x,y,head[x]);

    head[x]=sumedge;

}

void dfs1(int x){

    dep[x]=dep[fa[x]]+;deep[dep[x]][++deep[dep[x]][]]=x;

    for(int i=head[x];i;i=edge[i].nxt){

        int v=edge[i].y;fa[v]=x;

        dfs1(v);

    }

}

void dfs2(int x,int sum){

    if(sum>=ans)return;flag=;

    for(int i=;i<=deep[x][];i++){

        int v=deep[x][i];

        if(cut[fa[v]]==){flag=;sum++;cut[v]=;}

    }

    if(flag)sum--;

    for(int i=;i<=deep[x][];i++){

        int v=deep[x][i];

        if(cut[v])continue;

        cut[v]=;

        dfs2(x+,sum);

        cut[v]=;

    }

    for(int i=;i<=deep[x][];i++){

        int v=deep[x][i];

        cut[v]=;

    }

    if(flag==)ans=min(ans,sum);

}

int main(){

    scanf("%d%d",&n,&p);

    for(int i=;i<=p;i++){

        scanf("%d%d",&x,&y);

        if(x>y)swap(x,y);

        add(x,y);

    }

    for(int i=;i<=n;i++)cut[i]=;cut[]=;

    dfs1();dfs2(,);

    printf("%d\n",ans);

    return ;

}

巴特西

NOIP2003题解

传送门

T1 神经网络

题目背景

题目描述

输入输出格式

输入输出样例

题目描述

输入输出格式

输入输出样例

题目描述

输入输出格式

输入输出样例

T4传染病控制

题目背景

题目描述

输入输出格式

输入输出样例

最新文章

热门文章