Noip2003提高组

目录

• t1.神经网络
• t2.侦探推理
• t3.加分二叉树
• t4.传染病控制

又逢运动会，又是一个在机房刷题的日子。

---

t1.神经网络

题目

题意：略。

思路：[拓扑排序+模拟] 先处理出一个拓扑序，然后直接模拟即可。

Code:

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
//Mystery_Sky
//
#define M 1000100
#define INF 0x3f3f3f3f
#define ll long long
inline int read()
{
    int x=0,f=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

struct Edge{
    int to, next, w;
}edge[M];
int n, m;
int c[M], u[M], pos[M];
int cnt, head[M], dis[M], out[M], ind[M];
queue <int> q;
vector <int> t;

inline void add_edge(int u, int v, int w)
{
    edge[++cnt].to = v;
    edge[cnt].next = head[u];
    edge[cnt].w = w;
    head[u] = cnt;
}

inline void topo()
{
    for(int i = 1; i <= n; i++) 
        if(!ind[i]) q.push(i), pos[i] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        t.push_back(u); 
        for(int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            ind[v]--;
            if(!ind[v]) q.push(v); 
        }
    } 
}

int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; i++) c[i] = read(), u[i] = read();
    for(int i = 1; i <= m; i++) {
        int u = read(), v = read(), w = read();
        add_edge(u, v, w);
        ind[v]++;
        out[u]++;
    }
    topo();
    for(int a = 0; a < n; a++) {
        int i = t[a];
        if(pos[i] != 1) c[i] -= u[i];
        if(c[i] > 0) {
            for(int x = head[i]; x; x = edge[x].next) {
                int v = edge[x].to;
                c[v] += edge[x].w * c[i];
            }
        }
    }
    bool flag = false;
    for(int i = 1; i <= n; i++) {
        if(out[i] == 0 && c[i] > 0) printf("%d %d\n", i, c[i]), flag = true;
    }
    if(!flag) printf("NULL\n");
    return 0;
}

---

t2.侦探推理

题目

题意：有M个人，其中N个人只说谎话，其余的人只说实话，有P条证词。然后根据证词找出罪犯。

思路：[模拟] 不会，过

Code:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime> 
//Mystery_Sky
//QWQ
using namespace std;
int main (){
    srand(time(0));
    if(rand()%2) printf("Cannot Determine\n");
    else printf("Impossible\n");
    return 0;
}

---

t3.加分二叉树

题目

题意：自行领悟，略。

思路：[dp] 之前在外面培训的时候讲过，然而我好像忘了。设f[i][j]表示从i到j的这一段树的加分，那么枚举i到j之间的节点做根即可。f[i][j] = max{f[i][k-1] + f[k+1][j] + a[k]}(i<k<j)。对于第二问的输出前序遍历，设tree[i][j]为i到j的根节点，最后输出即可。

Code:

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
//Mystery_Sky
//
#define M 30
#define INF 0x3f3f3f3f
#define ll long long
inline int read()
{
    int x=0,f=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n;
ll f[M][M], tree[M][M], a[M];

inline void print(int l, int r)
{
    if(l > r) return;
    printf("%lld ", tree[l][r]);
    if(l == r) return;
    print(l, tree[l][r] - 1);
    print(tree[l][r] + 1, r);
}

int main() {
    n = read();
    for(int i = 1; i <= n; i++) {
        a[i] = read();
        tree[i][i] = i;
        f[i][i] = a[i];
    }
    for(int len = 1; len <= n; len++) {
        for(int i = 1; i + len <= n; i++) {
            int j = i + len;
            tree[i][j] = i;
            f[i][j] = f[i][i] + f[i+1][j];
            for(int k = i + 1; k < j; k++) {
                if(f[i][k-1] * f[k+1][j] + f[k][k] > f[i][j]) {
                    f[i][j] = f[i][k-1] * f[k+1][j] + f[k][k];
                    tree[i][j] = k;
                }
            }
        }
    }
    printf("%lld\n", f[1][n]);
    print(1, n);
    return 0;
}

---

t4.传染病控制

题目

题意：给定一棵树，从根节点开始逐步往下，每次感染一层，每次可以切断树上的一条边，求最少感染人数。

思路：[贪心（错误）]

拿到这道题，首先想到了贪心，就是每次割边的时候割掉与子树最大的点所连的边。然后得了90分。但是事实上这道题目贪心是错误的，能得到90分完全是因为数据过水。

为什么贪心错了呢？举个栗子：如果当前节点有一个左子树和一个右子树，其中左子树是一个很长很长的链，而右子树是一棵比左子树略短的二叉树，那么我们显然应该割掉与右子树相连的边，而贪心却是去割左子树，这样就错了。

Code:

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
//Mystery_Sky
//误人子弟的90分错误贪心
#define M 1000
#define INF 0x3f3f3f3f
#define ll long long
inline int read()
{
    int x=0,f=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct Edge{
    int to, next;
}edge[M];
int n, m, tot, max_dep;
int son[M], dep[M], remain[M], f[M];
int cnt, head[M];

inline void add_edge(int u, int v)
{
    edge[++cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

void dfs(int p, int fa)
{
    if(son[p]) return;
    son[p] = 1;
    for(int i = head[p]; i ; i = edge[i].next) {
        int v = edge[i].to;
        if(v == fa) continue;
        dep[v] = dep[p] + 1;
        max_dep = max(dep[v], max_dep);
        dfs(v, p);
        son[p] += son[v];
        f[v] = p;
    }
}

void del(int p)
{
    remain[p] = 0;
    for(int i = head[p]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(v == f[p]) continue;
        del(v);
    }
    return;
}

void dfs_1(int d)
{
    if(d > max_dep) return;
    int pos = 0, Max = 0; 
    for(int p = 1; p <= n; p++) {
        if(remain[p] && dep[p] == d) {
            for(int i = head[p]; i; i = edge[i].next) {
                int v = edge[i].to;
                if(v == f[p]) continue;
                if(son[v] >= Max) pos = v, Max = son[v];
            }   
        }
    }
    tot += Max;
    del(pos);
    dfs_1(d+1);
}

int main() {
    n = read(), m = read();
    for(int i = 1; i <= m; i++) {
        int u = read(), v = read();
        add_edge(u, v);
        add_edge(v, u);
    }
    dep[1] = 1;
    dfs(1, 0);
    for(int i = 1; i <= n; i++) remain[i] = 1;
    dfs_1(1);
    printf("%d\n", n - tot);
    return 0;
}

正解留坑待补

---

总分：100+10+100+90=300