每日一题
储物点的距离
https://ac.nowcoder.com/acm/problem/14683
思路：
1：首先预处理三个前缀和，a--前i个储物点的距离和，x_sum--前i个储物点的东西搬到第一个储物点的和，n_sum前i个储物点的东西和.
2：判断x与l和r的大小，如果x>=r,那么就先把[l,r]的东西全部搬到储物点1去，然后在全部搬到x点去，我们可以发现对于每个在[l,r]里面的j，[1,j]是重复搬了的，那么我们要减去，也就是减去x_sum[r]+x_sum[l-1]。
3：如果x<=l,也是先把[l,r]的东西全部搬到储物点1去，然后在全部搬到x点去，同理我们可以发现所有东西在[1,x]是重复搬了的，也就是减去(n_sum[r] - n_sum[l-1])*a[x].
4：如果l<x<r,和2，3算法相同。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e9+7;
using namespace std;
//781
LL a[200005],n_sum[200005],x_sum[200005];
int main()
{
int n,m;
cin >> n >> m;
a[1] = 0;
for(int i = 2; i <= n; i++) cin >> a[i];
for(int i = 2; i <= n; i++) a[i] = (a[i-1] + a[i]) % mod;
for(int i = 1; i <= n; i++){
cin >> n_sum[i];
x_sum[i] = (n_sum[i]*a[i] % mod + x_sum[i-1] % mod) % mod;
n_sum[i] = (n_sum[i - 1] + n_sum[i]) % mod;
}
while(m--){
int x,l,r;
LL ans = 0;
cin >> x >> l >> r;
if(x >= r){
ans = (((n_sum[r] - n_sum[l - 1] + mod) % mod * a[x] % mod) - (x_sum[r] - x_sum[l - 1] + mod) % mod + mod) % mod;
}
else if(x <= l){
ans = ((x_sum[r] - x_sum[l - 1] + mod) % mod - ((n_sum[r] - n_sum[l - 1] + mod) % mod * a[x] % mod) + mod)% mod;
}
else{
ans = (((n_sum[x] - n_sum[l - 1] + mod) % mod * a[x] % mod) - (x_sum[x] - x_sum[l - 1] + mod) % mod + mod) % mod;
ans = (ans % mod + ((x_sum[r] - x_sum[x - 1] + mod) % mod) - ((n_sum[r] - n_sum[x - 1] + mod) % mod * a[x] % mod) + mod) % mod;
}
cout << ans % mod << endl;
}
return 0;
}
旅游 树形dp
https://ac.nowcoder.com/acm/problem/15748
#include <bits/stdc++.h>
#include <iostream>
#define LL long long
#define inf 0x3f
const int mod = 1e9+7;
using namespace std;
int dp[500005][2];
vector<int>a[500005];
void dfs(int s,int f)
{
dp[s][1] = 1;
for(int i = 0; i < a[s].size(); i++){
if(a[s][i] == f) continue;
dfs(a[s][i],s);
dp[s][0] += max(dp[a[s][i]][1],dp[a[s][i]][0]);
dp[s][1] += dp[a[s][i]][0];
}
}
int main()
{
int s,x,y,n;
cin >> n >> s;
for(int i = 1; i < n; i++){
cin >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
dfs(s,-1);
cout << dp[s][1];
return 0;
} Protecting the flowers
https://ac.nowcoder.com/acm/problem/25043
题目大意：每个牛牵回牛舍需要Ti分钟，牵某个牛时，其他牛会继续吃花，问怎样牵牛可以使得破坏的花最少。
思路：对于两头牛c1,c2,当先牵c1时，破坏花的数量为sum1=c1d2,当先牵走c2时，sum2=c2d1,比较sum1和sum2,优先选择小的，所有我们先按ci*dj从小到大排序。
#include <bits/stdc++.h>
using namespace std;
struct S{
int t,d;
}s[100005];
bool cmp(S a,S b)
{
return a.t*b.d < b.t*a.d;
}
int main()
{
int n;
long long sum = 0;
cin >> n;
for(int i = 1; i <= n; i++) cin >> s[i].t >> s[i].d,sum += s[i].d;
sort(s+1,s+n+1,cmp);
long long ans = 0;
for(int i = 1; i <= n; i++){
sum -= s[i].d;
ans += sum * s[i].t * 2;
}
cout << ans;
return 0;
} codeforce：01背包
https://ac.nowcoder.com/acm/problem/21314
思路：和上一题类似，假设两道题目c1,c2,先做c1,总得分sum1=mp1-pp1t1+mp2-pp2(t2+t1),sum2=mp2-pp2t2+mp1-pp1(t1+t2),sum1-sum2=pp1t2-pp2t1,假设sum1>sum2,即pp1t2>pp2t1,按这个排序选题做即可.
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
//void lowit(x){return x&(-x)};
const int mod = 1e9+7;
using namespace std;
//781
struct node{
LL mp,pp,t;
}s[55];
bool cmp(node a,node b)
{
return a.t * b.pp < b.t * a.pp;
}
LL dp[100005];
int main()
{
int n,t;
cin >> n >> t;
for(int i = 1; i <= n; i++) cin >> s[i].mp;
for(int i = 1; i <= n; i++) cin >> s[i].pp;
for(int i = 1; i <= n; i++) cin >> s[i].t;
sort(s+1,s+n+1,cmp);
LL ans = 0;
for(int i = 1; i <= n; i++){
for(int j = t; j >= s[i].t; j--){
dp[j] = max(dp[j],dp[j - s[i].t] + s[i].mp - s[i].pp*j);
}
}
for(int i = 0; i <= t; i++) ans = max(ans,dp[i]);
cout << ans;
return 0;
}
滑动窗口
思路：一求最小值为例，我们先搞一个双端队列，这样好在队尾和队首删除元素，队首放的都是当前窗口所到位置的最小值，当窗口移动到下一个元素时，如果它比队尾元素小，那么队尾元素就不可能是最小值了，所有我们删去它，再次进行判断，直到满足条件为止，如果比队尾元素大，就直接让它入队，在窗口移动到后面的时候还是有可能成为最小元素的。然后还要判断队列里面的元素长度是否超过了窗口的长度，如果超过那么让队首元素出列，直至满足条件。
#include <bits/stdc++.h>
#include <iostream>
const int Max = 100 * 100 * 100 + 5;
#define LL long long
const int mod = 1e9+7;
//const int inx = INT_MAX;
using namespace std;
// srand(time(NULL));
// m = rand() % 1000 + 1;
//定义i i(A) i+n i+n(B) i+n+n i+n+n(C)
//bitset<Max>s,q;
deque<int>q1,q2;
int b1[1000005],b2[1000005];
int a[1000005];
int main()
{
int n,k,i,op,sp;
cin >> n >> k;
for(i = 1; i <= n; i++){
cin >> a[i];
}
for(i = 1; i <= n; i++){
while(!q1.empty() && i - k >= q1.front()){
q1.pop_front();
}
while(!q1.empty() && a[i] <= a[q1.back()]){
q1.pop_back();
}
while(!q2.empty() && i - k >= q2.front()){
q2.pop_front();
}
while(!q2.empty() && a[i] >= a[q2.back()]){
q2.pop_back();
}
q1.push_back(i);
q2.push_back(i);
if(i >= k) b1[i] = (a[q1.front()]);
if(i >= k) b2[i] = (a[q2.front()]);
}
for(i = k; i <= n; i++){
cout << b1[i] << " ";
}
cout << endl;
for(i = k; i <= n; i++){
cout << b2[i] << " ";
}
return 0;
}
wyh的物品：二分+01分数规划
思路：
设单位价值为x，则 x = (vi+...+v(i+k-1)) / (wi+...+w(i+k-1))
拆开：vi - wi*x + ...+ v(i+k-1) - w(i+k-1)*x = 0
用数组保存每个vi - wi*x ....,排好序后选择前k个，二分答案时要满足 vi - wi*x + ...+ v(i+k-1) - w(i+k-1)*x >= 0即可。
为啥排序选前k个，因为如果前k个都不满足，后面的比前k个都小，肯定不能满足。
#include <bits/stdc++.h>
#include <algorithm>
#define mod 1000000007
#define LL long long
using namespace std;
int v[100005],w[100005],n,k;
double v1[100005];
bool cmp(double a,double b)
{
return a > b;
}
bool pd(double x)
{
int i;
for(i = 1; i <= n; i++){
v1[i] = v[i] * 1.0 - x * w[i];
}
double sum = 0;
sort(v1 + 1,v1 + n + 1,cmp);
for(i = 1; i <= k; i++){
sum += v1[i];
}
if(sum >= 0) return true;
else return false;
}
int main()
{
int T,i;
cin >> T;
while(T--){
cin >> n >> k;
for(i = 1; i <= n; i++){
cin >> w[i] >> v[i];
}
double l = 0,r = 100000;
while(abs(l - r) > 0.00000001){
double mid = (l + r) / 2.0;
if(pd(mid)) l = mid;
else r = mid;
}
printf("%.2f\n",l);
}
return 0;
}
查看11道真题和解析
