bef-> NO.17

Veröffentlicht am

P3917 异或序列

题目描述

给出序列

求

的值。其中，

表示按位异或。

输入输出格式

输入格式：

第1 行，1 个整数NN。

第2 行，NN个整数A_1,A_2,\cdots,A_NA1,A2,⋯,AN。

输出格式：

一个数，为表达式的值

输入输出样例

输入样例#1：

1
2
2
1 2

输出样例#1： 

1
6

说明

• 对于60% 的数据，

• 对于100% 的数据，

题解

计算一个区间的xor我们首先可以想到前缀异或，两个前缀异或进行异或运算就是区间异或值。

然后我们怎么快速统计所有区间异或值呢？

不难想到按位统计，每一位上0和1的个数乘起来（0不要忘了+1，还有左端点为0的情况）就是所有这一位能是一的区间个数（乘法原理）

Code:

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
#define ll long long
ll A[maxn] , n , Xor[55][maxn] , ans;
int main()
{
    scanf("%lld",&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%lld",&A[i]);
    for(int i = 2 ; i <= n ; ++i)
        A[i] ^= A[i-1];
    for(int k = 53 ; k >= 0 ; --k)
        for(int i = 1 ; i <= n ; ++i)
            Xor[k][i] = (A[i]>>k)&1;
    for(int k = 53 ; k >= 0 ; --k)
    {
        int tot = 0 ;
        for(int i = 1 ; i <= n ; ++i)
            if(Xor[k][i])   ++tot;
        ans += (1<<k) * tot * (n-tot+1);
    }
    printf("%lld",ans);
}

P2188 小Z的 k 紧凑数

题目描述

小 Z 在草稿纸上列出了很多数，他觉得相邻两位数字差的绝对值不超过 k 的整数特别奇特，称其为 k 紧凑数。

现在小 Z 想知道 [l，r] 内有多少个 k 紧凑数，希望你帮帮他。

输入输出格式

输入格式：

第一行包含三个整数 l，r，k。

输出格式：

第一行包含一个整数，表示 [l，r] 内 k 紧凑数的个数。

输入输出样例

输入样例#1：

复制

1
1 13 1

输出样例#1：

复制

1
12

说明

【数据规模】

对于 30% 的数据，

对于另外 30% 的数据，l = 1，r 为 10 的倍数；

对于 100% 的数据，

题解

又独立切了省选难度的题嘤嘤嘤。

我的数位dp似乎比大佬的麻烦

状态设计为：
f(i,0/1,0/1,j)表示当前是从高位的第i位，卡不卡上界，是否全是前导0，最后一位是j的数量。

由于我是做差所以没有带卡下界状态，假如只做一次DP可以带上卡下界。

Code：

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
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define ll long long
ll L, R , k , f[25][2][2][10] , p[25] , len = 0;
inline void set(ll x)
{
    if(x < 10) {p[++len] = x;return;}
    set(x/10);
    p[++len] = x % 10;
}
inline int abs(ll x)
{
    return x >= 0 ? x : -x;
}
inline ll solve(ll x)
{
    ll ans = 0;
    std::memset(f,0,sizeof(f));
    std::memset(p,0,sizeof(p));
    len = 0;
    set(x);
    for(int i = 0 ; i <= p[1] ; ++i)
        f[1][i==p[1]][i==0][i] = 1;
    for(int i = 2 ; i <= len ; ++i)//cur digit
        for(int up = 0 ; up <= 1 ; ++up)
            for(int allz = 0 ; allz <= 1 ; ++allz)
                for(int la = 0 ; la <= 9 ; ++la)
                    if(f[i-1][up][la])
                        for(int nd = 0 ; nd <= 9 ; ++nd)
                        {
                            int nup = 0 , nz = 0;
                            if(up && (nd==p[i])) nup = 1;
                            if(up && nd > p[i]) continue;
                            if(allz && nd == 0) nz = 1;
                            if(abs(nd-la) > k && (!allz))  continue;
                            f[i][nup][nz][nd] += f[i-1][up][allz][la];
                            // printf("f[%d][%d][%d] += f[%d][%d][%d]\n",i,nup,nd,i-1,up,la);
                        }
    for(int up = 0 ; up <= 1 ; ++up)
        for(int az = 0 ; az <= 1 ; ++az)
            for(int la = 0 ; la <= 9 ; ++la)
                ans += f[len][up][az][la];
    return ans;
}
int main()
{
    // k = 9;
    scanf("%lld%lld",&L,&R);
    scanf("%lld",&k);
    printf("%lld",solve(R) - solve(L-1));
    // std::cout<<solve(13);
}