本文主要是介绍Codeforces Round 798 (Div. 2) (C 树形dp D 曼哈顿距离转换 E 位运算构造)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
C：dp以f[i]为根的时候能获得多少个节点，那么dp就是全部儿子里面找一个切掉，其他就是
f[v]的总和了
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using Node=tuple<int,int,int>;
const long long inf=1e9;int n,m,k;
vector<int> g[N];
int sz[N];
int son[N];
int f[N];
void dfs(int u,int fa)
{sz[u]=1;int s=0;for(auto v:g[u]){if(v==fa) continue;dfs(v,u);sz[u]+=sz[v];s+=f[v];//f[v] sz[v]}for(auto v:g[u]){if(v==fa) continue;f[u]=max(f[u],s-f[v]+sz[v]-1);}
}
void solve()
{cin>>n;for(int i=1;i<=n;i++) g[i].clear(),f[i]=0;for(int i=1;i<n;i++){int a,b;cin>>a>>b;g[a].push_back(b);g[b].push_back(a);}dfs(1,0);cout<<f[1]<<"\n";
}
//1 2 3 4
signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}D:曼哈顿距离两点最大值转换成max(max(xi+yi)-min(xi+yi), max(xi-yi)-min(xi-yi))
直接拿个multiset维护前面几个最小值和最大即可
#include<bits/stdc++.h>
using namespace std;
const int N = 2010+10,M=2*N,mod=1e9+7;typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using Node=tuple<int,int,int>;
const long long inf=1e9;int n,m,k;
char a[N][N];
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cin>>a[i][j];}//|xi-xj|+|yi-yj|//(xi+yi)-(xj+yj)//(xj+yj)-(xi+yi)//(xi-yi)-(xj-yj)//(xj-yj)-(xi-yi)//max({x+y}-({x+y}))//max({x-y}-(x-y))//任意两个点距离是//max{ max(xi+yi)-min(xj+yj)}// max(xi-yi)-min(xj-yj)multiset<int> x,y;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]=='B'){x.insert(i+j);auto it=x.begin();it++;it++;it++;while(x.size()>=10){x.extract(*it);}y.insert(i-j);it=y.begin();it++;it++;it++;while(y.size()>=10){y.extract(*it);}}}}if(x.size()==0){cout<<0<<"\n";return ;}if(x.size()==1){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]=='B'){cout<<i<<" "<<j<<"\n";return ;}}}}int mx=inf;int idx,idy;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]=='B'){x.extract(i+j);y.extract(i-j);}int xx=i+j;int yy=i-j;int cnt=max({xx-(*x.begin()),(*x.rbegin())-xx,yy-(*y.begin()),(*y.rbegin())-yy});// cout<<cnt<<" "<<mx<<" "<<i<<" "<<j<<"\n";mx=min(cnt,mx);if(cnt==mx){idx=i;idy=j;}if(a[i][j]=='B'){x.insert(i+j);y.insert(i-j);}}}cout<<idx<<" "<<idy<<"\n";}
//1 2 3 4
signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}E：先全部把0变成1，然后就找最大lowbit，至少可以通过两次构造
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using Node=tuple<int,int,int>;
const long long inf=1e9;int n,m,k;
int a[N],res[N];
class dsu {public:vector<int> p;int n;dsu(int _n) : n(_n) {p.resize(n);iota(p.begin(), p.end(), 0);}inline int get(int x) {return (x == p[x] ? x : (p[x] = get(p[x])));}inline bool unite(int x, int y) {x = get(x);y = get(y);if (x != y) {p[x] = y;return true;}return false;}
};
int lowbit(int x) // 返回末尾的1
{return x & -x;
}
int pos[N],pre[N],suf[N];
int ans;
void solve()
{cin>>n;ans=0;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]==0) a[i]=1,ans++;}int cnt=n;dsu d(n+10);for(int j=0;j<=29;j++){int x=0;for(int i=1;i<=n;i++){if(a[i]>>j&1){if(x==0) x=i;else d.unite(x,i);}}}cnt=0;for(int i=1;i<=n;i++)if(d.get(i)==i) cnt++;if(cnt==1){return ;}ans++;int mx=0,tot=0,qwq=0;for(int i=1;i<=n;i++)mx=max(mx,lowbit(a[i]));for(int i=1;i<=n;i++){if(lowbit(a[i])==mx){pos[++tot]=i;}else qwq|=a[i];}if(cnt==2){int x=d.get(pos[1]);for(int i=1;i<=n;i++){if(d.get(i)!=x&&(a[i]&1)){a[pos[1]]++;return ;}}}if(tot==1){a[pos[1]]--;return ;}pre[0]=suf[tot+1]=0;for(int i=1;i<=tot;i++){pre[i]=pre[i-1]|a[pos[i]];}for(int i=tot;i>=1;i--){suf[i]=suf[i+1]|a[pos[i]];}for(int i=1;i<=tot;i++){if((pre[i-1]|suf[i+1])&((a[pos[i]]^mx)|qwq)){a[pos[i]]--;return ; }}ans++;a[pos[2]]++;a[pos[1]]--;
}
//1 2 3 4
signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--){solve();cout<<ans<<"\n";for(int i=1;i<=n;i++){cout<<a[i]<<" \n"[i==n];}}
}这篇关于Codeforces Round 798 (Div. 2) (C 树形dp D 曼哈顿距离转换 E 位运算构造)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
