2018 Multi-University Training hdu Contest 3

Posted on | In , | Visitors:

嚯嚯嚯！补题！

hdu多校总链接

补题： 6题/13题

  • 状压
  • __builtin_popcount(i);
  • 分块dp

A. Ascending Rating

若是按照顺序的话，我们会将比他大的继续放着，比他小或者等于的删除，但是这样的话，比如7674821的时候，对于6的时候，又要开始重新计算；所以我们开始想倒序；

用单调队列维护一个严格的单调递减序列；我们将队列的内容置为下标，这样的话，我们可以知道队尾即最大值的下标j，这样我们就可以知道长度为j-now+1；于是我们可以轻易找到长度为m的maxrating和count的值了

忘记了初始化A和B，同时注意计算a[i]的时候会爆int

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=1e7+10;
int a[maxn],qu[maxn];
int head,tail;
int n,m,k,p,q,r,mod;
ll A,B;
int main(){
    int T;scanf("%d",&T);
    while(T--){
		A=0;B=0;
        scanf("%d%d%d%d%d%d%d",&n,&m,&k,&p,&q,&r,&mod);
        for(int i=1;i<=k;i++) scanf("%d",&a[i]);
        for(int i=k+1;i<=n;i++)
            a[i]=(1LL*p*a[i-1]%mod+1LL*q*i%mod+r)%mod;
        
        if(m>n){
            printf("0 0\n");
            continue;
        }
        head=tail=0;
        for(int i=n;i>n-m+1;i--){
            while(head>tail&&a[qu[head-1]]<=a[i]) head--;
            qu[head++]=i;
        }
        for(int i=n-m+1;i>=1;i--){
            while(head>tail&&a[qu[head-1]]<=a[i]) head--;
            qu[head++]=i;
            A+=(ll)a[qu[tail]]^i;
            B+=(ll)(head-tail)^i;
            while(tail<head&&i+m-2<qu[tail]) tail++;
        }
        printf("%lld %lld\n",A,B);
    }
    return 0;
}

C. Dynamic Graph Matching

f[i][S]表示前i次操作之后，S集合的点已经匹配的方案数。

对于加边操作，显然$f[i][S]=f[i−1][S]+f[i−1][S−u−v]$。i这一维可以省略，从大到小遍历S，$f[S]+=f[S−u−v]$。

对于删边操作，注意到加边操作的顺序不影响结果，可以假设第i−1次操作是加入要删除的边。将加边操作的更新倒过来，得到：从小到大遍历S，$f[S]−=f[S−u−v]$。

看数据规模，我们可以用状态压缩；借用cnt[i]=__builtin_popcount(i);统计1的个数；

这里脑抽了一下，计算中不用-而应该使用|，这样才可以加入新的点，否则会导致进位；

比如10[2]和11[6]会导致出现100[8]的现象；当然我们可以通过先用if(!(i&x))判断是否有借位，所以那个地方的代码有三种写法

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=(1<<12);
const int mod=1e9+7;
ll dp[maxn],cnt[maxn],ans[12];
int n,m,a,b,x;
char op[3];
void init(){
    for(int i=0;i<maxn;i++) cnt[i]=__builtin_popcount(i);//统计1的个数
}
int main(){
    int T;scanf("%d",&T);
    init();
    while(T--){
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&n,&m);
        dp[0]=1;
        while(m--){
            scanf("%s %d %d",op,&a,&b);
            a--;b--;
            x=((1<<a)|(1<<b));
            if(op[0]=='+'){
                for(int i=((1<<n)-1);i>=0;i--){
                    if(!(i&x))
                    dp[i|x]=(dp[i]+dp[i|x])%mod;
                    //dp[i^x]=(dp[i]+dp[i^x])%mod;
                    //dp[i+x]=(dp[i]+dp[i+x])%mod;都是可以的
                }
            }else{
                for(int i=0;i<=((1<<n)-1);i++){
                    if(!(i&x))
                    dp[i|x]=(dp[i|x]-dp[i]+mod)%mod;
                    //dp[i^x]=(dp[i^x]-dp[i]+mod)%mod;
                    //dp[i+x]=(dp[i+x]-dp[i]+mod)%mod;都是可以的
                }
            }
            memset(ans,0,sizeof(ans));
            for(int i=0;i<=((1<<(n+1))-1);i++){
//                if(dp[i]){
//                    bitset<12>aa(i);
//                    cout<<aa<<endl;
//                    cout<<dp[i]<<" "<<cnt[i]<<endl<<endl;
//                }
                ans[cnt[i]]=(ans[cnt[i]]+dp[i])%mod;
            }
            for(int i=2;i<n;i+=2){
                printf("%lld ",ans[i]);
            }
            printf("%lld\n",ans[n]);
        }
    }
    return 0;
}

D. Euler Function

观察素数打表公式可知：

euler[1]=1

对于素数来说就是euler[i]=i-1，除了2的素数以外，euler[i]一定是一个偶数，所以除了3以外euler[i]一定是一个合数；【这里我们可以知道素数里只有2，3的欧拉值不是合数】

对于合数来说，p=q1^a1*q2^a2*……qn^an，且q1<q2<……qn，则euler[j]=j/q1*(q1-1)/q2*(q2-1)……=q1^(a1-1)*q2^(a2-1)*……qn^(an-1)*(q1-1)*(q2-1);

所以只有当所有因子都是1【但是qi的值各不相同】，或者只含有素数一个因子，且一次方的时候【这个显然不可以，除非只含有一个3和一个2的一次方的因子的时候】；且qi的值不为1,所以euler[j]=2【q1=2 a1=2】【q1=2 a1=1 q2=3 a2=1】即为4,6的时候，对于其余的合数均为合数；

综上所述当1 2 3 4 6为合数，其余均为质数

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=105;
int euler[maxn];
void getEuler(){
    memset(euler, 0, sizeof(euler));
    euler[1]=1;
    for(int i=2;i<maxn;i++){
        if(!euler[i]){
            for(int j=i;j<maxn;j+=i){
                if(!euler[j])
                    euler[j]=j;
                euler[j]=euler[j]/i*(i-1);
            }
        }
    }
}
int main(){
//    getEuler();
//    for(int i=1;i<maxn;i++)
//        cout<<euler[i]<<endl;
    int T;scanf("%d",&T);
    int k;
    while(T--){
        scanf("%d",&k);
        if(k==1){
            printf("5\n");
        }else{
            printf("%d\n",k+5);
        }
    }
    return 0;
}

F. Grab Tree

现将每一个数都异或起来，这样对于最高位来说一定是由奇数个1异或出来的，所以只要先手拿到最高位的1就可以了；当所有数异或出来是0的时候，假设Q拿的是A，T拿的是B，则A^B一定是0，则A和B一定相同，所以平局

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll sum;
int n,x,y;
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        scanf("%lld",&sum);
        for(int i=1;i<n;i++){
            scanf("%d",&x);
            sum=sum^x;
        }
        for(int i=1;i<n;i++){
            scanf("%d%d",&x,&y);
        }
        if(sum==0) printf("D\n");
        else printf("Q\n");
    }
    return 0;
}

G. Interstellar Travel

坐标相同的点，选择编号最小的最优，这样字典序才会小；

It is guaranteed that y1=yn=0

H. Monster Hunter（未完成

优先队列+并查集

刚开始觉得，直接根据策略，选择最优的就可以，后来发现不是这样的，如下数据，就会导致我可能会先走减少血，但之后大幅加血的路

1
2
3
4
5
6
7
8
9
10
1
5
10 1
3 8
7 3
17 18
4 1
1 5
3 4
4 2

所以，从头开始分析

L. Visual Cube

先画了横的边，之后再画侧面的边，剩余点填充.

本来想直接打印的，但是总结不好，就用无脑方式啦！

打了一些漂亮的立方体，暗暗戳戳动次打次的博博，想回宿舍了【快十点半了哟

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
6 2 1
....+-+-+-+-+-+-+
.../././././././|
..+-+-+-+-+-+-+.+
./././././././|/.
+-+-+-+-+-+-+.+..
|.|.|.|.|.|.|/...
+-+-+-+-+-+-+....
6 2 4
....+-+-+-+-+-+-+
.../././././././|
..+-+-+-+-+-+-+.+
./././././././|/|
+-+-+-+-+-+-+.+.+
|.|.|.|.|.|.|/|/|
+-+-+-+-+-+-+.+.+
|.|.|.|.|.|.|/|/|
+-+-+-+-+-+-+.+.+
|.|.|.|.|.|.|/|/.
+-+-+-+-+-+-+.+..
|.|.|.|.|.|.|/...
+-+-+-+-+-+-+....
1 1 1
..+-+
././|
+-+.+
|.|/.
+-+..
6 3 1
......+-+-+-+-+-+-+
...../././././././|
....+-+-+-+-+-+-+.+
.../././././././|/.
..+-+-+-+-+-+-+.+..
./././././././|/...
+-+-+-+-+-+-+.+....
|.|.|.|.|.|.|/.....
+-+-+-+-+-+-+......
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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a,b,c;
char G[105][105];
int row,col;
int dot,nex;//从nex行开始右边有i-nex+1个点；从1到dot行左边有dot-i+1个点
int tmp,i,j;
int main(){
    int T;scanf("%d",&T);
    while(T--){
        memset(G,'.',sizeof(G));
        scanf("%d%d%d",&a,&b,&c);
        dot=2*b;col=dot+1+2*a;row=dot+1+2*c;
        for(i=1;i<=dot;i++){
            j=dot-i+2;
            if(i&1){
                G[i][j++]='+';
                for(int k=1;k<=a;k++){
                    G[i][j++]='-';G[i][j++]='+';
                }
            }
            else{
                G[i][j++]='/';
                for(int k=1;k<=a;k++){
                    G[i][j++]='.';G[i][j++]='/';
                }
            }
        }
        
        j=1;G[i][j++]='+';
        for(int k=1;k<=a;k++){
            G[i][j++]='-';G[i][j++]='+';
        }
        i++;
        
        for(int k=1;k<=c;k++){
            j=1;G[i][j++]='|';
            for(int x=1;x<=a;x++){
                G[i][j++]='.';G[i][j++]='|';
            }
            i++;
            j=1;G[i][j++]='+';
            for(int x=1;x<=a;x++){
                G[i][j++]='-';G[i][j++]='+';
            }
            i++;
        }
        
        j=col;i=2;
        for(int k=1;k<=b;k++){
            i=k*2;
            for(int x=1;x<=c;x++){
                G[i++][j]='|';G[i++][j]='+';
            }
            j--;
            i=k*2+1;
            for(int x=1;x<=c;x++){
                G[i++][j]='.';G[i++][j]='/';
            }
            j--;
        }
        for(i=1;i<=row;i++){
            for(j=1;j<=col;j++){
                printf("%c",G[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}

M. Walking Plan

首先最直接的思路就是

$dp[k][i][j]=min(dp[k-y][i][x]+dp[y][x][j],dp[k][i][j]);$

但是这样的话时间复杂度就是10000*50*50*50，就会爆掉；于是想到分块做，我们分为100为一块；

首先处理0-100的我们放在dp数组中，dp[k][i][j]表示恰好经过k条边从i走到j点的最短路

之后，通过每次叠加dp[100][i][j]，用dp1[k][i][j]表示恰好经过100*k条边从i走到j点的最短路

最后处理余数的k条边，首先将dist用最短路处理，那么dp2[k][i][j]表示至少经过k条边从i走到j点的最短路

这样对于任意两个点我们都可以通过dp1[k/100][i][x]+dp2[k%100][x][v]来构成

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=55;
const int INF=0x3f3f3f3f;
int dist[maxn][maxn];
int dp[105][maxn][maxn];
int dp1[105][maxn][maxn];
int dp2[105][maxn][maxn];
int n,m,u,v,w,q,x,y,ans;
void init(){
    memset(dist,INF,sizeof(dist));
    memset(dp,INF,sizeof(dp));
    memset(dp1,INF,sizeof(dp1));
    memset(dp2,INF,sizeof(dp2));
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        init();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&u,&v,&w);
            dist[u][v]=min(dist[u][v],w);
        }
        
        for(int i=1;i<=n;i++) dp[0][i][i]=0;
        for(int k=1;k<=100;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    for(int x=1;x<=n;x++){
                        dp[k][i][j]=min(dp[k-1][i][x]+dist[x][j],dp[k][i][j]);
                    }
                }
            }
        }
        
        for(int i=1;i<=n;i++) dp1[0][i][i]=0;
        for(int k=1;k<=100;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    for(int x=1;x<=n;x++){
                        dp1[k][i][j]=min(dp1[k-1][i][x]+dp[100][x][j],dp1[k][i][j]);
                    }
                }
            }
        }
        
        for(int i=1;i<=n;i++) dist[i][i]=0;
        
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
                }
            }
        }
        
        for(int k=0;k<=100;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    for(int x=1;x<=n;x++){
                        dp2[k][i][j]=min(dp[k][i][x]+dist[x][j],dp2[k][i][j]);
                    }
                }
            }
        }
        
        scanf("%d",&q);
        while(q--){
            scanf("%d%d%d",&u,&v,&w);
            x=w/100;y=w%100;
            ans=INF;
            for(int i=1;i<=n;i++){
//                cout<<dp1[x][u][i]<<" "<<dp2[y][i][v]<<endl;
                ans=min(ans,dp1[x][u][i]+dp2[y][i][v]);
            }
            if(ans==INF) printf("-1\n");
            else printf("%d\n",ans);
        }
    }
    return 0;
}

题解的思路是将合并的过程看作乘法，则 $f[t] = f[x]f[t − x] = G^t $

同样他也经过分块的处理，之后

设a[i] = G^{100i} , b[i] = G^i，那么 a[i] 即为经过恰好 100i 条边的最短路，对于 b[i] 需要再进行一次Floyd 得到至少i 条边的最短路。

枚举中间点u，则 ans = min(a[A][s][u] + b[B][u][t])

也就是说，在计算dp1和dp2数组的时候，他利用了线性代数中的矩阵的乘法，这点感觉很厉害呢！

不过时间复杂度是一样的，估计常数不同啦！

碎碎念

2018.08.24

说好的前几场超级简单的呢！

嚯嚯嚯！明天去看漫威！

2018.08.27

校园里人越来越多了呢！

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽