【牛客算法周周练1】题解A/C/E

https://ac.nowcoder.com/acm/contest/5086#question

A 前缀和

一个数移到左边所减少的量= 增加的量为
总的减少量
维护前缀和，枚举下标从k~n-1,找出最少的减少量delta即可

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+5;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n;scanf("%d",&n);
        int k;scanf("%d",&k);
        int nums[maxn];
        ll sum[maxn]={0};
        unsigned ll ans=0;
        for(int i=1;i<=n;++i){
            scanf("%d",&nums[i-1]);
            ans+=i*nums[i-1];
            sum[i]=sum[i-1]+nums[i-1];
        }
        ll delta = 9223372036854775807;
        for(int i=n-1;i>=k;--i){
            ll dd = nums[i]*k-sum[i]+sum[i-k];
            delta=min(delta,dd);
        }
        printf("%lld\n",ans-delta);
    }
}

C 树上距离

求树上两个节点的距离有个性质：

这道题我们求出B 到 C，C到 1的距离和 dis1
求出A 到 1的距离 dis2
如果 肯定抓不到
如果 肯定抓的到
如果 时且 则他们俩最终会在1相遇,抓不到，其他情况老师可以去守株待兔

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LONGLONGMIN -922337203685477580
const int maxn = 2e5 + 10;
#define MAXN 200010
int p[MAXN], h[MAXN], ne[MAXN]; 
int num = 0;
int dep[MAXN / 2], f[MAXN / 2][21];
int MAXDEPTH;
//加边
void addEdge(int from, int to)
{
    p[++num] = to; 
    ne[num] = h[from];
    h[from] = num;

    p[++num] = from;
    ne[num] = h[to];
    h[to] = num;
}

// 预处理深度和倍增
void dfs(int u, int father)
{
    dep[u] = dep[father] + 1;
    for (int i = 1; (1 << i) <= dep[u]; ++i) {
        f[u][i] = f[f[u][i - 1]][i - 1];
    }
    for (int i = h[u]; i; i = ne[i])if (p[i] != father) {
            f[p[i]][0] = u;
            dfs(p[i], u);
        }
}
// 求LCA
int LCA(int u, int v){
    if(dep[u] > dep[v]) swap(u, v);
    int hu = dep[u], hv = dep[v];
    for(int det = hv - hu, i = 0; det; det >>= 1, i++){
        if(det & 1){
            v = f[v][i];
        }
    }
    if(u == v){
        return u;
    }
    for(int i = MAXDEPTH - 1; i >= 0; i--){
        if(f[u][i] == f[v][i]) continue;
        u = f[u][i];
        v = f[v][i];
    }
    return f[u][0];
}
void init()
{
    MAXDEPTH = 20;
    num = 0;
    memset(f, 0, sizeof(f));
    memset(h, 0, sizeof(h));
}
int main()
{
    int t;
    cin >> t;
    while (t--) {
        init();
        int n, q;
        cin >> n >> q;
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            addEdge(u, v);
        }
        dep[0]=-1;
        dfs(1, 0);
        while (q--) {
            int a, b, c;
            cin >> a >> b >> c;
            if (b == c && b == 1) {
                cout << "NO\n";
                continue;
            }
            int dis1 = dep[b] + dep[c] - 2 * dep[LCA(b, c)] + dep[c];  // B -> C的距离+ C -> 1的距离dep[c]
            int dis2 = dep[a];
           // cout<<dis1<<" " <<dis2<<" "<<LCA(b, c)<<endl;
            if (dis1 < dis2) {
                cout << "NO\n";
            } else if (dis1 > dis2) {
                cout << "YES\n";
            } else {
                if (LCA(c, a) == 1)
                    cout << "NO\n";
                else
                    cout << "YES\n";
            }
        }
    }
    return 0;
}

E dfs打表预处理

dfs打表预处理出只含有4、7的数字
然后O(n)顺着往下找即可，比如l=48 找到第一个大于l的数为74 则[48,74]这个区间的数的下一个幸运数都为74。参看代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
ll a[N], k = 0;
void dfs(ll n)  //打表
{
    if(n>2e10) return;
    a[k++] = n;
    dfs(n*10+4);
    dfs(n*10+7);
}

int main()
{
    dfs(0);
    sort(a,a+k);
    ll l,r;
    scanf("%lld %lld",&l,&r);
    ll sum = 0, i = l, x = 0;
    while(i<=r)
    {
        while(a[x]<i) x++;
        sum += a[x]*(min(r,ax])-i+1);  
        i = a[x]+1;  //下一次从a[x]之后开始
    }
    printf("%lld\n",sum);
    return 0;
}