喜晴 宋 · 范成大 窗间梅熟落蒂，墙下笋成出林。 连雨不知春去，一晴方觉夏深。

热烈的盛夏，小虫伏在树影里的鸣叫， 绿叶挂着雨滴在下雨天闪闪发光如宝石。 飞扬的笑声被风卷得更远， 单车骑过水洼溅起水纹， 吹着咯吱作声的风扇吃一口西瓜， 一切冲动和灿烂都是夏日限定。

目标：理解一下T1的奇数偶数，T2的暴力，T3的规律推出020，202，T4树形dp的状态转移方程的推导和状态的确立

img

牛客周赛 Round 15

A

一眼以为直接前缀和暴力枚举

原来我是nt，奇数和偶数直接看最后一位数即可

右边的最后一位数又是确定的，只需要枚举前面的最后一位数即可

这样不就是直接O(n)暴力枚举一遍即可，前缀和个sum()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int ans = 0;
    string s;
    cin >> s;
    int f = (s[s.size() - 1] - '0') % 2;
    for (int i = 0;i < s.size() - 1;i++)
    {
        if ((s[i] - '0') % 2 == f)
        {
            ans ++;
        }
    }
    cout << ans;
    return 0;
}

B

总共也就26个字母，直接暴力

注意环形的话就是 abs(a-b)

和26-abs(a-b)了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
string s; 
int  main(){
    cin>>s;
    int ans=1e9+10;
    for(int i='a';i<='z';++i){
        int res=0;
        for(int j=0;j<s.size();j++){
            int t=abs(s[j]-i);
            res+=min(t,26-t);
        }
        ans=min(res,ans);
    }
    cout<<ans<<endl;
}

C

3的话有几种，就是直接

101

020

121

202

只有这些情况了

最后进行剔除之后

发现101和121也是不合理的，如果大于3的话，最后只能够推出202 ,020这两种情况了

一定是02交替着出现，不然一定不满足题意。

直接复制进行比对就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<string>
using namespace std;
bool is(string s,string t){
    if(s.size()!=t.size())return false;
    for(int i=0;i<s.size();i++)
        if(s[i]!=t[i]&&s[i]!='?')
            return false;
    return true;
}
int main(){
    string s,t="",tt="";
    cin>>s;
    for(int i=0;i<s.size();i++)t+=char('0'+i%2*2),tt+=('0'+(i+1)%2*2);
    string c[7]={"1","12","101","121","21",t,tt};
    for(int i=0;i<7;i++)
        if(is(s,c[i])){
            cout<<c[i]<<endl;
            return 0;
        }
    cout<<-1<<endl;
}

D

一眼树形dp，不过本题不是点不相邻，而是边

需要进行理解一下： 需要权值最大，就要计算子树最大时候

  • 状态为0的时候，表示未选择该节点，那么儿子选不选择其他边都无所谓，只需要在状态里面选择最大值即可。
1
dp[u][0] += max(dp[v][0] , dp[v][1]);    //  v是u的儿子

  • 复杂一点的就是1的时候了，代表要选择这样一条边了，那么他的儿子就不能被选择了，这样会亏损权值，子节点的贡献值为max(dp[v][0],dp[v][1]),然后最后得到的是dp[v][0]，因此是需要进行减去的。

    就是dp[v][0] - max(dp[v][1] , dp[v][0])

    然后权值自然要加上去

    但还有一个问题，其他子节点要怎么说呢，其实其他子节点就是dp[u][0]，直接忽视这个点。

    最后就得到了

1
2
dp[u][1] = max(dp[u][1] , dp[v][0] - max(dp[v][0] , dp[v][1]) + w[i]) + dp[u][0];
//注意这里的dp[u][0]得更新完再加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pii pair<int, int>
#define INF 0x3f3f3f3f
const int N = 1e5 + 3, mod = 1e9 + 7;

int n;
vector<pii> e[N];
ll dp[N][2];

void dfs(int u, int fa)
{
    for (auto x : e[u])
    {
        auto [v, c] = x;
        if (v == fa) continue;
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }
    for (auto x : e[u])
    {
        auto [v, c] = x;
        if (v == fa) continue;
        dp[u][1] = max(dp[u][1], dp[u][0] + c - max(dp[v][0], dp[v][1]) + dp[v][0]);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i < n; i++)
        {
            int u, v, c;
            cin >> u >> v >> c;
            e[u].push_back({v, c});
            e[v].push_back({u, c});
        }
        dfs(1, 0);
        cout << max(dp[1][0], dp[1][1]);
    }
    return 0;
}
img