Codeforces Round #489 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #489 (Div. 2)
过题数：3
排名：289/6253

A. Nastya and an Array

题意

$Nastya$ 有一个长度为 $n$ 的序列，每一秒她可以将这个序列上的所有非零的数字加上同一个数字，如果这个序列所有的数字都等于 $0$，那么这个序列就爆炸了，问最少需要多少秒，能够使这个序列爆炸。

输入

第一行包含一个整数 $n~(1\leq n\leq10^5)$，第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n~(-10^5\leq a_i\leq10^5)$ 表示这个序列中的每一个数字。

输出

一个整数，表示最少能够使这个序列爆炸的时间。

样例

题解

直接判断序列中有多少个不同的非零数字。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
typedef long long LL;
int n, x;
set<int> st;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        st.clear();
        for(int i = 0; i < n; ++i) {
            scanf("%d", &x);
            if(x != 0) {
                st.insert(x);
            }
        }
        int ans = st.size();
        printf("%d\n", ans);
    }
    return 0;
}

B. Nastya Studies Informatics

题意

定义一对好的整数，这对整数必须满足 $\gcd(a,b)=x$ 且 $lcm(a,b)=y$，问在区间 $[l,r]$ 内，有多少对好的整数。如果 $a\neq b$，则 $(a,b)$ 与 $(b,a)$ 被认为是不同的整数对。

输入

输入包含四个整数 $l,r,x,y~(1\leq l\leq r\leq 10^9,1\leq x\leq y\leq10^9)$。

输出

输出问题的答案。

样例

题解

要满足 $\gcd(a,b)=x$ 且 $lcm(a,b)=y$，首先必须满足 $y\%x=0$，否则不存在满足要求的整数对。设 $a=a'\times x,b=b'\times x$，则 $y=\frac{a\times b}{x}=a'\times b'\times x$ 且 $\gcd(a',b')=1$，所以 $\frac{y}{x}=a'\times b'$，因此问题就转化为求在区间 $[\lceil\frac{l}{x}\rceil,\lfloor\frac{r}{x}\rfloor]$ 内的 $\frac{y}{x}$ 的因子对 $(a',b')$ 的个数，其中 $\gcd(a',b')=1$，$O(\sqrt \frac{y}{x})$ 地枚举即可。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
typedef long long LL;
int l, r, x, y, ans;
int gcd(int a, int b) {
    return b == 0? a: gcd(b, a % b);
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d%d%d", &l, &r, &x, &y) != EOF) {
        ans = 0;
        if(y % x != 0) {
            printf("0\n");
            continue;
        }
        y /= x;
        l = (l + x - 1) / x;
        r /= x;
        for(int i = 1; i <= y / i; ++i) {
            if(y % i == 0) {
                int ii = y / i;
                if(i >= l && i <= r && ii >= l && ii <= r && gcd(i, ii) == 1) {
                    ++ans;
                    if(i != ii) {
                        ++ans;
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Nastya and a Wardrobe

题意

最初一个衣柜中有 $x$ 条裙子，每个月月末，衣柜里的裙子数就会翻倍，并且除了最后一个月以外，其他月的月末如果衣柜里有裙子的话都会有 $50\%$ 的概率被偷一条裙子，问 $k+1$ 个月后，衣柜里裙子数量的期望值。由于这个期望值总是整数，所以可以将答案对 $10^9+7$ 取模后输出。

输入

两个整数 $x,k~(0\leq x,k\leq10^{18})$。

输出

输出对 $10^9+7$ 取模后的答案。

样例

题解

先打出 $k+1=1,2,3,4$ 时的表：

月份	0	1	2	3	4
翻倍	$x$	$2x$	$4x$ $4x-2$	$8x$ $8x-4$ $8x-2$ $8x-6$	$16x$ $16x-8$ $16x-4$ $16x-12$ $16x-2$ $16x-10$ $16x-6$ $16x-14$
期望	$x$	$2x$	$4x-1$	$8x-3$	$16x-7$
被偷		$2x-1$	$4x-1$ $4x-3$	$8x-1$ $8x-5$ $8x-3$ $8x-7$	$16x-1$ $16x-9$ $16x-5$ $16x-13$ $16x-3$ $16x-11$ $16x-7$ $16x-15$

可以发现，答案就是 $2^{k+1}x-(2^k-1)$，由于 $k$ 很大，所有要用个快速幂。最后要注意一下 $x=0$ 的情况，由于对 $0$ 翻倍仍然是 $0$，这时候没有裙子可以被偷，所以不满足上面的规律，应直接输出 $0$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
typedef long long LL;
const LL MOD = 1000000000 + 7;
LL x, k;
LL fast_pow(LL res, LL n) {
    LL ans = 1;
    for(ans = 1; n != 0; n >>= 1) {
        if(n % 2 == 1) {
            ans = (ans * res) % MOD;
        }
        res = (res * res) % MOD;
    }
    return ans;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%I64d%I64d", &x, &k) != EOF) {
        if(x == 0) {
            printf("0\n");
            continue;
        }
        x %= MOD;
        LL ans = fast_pow(2, k + 1);
        ans = (ans * x) % MOD;
        LL tmp = fast_pow(2, k);
        tmp = ((tmp - 1) % MOD + MOD) % MOD;
        ans -= tmp;
        ans = (ans % MOD + MOD) % MOD;
        printf("%I64d\n", ans);
    }
    return 0;
}

D. Nastya and a Game

题意

给一个长度为 $n$ 的序列，要求找到满足 $\frac{p}{s}=k$ 的子段个数，其中 $p$ 为被选中子段的数字乘积，$s$ 为被选中子段的数字和。

输入

第一行包含两个整数 $n$ 和 $k~(1\leq n\leq2\times10^5,1\leq k\leq10^5)$。第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq10^8)$。

输出

输出满足条件的子段数量。

样例

题解

由于 $s\times k$ 的最大值为 $\max(n\times a_i\times k)=2\times10^5\times10^5\times10^8=2\times10^{18}$，所以满足条件的子段内，不等于 $1$ 的数字个数不会超过 $63$ 个 $(2^{63}\approx9\times10^{18})$，因此只要关注不等于 $1$ 的数字即可，通过枚举起点，当 $p>k\times\sum a_i$ 时跳出枚举终点的循环，时间复杂度可以达到 $O(63n)$。
我们可以知道，当 $p=s\times k$ 时，答案可以 $+1$；当 $p<s\times k$ 时，需要一个非 $1$ 的数字加入这个子段，才能使 $p$ 增大，而更多的 $1$ 反而使得 $s\times k$ 增大，不利于寻找答案，所以这时候应直接跳到下一个非 $1$ 的位置；当 $p>s\times k$ 时，更多的 $1$ 将会使 $s\times k$ 增大，这时候可以直接计算出所需要的 $1$ 的数量：$p=(s+x)\times k$，解得 $x=\lceil\frac{p-s\times k}{k}\rceil$，如果后面有连续的 $x$ 个 $1$，则可以直接跳到这个位置，否则直接跳到下一个非 $1$ 数字。最后注意一下乘法容易爆 $long~long$，应该用除法做比较。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
typedef long long LL;
const int maxn = 200000 + 100;
int n, Index;
LL ans;
LL k, sum, num[maxn];
int Next[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%I64d", &n, &k) != EOF) {
        sum = 0;
        ans = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%I64d", &num[i]);
            sum += num[i];
        }
        Index = n + 1;
        for(int i = n; i > 0; --i) {
            Next[i] = Index;
            if(num[i] != 1) {
                Index = i;
            }
        }
        for(int i = 1; i <= n; ++i) {
            LL p, s;
            p = 1;
            s = 0;
            for(int j = i; j <= n; ++j) {
                if(!(p <= sum * k / num[j])) {
                    break;
                }
                p *= num[j];
                s += num[j];
                if(p == s * k) {
                    ++ans;
                    continue;
                }
                int jj = Next[j] - 1;
                if(p < s * k) {
                    if(jj != j) {
                        s += jj - j;
                        j = jj;
                    }
                    continue;
                }
                LL x = (p - k * s + k - 1) / k;
                if(j + x > jj) {
                    x = jj - j;
                }
                s += x;
                j += x;
                if(p == k * s) {
                    ++ans;
                }
            }
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

E. Nastya and King-Shamans

题意

给定一个长度为 $n$ 的序列 $num_1,num_2,\cdots,num_n$，记 $sum_i=\sum_{j=1}^inum_j$，有 $q$ 次操作，每次操作将 $num_p$ 改为 $x$，问每次操作之后，哪个位置上的数字满足 $num_i=sum_{i-1}$。

输入

第一行为两个整数 $n,q~(1\leq n,q\leq2\times10^5)$，第二行为 $n$ 个整数 $num_1,num_2,\cdots,num_n~(0\leq num_i\leq10^9)$，接下去有 $q$ 行，每行两个整数 $p_i,x_i~(1\leq p_i\leq n,0\leq x_i\leq10^9)$，表示执行操作 $num_p=x$。

输出

输出 $q$ 行，第 $i$ 行表示进行第 $i$ 次操作之后，满足 $num_i=sum_{i-1}$ 的 $i$，如果有多个解，则输出任意一个，如果不存在解，则输出 $-1$。

样例

题解

我们定义一个新的数组 $New_i=num_i-sum_{i-1}$，于是相当于要在 $New$ 数组中查找满足条件 $New_i=0$ 的位置，对于这个数组，如果进行操作 $num_p=x$，对于第 $p$ 个数字，相当于 $num_p=num_p+(x-num_p)$，而这个数字的改变，也会使得在位置 $p$ 之后的前缀和发生改变，相当于 $sum_i=sum_i+(x-num_p)~(i\geq p)$，而对于 $New$ 数组，相当于执行了

$$New_i=\begin{cases} New_i+(x-num_p)&(i=p)\\ New_i-(x-num_p)&(i>p) \end{cases}$$
这种修改正是区间加减，于是可以用线段树对这种修改进行维护，要找到 $New$ 数组中为 $0$ 的数组，我们可以维护区间最大值，因为对于 $New_i=num_i-sum_{i-1}$ 这样一个数组，其中大于 $0$ 的数字个数是很少的，假设 $New$ 数组中每个数字都大于 $0$，在最坏情况下（$New$ 数组长度最长），$num$ 数组中的元素应该为 $1,2,4,8,\cdots,2^k$，$k$ 最大为 $30~(2^{30}\approx10^9)$，因此 $New$ 数组中最多只有 $30$ 个数字大于 $0$，通过维护区间最大值的方法找 $0$，每次查找时间复杂度为 $O(\log n)$，而查找出错（找到比 $0$ 大的数字）的次数最大为 $30$，因此总的时间复杂度为 $O(30\times q\log n)$。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
typedef long long LL;
const int maxn = 200000 + 100;
int n, q, p;
LL x;
LL num[maxn], sum[maxn];
LL Max[maxn << 2], lazy[maxn << 2];
void push_up(int rt) {
    Max[rt] = max(Max[rt << 1], Max[rt << 1 | 1]);
}
void push_down(int rt) {
    if(lazy[rt] != 0) {
        Max[rt << 1] += lazy[rt];
        Max[rt << 1 | 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt << 1] += lazy[rt];
        lazy[rt] = 0;
    }
}
void build(int l, int r, int rt) {
    lazy[rt] = 0;
    if(l == r) {
        Max[rt] = num[l] - sum[l - 1];
        return ;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    push_up(rt);
}
void update(int L, int R, LL x, int l, int r, int rt) {
    if(L <= l && r <= R) {
        lazy[rt] += x;
        Max[rt] += x;
        return ;
    }
    push_down(rt);
    int m = (l + r) >> 1;
    if(L <= m) {
        update(L, R, x, l, m, rt << 1);
    }
    if(m < R) {
        update(L, R, x, m + 1, r, rt << 1 | 1);
    }
    push_up(rt);
}
int query(int l, int r, int rt) {
    if(l == r) {
        if(Max[rt] == 0) {
            return l;
        }
        return -1;
    }
    push_down(rt);
    int m = (l + r) >> 1;
    int ret = -1;
    if(Max[rt << 1] >= 0) {
        ret = max(ret, query(l, m, rt << 1));
    }
    if(ret != -1) {
        return ret;
    }
    if(Max[rt << 1 | 1] >= 0) {
        ret = max(ret, query(m + 1, r, rt << 1 | 1));
    }
    return ret;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &q) != EOF) {
        sum[0] = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%I64d", &num[i]);
            sum[i] = sum[i - 1] + num[i];
        }
        build(1, n, 1);
        while(q--) {
            scanf("%d%I64d", &p, &x);
            LL d = x - num[p];
            num[p] = x;
            update(p, p, d, 1, n, 1);
            if(p != n) {
                update(p + 1, n, -d, 1, n, 1);
            }
            printf("%d\n", query(1, n, 1));
        }
    }
    return 0;
}