4.4 周练习 选集

目录

1. P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteinsdfs回溯 

2.P2440 木材加工 二分

 3.P2678 [NOIP2015 提高组] 跳石头二分+双指针

4.P3799 妖梦拼木棒枚举+组合数学

5.尼克的任务 反向线性dp

6.15. 三数之和 - 力扣（LeetCode） (leetcode-cn.com)​​​​​​双指针和操作去重

1. P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteinsdfs回溯 

 常规的dfs，但是输出路径和判断出口有点琐碎。输出路径需要一个ath数组在更新最优解的时候拷贝占位数组used（因为used回回溯，搜索结束为空），出口的话枚举每个被选过的饲料（used==1）的维生素，如果有不满足就return。比较简单

#include <iostream>
#include<vector>
#include<algorithm>
#include<deque>
using namespace std;
int n, m;
deque<int>q;
vector<int>need(100, 0);
int per[100][100];
int used[100];
vector<int>path(100,0);
int ans = 99999999;
int judge() {for (int i = 1; i <= n; i++) {int sum = 0;for (int j = 1; j <= m; j++) {if (used[j]){sum += per[j][i];}}if (sum < need[i])return 0;}return 1;
}
void dfs(int dep,int now) {if (dep > m) {if (judge()) {if (ans > now) {ans = now;for (int j = 1; j <= m; j++) {path[j] = used[j];}}}return;}if (now >= ans)return;used[dep] = 1;dfs(dep + 1, now + 1);used[dep] =0;//回溯dfs(dep + 1, now);
}
int main()
{cin >> n;for (int j = 1; j <= n; j++) {cin >> need[j];}cin >> m;for (int j = 1; j <= m; j++) {for (int i = 1; i <= n; ++i) {cin >> per[j][i];}}dfs(1, 0);cout << ans << " ";for (int j = 1; j <= m; j++) {if(path[j]==1)cout << j << " ";}
}

2.P2440 木材加工 二分

 题意不是很好理解，主要是说每根木头如果可以，都要分出若干根长为l的小段，所有分出的小段数加起来要等于k。找出这个l，理解完题意二分枚举出合适的l使每个能分出l的小段加起来有k根即可。注意二分的范围为木材的最长的长度，而不是最短的长度，因为有些木材可以不分割。最后特判一下k很大输出0的条件即可。

#include <iostream>
#include<vector>
#include<algorithm>
#include<deque>
using namespace std;
int n,k;
int mn=-999999999;
vector<int>arr(1000001);
int sum = 0;
int judge(int t) {int ans = 0;for (int j = 1; j <= n; j++) {//得到长为l的话能分出几根if (arr[j] >= t)ans += arr[j] / t;}if (ans >= k)return 0;return 1;//说明l取大了，导致分不出那么多根小段//所以右边界减小到mid
}
int myfind() {int l = -1, r = mn;int mid;while (l + 1 != r) {mid = (l + r) >> 1;if (judge(mid))r = mid;elsel = mid;}return l;
}
int main()
{cin >> n>>k;for (int j = 1; j <= n; j++) {cin >> arr[j];sum += arr[j];mn = max(arr[j], mn);}if (sum / k == 0) {//特判，k和sum差距很大的时候1cm都分不出cout << 0;return 0;}cout << (myfind());
}

 3.P2678 [NOIP2015 提高组] 跳石头二分+双指针

写了蛮久的二分题，难点主要是没想到直接枚举答案然后写判断函数判断就行。只能说还不够熟练吧。思路就是枚举过程中跳的最短距离，但是要用二分，前提要是有序，那么最短距离的顺序和题目的关系是什么是个不太好想的点。这样，如果最短距离越大，那么剩下的距离和就越小，要使二分的距离是最短距离，那么后面要移开的石头就要更多才能使最短距离更大。所以关系就建立了，

——最短距离越大，移开的石头就越多，但是移开的石头有上限，所以根据当前枚举的最短距离来计算移开的石头，根据移开的石头数来调整枚举方向

具体表现为：

如果移开的石头大于m，说明最短距离取大了，需要减小，二分右指针左移。

如果移开的石头数小于等于m，说明满足条件，最短距离可以大于等于此时的值，二分左指针右移到mid

#include <iostream>
#include<vector>
#include<algorithm>
#include<deque>
#define ll long long
using namespace std;
long long len;
int n, m;
vector<ll>d(100001, 0);int judge(ll t) {ll sum = 0;ll j = 0, i = 0;//双指针模拟遍历while (i <= n) {i++;//当前的位置if (d[i] - d[j] < t)//如果两点距离小于最短距离，显然矛盾，移开该石头sum++;elsej = i;}if (sum <= m)return 1;return 0;
}
long long myfind() {ll l = 0, r = len + 1;ll mid;while (l + 1 != r) {mid = (l + r) >> 1;if (judge(mid)) {l = mid;}elser = mid;}return l;
}
int main()
{cin >> len >> n >> m;for (int j = 1; j <= n; j++) {cin >> d[j];}d[n + 1] = len;//d[0]相当于原点0，d[n+1]看作终点不能省cout << myfind();
}

4.P3799 妖梦拼木棒枚举+组合数学

 桶计数，枚举正三角形的长度和其中一条短边，进而讨论第三条短边的情况，情况略微有些复杂，要分两条短边是否相等的情况，然后根据乘法原理用组合数求出每条边的方案数，相乘。具体见代码，注意取模。

#include <iostream>
#include<vector>
#include<algorithm>
#include<set>
#define ll long longusing namespace std;
int n;
int mod = 1e9 + 7;
vector<int>arr(50000,0);ll c(ll x, ll k=2) {return (x*(x-1)/2)%mod;
}
int main()
{cin >> n;int mx;ll sum = 0;for (int j = 1; j <= n; j++) {int t;cin >> t;arr[t]++;mx = max(mx, t);}for (int j = 2; j <= mx;j++) {for (int i = 1; i <= j/2; i++) {if (j - i == i&&arr[j]>=2&&arr[i]>=2) {//两短边相同sum = sum % mod + (c(arr[j]) * c(arr[i])) % mod;}else if (j - i != i && arr[j] >= 2 && arr[i] >= 1 && arr[j - i] >= 1) {
//两短边不同sum = sum % mod + (c(arr[j]) * arr[i] * arr[j - i])%mod;}}}cout << sum ;}

5.尼克的任务 反向线性dp

 正向直接推导会发现前一个状态会影响下一个状态的选择，也就是工作时间内不能选择工作。所以反向计算就变成了一个类似完全背包的问题

详情见P1280 尼克的任务 反向线性dp_Brokenrivers的博客-CSDN博客

//#include<bits/std c++.h>
#include <iostream>
#include<ctime>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<unordered_map>
#include<unordered_set>
#define ll long long
using namespace std;
struct node {int p, last;}task[100001];
int cmp(node a, node b) {return a.p > b.p;
}int n, k;
ll dp[10002];
int sum[100002];
int idx[100002];
int cnt = 1;
int main()
{cin >> n >> k;for (int j = 1; j <= k; j++) {cin >> task[j].p >> task[j].last;task[j].end = task[j].p + task[j].last - 1;sum[task[j].p]++;idx[task[j].p] = j;//idx表示同一个起始时间最后一个任务}for (int j = n; j >=1; j--) {if (sum[j] == 0) {dp[j] = dp[j + 1] + 1;}else {for (int i = 0; i < sum[j]; i++) {//回溯同一时间的其他任务dp[j] = max(dp[j + task[idx[j] - i].last], dp[j]);
//task[idx[j]-i]表示每个起始时间为 j 的任务}}}cout << dp[1];return 0;
}

6.15. 三数之和 - 力扣（LeetCode） (leetcode-cn.com)​​​​​​双指针和操作去重

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>>arr;arr.reserve(nums.size()>256?256:nums.size());//预先分配空间if(nums.size()<3)return arr;sort(nums.begin(),nums.end());if(nums[0]>0)return arr;for(int k=0;k<nums.size();k++){int i=k+1,j=nums.size()-1;//左右双指针if(k && nums[k]==nums[k-1])//去重，当前数讨论过，跳过continue;while(i<j){long long sum=nums[i]+nums[j]+nums[k];if(sum>0){--j;}else if(sum<0){++i;}else{arr.push_back(vector<int>{nums[k],nums[i],nums[j]});++i;--j;while(i<j&&nums[i]==nums[i-1])++i;while(i<j&&nums[j]==nums[j+1])--j;}}}return arr;}
};