Processing math: 0%

2018 Multi-University Training Contest 10(HDU)

Posted on | In , ,

补题进度：5/12
雅礼中学出题
2018多校end

题目链接

A

题意

题解

B

题意

题解

C

题意

题解

D

题意

题解

E

题解(树上启发式合并)

  • 因为每个数的约数都不是很多，事实上小于 100000 的数最多只有一百多个约数。
  • 对每个节点开一个set存这个节点所在子树的所有数的因子，不同子树出现两次这个因子即是gcd。
  • 启发式合并set，每次只要保证小的集合往的大的集合合并，这样就能保证复杂度。
  • 时间复杂度O(100·nlogn)
  • 注意每次合并后清空没用的set，否则会MLE

题解(线段树合并)

  • 可以对每个节点的因子开一颗线段树，约数的范围是[1,10^5]，但约数的数量不多，动态开树即可
  • 合并的时候写错了wa了十年(多亏了雨辰
  • 合并后更新要注意到叶子的时候，叶子没有左右儿子。
  • 时间复杂度O(100·nlogn)

代码(树上启发式合并)

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 100000+3;

int read() {
    int x = 0;
    char c = getchar();
    while (c < '0' || c > '9')c = getchar();
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}

vector<int>fac[maxn], g[maxn];
int n, col[maxn],  sz[maxn], son[maxn], Son, maxx, ans[maxn], st[maxn], ed[maxn], cnt, fan[maxn];
set<int>q[maxn], keep;

void init(){
    for(int i=1; i<maxn; i++)
    {
        int k=int(sqrt(i+0.5));
        for(int j=1; j<=k; j++)
            if(i%j==0)
            {
                 fac[i].push_back(j);
                 if(i/j!=j)
                    fac[i].push_back(i/j);
            }
    }
}

void dx(int x,int fa)
{
    sz[x]=1;
    int mx=-1;
    st[x]=++cnt;
    fan[cnt]=x;
    for(int i=0; i<int(g[x].size()); i++)
    {
        int v=g[x][i];
        if(v==fa)  continue;
        dx(v,x);
        sz[x]+=sz[v];
        if(sz[v] > mx){
            son[x]=v;
            mx=sz[v];
        }
    }
    ed[x]=cnt;
}


void dfs(int x,int fa)
{
    for(int i=0;i<int(fac[col[x]].size());i++){
        int v=fac[col[x]][i];
        q[x].insert(v);
    }
    for(int i=0; i<int(g[x].size()); i++){
        int v=g[x][i];
        if(v==fa)   continue;
        dfs(v, x);
        int nowsu=q[x].size(), nowsv=q[v].size();
        if(nowsv > nowsu) swap(q[x], q[v]);
        for(auto &it:q[v])
        {
            if(q[x].count(it))
                ans[x]=max(ans[x], it);
            else
                q[x].insert(it);
        }
        q[v].clear();
    }



}

int main()
{
    init();
    maxx=-1;
    int v;
    n=read();
    for(int i=1; i<=n-1; i++)
    {
        v=read();
        g[v].push_back(i+1);
    }
    for(int i=1; i<=n; i++)
        col[i]=read();
    dx(1, 0);
    dfs(1,0);
    for(int i=1;i<=n;i++){
        if(ans[i]!=0)
        printf("%d\n", ans[i]);
        else puts("-1");
    }
    return 0;
}

代码(线段树合并)

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 200000+7;

int read() {
    int x = 0;
    char c = getchar();
    while (c < '0' || c > '9')c = getchar();
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}

int n,col[maxn], root[maxn], ls[maxn*4*100], rs[maxn*4*100], tot, a[maxn*4*100];
int ans[maxn];
vector<int>fac[maxn], g[maxn];

void init(){
    for(int i=1; i<maxn; i++){
        int k=int(sqrt(i+0.5));
        for(int j=1; j<=k; j++)
            if(i%j==0){
                 fac[i].push_back(j);
                 if(i/j!=j)
                    fac[i].push_back(i/j);
            }
    }
}

void update(int &x,int l,int r,int pos)
{
    if(!x)  x=++tot;
    if(l==r){
        a[x]=pos;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid) update(ls[x], l, mid, pos);
    else update(rs[x], mid+1, r, pos);
    a[x]=max(a[ls[x]], a[rs[x]]);
}

int mergetree(int x,int y,int &ans)
{
    if(!x || !y) return x|y;
    if(a[x] == a[y]) ans=max(ans, a[x]);
    if(ls[x]||ls[y]) ls[x]=mergetree(ls[x],ls[y],ans);
    if(rs[x]||rs[y]) rs[x]=mergetree(rs[x], rs[y], ans);
    a[x]=max(a[x], max(a[ls[x]], a[rs[x]]));  // 
    return x;
}
void dfs(int x)
{
    for(int i=0;i<int(g[x].size());i++)
    {
        int v=g[x][i];
        dfs(v);
        mergetree(root[x], root[v], ans[x]);
    }
}

int main()
{
    init();
    int v;
    n=read();
    for(int i=1; i<=n-1; i++)
    {
        v=read();
        g[v].push_back(i+1);
    }
    for(int i=1; i<=n; i++)
    {
        col[i]=read();
        for(int j=0;j<int(fac[col[i]].size());j++){
            update(root[i], 1, 100000, fac[col[i]][j]);
        }
    }
    dfs(1);
    for(int i=1;i<=n;i++){
        if(ans[i]!=0)
        printf("%d\n", ans[i]);
        else puts("-1");
    }
}

另一个启发式合并

F

题意

题解

G

OEIS一下就好了啊

H

大数问题
大数板子或者Java
这样也可以过

1
cout << fixed << setprecision(0) << pow(2,n)<< endl;

但这样会挂

1
printf("%.0f\n", pow(2, n));

I

找规律发现第 i 个所有的 (i+j,i-j) 互质的个数为\frac{phi[2·i]}{2}。

J

题解

  • 实际上主副武器的S都是不变的，变化的只有x_i，|x_{mi}-x_{si}|=max(x_{mi}-x_{si}，x_{si}-x_{mi})
  • 考虑k，每个x[i]都有两种情况(+或-)，一共只有n·2^k种状态。
  • 暴力考虑所有主武器的状态，和副武器的状态进行匹配即可
  • 时间复杂度O(n·2^k)
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
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 1e5+3;

int sz[maxn], sf[maxn];
ll ansz[300], ansf[300];

int t, n, m, k , xm[6], xs[6];

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d", &n, &m, &k);
        for(int i=0;i<300;i++)
            ansz[i]=ansf[i]=-100000000000000000;
        for(int i=1;i<=n;i++){
            scanf("%d", &sz[i]);
            for(int j=0;j<k;j++)
            scanf("%d", &xm[j]);
            for(int j=0;j<(1<<k);j++){
                int t=j;
                ll now=0;
                for(int w=0;w<k;w++){
                    if((1<<w) & t)
                        now += xm[w];
                    else
                        now -= xm[w];

                }
                ansz[t]=max(ansz[t], now+sz[i]);
            }
        }
        for(int i=1;i<=m;i++){
            scanf("%d", &sf[i]);
            for(int j=0;j<k;j++)
                scanf("%d", &xs[j]);
            for(int j=0;j<(1<<k);j++){
                int t=j;
                ll now=0;
                for(int w=0;w<k;w++){
                    if((1<<w) & t)
                        now += xs[w];
                    else
                        now -= xs[w];
                }
                ansf[t]=max(ansf[t], now + sf[i]);
            }
        }
        ll ans=0;
        for(int i=0;i<(1<<k);i++)
            ans=max(ans, ansz[i] + ansf[(1<<k)-1-i]);
        
        printf("%lld\n", ans);
    }
    return 0;
}

K

题意

题解

L

题意

题解