Codeforces 每日一练 1228D+1155D+106C+877E

1228D Complete Tripartite

传送门
题意：给定一个图，询问是否可以把它划分成三分图，并且两个集合任意两个点之间都有连边，如果可行，输出染色方案，否则输出-1.
一道水题啦，一个集合内的点肯定是不存在连边的，那我们只需要从1开始把每个点相连的边染成当前点颜色+1即可（利用颜色大小关系防止重复即可），但最后染成的颜色可能仅仅只满足三分图，并不能满足任意两点存在连边，染完色判个边数即可。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 300005
#define IOS  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
vector<int> g[maxn];
int vis[maxn],tmp[maxn];
signed main(){
    IOS
    int n,m;
    cin>>n>>m;
    int t=m;
    while(t--){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int cnt=-1;
    for (int i = 1; i <=n ; ++i) {
        for(auto j:g[i]){
            if(j>i&&tmp[j]==tmp[i]){tmp[j]=tmp[i]+1;}
        }
        cnt=max(cnt,tmp[i]);
    }
    if(cnt!=2)cout<<-1;
    else {
        int a=0,b=0,c=0;
        for (int i = 1; i <=n ; ++i) {
            if(tmp[i]==0)a++;
            if(tmp[i]==1)b++;
            if(tmp[i]==2)c++;
        }
        if(a*b+b*c+c*a!=m)cout<<-1;
        else{
            for (int i = 1; i <=n ; ++i) {
                cout<<tmp[i]+1<<" ";
            }
        }
    }
    return 0;
}

1155D Beautiful Array

传送门
题意：一个数列，可以将某段连续子序列同时乘上x，也可以不进行操作，询问最大子段和。
看看范围是3e5，应该是线性或者加个状态，考虑到每个结点有染色或者不染色的可能，那就是一维带个状态的写法。
如果只开两种状态，会出现多段染色的情况，所以我们开三种状态，记录没染，正在染，已经染过，转移过程记录最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 300005
#define IOS  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll dp[maxn][4];
signed main(){
    IOS
    ll n,x;
    cin>>n>>x;
    ll ans=-1;
    for (int i = 1; i <=n ; ++i) {
        ll tmp;
        cin>>tmp;
        dp[i][1]=max(dp[i-1][1]+tmp,0ll);
        ans=max(ans,dp[i][1]);
        dp[i][2]=max(max(dp[i-1][1]+tmp*x,dp[i-1][2]+tmp*x),0ll);
        ans=max(ans,dp[i][2]);
        dp[i][3]=max(max(dp[i-1][2]+tmp,dp[i-1][3]+tmp),0ll);
        ans=max(ans,dp[i][3]);
    }
    cout<<ans;
    return 0;
}

106C Buns

传送门
题意：有n克面团和m种馅料，可以做带馅儿的也可以做不带馅儿的，每种价格不一，询问最大收益是多少。
多重背包裸题，对每种面包，根据所剩馅料的质量、面团质量以及需要材料的质量可以确定最大数量，这就转化成了多重背包问题，正好数据范围较小，甚至不需要优化。
（v、w写反了，见谅qwq）

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 20
#define IOS  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
struct bread{
    ll a,b,c,w,num;
}b[maxn];
struct bag{
    ll v,w;
};
ll dp[2000];
vector<bag> ba;
signed main(){
    IOS
    ll n,m,c0,d0;
    cin>>n>>m>>c0>>d0;
    for (int i = 1; i <=m ; ++i) {
        cin>>b[i].a>>b[i].b>>b[i].c>>b[i].w;
        b[i].num=min(n/b[i].c,b[i].a/b[i].b);
    }
    b[m+1]={n,n,c0,d0,n/c0};
    for (int i = 1; i <=m+1 ; ++i) {
        ll tmp=b[i].num,cnt=1;
        while(tmp>=cnt){
            ba.push_back({cnt*b[i].c,cnt*b[i].w});
            tmp-=cnt;
            cnt*=2;
        }
        if(tmp>0){
            ba.push_back({tmp*b[i].c,tmp*b[i].w});
        }
    }
    for (int i = 0; i <ba.size() ; ++i) {

        for (ll j = n; j >=ba[i].v ; j--) {
            dp[j]=max(dp[j],dp[j-ba[i].v]+ba[i].w);
        }
    }
    cout<<dp[n];
    return 0;
}

877E Danil and a Part-time Job

传送门
题意：给定一棵树，每个结点都有初始权值（0/1），有两种操作：

  • 对某棵子树的权值全部取反
  • 询问某棵子树中1的个数（求和）

输出每次询问的答案。
看题意，和区间操作很像，那么如果能转化成线形结构，直接线段树就可以解了。而树形转换成线形，我们就可以用dfs序去搞一搞（如果你还不知道dfs序，可以看看这篇博客：传送门），转换成线形结构之后就成了线段树板子题了。
（板子是白嫖的，如果你还不会线段树区间取反，可以看看这道题：洛谷 P2574 XOR的艺术）

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define ls(x) (x<<1)
#define rs(x) (ls(x)|1)
#define maxn 200005
#define IOS  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int in[maxn],out[maxn],cnt=0,a[maxn];
vector<int> g[maxn];
il void dfs(int x,int fa){
    in[x]=++cnt;
    a[cnt]=x;
    for(auto i:g[x]){
        if(i==fa)continue;
        else{
            dfs(i,x);
        }
    }
    out[x]=cnt;
}
int w[maxn];
struct FFF{
    int l,r;
    int op;
    int cl;
    bool rev;
    int mid(){return l+r>>1;}
    int len(){return r-l+1;}
}t[maxn*4];
int n;
void up(int o){
    t[o].op=t[ls(o)].op+t[rs(o)].op;
    t[o].cl=t[ls(o)].cl+t[rs(o)].cl;
}
void build(int l=1,int r=n,int o=1){
    t[o].l=l;t[o].r=r;
    t[o].op=0;
    if(l==r){
        t[o].cl=1;
        if(w[l]==1)swap(t[o].op,t[o].cl);
        return;
    }
    int mid=l+r>>1;
    build(l,mid,ls(o));
    build(mid+1,r,rs(o));
    up(o);
}
void down(int o){
    if(t[o].rev){
        for(int i=0;i<=1;++i){
            t[ls(o)|i].rev^=1;
            swap(t[ls(o)|i].op,t[ls(o)|i].cl);
        }
        t[o].rev=0;
    }
}
void add(int l,int r,int o=1){
    if(l<=t[o].l&&t[o].r<=r){
        t[o].rev^=1;
        swap(t[o].op,t[o].cl);
        return;
    }
    int mid=t[o].mid();
    down(o);
    if(l<=mid)add(l,r,ls(o));
    if(r>mid)add(l,r,rs(o));
    up(o);
}
int getsum(int l,int r,int o=1){
    if(l<=t[o].l&&t[o].r<=r){
        return t[o].op;
    }
    int ans=0;
    int mid=t[o].mid();
    down(o);
    if(l<=mid)ans+=getsum(l,r,ls(o));
    if(r>mid)ans+=getsum(l,r,rs(o));
    return ans;
}
signed main(){
    IOS
    cin>>n;
    for (int i = 1; i <=n-1; ++i) {
        int x;
        cin>>x;
        g[x].push_back(i+1);
    }
    dfs(1,0);
    for (int i = 1; i <=n ; ++i) {
        int tmp;
        cin>>tmp;
        w[in[i]]=tmp;
    }
    int m;
    cin>>m;
    build(1,n,1);
    while(m--){
        string s;
        int op;
        cin>>s>>op; int l=in[op],r=out[op];
        //cout<<s<<endl;
        if(s=="get"){
            cout<<getsum(l,r,1)<<endl;
        }else{
            add(l,r,1);
        }
    }
    return 0;
}