Gym – 101102J J. Divisible Numbers 位运算+优化+前缀和

Source

2016 ACM Amman Collegiate Programming Contest

UESTC 2017 Winter Training #1

Gym - 101102J

My Solution

题意：给出n个数，然后每次询问l r s，表示在lr区间内有多少个x，是x能被集合s里的至少一个元素整除，s表示一个{1~10}的子集

位运算+优化+前缀和

可以预处理出前缀和 sum[i][j]表示1~j中能被集合i满足的数的个数，

且i为奇数时比有元素1，lr区间内所有的数必定可以被1整除，所以只剩下512中情况

故 int sum[512][maxn];

读入的时候每次判断v可以被哪些数整除，然后得到集合s，s说表示的集合中所有的元素皆可以整除v，

然后用这个s和0~512位于返回非0值则有公共元素，则sum[j][i] = sum[j][i-1] + 1,否则只是普通传递 sum[j][i] = sum[j][i-1];

对于l r s

当s为偶数时 ans = sum[s>>1][r] - sum[s>>][l-1]; s为奇数时 ans = r - l + 1;

复杂度 O(n*512)

#include 
#include 
#include 

using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;

template 
inline void cinn(T &ret)
{
    char c = getchar();
    while(c < '0' || c > '9')
        c = getchar();
    ret = c - '0';
    while(c = getchar(), c>='0' && c<='9')
        ret = ret * 10 + (c - '0');
}

inline void coutt(int a)
{    //  输出外挂
    if (a < 0) { putchar('-'); a = -a; } if (a >= 10)
    {
       coutt(a / 10);
    }
    putchar(a % 10 + '0');
}

int sum[512][maxn];

int main()
{
    #ifdef LOCAL
    freopen("g.txt", "r", stdin);
    //freopen("g.coutt", "w", stdcoutt);

    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int T, n, q, v, i, j, l, r, s;
    cinn(T);
    while(T--){
        cinn(n); cinn(q);
        for(i = 1; i <= n; i++){
            cinn(v);
            s = 0;
            for(j = 2; j <= 10; j++){
                if(v % j == 0) s |= 1<<(j - 2);

            }
            //ccoutt << s << endl;
            for(j = 0; j < 512; j++){ sum[j][i] = sum[j][i - 1]; if(j & s) sum[j][i] += 1; } } while(q--){ cinn(l); cinn(r); cinn(s); if(s&1) coutt(r - l + 1); else coutt(sum[s>>1][r] - sum[s>>1][l - 1]);
            puts("");
        }

    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx