百度之星 (2021-08-01)

2021 百度之星初赛第二场，记一下这几题。

A. 签到

题意

每次把 $(a,b)$ 同时变成 $(a+b,a-b)$ 。求做完 $k$ 次后的两个数，对 $998244353$ 取模。

思路

连续变换两次就变成 $(2a,2b)$ 。先用快速幂算出 $2^{\lfloor k/2\rfloor}$ ，如果 $k$ 是奇数，再做一次变换就行。减法记得补一下模数。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mo = 998244353;


int T, a, b, k;

int fpow(int y, int x) {
    int res = 1; for(; x; x >>= 1, y = 1ll * y * y % mo) if(x & 1) res = 1ll * res * y % mo; return res;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &a, &b, &k);
        int tmp = k / 2;
        int f2 = fpow(2, tmp);
        // cout << f2 << endl;
        int A = 1ll * a * f2 % mo, B = 1ll * b * f2 % mo;
        if(k & 1) printf("%d %d\n", (A + B) % mo, (A - B + mo) % mo);
        else printf("%d %d\n", A, B);
    }
    return 0;
}

B. 随机题意

题目链接

题意

给定 $n$ 个整数，每个数都可以加上一个 $[-k,k]$ 内的整数。求修改后最多能有多少个不同的数。

思路

从小到大处理。一个数能放的位置是 $[a_i-k,a_i+k]$ ，尽量占最靠左的空位置，给后面的数留空间。相同的数一起统计，直接算这一段还能塞下几个，不用一个个枚举。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 17;
const int oo = 0x3f3f3f3f;
int T, n, k, a[maxn], L, ans;
map<int, int> mp;
int main() {
    scanf("%d", &T);
    while(T--) {
        L = -oo;
        ans = 0;
        mp.clear();
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for(int i = 1; i <= n; i++) mp[a[i]]++;
        for(auto &it : mp) {
            int d = it.first, cnt = it.second;
            int l = d - k, r = d + k;
            l = max(l, L);
            r = min(r, l + cnt - 1);
            ans += max(0, r - l + 1);

            L = max(L, r + 1);

        }
        printf("%d\n", ans);
    }
    return 0;
}

C. 魔怔

题目链接

题意

完全无向图的边有黑白两种颜色。从 $s$ 出发，每经过一条边就把它的颜色翻转，要求最后所有边都变黑。求最少走多少条边，无解输出 $-1$ 。

思路

白边要走奇数次，黑边要走偶数次，所以先看白边图的欧拉路条件：奇度点只能有零个或两个；有两个时，起点必须是其中一个。

白边先各算一次。不同的白边连通块之间需要往返连接，每多接一个块加两步；起点如果不在任何白边块里，还要额外往返一次。用并查集数一下块数就行。

代码

/*
2
5 1
0
11
110
1100
4 1
0
00
000

2
5 1
1
11
110
1100
4 1
0
00
000
*/

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 17;
int T, n, s;
int du[maxn];
int ans, fa[maxn], vis[maxn];
char str[maxn];

int getf(int x) {
    return fa[x] == x ? x : fa[x] = getf(fa[x]);
}

void merge(int x, int y) {
    int fx = getf(x), fy = getf(y);
    if(fx != fy) fa[fx] = fy;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        memset(du, 0, sizeof(du));
        memset(vis, 0, sizeof(vis));
        ans = 0;
        int flg1 = 1, flg2 = 1;
        scanf("%d%d", &n, &s);
        for(int i = 1; i <= n; i++) fa[i] = i;
        for(int i = 2; i <= n; i++) {
            scanf("%s", str + 1);
            for(int j = 1; j < i; j++) {
                if(str[j] == '0') {
                    ans++;
                    merge(i, j);
                    du[i]++, du[j]++;
                }
                else du[i] += 2, du[j] += 2;
            }
        }
        ans -= 2;
        for(int i = 1; i <= n; i++) {
            if(getf(i) != i) {
                if(!vis[getf(i)]) ans += 2;
                vis[getf(i)] = 1;
            }
        }
        if(!vis[getf(s)]) ans += 2;
        for(int i = 1; i <= n; i++) if(du[i] & 1) flg1 = 0;
        for(int i = 1; i <= n; i++) {
            if(du[i] & 1 && i != s) {
                if(flg2 == 1) flg2++;
                else if(flg2 == 2) flg2 = 0;
            }
        }
        if(!(du[s] & 1)) flg2 = 0;
        if(flg1 || flg2) {
            printf("%d\n", ans);
        }
        else printf("-1\n");
    }
    return 0;
}

D. 净化

题目链接

题意

初始数值为 $0$ ，每轮依次加上 $a_1,\ldots,a_n$ ，每次加完如果小于 $0$ 就变成 $0$ 。求最早在哪一轮能达到至少 $m$ ，永远达不到就输出 $-1$ 。

思路

先把前两轮模拟出来，不能只看一轮结束时的值，中间也可能已经达到 $m$ 。

设第一轮结束值为 $x$ ，一轮总和为 $S$ 。如果 $S\le0$ ，第二轮结束后就稳定了，再往后不会出现新值。如果 $S>0$ ，从第二轮开始就不会再被截到零，每轮都比上一轮多 $S$ 。枚举轮内前缀和 $s_i$ ，算出 $x+s_i$ 还差多少个 $S$ ，取最小轮数。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 17;
const ll oo = 2e18;
int T, n, tot;
ll m, a[maxn], s[maxn], b[maxn];

inline void add(int x, ll k) {
	 for(; x <= n; x += x & -x) b[x] += k;
}

inline ll ask(int x) {
	ll res = 0; for(; x; x -= x & -x) res += b[x]; return res;
}

ll work() {
    memset(b, 0, sizeof(b));
    memset(s, 0, sizeof(s));
    for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
    for(int i = 1; i <= n; i++) b[i] = s[i] - s[i - (i & -i)];
    for(int i = 1; i <= n; i++) {
        ll tmp = ask(i);
        if(tmp >= m) return 1;
        if(tmp < 0) {
            add(i, -tmp);
        }
    }
    ll x = ask(n);
    ll res = oo;
    ll cur = x;
    for(int i = 1; i <= n; i++) {
        cur = max(0ll, cur + a[i]);
        if(cur >= m) return 2;
    }
    if(s[n] <= 0) return -1;
    for(int i = 1; i <= n; i++) {
        ll diff = m - x - s[i];
        if(diff <= 0) return 2;
        res = min(res, (diff - 1) / s[n] + 1);
    }
    if(res == oo) return -1;
    return res + 2;

    // tot = 0;
    // ll mx = 0;
    // int p = 1;
    // for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i], mx = max(s[i], mx);
    // for(int i = 1; i <= n; i++) if(s[i] < 0) v[++tot] = s[i];
    // sort(v + 1, v + 1 + tot, greater<int>());
    // ll t = 1, x = 0;
    // while(1) {
    //     for(int i = 1; i <= n; i++) b[i] = s[i] - s[i - (i & -i)];
    //     for(int i = 1; i <= n; i++) {
    //         ll tmp = ask(i);
    //         if(x + tmp == m) return t;
    //         if(x + tmp < 0) {
    //             add(i, -x - tmp);
    //         }
    //     }
    //     ll tmp = ask(n);
    //     if(tmp == 0) return -1;
    //     x += tmp, t++;
    //     while(v[p] + x >= 0 && p <= tot) p++;
    //     if(p > tot) {
    //         ll diff = m - x - mx;
    //         t += (diff / s[n]);
    //         if(diff % s[n]) t++;
    //         return t;
    //     }
    //     ll diff = 0 - (x + v[p]);
    //     t += (diff / tmp), x += (diff / tmp) * tmp;
    // }

}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%lld", &n, &m);
        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        printf("%lld\n", work());
    }
    return 0;
}

A. 签到

题意

思路

代码

B. 随机题意

题意

思路

代码

C. 魔怔

题意

思路

代码

D. 净化

题意

思路

代码

Random Posts