笔试专题（九）

十字爆破（暴力）

题目链接

题解

1. 暴力 + 预处理
2. 如果单纯的暴力写法是会超时的，遍历n*m的矩阵和每次在循环里求当前行和列，n * m * (n+m)->2e9的时间复杂度
3. 在输入的时候就预处理每一行的和和每一列的和，可以在后面输出的时候直接用，row[i] + col[j] - a[i][j]，注意一个细节就是当前点会加两次，减去一次

代码

#include<iostream>

using namespace std;
typedef long long ll;
ll n,m;
const int N = 1e6 + 10;
ll row[N];// 行
ll col[N];// 列


int main()
{
    scanf("%lld %lld",&n,&m);
    ll a[n][m];
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            scanf("%lld",&a[i][j]);
            // 预处理每一行
            // 预处理每一列
            row[i] += a[i][j];
            col[j] += a[i][j];
        }
    }    
    
     for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            printf("%lld ",row[i] + col[j] - a[i][j]);
        }
        cout << '\n';
    }
    
    return 0;
}

比那名居的桃子（滑动窗口/前缀和）

题目链接

题解

1. 暴力解法是维护一个长度为k的区间，每次都要重新从一个点出发走k个点的距离
2. 滑动窗口是两个指针维护一个k大小的固定区间，每次找到happy值大的区间更新begin，如果happy值相同的话并且羞耻值小的话，更新begin，注意一下细节，天数是从1开始的
3. 前缀和也是维护一个区间的快乐值和羞耻度，思路和滑动窗口是一样的

优先级最高的就是快乐值多的，其次就是快乐值相同，羞耻度小的优先，快乐值和羞耻度都相等是不用判断的，因为在前面判断的有一个这种值，后面也不更新，不就是最早的了

代码

// 滑动窗口
#include<iostream>

using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
ll h[N],s[N];// 快乐值和羞耻度
ll n,k;

int main()
{
    cin >> n >> k;
    for(int i = 0;i < n;i++) cin >> h[i];
    for(int i = 0;i < n;i++) cin >> s[i];
    
    ll hMax = 0,sMin = 0;
    ll hSum = 0,sSum = 0,begin = 0,left = 0,right = 0;
    
    while(right < n)
    {
        // 进窗口
        hSum += h[right];
        sSum += s[right];
        // 判断出窗口
        while(right - left + 1 > k)
        {
            hSum -= h[left];
            sSum -= s[left];
            left++;
        }
        // 更新结果
        if(right - left + 1 == k)
        {
            if(hSum > hMax)
            {
                hMax = hSum;
                sMin = sSum;
                begin = left;
            }
            if(hSum == hMax && sSum < sMin)
            {
                hMax = hSum;
                sMin = sSum;
                begin = left;
            }
        }
        right++;
    }
    cout << begin + 1<< '\n';
    
    return 0;
}

// 前缀和
#include<iostream>

using namespace std;

typedef long long ll;
ll n,k;
const int N = 1e5 + 10;
int a[N];// happy
int b[N];// shy
ll h[N];
ll s[N];

int main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++) cin >> b[i];
    
    for(int i = 1;i <= n;i++) 
    {
        h[i] = h[i-1] + a[i];
        s[i] = s[i-1] + b[i];
    }
    
    ll left = 1,right = k,hMax = 0,sMin = 0;
    ll hSum = 0,sSum = 0,begin;
    while(right <= n)
    {
        hSum = h[right] - h[left-1];
        sSum = s[right] - s[left-1];
        if(hSum > hMax)
        {
            hMax = hSum;
            sMin = sSum;
            begin = left;
        }
        else if(hSum == hMax && sSum < sMin)
        {
            hMax = hSum;
            sMin = sSum;
            begin = left;
        }
        left++;
        right++;
    }
    
    cout << begin << '\n';
    
    return 0;
} 

分组（暴力枚举 + 优化二分）

题目链接

题解

1. 方法一：暴力枚举
2. 如果声部的数量大于小组的数量，那么无法分配，会输出-1，题意理解，让人数多的小组也尽可能要少的人数
3. 可以枚举每组的人数，从小到大枚举，统计每个声部可以分成的组数，这些组数相加，如果小于等于m，就是合法的，hmax是某种声部人数最多的，可以分成一组的最大人数
4. 第二种方法：二分法，产生了一个二段性，check(mid) <= m（合法的）和check(mid) > m（不合法的），合法的在右边，right = mid，不合法的在左边，left = mid + 1

代码

#include<iostream>
#include<unordered_map>
#include<algorithm>
using namespace std;

unordered_map<int,int> cnt;// <种类,人数> 统计每种声部的人数
int n,m;

bool check(int k)
{
    int ans = 0;
    for(auto& [a,b] : cnt)
    {
        ans += b / k + (b % k == 0 ? 0 : 1);
    }
    return ans <= m;
}

int main()
{
    cin >> n >> m;
    
    int hashmax = 0;// 统计可以枚举的最多的人数
    for(int i = 0;i < n;i++)
    {
        int x;
        cin >> x;
        hashmax = max(hashmax,++cnt[x]);
    }
    
    int k = cnt.size();// 声部的种类
    // 声部的种类大于组数是无法分的
    if(k > m)
    {
        cout << -1 << '\n';
    }
    else
    {
       //for(int i = 1;i <= hashmax;i++)
       //{
         //  if(check(i)) 
           //{
             //  cout << i << '\n'; 
              // break;
          // }
       //}
        // 二分
        int l = 1,r = hashmax;
        while(l < r)
        {
            int mid = (l + r) / 2;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        cout << l << '\n';
    }    
    
    return 0;
}