「ZROI 2018」0821 暑假普转提模拟赛

发表于 | | 阅读次数:
字数统计: 1k 字

题目列表

  1. 「A 酱的体育课」
  2. 「B 酱的无向图」
  3. 「C 酱的商店」

A. 「A 酱的体育课」

因为期望具有可加性，于是我们可以考虑第 $i$ 个人在第 $j$ 个位置对答案的贡献，累加即可。

时间复杂度：$O(n^2)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
 
#include <cstdio>
const int N=1005;
int n;
double u,v,c[N],d[N];
int main() {
    scanf("%d%lf%lf",&n,&v,&u);
    for(int i=1;i<=n;++i) scanf("%lf",&c[i]);
    for(int i=1;i<=n;++i) scanf("%lf",&d[i]);
    double ans=0;
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) ans+=1.0*u/(c[i]-(j-1)*d[i]-v);
    printf("%.3lf\n",ans);
    return 0;
}

B. 「B 酱的无向图」

对于所有不会构成环的边建树，其维护深度和父节点。

对于会构成环的边，暴力向上爬，把环中的所有点用并查集缩点。

最后，树上没有被缩起来的点即为桥。

时间复杂度：$O(n\cdot\alpha(n))$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
#include <cstdio>
#include <algorithm>
const int N=500005;
struct Edge {
    int to,nxt;
}e[N<<1];
int n,m,p,tot,hd[N],ff[N],fa[N],dep[N],u[N],v[N];
bool mark[N],vis[N];
int find(int x) {return x==ff[x]?x:ff[x]=find(ff[x]);}
void add(int u,int v) {
    e[++tot].to=v;
    e[tot].nxt=hd[u];
    hd[u]=tot;
}
void dfs(int u) {
    dep[u]=dep[fa[u]]+1; ff[u]=u; vis[u]=1;
    for(int i=hd[u];i;i=e[i].nxt) {
        int v=e[i].to;
        if(v!=fa[u]) fa[v]=u,dfs(v);
    }
}
void jump(int &x) {x=ff[x]=find(fa[x]);}
int main() {
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;++i) ff[i]=i;
    for(int i=1;i<=m;++i) {
        scanf("%d%d",&u[i],&v[i]);
        int fu=find(u[i]),fv=find(v[i]);
        if(fu^fv) {
            ff[fu]=fv; mark[i]=1;
            add(u[i],v[i]); add(v[i],u[i]);
        }
    }
    for(int i=1;i<=n;++i) if(!vis[i]) dfs(i);
    long long sum=0,ans=1LL;
    for(int i=1;i<=m;++i) {
        if(mark[i]) ++sum;
        else {
            int x=find(u[i]),y=find(v[i]);
            int loopsize=0;
            while(x^y) {(dep[x]<dep[y])?jump(y):jump(x);loopsize++;}
            sum-=loopsize;
        }
        ans=(1LL*ans*(sum+1))%p;
    }
    printf("%lld\n",ans);
    return 0;
}

C. 「C 酱的商店」

由于在树上直接进行背包的复杂度是 $O(m^2)$ 的，所以需要进行 $\text{DP}$ 的优化。

考虑在树上的 $\text{DFS}$ 序上进行 $01$ 背包 $\text{DP}$，各种细节在代码中都有实现和写明（状态和转移等都与一般的背包问题类似）。

时间复杂度：$O(nm\log m)$（$\text{DFS}$ 序多重背包和二进制优化）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=4005;
int n,m,tot,cnt,w[N],s[N],c[N],hd[N],en[N],b[N],f[N][N];
struct Edge {
    int to,nxt;
}e[N];
void add(int u,int v) {
    e[++tot].to=v;
    e[tot].nxt=hd[u];
    hd[u]=tot;
}
void dfs(int x) {
    b[++cnt]=x;
    for(int i=hd[x];i;i=e[i].nxt) dfs(e[i].to);
    en[x]=cnt;
}
void solve() {
    memset(f,-0x3f,sizeof(f));
    f[1][0]=0;
    for(int i=1;i<=n;++i) {
        for(int j=0;j<=m;++j) f[en[b[i]]+1][j]=max(f[en[b[i]]+1][j],f[i][j]);
        int ss=s[b[i]]-1,cc=c[b[i]],ww=w[b[i]];
        for(int j=m;j>=0;--j) {
            if(j>=cc) f[i][j]=(f[i][j-cc]>=0?f[i][j-cc]+ww:-(1<<30));
            else f[i][j]=-(1<<30);
        }
        for(int k=1;k<=ss;ss-=k,k<<=1)
            for(int j=m;j>=k*cc;--j) f[i][j]=max(f[i][j],f[i][j-k*cc]+k*ww);
        if(ss) for(int j=m;j>=ss*cc;--j) f[i][j]=max(f[i][j],f[i][j-ss*cc]+ss*ww);
        for(int j=0;j<=m;++j) f[i+1][j]=max(f[i+1][j],f[i][j]);
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int p,i=2;i<=n;++i) scanf("%d",&p),add(p,i);
    for(int i=1;i<=n;++i) scanf("%d%d%d",&w[i],&c[i],&s[i]);
    cnt=0; dfs(1);
    solve();
    for(int i=1;i<=m;++i) {
        f[n+1][i]=max(f[n+1][i],f[n+1][i-1]);
        printf("%d%c",f[n+1][i]," \n"[i==m]);
    }
    return 0;
}
0%