NOIP2003提高组题解

\(D1T1\) 神经网络 \((OK)\)

\(D1T2\) 侦探推理

\(D1T3\) 加分二叉树 \((OK)\)

\(D1T4\) 传染病控制 \((OK)\)

这年的题之前都没做过,而且都是绿题蓝题,\(T2\)听说是字符串+大模拟,走了走了.

\(T1\)很明显的拓扑排序啊.注意几个细节就行,只有状态大于\(0\),才能传递状态,然后这个点已经传递完之后它的状态就是\(0\)了,最后输出只要输出大于\(0\)的状态.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=105;
int n,m,c[N],d[N],deg[N],w[N][N];
queue<int>q;
int main(){
    n=read();m=read();
    for(int i=1;i<=n;++i){
        c[i]=read(),d[i]=read();
        if(c[i])q.push(i);
    }
    memset(w,0x3f,sizeof(w));
    for(int i=1;i<=m;++i){
        int a=read(),b=read(),v=read();
        w[a][b]=v;if(!c[b])++deg[b];
    }
    while(q.size()){
        int u=q.front(),bj=0;q.pop();
        if(c[u]<=0)continue;
        for(int i=1;i<=n;++i){
            if(w[u][i]==0x3f3f3f3f||!deg[i])continue;
            --deg[i];c[i]+=w[u][i]*c[u];
            if(!deg[i]){c[i]-=d[i];q.push(i);};
            bj=1;
        }
        if(bj)c[u]=0;
    }
    int bj=0;
    for(int i=1;i<=n;++i)if(c[i]>0){printf("%d %d\n",i,c[i]);bj=1;} 
    if(!bj)puts("NULL");
    return 0;
}

\(T2\)咕咕咕.

\(T3\)"树的中序遍历对应的是一段区间",所以这道题就这么由树形结构转化到了区间\(DP\).设\(f[i][j]\)表示区间\([i,j]\)构成一棵树产生的最大得分.

初始化\(f[i][i]=a[i]\),然后一般区间\(DP\)都是从区间长度为2开始\(DP\)转移,但是这道题我这么写的时候写挂了,于是就把区间长度为\(2\)也放进了初始化中,\(f[i][i+1]=a[i]+a[i+1]\).

那么\(f[i][j]=max(f[i][j],f[i][k-1]*f[k+1][j]+a[k]),i+1<=k<=j-1\).

然后题目还要输出前序遍历,所以转移的时候记录一下区间\([i,j]\)构成的树是以哪个节点为根的就行.最后递归输出即可.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=31;
int a[N],g[N][N];ll f[N][N];
inline void print(int l,int r){
    if(l>r)return;
    if(l==r){printf("%d ",l);return;}
    printf("%d ",g[l][r]);
    print(l,g[l][r]-1);print(g[l][r]+1,r);
}
int main(){
    int n=read();for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)f[i][j]=1;
    for(int i=1;i<=n;++i)f[i][i]=a[i];
    for(int i=1;i<n;++i)f[i][i+1]=a[i]+a[i+1],g[i][i+1]=i;
    for(int len=3;len<=n;++len){
        for(int i=1;i+len-1<=n;++i){
            int j=i+len-1;
            for(int k=i+1;k<=j-1;++k){
                if(1ll*f[i][k-1]*f[k+1][j]+a[k]>f[i][j]){
                    f[i][j]=1ll*f[i][k-1]*f[k+1][j]+a[k];
                    g[i][j]=k;
                }
            }
        }
    }
    printf("%lld\n",f[1][n]);print(1,n);printf("\n");
    return 0;
}

\(T4\)这种数据范围明明很不像爆搜题啊,我真的佛了.传染是一层一层的传染,所以我们一层一层地搜,每一层枚举断掉哪条边(即哪个子节点不会被感染),就把这个以子节点为根的子树都标记为安全状态.

\(dfs\)预处理出每一层有哪些节点,每个节点有哪些子节点.刚开始用的\(vector\),会\(T\).改成二维数组就行了.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=305;
int n,p,ans=N,depth;
int dep[N],size[N],safe[N],g[N][N],son[N][N];
int tot,head[N],nxt[N<<1],to[N<<1];
inline void add(int a,int b){nxt[++tot]=head[a];head[a]=tot;to[tot]=b;}
inline void dfs(int u,int fa){
    size[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];if(v==fa)continue;
        son[u][++son[u][0]]=v;;dep[v]=dep[u]+1;
        dfs(v,u);size[u]+=size[v];
    }
}
inline int calc(int dep){
    int sum=0;
    for(int i=1;i<=g[dep][0];++i)
        if(!safe[g[dep][i]])++sum;
    return sum;
}
inline void play_bj(int i,int val){
    for(int j=1;j<=son[i][0];++j){
        safe[son[i][j]]=val;
        play_bj(son[i][j],val);
    }
}
inline void DFS(int now,int has){//now:当前层数,has:当前被感染的点数
    if(has>=ans)return;//最优性剪枝
    if(now>depth){ans=has;return;}//搜完了更新答案
    int down=0;//标记这一层是否有节点不是安全状态
    for(int i=1;i<=g[now][0];++i){
        if(safe[g[now][i]])continue;//已经安全了就不管
        down=1;
        safe[g[now][i]]=1;play_bj(g[now][i],1);//标记这个点及其子树内所有点
        DFS(now+1,has+calc(now));
        safe[g[now][i]]=0;play_bj(g[now][i],0);
    }
    if(!down){ans=has;return;}//如果这一层的所有节点都是安全状态,直接更新答案,不加这一句会WA而不是T?
}
int main(){
    n=read();p=read();
    for(int i=1;i<=p;++i){int a=read(),b=read();add(a,b);add(b,a);}
    dep[1]=1;dfs(1,0);
    for(int i=1;i<=n;++i)g[dep[i]][++g[dep[i]][0]]=i,depth=max(depth,dep[i]);
    DFS(2,1);printf("%d\n",ans);//从第2层开始搜
    return 0;
}

NOIP2003提高组题解

原文：https://www.cnblogs.com/PPXppx/p/11826161.html