情况

时间：2024年7月4日13:45

image.png
C题wa3发。

题解

A - Guess the Maximum

题意

一个人说一个数K，另一个人在一串数组中找一个区间，如果这个区间最大值严格大于K，符合要求。找出最小的k

思路

所有长度为2的区间最大值的最小值严格大于K。也就是K取所有长度为2的区间元素最大值的最小值-1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve()
{
    int n;
    cin >> n;
    int ans = 10e9;
    cin >> a[1];
    for (int i = 2; i <= n;i++) {
        cin >> a[i];
        int k = max(a[i-1], a[i]);
        ans = min(k, ans);
        }
            cout << ans-1 << endl;

}

B - XOR Sequences

题意

位异或运算：XOR，运算符为^，公式符号为⊕

有两个无限长序列a,b.
$𝑎_𝑛=𝑛⊕𝑥\
𝑏_𝑛=𝑛⊕𝑦$
提供x和y的值，寻找$a_n\text{和}b_n\text{的最长公共子串}$

思路

我们要寻找的子串，每一位n满足下面（i和j对应序列a和b中的位置）：

1
2
3
i^x = j^y 
i   = j^y^x = j^x^y
i^j=x^y

无限子序列，i^j
把 x^y写为 k(定值)
当i+1,j+1时候，发现同时加一，如果加一影响的下一位是同，对是否等于k没有影响（还是k）
直到i+a,j+a遇到非同的位。
最终就是，输出x^y的lowbit(遇到第一个为1的位置表示的数)
每日一个算法知识点 - lowbit方法-CSDN博客
详解x&(-x)以及x&(x-1)_x & (~x + 1) = x & (-x)-CSDN博客

代码

1
2
3
4
5
6
7
void solve()
{
    int x, y;
    cin >> x >> y;
    x ^= y;
    cout << (x&(-x))<<endl;
}

问题

没思路，位运算很不熟练，也没动笔

C - Earning on Bets

题意

给出一个数组，对应若干结果，代表着赢的时候一个硬币能赚的值。只有一个结果能赢。任意分配硬币，要保证每一个结果产生的赢得的值严格大于分配的总硬币数

思路

首先想到的是，给的数组与分配硬币的比例有关。
观察用例，发现下面几个用例都是最小公倍数除以数组各值。
抄了一个算gcd循环的代码，如果使用最小公倍数的方案没有满足最小公倍数严格大于分配硬币之和，则不能成功，输出-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
58
59
60
61
62
63
64
65
66
67
68
69
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 50 + 2;
int k[N];       // given
int r[N] = {1}; // result

LL gcd(LL x, LL y) // 欧几里得算法求最大公因数
{
    LL temp;
    while (y > 0)
    {
        temp = x % y;
        x = y;
        y = temp;
    }
    return x;
}
void solve()
{
    int flag = 1;
    int n;
    cin >> n;
    LL ans[N] = {0};
    LL gcdres = 1;
    for (int i = 0; i < n; ++i)
    {
        cin >> k[i];
        gcdres = gcdres * k[i] / gcd(gcdres, k[i]);
    }
    LL sumc = 0;

    for (int i = 0; i < n; ++i)
    {
        ans[i]=gcdres/k[i];sumc += ans[i];
    }
    if(sumc >= gcdres){
        flag = 0;
    }


    if(flag == 1)
    for (int i = 0; i < n; ++i){
        cout << ans[i] << " ";
    }
    else {cout << -1;}
    cout << endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

问题

刚开始WA on test 2，面向用例解题了，两个-1的情况都是硬币和等于最小公倍数。
后来改条件还WA on test 4。改了LL再试一次，过了。
对于10e9的涉及增加的计算，还是得开LL。