牛客练习赛98_部分题解

本篇题解只是记录我的做题过程代码，不提供最优解
（另外这里所有的时间复杂度都只分析单个样例，不算$t$的时间复杂度）

A

点击此处查看对应的题目.
本题设计算法：贪心
贪心策略：选择一轮中伤害高的攻击方式即可
记得开long long

时间复杂度 $O(1)$

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5   10;

int main()
{
    ll h,a,b;
    cin >> h >> a >> b;
    ll x = 0,cnt = 0;
    
    if (a > 3 * b) {
        x = a;
    }else x = 3 * b;
    
    ll r = x * 5;
    ll res = h / r   ((h % r) ? 1 : 0);
    cout << res << '\n';
    
    return 0;
}

B

点击此处查看对应的题目.
本题设计算法：贪心

贪心策略：从大到小排序后,从大到小判断当前数值与前一个数值相加是否>=m。

如此即可保证所有的 $1\le i\ne j\le k$, x i x j ≥ m x_i x_j \geq m xi xj≥m

时间复杂度 $O(nlogn)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e6   10;
int a[N];

void solve()
{
    int n,m,res =0,minn = 0;
    cin >> n >> m;
    for (int i = 1;i <= n;i    ) scanf("%d",&a[i]);
    sort(a   1, a   n   1, greater<>());
    
    for (int i = 1; i <= n;   i) {
        if (a[i]   a[i - 1] >= m)  res;
        else break;
    }
    cout << res << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t -- ) solve();
    return 0;
}

C

点击此处查看对应的题目.
本题设计算法：位运算 排列组合

首先，要明白异或的性质：只有相等，异或才可以为0。所以题目要求的三元组传递异或为0即为三元组必须完全相等。

所以第一步，需要统计出所有数的数量进行排列组合，在其中选择三个，即 C x 3 C_x^3 Cx3 ,其中 $3\le x\le n$。然而，实际上随着x增长， C x 3 C_x^3 Cx3 的变化也是有规律，规律见代码。通过这个规律，我们就可以得到任意x下， C x 3 C_x^3 Cx3的值，并将这个值记录regualr数组。

从而也就可以求出所有大于等于3的组合数，最后算上单点变化的过程就是打答案了(通过前后 regular 变化计算)。

note：要注意，因为最后计算时是分开计算的，所以为防止输入数据不变化（a[x] = y）导致的分步状态没有及时更新，我们因该要即使将 cnt[a[x]] –

时间复杂度 $O(N)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int N = 1e6   10;
ll a[N],regular[10 * N],cnt[10 * N];

int main()
{
    ll n,m;
    scanf("%lld%lld",&n,&m);
    
    for (int i = 1;i <= n;i    ) {
        scanf("%lld",&a[i]);
        cnt[a[i]]   ;
    }
    regular[3] = 1;//规律提取
    for (int i = 4,j = 3,k = 3;i <= N;i   ,k    ) {
        regular[i] = regular[i - 1]   j;
        j  = k;
    }

    ll res = 0;
    for (int i = 1;i <= N;i    ) 
        if (cnt[i] >= 3) 
            res  = regular[cnt[i]];
    
    while (m -- ) {
        ll x,y;
        cin >> x >> y;
       
        res -= regular[cnt[a[x]]] - regular[cnt[a[x]] - 1];
        cnt[a[x]] --;//note
        res  = regular[cnt[y]   1] - regular[cnt[y]];
        
        cnt[y]   ;
        a[x] = y;
        printf("%lld\n",res);
    }
    
    return 0;
}

这篇好文章是转载于：学新通技术网