2020牛客暑期多校第十场
MorphLing
8月 23, 2020
E.Game
标签：二分答案
推方块的操作其实本质上就是把某一列的一个方块移到它左侧比它低的列上，也就相当于说第i列的方块可以与第[1..i-1]列分摊。考虑二分答案，若当前答案为x，从左到右统计前缀和，计算当前将方块分摊后能否做到每一列都小于等于x。
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
using namespace std;
const int N=1e5+5;
int T,n,a[N];
bool check(int x) {
LL sum=0;
for (int i=1;i<=n;i++){
sum+=a[i];
if ((sum-1)/i+1>x) return 0;
}
return 1;
}
int main() {
cin>>T;
while(T--) {
cin>>n;
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
int l=1,r=1e9;
while(l<r) {
int mid=(l+r)>>1;
if (check(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",l);
}
}
J.Identical-Trees
标签：树形dp，二分图最小权匹配
奇怪的树形dp又增加了。。二分图匹配还能用来做dp转移是我没想到的。
dp[i][j]表示把第一棵树中的i子树变为和第二颗树中的j子树完全一样所需要改变的点的个数。
那么首先i和j子树的个数肯定要相等，否则dp[i][j]=INF
假设子树个数都为k，要给这2k个点找到一个匹配，可以给u、v两点再两两连一条权值为dp[u][v]的边，跑一次最小权匹配（或者最小费用流），如果i!=j还要把i改成j，所以花费+1，最后得到的答案就是dp[i][j]。
最后输出dp[root1][root2]即可
写代码的话要在转移前先把dp[u][v]都预处理好，再把处理出来的结果作为边权建图跑费用流。（因为跑费用流的部分是共用的，等建图的时候再处理权值会导致建图的过程被打乱）
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5,M=5e2+5;
const int INF=1e9,inf=1e3;
int n,m;
struct MCMF {
struct E{
int from,to,flow,dis;
};
queue<int>Q;
vector<E>edge;
vector<int>G[N];
bool vis[N];
int n,m,s,t,dis[N],pre[N],last[N],flow[N],maxflow,mincost;
void init(int _n,int _s,int _t) {
n=_n,s=_s,t=_t;
for (int i=0;i<=n;i++) G[i].clear();
edge.clear();m=0;
maxflow=mincost=0;
}
void addEdge(int from,int to,int flow,int cost) {
edge.push_back({from,to,flow,cost});
edge.push_back({to,from,0,-cost});
G[from].push_back(m++);
G[to].push_back(m++);
}
bool spfa(int s,int t) {
for (int i=0;i<=n;i++) {
dis[i]=9999;flow[i]=9999;vis[i]=0;
}
Q.push(s);dis[s]=0;vis[s]=1;pre[t]=-1;
while(!Q.empty()) {
int now=Q.front();
Q.pop();
vis[now]=0;
for (int i:G[now]) {
if (edge[i].flow && dis[edge[i].to]>dis[now]+edge[i].dis) {
dis[edge[i].to]=dis[now]+edge[i].dis;
pre[edge[i].to]=now;
last[edge[i].to]=i;
flow[edge[i].to]=min(flow[now],edge[i].flow);
if (!vis[edge[i].to]) {
vis[edge[i].to]=1;
Q.push(edge[i].to);
}
}
}
}
return pre[t]!=-1;
}
void go() {
while(spfa(s,t)) {
int now=t;
maxflow+=flow[t];
mincost+=flow[t]*dis[t];
while(now!=s) {
edge[last[now]].flow-=flow[t];
edge[last[now]^1].flow+=flow[t];
now=pre[now];
}
}
}
}mcmf;
vector<int>G1[M],G2[M];
int r1,r2;
int dp[M][M];
int solve(int sr1,int sr2) {
if (~dp[sr1][sr2]) return dp[sr1][sr2];
if (G1[sr1].size()!=G2[sr2].size()) return dp[sr1][sr2]=inf;
int sz=G1[sr1].size();
for (int i=1;i<=sz;i++)
for (int j=1;j<=sz;j++) solve(G1[sr1][i-1],G2[sr2][j-1]);
int s=0,t=2*sz+1;
mcmf.init(2*sz+1,s,t);
for (int i=1;i<=sz;i++) mcmf.addEdge(s,i,1,0);
for (int i=1;i<=sz;i++) mcmf.addEdge(sz+i,t,1,0);
for (int i=1;i<=sz;i++)
for (int j=1;j<=sz;j++) mcmf.addEdge(i,sz+j,1,solve(G1[sr1][i-1],G2[sr2][j-1]));
mcmf.go();
int res=mcmf.mincost;
if (sr1!=sr2) res++;
if (res>inf) res=inf;
return dp[sr1][sr2]=res;
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++) {
int u; scanf("%d",&u);
if (u==0) r1=i;
else G1[u].push_back(i);
}
for (int i=1;i<=n;i++) {
int u; scanf("%d",&u);
if (u==0) r2=i;
else G2[u].push_back(i);
}
memset(dp,-1,sizeof(dp));
printf("%d",solve(r1,r2));
return 0;
}
C.Decrement on tree
可以找到一个贪心策略
然后发现修改一条边影响的只有两端的两个点
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " : " << x << " "
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
struct Edge{
int to, w;
};
struct Edge2{
int from, to;
};
vector<Edge2> E;
vector<Edge> G[N];
multiset<int> ms[N];
int n, q, fa[N], up[N];
LL sum[N], ans, val[N];
void dfs(int x, int ff) {
for (auto T : G[x]) {
int to = T.to, w = T.w;
if (to == ff) continue;
up[to] = w;
fa[to] = x;
dfs(to, x);
sum[x] += up[to];
ms[x].insert(up[to]);
}
if (ms[x].size() == 0) return;
int mx = *(--ms[x].end());
if (sum[x] - up[x] <= 0) val[x] = 0;
else {
if (2ll * mx - sum[x] <= up[x]) {
val[x] = (sum[x] - up[x] + 1) / 2;
} else {
val[x] = (sum[x] - mx) + (2ll * mx - sum[x]) - up[x];
}
}
ans += val[x];
}
int main() {
cin >> n >> q;
for (int i = 1; i <= n - 1; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u].push_back({v,w});
G[v].push_back({u,w});
E.push_back({u,v});
}
G[0].push_back({1,0});
dfs(0, -1);
printf("%lld\n", ans);
for (int i = 1; i <= q; i++) {
int u, v;
scanf("%d %d", &u, &v);
int x = E[u - 1].from, y = E[u - 1].to;
if (fa[x] == y) swap(x, y);
ans -= val[x];
ans -= val[y];
ms[x].erase(ms[x].find(up[y]));
sum[x] -= up[y];
up[y] = v;
ms[x].insert(up[y]);
sum[x] += up[y];
int mx;
mx = *ms[x].rbegin();
if (sum[x] - up[x] <= 0) val[x] = 0;
else {
if (2ll * mx - sum[x] <= up[x]) {
val[x] = (sum[x] - up[x] + 1) / 2;
} else {
val[x] = (sum[x] - mx) + (2ll * mx - sum[x]) - up[x];
}
}
ans += val[x];
swap(x, y);
if (ms[x].size() != 0) {
mx = *ms[x].rbegin();
if (sum[x] - up[x] <= 0) val[x] = 0;
else {
if (2ll * mx - sum[x] <= up[x]) {
val[x] = (sum[x] - up[x] + 1) / 2;
} else {
val[x] = (sum[x] - mx) + (2ll * mx - sum[x]) - up[x];
}
}
}
ans += val[x];
printf("%lld\n", ans);
}
return 0;
}