Diamond_Sea#Day5

E. Company

容易想到使用st表来维护区间的lca（注意实现的过程中，位运算的优先级）

我们发现如果是改变一个点就能使得lca的深度变大的话，那这个点去掉之后，剩余点的lca必须是原lca的后代节点废话

相当于，剩下的点在原lca的最多两个不同子节点的子树中，且其中有一个子树只含有一个在当前区间中的点，我们要删除的就是这个点。

这里采用了分治的方法，具体可参见实现过程

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,q;
int fa[maxn][30];
vector<int>e[maxn];
int dep[maxn];
int st[maxn][30],lg[maxn];
void dfs(int u){
	for(auto v:e[u]){
		dep[v]=dep[u]+1;
		dfs(v);
	}
}

int lca(int x,int y){
	if(!x)return y;
	if(!y)return x;
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--){
		if(fa[x][i]&&dep[fa[x][i]]>=dep[y])
			x=fa[x][i];
	}
	if(x==y)return x;
	for(int i=20;i>=0;i--){
		if(fa[x][i]&&fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	}
	return fa[x][0];
}

void init(){
	for(int i=1;i<=20;i++){
		for(int j=1;j<=n;j++)
		fa[j][i]=fa[fa[j][i-1]][i-1];
	}
	dfs(1);	
	for(int i=1;i<=n;i++)st[i][0]=i;
	for(int i=1;i<=20;i++){
		for(int j=1;j+(1<<i)-1<=n;j++){
			st[j][i]=lca(st[j][i-1],st[j+(1<<(i-1))][i-1]);
			// printf("#%d %d %d\n",j,i,st[j][i]);

		}
	}
	for(int i=2;i<=n;i++)
		lg[i]=lg[i/2]+1;
}


int query(int l,int r){
	int s=lg[(r-l+1)];
	return lca(st[l][s],st[r-(1<<s)+1][s]);
}

int solve(int l,int r,int rt,int pre){
	if(l==r){
		return l;
	}
	int mid=l+r>>1;
	int le=query(l,mid);
	int ri=query(mid+1,r);
	for(int i=20;i>=0;i--){
		if(fa[le][i]&&dep[fa[le][i]]>dep[rt])
			le=fa[le][i];
	}
	for(int i=20;i>=0;i--){
		if(fa[ri][i]&&dep[fa[ri][i]]>dep[rt])
			ri=fa[ri][i];
	}	
	// printf("$%d %d %d\n",l,r,lca(1,3));
	if(le==rt){
		if(ri==rt)return 0;
		else {
			if(pre&&pre!=ri)return 0;
			else return solve(l,mid,rt,ri);
		}
	}
	else {
		if(ri==rt){
			if(pre&&pre!=le)return 0;
			else return solve(mid+1,r,rt,le);
		}
		else {
			vector<int>vec;
			if(l==mid){
				if(ri==pre||!pre)vec.push_back(l);
			}
			if(r==mid+1){
				if(le==pre||!pre)vec.push_back(r);
			}
			if(vec.size()==2){
				if(dep[vec[0]]>dep[vec[1]])swap(vec[0],vec[1]);
			}
			if(vec.size())return vec[0];
			else return 0;
		}

	}
}

int main(){
	scanf("%d%d",&n,&q);
	for(int i=2;i<=n;i++){
		int x;
		scanf("%d",&x);
		fa[i][0]=x;
		e[x].push_back(i);
	}
	init();
	while(q--){
		int l,r;
		scanf("%d%d",&l,&r);
		int cur=solve(l,r,query(l,r),0);
		if(!cur)cur=l;
		int ans;
		if(cur>l){
			ans=query(l,cur-1);
			if(cur<r)ans=lca(ans,query(cur+1,r));
		}
		else ans=query(cur+1,r);
		printf("%d %d\n",cur,dep[ans]);
	}
	return 0;
}
/*
11 1
1 1 3 3 3 4 2 7 7 6
4 8
*/

E. Politics(https://codeforces.com/problemset/problem/1061/E)

这种限制很多，数据范围较小的题目，基本上都可以一眼鉴定为网络流

可问题是，如何建图？

这里的最大问题是，如何考虑在满足当前点的限制时，不会打破其后代节点的限制。如果采用了分开计算的形式，那么在当前点被选取之后，怎么保证它不会在后面被重复选取

这道题目采用了很有启发性的解决方式，对于一个子树的点数要求，我们减去它的所有后代需要选取的点后，直接作为该点的新点数。

对于每个点，记录其上方离他最近的有限制条件的点（当然这个点也可以是他本身）。

我们在两棵树的相同点之间连一条流量为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
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
const int maxn=1e3+5;
const ll mod=998244353;
const double eps=1e-10;
const int inf=1e9;
int n,rt[2],q[2],flag=1;
int a[maxn];
int cmd[2][maxn],sum[2][maxn],col[2][maxn];
vector<int>e[2][maxn];

struct Edge{
    int from,to,cap,flow,cost;
    Edge(int u,int v,int c,int f,int co):from(u),to(v),cap(c),flow(f),cost(co){}
};

struct MCMF{
    int n,m,s,t;
	ll ans;
    vector<Edge> edges;
    vector<int> g[maxn];
    int inq[maxn];  
    int d[maxn];    
    int p[maxn];    
    int a[maxn];    

    void init(int n){
        this->n=n;
        for(int i=0;i<n;++i) g[i].clear();
        edges.clear();
		s=0,t=n-1;
		ans=0;
    }

    void add(int from,int to,int cap,int cost){
        edges.push_back(Edge(from,to,cap,0,cost));
        edges.push_back(Edge(to,from,0,0,-cost));
        m=edges.size();
        g[from].push_back(m-2);
        g[to].push_back(m-1);
    }

    bool BellmanFord(int s,int t,int& flow,long long& cost){
        for(int i=0;i<n;++i) d[i]=inf;
        memset(inq,0,sizeof(inq));
        d[s]=0;
        inq[s]=1;
        p[s]=0;
        a[s]=inf;

        queue<int> que;
        que.push(s);
        while(!que.empty()){
            int u=que.front();
            que.pop();
            inq[u]=0;
            for(int i=0;i<g[u].size();++i){
                Edge& e=edges[g[u][i]];
                if(e.cap>e.flow && d[e.to]>d[u]+e.cost){
                    d[e.to]=d[u]+e.cost;
                    p[e.to]=g[u][i];
                    a[e.to]=min(a[u],e.cap-e.flow);
                    if(!inq[e.to]){ que.push(e.to);inq[e.to]=1; }
                }
            }
        }
        if(d[t]==inf) return false;
        flow+=a[t];
        cost+=(long long)d[t]*(long long)a[t];
        for(int u=t;u!=s;u=edges[p[u]].from){
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
        }
        return true;
    }

    int MincostMaxflow(int s,int t,long long& cost){
        int flow=0;
        cost=0;
        while(BellmanFord(s,t,flow,cost));
        return flow;
    }

	ll check(){
		int pre=0,le=0,ri=0;
		for(int i=0;i<g[s].size();i++){
			Edge e=edges[g[s][i]];
			le+=e.cap;
		}
		for(int i=0;i<g[t].size();i++){
			Edge e=edges[g[t][i]^1];
			ri+=e.cap;
		}			
		if(le!=ri)return -1;
		

		MincostMaxflow(s,t,ans);
		
		le=0;
		for(int i=0;i<g[s].size();i++){
			Edge e=edges[g[s][i]];
			le+=e.flow;
		}	

		if(le!=ri)return -1;

		return -ans;
	}

}G;

void dfs(int sgn,int u,int p,int cur){
	if(cmd[sgn][u])cur=u;
	col[sgn][u]=cur;
	for(auto v:e[sgn][u]){
		if(v==p)continue;
		dfs(sgn,v,u,cur);
		sum[sgn][u]+=sum[sgn][v];
	}
	if(cmd[sgn][u]){
		int pre=cmd[sgn][u];
		cmd[sgn][u]-=sum[sgn][u];
		sum[sgn][u]=pre;
		if(cmd[sgn][u]<0)flag=0;
	}
}

void build(){
	G.init(n*2+2);
	for(int i=1;i<=n;i++){
		G.add(col[0][i],col[1][i]+n,1,-a[i]);
	}
	for(int i=1;i<=n;i++){
		if(cmd[0][i]){
			G.add(0,i,cmd[0][i],0);
			// cout<<"$$"<<cmd[0][i]<<endl;
		}
		if(cmd[1][i]){
			G.add(i+n,2*n+1,cmd[1][i],0);
			// cout<<"##"<<cmd[1][i]<<endl;
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&rt[0],&rt[1]);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		e[0][u].push_back(v);
		e[0][v].push_back(u);
	}
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		e[1][u].push_back(v);
		e[1][v].push_back(u);	
	}
	scanf("%d",&q[0]);
	for(int i=1;i<=q[0];i++){
		int k,x;
		scanf("%d%d",&k,&x);
		cmd[0][k]=x;
	}
	scanf("%d",&q[1]);
	for(int i=1;i<=q[1];i++){
		int k,x;
		scanf("%d%d",&k,&x);
		cmd[1][k]=x;
	}
	for(int i=0;i<2;i++)
		dfs(i,rt[i],0,rt[i]);	
	build();
	if(!flag)puts("-1");
	else printf("%lld\n",G.check());
	return 0;
}

Diamond_Sea#Day6

D. Barcelonian Distance

太ex了这题…

最开始想的是讨论这条直线的各种情况，然后算答案。但是一直有些误差（当然也有可能是写假了）。

最后实在受不了了，索性直接把点看成端点，点之间的线段长看成边长跑最短路。

这里有个地方需要注意，直线的交点可能和矩形的顶点重合，所以需要人为制造一个偏移（因为斜率的分子分母都是整数，且最小精度为1e-9，所以这样是可行的），以避免同一个交点被看成是两个不同的点。

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
111
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
const int maxn=2e5+5;
const ll mod=998244353;
double eps=1e-10;
int a,b,c;
int r1,c1,r2,c2;
pair<db,db>nd[10];
bool check(db x,db up,db dn,int sgn){
	eps=1e-10;
	if(!sgn)eps=-eps;
	if(up>dn)swap(up,dn);
	return x-eps<=dn&&x+eps>=up;
}
vector<pair<int,db>>e[10];
db dij(int s,int t){
	priority_queue<pair<db,int>,vector<pair<db,int>>,greater<pair<double,int>>>q;
	q.push({0,s});
	double dis[10];
	for(int i=0;i<10;i++)dis[i]=1e10;
	dis[s]=0;
	while(!q.empty()){
		auto it=q.top();q.pop();
		for(auto v:e[it.second]){
			if(dis[v.first]>dis[it.second]+v.second){
				dis[v.first]=dis[it.second]+v.second;
				q.push({dis[v.first],v.first});
			}
		}
	}
	return dis[t];
}
int main(){
	int T=1;//scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&a,&b,&c);
		scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
		for(int i=0;i<10;i++)e[i].clear();
		nd[0]={r1,c1};
		nd[1]={r1,c2};
		nd[2]={r2,c1};
		nd[3]={r2,c2};
		e[0].push_back({1,abs(c1-c2)});
		e[1].push_back({0,abs(c1-c2)});
		e[1].push_back({3,abs(r1-r2)});
		e[3].push_back({1,abs(r1-r2)});
		e[0].push_back({2,abs(r1-r2)});
		e[2].push_back({0,abs(r1-r2)});
		e[2].push_back({3,abs(c1-c2)});
		e[3].push_back({2,abs(c1-c2)});
		db nx,ny;
		vector<int>vec;
		if(b){
			nx=r1,ny=(-c-a*nx)/b;
			if(check(ny,c1,c2,1)){
				nd[4]={nx,ny};
				e[4].push_back({0,abs(ny-c1)});
				e[0].push_back({4,abs(ny-c1)});
				e[4].push_back({1,abs(ny-c2)});
				e[1].push_back({4,abs(ny-c2)});
				vec.push_back(4);
			}
			nx=r2,ny=(-c-a*nx)/b;
			if(check(ny,c1,c2,1)){
				nd[5]={nx,ny};
				e[5].push_back({2,abs(ny-c1)});
				e[2].push_back({5,abs(ny-c1)});
				e[5].push_back({3,abs(ny-c2)});
				e[3].push_back({5,abs(ny-c2)});
				vec.push_back(5);
			}		
						
		}
		if(a){
			ny=c1,nx=(-c-b*ny)/a;
			if(check(nx,r1,r2,0)){
				nd[6]={nx,ny};
				e[6].push_back({0,abs(nx-r1)});
				e[0].push_back({6,abs(nx-r1)});
				e[6].push_back({2,abs(nx-r2)});
				e[2].push_back({6,abs(nx-r2)});
				vec.push_back(6);
			}
			ny=c2,nx=(-c-b*ny)/a;
			if(check(nx,r1,r2,0)){
				nd[7]={nx,ny};
				e[7].push_back({1,abs(nx-r1)});
				e[1].push_back({7,abs(nx-r1)});
				e[7].push_back({3,abs(nx-r2)});
				e[3].push_back({7,abs(nx-r2)});
				vec.push_back(7);
			}
		}
		if(vec.size()==2){
			db res=pow(nd[vec[0]].first-nd[vec[1]].first,2)
				+pow(nd[vec[0]].second-nd[vec[1]].second,2);
			res=sqrt(res);
			e[vec[0]].push_back({vec[1],res});
			e[vec[1]].push_back({vec[0],res});
			// puts("OK");
			// printf("%d %d\n",vec[0],vec[1]);
		}
		printf("%.7lf\n",dij(0,3));
	}


	return 0;
}

Diamond_Sea#Day7

E. The Fair Nut and Rectangles

注意观察，题目中保证“It is guaranteed that there are no nested rectangles.”

则可知，没有任何两个矩形有相同的长或者宽。不妨以x为关键字对所有矩形从小到大排序。

定义dp[i]，表示最后一个选择的矩形为第i个时，得到的最大答案。

则很容易写出DP式子，即：

dpi=max⁡1≤j<idpj+xi⋅yi−xj⋅yid p_{i}=\max _{1 \leq j<i} d p_{j}+x_{i} \cdot y_{i}-x_{j} \cdot y_{i}

但是这里的状态更新貌似是O(n)的，明显会超时。但是再次观察，可以下面的式子其实是一个以yi{y_i}为变量的一次函数：

−xj⋅yi+dpj-x_{j} \cdot y_{i}+d p_{j}

进而想到使用凸包（convex hull trick）来维护，从而在其上二分，在O(logn)内完成状态更新。

注意数据范围很大不要和我一样因为没发现爆long long导致这个题卡了很久

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
const int maxn=1e6+5;
const ll mod=998244353;
const double eps=1e-10;
int n;
ll ans;
struct node{
	ll x,y,val;
}a[maxn];
bool cmp(node x,node y){
	return x.x<y.x;
}
struct Line{
	ll k,b;
};
vector<Line>line;
ll cal(Line cur,ll x){
	return cur.k*x+cur.b;
}
ll query(ll x){
	int l=0,r=line.size()-1;
	ll ans=0;
	if(r>=l){
		ans=max(ans,cal(line[l],x));
		ans=max(ans,cal(line[r],x));
		l++,r--;
		while(l<=r){
			int mid=l+r>>1;
			if(cal(line[mid],x)<=cal(line[mid+1],x))
				l=mid+1;
			else 
				r=mid-1;
			ans=max(ans,cal(line[mid],x));
		}		
	}
	return ans;
}

bool check(ll x1,ll y1,ll x2,ll y2){
	if(x1/y1>x2/y2)return true;
	else if(x1/y1==x2/y2){
		x1%=y1,x2%=y2;
		return x1*y2>=x2*y1;
	}
	return false;
}

int main(){
	int T=1;//scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			ll x,y,val;
			scanf("%lld%lld%lld",&x,&y,&val);
			a[i]={x,y,val};
		}
		sort(a+1,a+n+1,cmp);
		for(int i=1;i<=n;i++){
			ll b=query(a[i].y)+1ll*a[i].x*a[i].y-a[i].val;
			ans=max(ans,b);
			ll k=-a[i].x;
			Line cur={k,b};
			int sz=line.size();
			while(sz>1){
				ll b1=line[sz-2].b,b2=line[sz-1].b,b3=cur.b;
				ll k1=line[sz-2].k,k2=line[sz-1].k,k3=cur.k;
				
				if(check((b3-b2),(k2-k3),(b2-b1),(k1-k2))){
					line.pop_back();
					sz--;
				}
				else break;
			}
			line.push_back(cur);
		}		
		cout<<ans;
	}


	return 0;
}

E. Ehab and a component choosing problem

煞笔题

分两步完成任务，即先确定好最终的答案是什么，然后再用这个答案去求解最大的k值

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef double db;
const int maxn=3e5+5;
const ll mod=998244353;
const double eps=1e-10;
int n;
vector<int>e[maxn];
ll ans=-1e18,cnt;
ll mx[maxn],a[maxn];
void dfs(int u,int p,int f){
	mx[u]=a[u];
	for(auto v:e[u]){
		if(v==p)continue;
		dfs(v,u,f);
		mx[u]+=max(0ll,mx[v]);
	}
	if(f){
		if(mx[u]>ans)ans=mx[u];
	}
	else if(mx[u]==ans){
		cnt++;
		mx[u]=0;
	}
}
int main(){
	int T=1;//scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
		for(int i=1;i<n;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		dfs(1,0,1);
		dfs(1,0,0);
		printf("%lld %lld\n",ans*cnt,cnt);
	}	

	return 0;
}