[原创]第十四届浙江省赛 ZOJ 3962~3965 【E,F,G,H】 (其他并不准备补。)

2017-04-22 23:30:04 Tabris_ 阅读数：829

博客爬取于2020-06-14 22:40:55
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/70478134

EF是纯自己做的,G,H是参(chao)考(xi)了dalao们的思(dai)路(ma)才补上的.

ZOJ 3962 E Seven Segment Display

————————————————————————————————————————————

现在就是有一个8位16进制的一个数x，数字[0,F]有自己的贡献 ,问你[x,x+n]的数中的贡献和是多少,
(注意FFFFFFFF+1 是00000000)

解题思路:
当时想的是数位dp
每次计算当前数字为i的时候的结果,然后超时了, 最后测试发现是被卡卡常了
最最后终于观察到,有几个数字的贡献是一样的,贡献只有[2,7]6种,这样的话 ,我就枚举6种贡献的数字,算式优化了下常数,然后AC…

其他处理的时候就是注意要是超过了0xffffffff 将区间变成首尾的两段和就行了.

附本题代码
————————————————————————————————————————

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
# include<stdio.h>
# include<math.h>
# include<string.h>

typedef long long int LL;

using namespace std;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int val[16]={6,2,5,5,4,5,6,3,7,6,6,5,4,5,5,4};
char a[45];
int getnum(char a){
    if(a>='0'&&a<='9')return a-'0';
    return a-'A'+10;
}

int num[30],len;
LL dp[30][16+2][10];


LL dfs(int pos,int pre,bool limit,int sum,int &n){
    if(pos<0) return sum;
    if(!limit&&dp[pos][sum][n]!=-1) return dp[pos][sum][n];

    int endi = 15; if(limit) endi = num[pos];

    LL res = 0;
    for(int i=0;i<=endi;i++)
        res+=dfs(pos-1,i,limit&&(endi==i),sum+(val[i]==n),n);

    if(!limit) dp[pos][sum][n] = res;
    return res;
}

LL solve(LL n,int i){
    if(n<0) return 0;
    len = 0;LL tem = n;
    while(n){
        num[len++]=n%16;
        n/=16;
    }
    LL ans = dfs(len-1,0,1,0,i);
    if(i == val[0])  ans+=(tem+1)*(8-len);//前导0;
    return ans;
}

int main(){
    memset(dp,-1,sizeof(dp));
//    for(int i=0;i<16;i++) solve(1ll*0xffffffff,i);

    int t=read();
    while(t--){
        int n=read();n--;

        LL nn = 0;
        for(int i=0;i<8;i++)  nn=(nn<<4)+getnum(getchar());

        LL n16 = 0xffffffff;

        LL ans = 0;
        if(nn+n<=n16){
            for(int i=2;i<=7;i++)
                ans+=(solve(nn+n,i)-solve(nn-1,i))*i;
        }
        else {
            for(int i=2;i<=7;i++)
                ans+=(solve(n16,i)-solve(nn-1,i))*i;
            for(int i=2;i<=7;i++)
                ans+=solve(nn+n-n16-1,i)*i;
        }
        printf("%lld\n",ans);
    }
    return 0;
}


ZOJ 3963 F Heap Partition

————————————————————————————————————————————

现在有一个序列，让你把它分成几个集合，使得每个集合中的数能被放到最大堆上，其父子节点关系满足sj≤siandj<is_j ≤ s_i and j < i

首先很容易想到，就是找这个数前面有没有比它小的，有就作为这个数的儿子就好了，
注意的是一个节点只有两个儿子，明确这个，随便搞搞就行了。

（其实我这个并查集是不用的，只需要写个数组映射过去就好，当时纯属脑抽

附本题代码
————————————————————————————————————————————

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
105
106
# include <bits/stdc++.h>
using namespace std;

const int N = 100000+7000;

int a[N],h[N];
int n;
int sum[N];

# define lowbit(x) (x&-x)
void update(int i,int v){
    for(;i<=n;i+=lowbit(i)) sum[i]+=v;
}
int getSum(int i){
    int ans = 0;
    for(;i;i-=lowbit(i)) ans+=sum[i];
    return ans;
}

int BS(int x){
    int l=1,r=n,mid,ans;
    while(l<=r){
        mid = r+l >>1;
        if(getSum(mid)>=x) r=mid-1,ans = mid;
        else   l=mid+1;
    }
    return ans;
}

int pre[N];
int findi(int x){
    int r = x;
    while(r!=pre[r])r=pre[r];

    int i=x,j;
    while(i!=r){
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;
}

void join(int x,int y){
    int fx=findi(x),fy=findi(y);
    pre[fy]=fx;
}

vector<int >G[N];

int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        int ans = 0,x,y;
        scanf("%d",&n);

        for(int i=1;i<=n;i++) pre[i]=i;

        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            int flag = getSum(a[i]);
            if(flag){
                x = BS(flag);
                update(x,-1);
                join(h[x],i);
            }
            update(a[i],2);
            h[a[i]]=i;
        }

//        for(int i=1;i<=n;i++){
//            printf("%d %d\n",h[i],pre[i]);
//        }

        for(int fi,i=1;i<=n;i++){
            fi = findi(i);
            if(fi==i) {
                ans++;
                G[i].push_back(0);
            }
            G[fi].push_back(i);
        }

        printf("%d\n",ans);
        for(int i=1;i<=n;i++){
            int sz = G[i].size();
//            printf("%d  ++\n",sz);
            if(sz){
                printf("%d",sz-1);
                for(int j=1;j<sz;j++)printf(" %d",G[i][j]);
                puts("");
            }
        }


        for(int i=1;i<=n;i++){
            sum[i]=0;
            G[i].clear();
        }

    }
    return 0;
}


ZOJ 3964 G Yet Another Game of Stones

————————————————————————————————————————————
有N堆石子，Alice和Bob轮流取石子，现在规定对于每堆石子Bob想怎么拿怎么拿，但是堆Alice不一样
如果对应$b_i = 0\ $ 那么对Alice也没有限制
如果对应$b_i = 1\ $ 那么对Alice只能拿奇数个石子
如果对应$b_i = 2\ $ 那么对Alice只能拿偶数个石子
对于不能操作的人输,Alice先手,问你谁是赢家

首先考虑,如果$b_i = 0\ $恒成立，那么就是退化为最基本的Nim游戏即可。

然后考虑有$b_i = 1\的情况，如果对应的的情况，如果对应的a_i = 1\，那么就相当于，那么就相当于b_i = 0\，除去， 除去a_i = 1\的情况发现一个的时候相当于先后手交换。那么显然如有两个以上的情况发现一个的时候相当于先后手交换。那么显然如有两个以上b_i = 1\ $Alice一定输。

然后考虑有$b_i = 2\的情况，如果对应的的情况，如果对应的a_i %2= 1 \，那么在Bob不傻的情况下Alice一定取不完这堆。如果有多个，那么在Bob不傻的情况下Alice一定取不完这堆。如果有多个b_i = 2\ $ 那么Bob至少能使其中一堆变成$a_i %2= 1 \ $，那么Alice还是输。

能确定$b_i = 1\和和b_i = 2\ $之多只能由一种且只有一个Alice才有可能赢。

最后大力讨论一下就好了。

（学习了这种分类讨论实现起来666的姿势

附本题代码
————————————————————————————————————————————

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
int _,n;
int  a[N],b[N];

bool solve(){
    int ans = 0;
    bool flag = false;
    for(int i=1;i<=n;i++){
        if(b[i]==0)          ans^=a[i];
        else if(b[i]==1){
            if(a[i]==1)ans^=1;
            else {
                if(flag ) return false;
                flag = true;
                if(~a[i]&1) ans^=1;
            }
        }
        else {
            if(a[i]&1) return false;
            if(flag)  return false;
            flag = true;
        }
    }
    return flag?ans==0:ans;
}

int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)       scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)       scanf("%d",&b[i]);
        puts(solve()?"Alice":"Bob");
    }
    return 0;
}

ZOJ 3965 H Binary Tree Restoring

————————————————————————————————————————————
给你一个二叉树的两种dfs遍历的顺序,让你构造出一个满足这两种dfs序的二叉树.(有SPJ);

首先考虑我们在讲一个树形结构转化为线结构的时候,通过dfs序,可以将一个节点为根的子树中其他节点包含起来,编号是连续的,从而能够采用线段树and so on的数据结构维护.

同理在dfs序中一个连续的区间即可能是一个子树中的结构
同时思考dfs序不同是因为遍历的不知道是按左儿子先,还是右儿子先.于是产生了多种dfs序…

也就是说
对于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
24
25
26
27
28
29
30
31
32
int _,n,q,mx;
int a[N],b[N];
int h[N],f[N];
int visa[N],visb[N];

void dfs(int l1,int r1,int l2,int r2,int fa) {
    if(l1>r1||r1>n||r2>n)   return;
    if(a[l1]==b[l2]) {
        f[a[l1]]=fa;if(h[fa]) h[fa]--;
        dfs(l1+1,r1,l2+1,r2,a[l1]);
    }
    else {
        int len1=visa[b[l2]]-l1-1;
        int len2=visb[a[l1]]-l2-1;
        dfs(l1,l1+len1,l2+len2+1,l2+len1+len2+1,fa);
        dfs(l1+len1+1,l1+len1+len2+1,l2,l2+len2,fa);
        while(!h[fa])   fa=f[fa];
        dfs(l1+len1+len2+2,r1,l2+len1+len2+2,r2,fa);
    }
}
int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),visa[a[i]]=i,h[i]=2;h[0]=2;
        for(int i=1;i<=n;i++) scanf("%d",&b[i]),visb[b[i]]=i;
        dfs(1,n,1,n,0);
        for(int i=1;i<=n;i++) printf("%d%c",f[i],(i<n)?' ':'\n');
    }
    return 0;
}