11月10日

1、CF 1359D(2000分):

​ 选出一个区间[l,r]，使得$sum\{a[l], … , a[r]\} - max\{a[l], … ,a[r]\}$最大
​ 数据范围：$-30 <= a[i] <= 30, n = 100000$

分析：

维护一个前缀和，如果当前$sum\{a[l],…,a[r]\}$的值为负数，那么将$[1,r]$段加入答案一定不会更优，将$sum$ 直接清零

• 如果区间内的最大值大于枚举的最大值，那么将维护的前缀和清零，不选择这一段
• 如果区间内的最大值小于枚举的最大值，sum - maxi不是最优的，不会对答案有影响

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100005;

int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    int ans = 0;
    for(int maxv = 0; maxv <= 30; maxv ++ )
    {
        int sum = 0;
        for(int i = 1; i <= n; i ++ )
        {
            sum += a[i];
            if(a[i] > maxv) sum = 0;
            sum = max(sum, 0);
            ans = max(ans, sum - maxv);
        }
    }
    cout << ans << endl;
    return 0;
}

2、CF 1388D（2000分）:

有两个长度为n的数组a, b，每次可以选择一个位置$i$，将$a[i]$的值加入到$ans$中。如果$b_i \ne -1$，就将$a[b_i] += a[i]$

你需要进行$n$次以上操作，求出一个操作序列，使得$ans$的值最大

数据范围：$1 \le n \le 200000$，$-10^6 \le a_i \le 10^6$, $1 \le b_i \le n \ or \ b_i = -1$

分析：

经研究可知，该图是拓扑图，在图上进行拓扑排序。

维护一个队列和一个栈

对于一个点$x$，如果它的值大于等于0，就将其加入队列，并将其值下放到它的所有子节点

如果它的值小于0，就将其加入栈，最终统计答案的时候应该倒着输出（如果一对父子关系都是负的，那么一定先输出子节点）

#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int N = 200005;

int n;
int a[N], b[N];
int h[N], e[N], ne[N], idx;
int indeg[N];

queue<int> q;
vector<int> v;
deque<int> st;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

signed main()
{
    scanf("%lld", &n);
    for(int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &b[i]);
        add(i, b[i]);
        if(b[i] != -1) indeg[b[i]] ++ ;
    }

    for(int i = 1; i <= n; i ++ )
    {
        if(!indeg[i]) q.push(i);
    }
    int ans = 0;
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        int x = a[t];
        if(x >= 0) 
        {
            ans += x;
            v.push_back(t);
        }
        else
        {
            st.push_front(t);
        }
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(x >= 0) a[j] += x;
            if(-- indeg[j] == 0) q.push(j);
        }
    }

    for(auto it: st)  ans += a[it];
    cout << ans << endl;
    for(auto it : v)
    {
        cout << it << " ";
    }
    for(auto it : st)
    {
        cout << it << " ";
    }

    return 0;
}

3、CF 514C（2000分）

给定$n$个字符串，现在给出$m$次询问，每次询问是给出一个长度$\le 3·10^5$的串，

求原来这$n$个串中，有多少个串和给出的串，有且仅有一个位置不同

数据范围：

字符串中只有$a\ b\ c$三种字符

$1 \le n,m \le 3·10^5$

分析：

trie树+dfs

注意剪枝

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 300005, M = 600005;

int n, m;
int son[M][3], cnt[M], idx;
char str[N];
bool flag;

void insert(char str[])
{
    int p = 0;
    for(int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

void dfs(char str[], int p, int now, int len, int diff)
{
    if(flag) return;
    if(diff >= 2) return;
    if(now == len)
    {
        if(cnt[p] > 0 && diff == 1) flag = true;
        return;
    }
    for(int i = 0; i < 3; i ++ )
    {
        if(son[p][i])
        {
            if(char('a' + i) == str[now]) dfs(str, son[p][i], now + 1, len, diff);
            else dfs(str, son[p][i], now + 1, len, diff + 1);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ )
    {
        scanf("%s", str);
        insert(str);
    }

    while(m -- )
    {
        scanf("%s", str);
        flag = false;
        dfs(str, 0, 0, strlen(str), 0);
        if(flag) puts("YES");
        else puts("NO");
    }

    return 0;
}

4、CF 1399E1（2000分）

在一棵 $n$个节点、根为 $1$号点的树上，每一条边都有边权。

每次操作可以使一条边的边权除以 $2$ 并下取整，问最少操作多少次可以让点 $1$ 到各个叶子结点的距离和不超过 $S$。

数据范围：

多组数据

$n \le 10^5,S\le 10^{16},1\le w_i\le 10^6$

分析：

每条边不断除以2，最多不超过$\log n$次就可以变成0

所以可用一个优先队列，维护每条边对答案的贡献，是$w_i *经历这条边的叶子结点个数$

首先可以dfs一遍，求出经历每条边的叶子结点个数

然后将这些边存入优先队列，按照$(w_i - w_i/2)*经历这条边的叶子结点个数$从大到小排序，每次取出最优解，然后把新的边加入队列

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;

const int N = 100005, M = 2 * N;

int n;
int h[N], e[M], ne[M], idx;
ll w[M], S;
int cnt[M], cnt_p[M];

struct Edge
{
    ll w;
    int cnt;
    bool operator< (const Edge &t) const
    {
        return (w - w / 2) * cnt * 1ll < (t.w - t.w / 2) * t.cnt * 1ll;
    }
}edge[M];

priority_queue<Edge> qu;

void add(int a, int b, ll c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs1(int u, int fa)
{

    bool ifleaf = true;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        ifleaf = false;
        dfs1(j, u);
        cnt_p[u] += cnt_p[j];
        cnt[i] = cnt_p[j];
    }

    if(ifleaf) cnt_p[u] = 1;

}

void solve()
{
    idx = 0;

    while(!qu.empty()) qu.pop();

    scanf("%lld%lld", &n, &S);

    memset(h, -1, sizeof h);
    memset(cnt_p, 0, sizeof cnt_p);
    memset(cnt, 0, sizeof cnt);

    ll sum = 0;
    for(int i = 0; i < n - 1; i ++ )
    {
        int u, v;
        ll w;
        scanf("%lld%lld%lld", &u, &v, &w);
        add(u, v, w), add(v, u, w);
    }

    dfs1(1, -1);

    for(int i = 0; i < idx; i ++ )
    {
        if(w[i] > 0) sum += w[i] * cnt[i], qu.push({w[i], cnt[i]});
    }

    int ans = 0;

    while(sum > S)
    {
        auto t = qu.top();
        qu.pop();
        ll tmp = (t.w - t.w / 2) * t.cnt;
        sum -= tmp;
        ans ++ ;
        qu.push({t.w / 2, t.cnt});
    }
    printf("%lld\n", ans);
}


signed main()
{
    int t;
    scanf("%lld", &t);
    while(t -- ) solve();
    return 0;

}