Codeforces Round #670 (Div. 2) 题解
[CF1406A] Subset Mex 提交地址:https://codeforces. …
May all the beauty be blessed.
题目地址:洛谷:【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;
}
题目地址:洛谷:【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;
}