img

牛客周赛8

这场题比较水

除了最后一个树形dp比较典型

A

注意左右

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
//by Totoro
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
signed main()
{
int n;
cin>>n;
vector<int>a;
rep(i,1,n)
{
    int x;
    cin>>x;
    a.push_back(x);
}
int x,y;
cin>>x>>y;
rep(i,0,n-2)
{
if((a[i]==x&&a[i+1]==y)||(a[i]==y&&a[i+1]==x))
{
    cout<<"Yes"<<'\n';
    return 0;
}
}
cout<<"No"<<'\n';
return 0;
}

B

直接前缀和优化两边，进行求和即可

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
//by Totoro
//直接前缀和即可
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
const int N=1e5+100;
int sum[N];
signed main()
{
    int n;
    cin>>n;
    vector<int>a(n);
    rep(i,1,n)
    {
        int x;
        cin>>x;
        a.push_back(x);
        sum[i]=sum[i-1]+x;
    }   
    int x,y;
    cin>>x>>y;
    if(x>y)
    {
        swap(x,y);
    }
    cout<<min(sum[y-1]-sum[x-1],sum[n]-sum[y-1]+sum[x-1]);
    return 0;
}

C

不加证明的贪心

双指针不断大小大的放

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
//by Totoro
//这题很一眼
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
signed main()
{
//一个排列，取两项相加，然后最大值最小值要尽量小
//感觉就是直接贪心
//都不需要证明的
//直接写就行
int n;
cin>>n;
vector<int>ans;
int l=1;
int r=n;
while(l<=r)
{
    if(l==r)
    {
        ans.push_back(l);
        break;
        //边界
    }
    else
    {
        ans.push_back(l);
        ans.push_back(r);
        l++;
        r--;
    }
}
for(auto c:ans)
{
    cout<<c<<' ';
}
cout<<'\n';
    return 0;
}

D

注释很详细

这种题很典型，还是需要好好写一下。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//by Totoro
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
const int N=1e5+100;
int dp[N][2];
//dp数组
vector<int>edge[N];
//存边数组
int a[N];
//存节点值
void dfs(int u,int fa)
{
    for(auto v:edge[u])
    {
if(v==fa)
{
    continue;
}
dfs(v,u);
dp[u][0]+=max(dp[v][0],dp[v][1]);
    }
for(auto v:edge[u])
{
    if(v==fa)
    {
        continue;
    }
    int sum=a[u]*a[v];
    int t=sqrt(sum);
    if(t*t==sum)
    {
        dp[u][1]=max(dp[u][1],dp[v][0]+2+dp[u][0]-max(dp[v][0],dp[v][1]));
    }
}
}
signed main()
{
//两个白色并且权值乘积是完全平方数就可以染红
//只需要建树，然后跑dp应该就可以
//那么就需要定义状态
//dp[i][1]表示以i为节点，然后子节点已经染色了的最大数量
//dp[i][0]表示以i为节点，然后子节点还没有染色的最大数量
//这点显然是显而易见
//dp[i][0]=求和max(dp[j][0],dp[j][1])
//如果是这个子节点已经进行选择了
//j就是选择的了那个节点
//注意要先推理dp[i][0]
//再推理dp[i][1]
//dp[i][1]=max(dp[i][1],2+dp[i][0]-max(dp[j][0],dp[j][1]))
int n;
cin>>n;
rep(i,1,n)
{
    cin>>a[i];
}
rep(i,1,n-1)
{
    int x,y;
    cin>>x>>y;
    edge[x].push_back(y);
    edge[y].push_back(x);
}
dfs(1,0);
cout<<max(dp[1][1],dp[1][0]);
    return 0;
}
img