笔试专题（九）

十字爆破（暴力）

题目链接

题解

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;
}