牛客周赛 Round 15

游游的整数切割

遍历$0\le i<n-1$，判断多少个i满足$str[i]$和$str[n-1]$奇偶性相同

int main(){
    string s;cin>>s;
    int ans = 0;
    for(int i=0;i<s.size()-1;++i)
        if((s[i]-'0'+s[s.size()-1]-'0')%2==0)
            ans++;
    cout<<ans<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9

游游的字母串

计算所有字符变为字符c的代价
$$\underset{c}{\min }\sum _{i=1}^{n}min(abs(i-c),26-abs(i-c))$$

游游的问号替换

条件转化为：

• 字符串的相邻的字符都是不相等的。
• 连接三个字符之和为偶数

按照上述规则进行dfs剪枝即可找到答案

#include
using namespace std;
string str;
bool ok;
void dfs(int x)
{
    if(ok)return;
    if(x==str.size())
    {
        cout<<str<<endl;
        ok = 1;
        return;
    }
    if(str[x]=='?')
    {
        str[x] = '0';dfs(x);
        str[x] = '1';dfs(x);
        str[x] = '2';dfs(x);
        str[x] = '?';
    }
    else
    {
        if(x>0 && str[x]==str[x-1])
            return;
        if(x>1 && (str[x]-'0'+str[x-1]-'0'+str[x-2]-'0')%2==1)
            return;
        dfs(x+1);
    }
}

int main()
{
    cin>>str;    
    dfs(0);
    if(ok==0)
        cout<<-1<<endl;
}
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

游游的树上边染红

经典的树上dp
令$i$为$j$的父亲节点，有
$$\begin{gathered} dp[i][0]=\sum max(dp[j][1],dp[j][0]) \\ dp[i][1]=\underset{j}{\max }(\sum max(dp[j][1],dp[j][0]))-max(dp[j][1],dp[j][0])+w_{ij}+dp[j][0] \end{gathered}$$

#include
#include
#define ll long long
using namespace std;
vector<pair<int,int>>G[100010];
ll dp[100010][2];
void dfs(int u,int fa)
{
    ll mx = 0;
    for(auto [v,w]:G[u])
    {
        if(v==fa)continue;
        dfs(v,u);
        dp[u][0] += max(dp[v][0],dp[v][1]);
        mx = max(dp[v][0] +w-max(dp[v][0],dp[v][1]),mx);
    }
    dp[u][1] =dp[u][0]+mx;
}
int main()
{
    int n;cin>>n;
    for(int i=1;i<n;++i)
    {
        int x,y,w;cin>>x>>y>>w;
        G[x].push_back({y,w});
        G[y].push_back({x,w});
    }
    dfs(1,-1);
    cout<<max(dp[1][0],dp[1][1])<<endl;
}
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