A.Nastya and an Array—签到

题意：有一个大小为 n 的数组，一次操作可以将数组中所有非零的数字全部加上一个整数（整数可以为负数），求至少要多少次操作才能将数组中的数全部变为 0

思路：统计不同的非零数的数量就是答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    while (cin >> n) {
        map<int, int> mp;
        for (int i = 1; i <= n; ++i) {
            int x;
            cin >> x;
            if (x != 0)
                mp[x] = 1;
        }
        cout << mp.size() << endl;
    }
    // system("pause");
    return 0;
}

B.Nastya Studies Informatics—剪枝+思维

题意：给出整数 x 和 y，请你求出当 l<=a,b<=r 时有多少对 (a,b) 能同时满足 gcd(a,b)==x&&lcm(a,b)==y，注意当 a!=b 时 (a,b) 和 (b,a) 是不相同的

思路：直接从给出的 [l,r] 区间中枚举会 TLE 需要缩小范围。不难想到 lcm/gcd 结果就是满足条件的 a 和 b 同时除去 gcd 后各自剩下的互质的因数的乘积，剩下的因数要么是相同的 (1,1) 要么是不同的，所以我们就从 [l/gcd(向上取整),r/gcd(向下取整)] 中找到两个数相乘是 lcm/gcd 的因数就是一对符合条件的答案，虽然枚举范围变小了但是这样还是会 TLE，根据上面我们推出的结果我们再进一步缩小范围小于sqrt(lcm/gcd) 的一边找，如果另一个因数和它不同说明还可以颠倒两个因数再组成一对，所以答案 +2，如果相同则答案 +1

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ll

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int l, r, x, y;
    while (cin >> l >> r >> x >> y) {
        if (y % x != 0) {  //特判:不能整除说明肯定不存在
            cout << 0 << endl;
            continue;
        }
        int ret = y / x;
        int cnt = 0;
        int tot1 = r / x;      //右边界1
        int tot2 = sqrt(ret);  //右边界2
        for (int i = ceil(l * 1.0 / x); i <= tot1 && i <= tot2; ++i) {
            if (ret % i == 0 && __gcd(ret / i, i) == 1 && ret / i <= tot1) {  //判断另一个因数是否在范围内并且互质
                if (ret / i == i)
                    ++cnt;  //拆除的因数相同只能形成一对
                else
                    cnt += 2;
            }
        }
        cout << cnt << endl;
    }
    // system("pause");
    return 0;
}

C.Nastya and a Wardrobe—规律+数学

题意：小 N 有一个神奇的衣柜，在每个月底衣柜中的裙子数量会翻倍。在第一年里衣柜中有 x 条裙子，在前 k 个月中裙子数量翻倍之后小 N 都会有 50% 的几率从衣柜中取走一条裙子（当然要保证衣柜中有裙子）。请你你算出第 k+1 个月底衣柜中的裙子数量翻倍后的期望值，答案对 1e9+7 取模

思路：因为是 C 题所以肯定又是有规律可循的 😂。两种做法：

  • 找规律：因为衣柜逐月翻倍所以我们猜测肯定是和 2 的幂数有关系，如果不考虑拿走衣服的情况那么最终肯定有 n*2k+1 的条，因为拿走的了所有应该是需要减去一个值

    • 样例一：n*2k+1=4，那么我们猜测减去的值有可能是 2k
    • 样例二：n*2k+1=8，否定了上面的猜测，那么减去的值有可能是 2k-1，还有可能是 2k-1
    • 样例三：经过用样例二的猜测验证发现答案应该是 n*2k+1-(2k-1)=n*2k+1-2k+1

  • 数学计算：感觉并不好想，但是对着找到的规律很容易理解。假设第 i 个月拿走了一条裙子并且到第 j 个月再也没有拿过裙子，那么当前月拿走和不拿走就差了 1 条裙子，下个月就差了 2 条裙子，再下个月就差了 4 条裙子，也就是说第 i 个月拿走一条裙子会导致第 j 个月少了2j-i 条裙子。那么第 1到 k+1 月都不拿走裙子会有 n*2k+1 条，再考虑拿走裙子的影响，第 1 到 k 月都拿走裙子就到第 k 月累计总共少了

    综上减去少了的裙子就得出了答案

另外还要特判 x=0 的情况以及减法取模保证答案取整的细节

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

ll quick_pow(ll a, ll b) {
    ll ans = 1, base = a;
    while (b) {
        if (b & 1) ans = ans * base % mod;
        base = base * base % mod;
        b >>= 1;
    }
    return ans % mod;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    ll x, k;
    while (cin >> x >> k) {
        if (x == 0) {
            cout << 0 << endl;
            continue;
        }
        ll ans = (x % mod) * quick_pow(2, k + 1);   
        ans = ((ans - quick_pow(2, k) + mod) % mod + 1) % mod; //因为是取模后相减有可能2^k+1比2^k小,防止取到负数
        cout << ans << endl;
    }
    // system("pause");
    return 0;
}

D.Nastya and a Game—思维+剪枝暴力+溢出判断

题意：有一个大小为 n 的数组 a，请确定它有多少个子区间满足子区间内数的乘积是区间内数的加和的 k 倍（ 1<=n<=2e5，1<=k<=1e5，1<=a[i]<=1e8）

思路： 参考博客 这题难在数据范围太大了，考虑区间 dp 但是根本开不了那么大的数组也不会转移方程。乘积实际上是有限制的，最大是 2e5*1e5*1e8=2e18 在 long long 范围内，再大的乘积肯定不满足题意了，而 long long 是 264，也就是说最多由 64 个非 1 的数相乘得到（数据量已经很小了可以暴力判断），综上我们在考虑特殊的数组中 1 就可以了

  • 先预处理出每个位置的下一个非 1 的数的位置用来暴力判断

  • 我们对于每个位置作位区间左边界的情况下，统计不同右边界形成的满足条件的区间进行统计

    • 每到一个位置先判断乘积是否会 longlong 溢出

    • 对于连续的 1 区间实际上区间乘积是不变的，只有区间的和在递增，那么商也就是在递减所以这段区间答案不超过 1，所以直接整体判断整个连续的 1 区间

    • 对于非 1 的位置我们就逐位置暴力判断

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
56
57
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;

ll n, k;
ll a[maxn], nex[maxn];

void init() {
    nex[n + 1] = n + 1;  //处理边界
    for (int i = n; i >= 1; --i) {
        if (a[i] == 1)
            nex[i] = nex[i + 1];
        else
            nex[i] = i;
    }
}

bool overflow(ll x, ll y) {  //判断乘积是否会溢出long long
    return x > LLONG_MAX / y;
}

ll cal(int pos) {
    int cnt = 0;
    ll pro = a[pos], sum = a[pos];
    if (k == 1) ++cnt;                        //特判k=1情况需要算上自己
    for (int j = pos + 1; j <= n; ++j) {      //枚举右端点
        if (overflow(pro, a[j])) return cnt;  //先判断是否溢出,溢出后面肯定没有答案返回
        if (a[j] == 1) {                      //看其后面连续的1区间中是否满足条件的唯一的区间
            int ret = nex[j] - j;
            if (pro % k == 0 && (sum + 1) <= (pro / k) && (sum + ret) >= (pro / k))  //pro满足答案的区间和是否处于连续的1区间的范围中
                ++cnt;
            sum += ret;      //直接跳到不为1的下一个位置
            j = nex[j] - 1;  //这是个循环最后还会有个+1所以这里先跳到目标位置的前面一个位置
        } else {
            pro *= a[j], sum += a[j];
            if (pro % sum == 0 && pro / sum == k)  //暴力判断区间是否满足条件
                ++cnt;
        }
    }
    return cnt;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    while (cin >> n >> k) {
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        init();  //统计出下一个不为1的位置
        ll ans = 0;
        for (int i = 1; i <= n; ++i)  //统计以i为左端点的满足条件的区间个数
            ans += cal(i);
        cout << ans << endl;
    }
    // system("pause");
    return 0;
}