CF 620E
首先我们选择用dfs序来代表一棵树，那么子树就是dfs序里的一部分，我们用线段树就可以完成子树修改的操作
之后呢，由于颜色只有60种，状态压缩来表示一哈就好了，之后就很简单了
注意不要犯错（比如tree[c]=a[pos[l]]）
#define lowbit(x) (x&-x)
vector<int>pos,a;
vector<int>c,in,out;
struct ST{
vector<ll>tree;
vector<ll>tag;
ST(int n){
tree.resize(n<<2);
tag.resize(n<<2);
}
inline void push_down(int c){
if(tag[c]!=0){
tag[c<<1]=tag[c<<1|1]=tag[c];
tree[c<<1]=tree[c<<1|1]=tag[c];
tag[c]=0;
}
}
inline void push_up(ll c){
tree[c]=tree[c<<1]|tree[c<<1|1];
}
void build(int l,int r,int c){
if(l==r){
tree[c]=1ll<<(a[pos[l]]);//纯低能错误
return;
}
int mid=(l+r)>>1;
build(l,mid,c<<1);
build(mid+1,r,c<<1|1);
push_up(c);
}
void update(int l,int r,int c,int nl,int nr,ll v){
if(nl<=l&&nr>=r){
tree[c]=(1ll<<v);
tag[c]=(1ll<<v);
return;
}
push_down(c);
int mid=(l+r)>>1;
if(nl<=mid)update(l,mid,c<<1,nl,nr,v);
if(nr>mid)update(mid+1,r,c<<1|1,nl,nr,v);
push_up(c);
}
ll query(int l,int r,int ql,int qr,int c){
if(ql<=l&&qr>=r){
return tree[c];
}
push_down(c);
ll res=0;
int mid=(l+r)>>1;
if(ql<=mid){
res|=query(l,mid,ql,qr,c<<1);
}
if(qr>mid){
res|=query(mid+1,r,ql,qr,c<<1|1);
}
return res;
}
};
void solve(){
int n,q;
cin>>n>>q;
int cnt=0;
a.resize(n+1);
in.resize(n<<2);
out.resize(n<<2);
pos.resize(n+1);
vector<vector<int>>E(n+1);
for(int i=1;i<=n;++i){
cin>>a[i];
}
for(int i=0;i<n-1;++i){
int u,v;
cin>>u>>v;
E[v].push_back(u);
E[u].push_back(v);
}
function<void(int,int)>dfs=[&](int x,int f){
in[x]=++cnt;
pos[cnt]=x;
for(int v:E[x]){
if(v==f)continue;
dfs(v,x);
}
out[x]=cnt;
};
dfs(1,0);
ST seg(cnt);
seg.build(1,cnt,1);
while(q--){
int type;
cin>>type;
if(type==1){//change
int v,c;
cin>>v>>c;
seg.update(1,n,1,in[v],out[v],c);
}else{//get
int k;
cin>>k;
ll res=seg.query(1,n,in[k],out[k],1);
int ans=0;
while(res){
res-=lowbit(res);
ans++;
}
cout<<ans<<'\n';
}
}
return;
}
CF 1679F
同样的状态压缩，我们依旧选用lowbit来对当前的status进行操作
dp[status]表示当前选择了的数的状态
剩下的就是常规了
#define lowbit(x) (x&-x)
void solve(){
int n;
cin>>n;
vector<int>a(n);
vector<ll>sum(1<<n);
for(int i=0;i<n;++i){
cin>>a[i];
sum[1<<i]=a[i];
}
int k;cin>>k;
vector<int>no(2);
for(int i=0;i<k;++i)cin>>no[i];
vector<ll>dp(1<<n);
for(int i=0;i<n;++i){
dp[1<<i]=(a[i]!=no[0]&&a[i]!=no[1]?1:0);
}
for(int i=1;i<(1<<n);++i){
sum[i]=sum[i^lowbit(i)]+sum[lowbit(i)];
if(sum[i]==no[0]||sum[i]==no[1])continue;
for(int j=i;j;j-=lowbit(j)){
dp[i]+=dp[i^lowbit(j)];
dp[i]%=MOD;
}
}
cout<<dp[(1<<n)-1]<<'\n';
return;
}
CF 429B
区间dp
我们首先处理从四个角出发可能拥有的最大值
之后我们枚举交点，然后判断最大值
注意交点处，从左上角出发的点可以从上面进入交点，也可以从左边进入交点
void solve(){
int n,m;
cin>>n>>m;
vector a(n+1,vector<int>(m+1));
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin>>a[i][j];
}
}
vector dp1(n+2,vector<int>(m+2)),dp2(dp1),dp3(dp1),dp4(dp1);
for(int i=1;i<=n;++i){//左上角
for(int j=1;j<=m;++j){
dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1])+a[i][j];
}
}
for(int i=n;i>=1;--i){//右下角
for(int j=m;j>=1;--j){
dp2[i][j]=max(dp2[i+1][j],dp2[i][j+1])+a[i][j];
}
}
for(int i=1;i<=n;++i){//右上角
for(int j=m;j>=1;--j){
dp3[i][j]=max(dp3[i-1][j],dp3[i][j+1])+a[i][j];
}
}
for(int i=n;i>=1;--i){//左下角
for(int j=1;j<=m;++j){
dp4[i][j]=max(dp4[i+1][j],dp4[i][j-1])+a[i][j];
}
}
int ans=0;
for(int i=2;i<n;++i){
for(int j=2;j<m;++j){
ans=max(ans,dp1[i-1][j]+dp2[i+1][j]+dp3[i][j+1]+dp4[i][j-1]);
ans=max(ans,dp1[i][j-1]+dp2[i][j+1]+dp3[i-1][j]+dp4[i+1][j]);
}
}
cout<<ans<<'\n';
return;
}
今天收到字节的录用函了，等等鹅厂吧