Solution1028

一:猴猴吃苹果

题目描述

一棵n个节点的树,每个节点一个苹果,从点k出发,每次走苹果最多的一条路径,并且取走路径上的苹果,到达下一个点,重复操作。

问依次经过了哪些点。

数据范围

$n \le 50000$

思路

考场上想的是,每次将一条路径的苹果清空,相当于把树分裂成小的树。

于是用线段树维护dfs序,维护每个点的深度。

然而打挂了。

正解:

考虑到所有终点的集合就是叶子节点,并且取走苹果$i$的那条路径的终点,就是子树$i$的最大深度叶子节点。

dp求节点$i$为根的子树中,最大深度的点$id_i$。同时,求以每个叶子节点为终点的路径长度$f$($\forall id_j=i$,$j$与$i$的最大距离)

回到题目,路径覆盖的顺序就是按照长度(长度就是覆盖苹果数)来的,因此将所有叶子节点$i$按照$f_i$排序。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i = (a);i <= (b);i++)
#define PER(i,a,b) for(int i = (a);i >= (b);i--)
#define SF scanf
#define PF printf
#define DB(...) fPF(stderr,__VA_ARGS__)
#define N 50010
using namespace std;
vector<int>g[N];
int tmp[N];
int len[N],id[N];
int n,k;
int f[N];
bool cmp(const int &i, const int &j) {
    if(f[i] != f[j]) return f[i] > f[j];
    return i < j;
}
void dfs(int u,int fa) {
    len[u] = 1, id[u] = u;
    int sz = g[u].size();
    REP(i,0,sz - 1){
        int v = g[u][i];
        if(v == fa) continue;
        dfs(v,u);
        if(len[u] < len[v] + 1 || (len[u] == len[v] + 1 && id[u] > id[v]))
            len[u] = len[v] + 1, id[u] = id[v];
    }
    f[id[u]] = max(f[id[u]],len[u]);
}

int main(){
//    freopen("apple.in", "r", stdin);
//    freopen("apple.out", "w", stdout);
    cin>>n>>k; k++;
    if(n == 1) return puts("0"), 0;
    REP(i,2,n){
        int x;
        SF("%d",&x);
        g[i].push_back(x + 1);
        g[x + 1].push_back(i);
    }
    dfs(k,0);
    REP(i,1,n) tmp[i] = i;
    sort(tmp + 1, tmp + 1 + n, cmp);
    PF("%d\n",k - 1);
    REP(i,1,n) if(f[tmp[i]])
        PF("%d\n",tmp[i] - 1);
    return 0;
}

二:猴猴吃香蕉

题目描述

n个数,选出一些,使得它们的乘积为k,就方案数。

D组数据。

数据范围

$n\le 1000 \; , \; K\le100000000 \; , \; D\le 20$

思路

向背包一样dp,因为k太大,用map离散化。

一些优化:

只考虑是$k$因数的$a_i$。

只考虑是$k$因数的dp状态。

Code

reverse_iterator 实现反向遍历(用.rbegin(), .rend()

注意:事先把map中的状态位置开好,否则访问之前未访问过的下标时会导致当前iterator错误!

#pragma GCC optimize(2)
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i = (a);i <= (b);i++)
#define PER(i,a,b) for(int i = (a);i >= (b);i--)
#define SF scanf
#define PF printf
#define DB(...) fprintf(stderr,__VA_ARGS__)
#define N 1010
#define MOD 1000000007
using namespace std;
typedef long long ll;
int T,n,k,a[N];
map<int,int>f;
map<int,int>::reverse_iterator it;
int main()
{
//	return 0;
//	freopen("banana.in","r",stdin);
//	freopen("banana.out","w",stdout);
    cin>>T;
    while(T--){
        cin>>n>>k;
        REP(i,1,n) SF("%d",&a[i]);
        f.clear();
        for(int i = 1;i * i <= k;i++)
            if(k % i == 0) f[i] = 0, f[k / i] = 0;
        f[1] = 1;
        REP(i,1,n){
            if(k % a[i]) continue;
            for(it = f.rbegin();it != f.rend();it++){
                ll tmp = (ll)it->first * (ll)a[i];
                if(tmp > (ll)k || (ll)k % tmp) continue;
                (f[tmp] += it->second) %= MOD;
            }
        }
        PF("%d\n",f[k]);
    }
    return 0;
}

三:猴猴的比赛

题目描述

给定两棵大小为n的树,求有多少点对$(u,v)$使得在两棵树中,$u$都是$v$的父亲。

数据范围

$n \le 100000$

思路

dfs序。

在第一棵树中dfs,记录dfs序区间。在树二中dfs到u时,对树一中u的子树的节点+1,回溯时撤销。于是在子树中dfs时,这个子节点对应dfs序上的标记和就表示有几个在两棵树里都是它祖先的节点。

需要的数据结构:区间修改,单点查询。所以用树状数组维护差分。

Code

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i = (a);i <= (b);i++)
#define PER(i,a,b) for(int i = (a);i >= (b);i--)
#define SF scanf
#define PF printf
#define DB(...) fprintf(stderr,__VA_ARGS__)
#define N 100010
using namespace std;
int n,res[N],l[N],r[N],dfn = 0;
int t[N];
vector<int>g[2][N];
void add(int x,int val){
    for(;x <= n;x += x & (-x))
        t[x] += val;
}
int query(int x){
    int sum = 0;
    for(;x;x -= x & (-x))
        sum += t[x];
    return sum;
}
void dfs1(int u,int fa){
    l[u] = ++dfn;
    for(int v : g[1][u]){
        if(v == fa) continue;
        dfs1(v,u);
    }
    r[u] = dfn;
}
void dfs2(int u,int fa){
    res[u] = query(l[u]);
    add(l[u],1); add(r[u] + 1,-1);
    for(int v : g[0][u]){
        if(v == fa) continue;
        dfs2(v,u);
    }
    add(l[u],-1); add(r[u] + 1,1);
}
int main()
{
//  freopen("climb.in","r",stdin);
//  freopen("climb.out","w",stdout);
    memset(t,0,sizeof t);
    cin>>n;
    REP(id,0,1) REP(i,1,n - 1){
        int x,y;
        SF("%d %d",&x,&y);
        g[id][x].push_back(y);
        g[id][y].push_back(x);
    }
    dfs1(1,0);
    dfs2(1,0);
    long long ans = 0;
    REP(i,1,n) ans += res[i];
    cout<<ans<<endl;
    return 0;
}

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注