每日一题

储物点的距离

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

滑动窗口

https://ac.nowcoder.com/acm/problem/50528

思路：一求最小值为例，我们先搞一个双端队列，这样好在队尾和队首删除元素，队首放的都是当前窗口所到位置的最小值，当窗口移动到下一个元素时，如果它比队尾元素小，那么队尾元素就不可能是最小值了，所有我们删去它，再次进行判断，直到满足条件为止，如果比队尾元素大，就直接让它入队，在窗口移动到后面的时候还是有可能成为最小元素的。然后还要判断队列里面的元素长度是否超过了窗口的长度，如果超过那么让队首元素出列，直至满足条件。