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;
}