K - 给点…资金#

题目链接：https://ac.nowcoder.com/acm/contest/130737/K
一道二分题，当时赛场上想到了 $O(n^2)$ 的暴力模拟方法，没想到可以二分优化。后面问了其他大佬之后一语点醒梦中人了。
大致题意：有 $n$ 个价值为 $a_i$ 卡牌，商店在第 $i$ 天有相应的倍率 $b_i$ 。在第 $i$ 天出售第 $j$ 张牌可以获得 $a_j \times b_i$ 元。每张牌只能出售一次，但可以自己决定哪一天出售。现希望可以尽快卖到 $x$ 元，并输出最快达到 $k$ 元的是第几天。

思路：根据题意我们可知，想要收益最大化肯定是要尽可能让在高倍率的天出售高价值的卡牌。那么我们可以先对 $A$ 数组从大到小排列，然后让在对应的天数区间里面按大倍率配大价值的规律计算。这里查找可能的天数时采用了二分答案，优化我们搜索的过程，否则会超时。最终输出满足条件的最小天数。
我们这里用了一个 $C$ 数组来存入我们选取的第 $mid$ 天内的 $B$ 数组存有的值。然后我们按从大到小排列，与 $A$ 数组一一相乘后计入总和。如果达到 $x$ 就继续向左取半搜索，看看有没有更小的值。没有达到 $x$ 就向右取半搜索，找到第一个满足条件的 $mid$ 。这里因为二分查找的时间复杂度为 $O(log N)$ ，所以这种解法的最终复杂度其实只有 $O(NlogN)$ ，可以轻松通过这道题目。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7

8
void solved(){
9
    ll n, x;
10
    cin >> n >> x;
11
    vector<ll> A(n);
12
    vector<ll> B(n);
13
    for (int i = 0; i < n;i++){
14
        cin >> A[i];
15
    }
16
    for (int i = 0; i < n;i++){
17
        cin >> B[i];
18
    }
19
    sort(A.begin(), A.end(), greater<ll>());
20
    ll l = 1, r = n, ans = -1;
21
    while(l <= r){
22
        ll mid = (l + r) / 2;
23
        vector<ll> C(B.begin(), B.begin() + mid);
24
        sort(C.begin(), C.end(),greater<ll>());
25
        ll sum = 0;
26
        for (ll i = 0; i < mid;i++){
27
            sum += A[i] * C[i];
28
            if(sum >= x){
29
                break;
30
            }
31
        }
32
        if(sum >= x){
33
            r = mid - 1;
34
            ans = mid;
35
        }
36
        else{
37
            l = mid + 1;
38
        }
39
    }
40
    cout << ans << '\n';
41
}
42

43
int main() {
44
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
45
    solved();
46
    return 0;
47
}

P10426 宝石组合#

需要化简题目给的条件。然后再找到最小的可能的因数。只不过后者代码上也不是那么好实现。
题目链接：https://www.luogu.com.cn/problem/P10426
大致题意：给定 $n$ 个属性值为 $H_i$ 的宝石。我们会随机从这 $n$ 枚宝石里面选出三枚来进行组合，组合成的精美程度 $S$ 计算方式为 $S = H_a H_b H_c \cdot \frac{LCM(H_a,H_b,H_c)}{LCM(H_a,H_b) \cdot LCM(H_a,H_c) \cdot LCM(H_b,H_c)}$ ， $LCM$ 表示的是最小公倍数。现在要求输出 $S$ 最高的组合，如果有多个方案只需输出字典序最小的三个。

思路：这题我们需要先对原式进行化简，题解里的大佬都是各显神通的，我就不掺和了。（）我这里直接使用公式 $LCM(x,y) = \frac{xy}{gcd(x,y)}$ , $LCM(x,y,z) = \frac{xyz \cdot gcd(x,y,z)}{gcd(x,y) \cdot gcd(x,z) \cdot gcd(y,z)}$ 。代入原式可以解得 $S = gcd(a,b,c)$ 。所以我们的问题就转化为要使得组合成的三个数的最大公因数最大了。
解决方法还是有点需要一点技巧的。我们需要先找出所有宝石里面的有的因数。然后用 $cnt[factor]$ 记录其出现的数量。这里优化复杂度的方法是找到一个因数之后直接用原数除于它就可以找到另外一个对应较大因数。（如果另一个因数是本身就不计入）计入对应的 $cnt$ 中。接着我们倒序查找 $cnt[factor]$ 出现次数大于等于 $3$ 次的因数 $factor$ 的最大值并用 $x$ 记录。然后我们正序从小到大判断 $x$ 是 $H_i$ 的因数的数并输出前三个即可。

1
#include <bits/stdc++.h>
2

3

4
using namespace std;
5
using ll = long long;
6
#define endl '\n'
7
#define mod 1000000007LL
8
typedef pair<int, int> pii;
9

10
vector<ll> H;
11
int cnt[200010];
12

13
void solved(){
14
    int n;
15
    int x = 0;
16
    cin >> n;
17
    H.resize(n + 1);
18
    for (int i = 1; i <= n;i++){
19
        cin >> H[i];
20
        for (int j = 1; j * j <= H[i];j++){
21
            if(H[i] % j == 0){
22
                if(j * j != H[i]) cnt[H[i] / j]++;
23
                cnt[j]++;
24
            }
25
        }
26
    }
27
    sort(H.begin() + 1, H.begin() + 1 + n);
28
    for (int i = 1e5; i >= 1;i--){
29
        if(cnt[i] >= 3){
30
            x = i;
31
            break;
32
        }
33
    }
34
    int cnt1 = 0;
35
    for (int i = 1; i <= n;i++){
36
        if(cnt1 == 3){
37
            break;
38
        }
39
        if(H[i] % x == 0){
40
            cnt1++;
41
            cout << H[i] << " ";
42
        }
43
    }
44
}
45

46
int main(){
47
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
48
    solved();
49
    return 0;
50
}

P10429 拔河#

双指针优化的题目，个人觉得比较吃技巧，想要去优化这个查找和计算答案的过程实在不好想。
题目链接：https://www.luogu.com.cn/problem/P10429
大致题意：给定 $n$ 个力量值为 $a_i$ 的同学，我们要从中挑选出两个队伍。满足以下条件： $\{ a_{l_1},a_{l_1 + 1},\dots a_{r_1 - 1},a_{r_1} \}$ 和 $\{ a_{l_2},a_{l_2 + 1},\dots , a_{r_2 - 1}, a_{r_2} \}$ ，其中 $l_1 \leq r_1 \leq l_2 \leq r_2$ 。两个队伍的人数不必相同，现在要使两个队伍内的力量值总和之差最小，输出能达到这个最小值。

思路：这道题给的数据 $n$ 是 $1e3$ ，也就是说我们最多只能使用到 $O(N^3)$ 。（但实际上 $O(N^3)$ 也是过不了的）最保险的还是是 $O(N^2logN)$ 。但目前比较直观直接暴力枚举加前缀和预处理优化最终的复杂度也还是会有 $O(N^4)$ ，我们必须另寻他法继续优化。
这里我参考大佬的题解用了一种类似预处理答案的做法。核心思路是在每一次组成队伍的时候就查找可能的最小值，并在过程中不断更新。循环两次 $N^2$ ，加上查找最近值 $logN$ ，恰好能满足复杂度的要求。
我们用前缀和预处理求和，然后用一个有序集合存储第一个队伍可能的力量值总和。每一次循环，对于未在第一个队伍的同学就计算可能组成的第二个队伍的力量的总和的值。然后再在集合中二分查找找到一个最相近的值减去，更新 $ans$ 。最后结束时，我们再更新当第一支队伍取到第 $i + 1$ 个同学时，可能组成的队伍的力量值总和。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
using ll = long long;
5
#define endl '\n'
6
#define mod 998244353
7

8

9
void solved(){
10
    int n;
11
    cin >> n;
12
    vector<ll> A(n + 1);
13
    for (int i = 1; i <= n;i++){
14
        cin >> A[i];
15
    }
16
    if(n == 1){
17
        cout << 0 << '\n';
18
        return;
19
    }
20
    vector<ll> B(n + 1);
21
    for(int i = 1; i <= n;i++){
22
        B[i] = B[i - 1] + A[i];
23
    }
24
    multiset<ll> Lsum;
25
    Lsum.insert(A[1]);
26
    ll ans = LLONG_MAX;
27
    for (int j = 2; j <= n;j++){
28
        for (int r = j; r <= n;r++){
29
            ll sumr = B[r] - B[j - 1];              //j每次循环第二支队伍有n - r种可能的力量总值。
30
            auto it = Lsum.lower_bound(sumr);
31
            if(it != Lsum.end()){                   //第一个大于等于sumr的判断一次
32
                ans = min(ans, abs(sumr - *it));
33
            }
34
            if(it != Lsum.begin()){                 //第一个小于sumr的判断一次
35
                --it;
36
                ans = min(ans, abs(sumr - *it));
37
            }
38
        }
39
        for (int l = 1; l <= j;l++){                  //取到下一个新同学后，更新添加suml里的元素
40
            ll suml = B[j] - B[l - 1];
41
            Lsum.insert(suml);
42
        }
43
    }
44
    cout << ans;
45
}
46

47
int main() {
48
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
49
    solved();
50
    return 0;
51
}

P12349 翻转硬币#

比较难的一道 $dp$ ，对于我这种蒟蒻备赛来说其实没有什么补题的必要了。（）不过还是贴一下我学习时 $AC$ 的代码吧，详细解析可以参考一下洛谷该题题解的第一个，再加 $AI$ 硬啃一下。（我就是这样）
题目链接：https://www.luogu.com.cn/problem/P12349
参考题解：https://www.luogu.com.cn/problem/solution/P12349
大致题意：给定 $n$ 行 $m$ 列的硬币，每一个硬币的价值取决于上下左右相邻的硬币中与其正反相同的硬币数之和的平方。我们可以进行任意次操作让任意一行的硬币翻转。求硬币的价值之和最大可能是多少。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
typedef long long ll;
5
#define endl '\n'
6

7
int n, m;
8
int dp[1010][2];    //1.第i行。2.是否和原来相反(0为相同，1为不同)
9
int a[1010][1010];   //dp[i][{0,1}]为前i - 1行中第i行与第i - 1行的贡献
10
char c[1010][1010];
11

12
//calc，p1为第x行和第x-1行的状态{0,1}，p2为第x行和第x+1行的状态{0,1}
13
int calc(int x, int p1,int p2){
14
    int sum = 0;
15
    for (int j = 1; j <= m; j++){
16
        int cnt = 0;
17
        if(x > 1){
18
            cnt += ((a[x][j] ^ p1) == a[x - 1][j]);
19
        }
20
        if(x < n){
21
            cnt += ((a[x][j] ^ p2) == a[x + 1][j]);
22
        }
23
        if(j > 1){
24
            cnt += (a[x][j] == a[x][j - 1]);
25
        }
26
        if(j < m){
27
            cnt += (a[x][j] == a[x][j + 1]);
28
        }
29
        sum += cnt * cnt;
30
    }
31
    return sum;
32
}
33

34
void solved(){
35
    cin >> n >> m;
36
    for (int i = 1; i <= n;i++){
37
        for (int j = 1; j <= m;j++){
38
            cin >> c[i][j];
39
        }
40
    }
41
    for (int i = 1; i <= n;i++){
42
        for (int j = 1; j <= m;j++){
43
            a[i][j] = c[i][j] - '0';
44
        }
45
    }
46
    dp[2][0] = calc(1, 0, 0);
47
    dp[2][1] = calc(1, 1, 1);
48
    for (int i = 3; i <= n + 1;i++){
49
        dp[i][0] = max(dp[i - 1][0] + calc(i - 1, 0, 0), dp[i - 1][1] + calc(i - 1, 1, 0));
50
        dp[i][1] = max(dp[i - 1][0] + calc(i - 1, 0, 1), dp[i - 1][1] + calc(i - 1, 1, 1));
51
    }
52
    cout << max(dp[n + 1][0], dp[n + 1][1]);
53
}
54

55
int main(){
56
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
57
    solved();
58
    return 0;
59
}