标签: 根号

Codeforces Round #670 (Div. 2) 题解

Codeforces Round #670 (Div. 2) 题解

[CF1406A] Subset Mex 提交地址:https://codeforces. 

[BZOJ3343]教主的魔法 题解

[BZOJ3343]教主的魔法 题解

题目地址:洛谷:【P2801】教主的魔法 – 洛谷、BZOJ:Problem  

[洛谷3674]小清新人渣的本愿 题解

[洛谷3674]小清新人渣的本愿 题解

题目地址:洛谷:【P3674】小清新人渣的本愿 – 洛谷

题目描述

给你一个序列a,长度为n,有m次操作,每次询问一个区间是否可以选出两个数它们的差为x,或者询问一个区间是否可以选出两个数它们的和为x,或者询问一个区间是否可以选出两个数它们的乘积为x ,这三个操作分别为操作1,2,3
选出的这两个数可以是同一个位置的数

输入输出格式

输入格式:
第一行两个数n,m
后面一行n个数表示ai
后面m行每行四个数opt l r x
opt表示这个是第几种操作,l,r表示操作的区间,x表示这次操作的x

输出格式:
对于每个询问,如果可以,输出hana,否则输出bi

输入输出样例

输入样例#1:

10 10
1 1 8 9 9 1 1 1 1 9 
3 5 9 42
2 1 3 14
2 3 5 2
2 3 3 6
1 6 10 18
3 4 9 14
2 1 4 22
3 1 3 32
2 5 6 32
3 1 9 17

输出样例#1:

bi
bi
bi
bi
bi
bi
bi
bi
bi
bi

输入样例#2:

5 5
1 1 2 3 4
2 1 1 2
1 1 2 2
3 1 1 1
3 5 5 16
1 2 3 4

输出样例#2:

hana
bi
hana
hana
bi

说明

定义c为每次的x和ai中的最大值,ai >= 0,每次的x>=2
对于10%的数据,n,m,c <= 100
对于另外10%的数据,n,m,c <= 3000
对于另外10%的数据,只有1操作
对于另外10%的数据,只有2操作
对于另外10%的数据,只有3操作
对于100%的数据,n,m,c <= 100000

题解

参考资料:题解 P3674 【小清新人渣的本愿】 – zcysky – 洛谷博客
莫队和bitset的完美结合。
我们用bitset来维护区间内是否有这个数的状态,但是要开两个bitset,一个正着存,一个反着存。减法就枚举减数找被减数,具体来讲就是bs & (bs >> x)这样判断一下,加法就用bs & (rbs & (MAXN – x))其中rbs是倒着存的bitset。乘法比较麻烦,考虑枚举每个因数判断是否存在。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cmath>

#include <algorithm>
#include <bitset>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005;

int n, m, block, a[MAXN], cnt[MAXN];
bool ans[MAXN];
std::bitset<MAXN> bs1, bs2;

inline int bid(int pos) {
    return pos / block + 1;
}

inline void add(int x) {
    if(cnt[x]++ == 0) bs1[x] = bs2[MAXN - x] = 1;
}

inline void del(int x) {
    if(--cnt[x] == 0) bs1[x] = bs2[MAXN - x] = 0;
}

struct Query {
    int op, l, r, x, id;
} qur[MAXN];

inline bool cmp(Query a, Query b) {
    return bid(a.l) == bid(b.l) ? a.r < b.r : a.l < b.l;
}

int main() {
    n = readint(); m = readint(); block = sqrt(n);
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
    }
    for(int i = 1; i <= m; i++) {
        qur[i].op = readint(); qur[i].l = readint(); qur[i].r = readint(); 
        qur[i].x = readint(); qur[i].id = i;
    }
    std::sort(qur + 1, qur + m + 1, cmp);
    int l = 1, r = 0;
    for(int i = 1; i <= m; i++) {
        for(; l < qur[i].l; l++) del(a[l]);
        for(; l > qur[i].l; l--) add(a[l - 1]);
        for(; r < qur[i].r; r++) add(a[r + 1]);
        for(; r > qur[i].r; r--) del(a[r]);
        if(qur[i].op == 1) {
            if((bs1 & (bs1 << qur[i].x)).any()) ans[qur[i].id] = true;
        } else if(qur[i].op == 2) {
            if((bs1 & (bs2 >> (MAXN - qur[i].x))).any()) ans[qur[i].id] = true;
        } else {
            for(int j = 1; j * j <= qur[i].x; j++) {
                if(qur[i].x % j == 0 && bs1[j] && bs1[qur[i].x / j]) {
                    ans[qur[i].id] = true; break;
                }
            }
        }
    }
    for(int i = 1; i <= m; i++) {
        puts(ans[i] ? "hana" : "bi");
    }
    return 0;
}
[BZOJ3781]小B的询问 题解

[BZOJ3781]小B的询问 题解

题目地址:洛谷:【P2709】小B的询问 – 洛谷、BZOJ:Problem  

[国家集训队]小Z的袜子 题解

[国家集训队]小Z的袜子 题解

题目地址:洛谷:【P1494】[国家集训队]小Z的袜子 – 洛谷、BZOJ:P 

[洛谷1822]魔法指纹 题解

[洛谷1822]魔法指纹 题解

题目地址:洛谷:【P1822】魔法指纹 – 洛谷

题目描述

对于任意一个至少两位的正整数n,按如下方式定义magic(n):将n按十进制顺序写下来,依次对相邻两个数写下差的绝对值。这样,得到了一个新数,去掉前导0,则定义为magic(n)。若n为一位数,则magic(n)=n。
例如:magic(5913)=482,magic(1198)=081=81,magic(666)=00=0。
对任意一个数n,序列n,magic(n),magic(magic(n)),…迟早会变成一个一位数。最后的这个值称为数n的magic指纹。
例如,对于n=5913,我们得到序列:5913,482,46,2。所以5913的magic指纹为2。
若一个数的magic指纹为7,则认为这个数是个幸运数。
现在,给定A,B,计算出[A,B]中有多少个数是幸运数。

题意简述

一个magic(n)为对一个数求相邻数位之间的差组成的不含前导0的新数。连续对一个数做magic操作会得到一个一位数,求区间[A, B]中连续magic操作后得到的一位数是7的数的个数。

输入输出格式

输入格式:
输入两行,每行一个数。第一行是A,第二行表示B。

输出格式:
输出[A,B]中有多少个数是幸运数。

输入输出样例

输入样例#1:

1
9

输出样例#1:

1

说明

数据范围:
对30%数据,B≤10000。
对100%数据,0<A≤B≤1,000,000,000。

题解

参考资料:P1822 魔法指纹 题解
拿到这个题的时候除了暴力以外就没什么思路,那就打表呗。但是表太大内存装不下,那就分块呗。计算出1到109之间每\sqrt{10^9}个区间的答案,区间以外的就暴力验证,每次验证的时间是O(\log_{10} n),总复杂度也不高。
不过神犇rqy发现直接BFS套DFS时间也是可以接受的。具体做法就是,从7开始反向BFS找到可以magic操作一次得到7的数字,反向扩展的过程用DFS实现。DFS过程中,下一位只有两种选择,加上差值或者减去差值,无效状态也很多,时间上是能够接受的。需要注意的是,可以将最高位重复若干次,这样会产生前导0,magic一次就消去了。
下面的代码是BFS套DFS版本的。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

LL a, b, ans;
std::queue<LL> que;

inline void dfs(LL magic, LL real, LL digit) {
    if(real > b) return;
    if(!magic) {
        int lst = real * 10 / digit;
        if(!lst) return;
        dfs(magic, real + lst * digit, digit * 10);
        if(real >= a && real <= b) ans++;
        if(digit < b) que.push(real);
        return;
    }
    int lst = real * 10 / digit, nxt = magic % 10;
    if(lst - nxt >= 0) dfs(magic / 10, real + (lst - nxt) * digit, digit * 10);
    if(nxt && lst + nxt <= 9) dfs(magic / 10, real + (lst + nxt) * digit, digit * 10);
}

int main() {
    a = readint(); b = readint();
    if(a <= 7 && b >= 7) ans++;
    que.push(7);
    while(!que.empty()) {
        for(int i = 0; i <= 9; i++) {
            dfs(que.front(), i, 10);
        }
        que.pop();
    }
    printf("%lld", ans);
    return 0;
}
[洛谷3396]哈希冲突 题解

[洛谷3396]哈希冲突 题解

题目地址:洛谷:【P3396】哈希冲突 – 洛谷 题目描述 众所周知,模数的h 

[APIO2015]雅加达的摩天楼 题解

[APIO2015]雅加达的摩天楼 题解

题目地址:洛谷:【P3645】[APIO2015]雅加达的摩天楼 – 洛谷、B