2025牛客暑期多校训练营3 补题

Flower

如果总数量少于 a，一定会走，否则，直接模 a+b，剩下的比 a 多或者不剩即可

 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


#include <bits/stdc++.h>
#define rep(x,l,r) for(int x=l;x<=r;++x)
#define per(x,r,l) for(int x=r;x>=l;--x)
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
// #define max(x,y) ((x)<(y)?(y):(x))
// #define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
typedef double db;
typedef __int128 i128;
const ll N=5e3+7,M=1e7+7,mod=1e9+7;
const ll inf=1e18+7;
const db eps=1e-8,PI=acos(-1.0);

void solve()
{
    ll n,a,b;
    cin>>n>>a>>b;
    if(n<=a) {
        printf("Sayonara\n");
        return;
    }
    n%=(a+b);
    ll ans=n;
    if(n>a)  ans=0;
    printf("%lld\n",ans);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

Distant Control

找有没有能操作的片段，只要有一个，就可以以这个片段为基础，向两侧不断拓展，覆盖整个区域

 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


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    int n, a;
    cin >> n >> a;
    string s;
    cin >> s;
    int lst = -1, cnt = 1, res = 0;
    vector<pair<int, int>> seg;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') res++;
        if (s[i] - '0' == lst) {
            cnt++;
        } else {
            if (cnt > 0 && lst != -1) seg.push_back({cnt, lst});
            lst = s[i] - '0';
            cnt = 1;
        }
    }
    seg.push_back({cnt, lst});
    for (auto [c, v] : seg) {
        if (v == 1) {
            if (c >= a) {
                cout << n << endl;
                return;
            }
        } else {
            if (c > a) {
                cout << n << endl;
                return;
            }
        }
    } 
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

Jetton

去年好像就有这狗屎题来着，忘记补了。

队长的暴力好像写复杂了。

按题意模拟，因为最多 log 次就会出现循环，手动给他一个轮数限制即可。

 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


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    int x, y;
    cin >> x >> y;
    int tot = 0;
    while (tot < 100) {
        tot++;
        if (x > y) {
            x -= y;
            y *= 2;
        } else {
            y -= x;
            x *= 2;
        }
        if (x == 0 || y == 0) {
            cout << tot << endl;
            return;
        }
    }
    cout << "-1\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

Equal

读假题想半天二进制，原来是整除号。。。。

观察到和质因数密切相关，如果每个质因数的个数都是偶数，就是 Yes，同时队友手玩得出奇数长度数组一定可以。

注: 这里拆解数时不能遍历质数来拆，而是要通过线性筛得到的每个数的最小质因数来拆。

 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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 5e6 + 7, mod = 1e9 + 7;

bool is_prime[N];
vector<int> primes;
int mi[N],cnt[N];
vector<int> num;
void sieve() {
    fill(is_prime, is_prime + N, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i < N; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            mi[i]=i;
        }
        for (auto j : primes) {
            if(j*i >= N) break;
            is_prime[j*i] = false;
            mi[j*i]=j;
            if(i % j == 0) break;
        }
    }
}

void solve() {
    int n;
    cin >> n;
    for(auto x:num)  cnt[x]=0;
    num.clear();
    if (n == 2) {
        int x, y;
        cin >> x >> y;
        if(x == y) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
        return;
    }
    
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        while (x > 1) {
            int p = mi[x];
            while (x % p == 0) {
                cnt[p]++;
                x /= p;
                if(cnt[p]==1)  num.push_back(p);
            }
        }
    }
    if (n % 2 == 1) {
        cout << "YES\n";
        return;
    }
    for (auto p : num) {
        if (cnt[p] % 2 == 1) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    sieve();
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

Ad-hoc Newbie

观察到图像有对称性质。

对于每个 $f_i$，用一个对应的队列储存需要的值，即 $0$ ~ $f_i - 1$。

对每列处理，操作当前列的 $q_i$，取出首位元素，看是否和当前行的 $f_i$ 冲突，不冲突就放，冲突就放下一个现在这个塞回去。

 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


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<vector<int>> ans(n + 1, vector<int>(n + 1));
    deque<int> q[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = 0; j < a[i]; j++) {
            q[i].push_back(j);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (q[i].empty()) ans[i][i] = 0;
        else ans[i][i] = q[i][0];
        for (int j = i + 1; j <= n; j++) {
            if (q[j].empty() || (q[j].size() == 1 && q[j][0] == a[i])) ans[j][i] = ans[i][j] = 0;
            else {
                int tmp = q[j][0];
                q[j].pop_front();
                if (tmp != a[i]) ans[j][i] = ans[i][j] = tmp;
                else {
                    ans[i][j] = ans[j][i] = q[j][0];
                    q[j].pop_front();
                    q[j].push_front(tmp);
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        q[i].clear();
        for (int j = 1; j <= n; j++) cout << ans[i][j] << " ";
        cout << endl;
    }

}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

Head out to the Target

可视作一个从 1 开始不断向外拓展的区域，如果某次询问在区域内，即可到达。

先通过预处理得到每个节点的深度，同时通过倍增处理得节点倍增表。

接着按顺序遍历 k 个事件，查询离 now 最近的在已找到区域内的节点。

计算找到的点到目标需要的步数是否足够。

如果够，那得到答案。

否则，向 now 拓展，扩大区域。

 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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;

int fa[N][21], dep[N];
bool vis[N];
vector<int> nx[N];

void dfs(int x) {
    dep[x] = dep[fa[x][0]] + 1;
    for (auto y : nx[x]) dfs(y);
}

int find(int x) {
    if (vis[x]) return x;
    for (int i = 20; i >= 0; i--) {
        if (fa[x][i] && !vis[fa[x][i]]) x = fa[x][i];
    }
    return fa[x][0];
}

int fun(int now, int x, int tim) {
    for (int i = 20; i >= 0; i--) {
        if (fa[now][i] && dep[fa[now][i]] - dep[x] >= tim) now = fa[now][i];
    }
    return now;
}

void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 2; i <= n; i++) {
        cin >> fa[i][0];
        nx[fa[i][0]].push_back(i);
    }
    dfs(1);
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i <= n; i++) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }
    vis[1] = 1;
    int ans = -1;
    while (k--) {
        int now, l, r;
        cin >> now >> l >> r;
        int x = find(now);
        if (x == now) {
            ans = l;
            break;
        }
        int tim = r - l + 1;
        if (dep[now] - dep[x] <= tim) {
            ans = l + dep[now] - dep[x] - 1;
            break;
        }
        int y = fun(now, x, tim);
        while (!vis[y]) {
            vis[y] = 1;
            y = fa[y][0];
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Bitwise Puzzle

注意到题目所说的 64 次操作，易想到二进制。

注意数据最大不到 $2^31$，如果能有一个一直是 1 的位数来操作 a 的每一位，一定能得到 c，同时对于 b，几次异或就能使其变为 a。

注： != 的优先级是大于 & 的，使用一定要记得加括号。。。

  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
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105


#include <bits/stdc++.h>
#define rep(x,l,r) for(int x=l;x<=r;++x)
#define per(x,r,l) for(int x=r;x>=l;--x)
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
// #define max(x,y) ((x)<(y)?(y):(x))
// #define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
typedef double db;
typedef __int128 i128;
const ll N=1e6+7,M=1e7+7,mod=1e9+7;
const ll inf=1e18+7;
const db eps=1e-8,PI=acos(-1.0);

void solve()
{
    vector<int> ans;
    ll a,b,c;
    cin>>a>>b>>c;
    if(a==b&&a==0) {
        if(c)  printf("-1\n");
        else  printf("0\n\n");
        return;
    }
    ll mxa=0,mxb=0,mxc=0;
    for(ll i=1ll<<31;i>=1;i>>=1) {
        if(a&i) {
            mxa=i;
            break;
        }
    }
    for(ll i=1ll<<31;i>=1;i>>=1) {
        if(b&i) {
            mxb=i;
            break;
        }
    }
    for(ll i=1ll<<31;i>=1;i>>=1) {
        if(c&i) {
            mxc=i;
            break;
        }
    }
    if(mxb<mxa) {
        mxb=mxa;
        b^=a;
        ans.push_back(4);
    }
    if(mxc>=mxb) {
        if(mxa<mxb)  {
            mxa=mxb;
            a^=b;
            ans.push_back(3);
        }
        ll now=mxc;
        // if((c&now)!=(a&mxb)) {
        //     a^=b;
        //     ans.push_back(3);
        // }
        while(mxa<mxc) {
            mxa<<=1;
            a<<=1;
            ans.push_back(1);
            now>>=1;
            if(((c&now)!=0)!=((a&mxb)!=0)) {
                a^=b;
                ans.push_back(3);
            }
        }
    }
    while(mxb>=1) {
        if(((c&mxb)!=0)!=((a&mxb)!=0)) {
            a^=b;
            ans.push_back(3);
        }
        mxb>>=1;
        b>>=1;
        ans.push_back(2);
    }
    ans.push_back(4);
    // printf("%lld %lld %lld\n",a,b,c);
    // if(a!=c) {
    //     printf("-1\n");
    //     return;
    // }
    // if(ans.size()>64)  while(1);
    printf("%d\n",ans.size());
    for(auto x:ans) {
        printf("%d ",x);
    }
    printf("\n");
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}