2022杭电第六场

1006 Maex

题意：

给定一棵n个节点的树，给每个节点标上0~n-1的权重，求各子树MEX和的最大值

思路：

易知MEX的最大值有一条链构成，统计子树大小然后从上往下去搜索每个叶子即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int N=5e5+10;
vector<ll> v[N];
ll son[N],siz1[N];
ll dfss(int u,int fa){
	son[u]=1;
	for(auto y:v[u]){
		if(y==fa) continue;
		
		son[u]+=dfss(y,u);
	}
    return son[u];
}
ll dfs(int u,int fa){
	
	siz1[u]=1;
	
	for(auto y:v[u]){
		
		if(y==fa) continue;
		siz1[u]=max(siz1[u],son[u]+dfs(y,u));
	}
    return siz1[u];
}

void solve(){
	memset(son,0,sizeof son);
	memset(siz1,0,sizeof siz1);
    for(int i=1;i<=n;i++) v[i].clear();
	cin>>n;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfss(1,0);
	dfs(1,0);
	cout<<siz1[1]<<endl;
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--){
		solve();
	}

}

1009 Map

题意：

给定大矩形和按比例缩小的小矩形，其中有一个两个矩形对应相同的点P，小矩形绕点P旋转，给定大矩形和旋转后的小矩形顶点坐标求P点坐标。

思路：

看大矩形，以AB,AD两条互相垂直的边作为坐标轴，能表示出所有的点 即

$\overrightarrow{AP}\backslash vec\{AP\}$=$\mu \overrightarrow{AB}\backslash mu\backslash vec\{AB\}$+$\lambda \overrightarrow{AD}\backslash lambda\backslash vec\{AD\}$;

同理小矩形也是如此：

$\overrightarrow{aP}\backslash vec\{aP\}$=$\mu \overrightarrow{ab}\backslash mu\backslash vec\{ab\}$+$\lambda \overrightarrow{ad}\backslash lambda\backslash vec\{ad\}$;

联立得：$\mu (\overrightarrow{AB}-\overrightarrow{ab})\backslash mu(\backslash vec\{AB\}-\backslash vec\{ab\})$+$\lambda (\overrightarrow{AD}-\overrightarrow{ad})\backslash lambda(\backslash vec\{AD\}-\backslash vec\{ad\})$=$\overrightarrow{aA}\backslash vec\{aA\}$

求出$\mu \backslash mu$和$\lambda \backslash lambda$，P也可以求出

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int X[4], Y[4];
int x[4], y[4];
int cross(int a1, int a2, int a3, int a4) {
  return a1 * a4 - a2 * a3;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int T;
  cin >> T;
  while (T--) {
    for (int i = 0; i < 4; i++) cin >> X[i] >> Y[i];
    for (int i = 0; i < 4; i++) cin >> x[i] >> y[i];
    int Ux = X[3] - X[0], Uy = Y[3] - Y[0];
    int Vx = X[1] - X[0], Vy = Y[1] - Y[0];
    int ux = x[3] - x[0], uy = y[3] - y[0];
    int vx = x[1] - x[0], vy = y[1] - y[0];
    double p = cross(X[0] - x[0], vx - Vx, Y[0] - y[0], vy - Vy) / (double)cross(ux - Ux, vx - Vx, uy - Uy, vy - Vy);
    double q = cross(ux - Ux, X[0] - x[0], uy - Uy, Y[0] - y[0]) / (double)cross(ux - Ux, vx - Vx, uy - Uy, vy - Vy);
    cout << fixed << setprecision(10) << x[0] + p * ux + q * vx << ' ' << y[0] + p * uy + q * vy << endl; 
  } 
  return 0;
}