题目链接：牛客练习赛41
官方题解：题解

A题

解题思路：考虑m，n相等或者m为1时一定能完全成功翻转，其他情况例如m=n-1或m=n-2均无法成功，交了一发，1A。

AC代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T,n,m;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        if (n == m || m == 1) {
            puts("Yes");
        }else {
            puts("No");
        }
    }
    return 0;
}

C题

解题思路：利用并查集将所有集团的犯人数集中到一块，然后将前m大的集团求和，这个m可能大于集团数！其实就是个联通分块。

AC代码：


#include <bits/stdc++.h>

using namespace std;
const int maxn = (int)1e5+5;
typedef long long LL;

int val[maxn],nxt[maxn],n,m;
LL res,Hash[maxn],mp[maxn];
vector<LL> vct;

bool Compare(LL a, LL b) {
	return a > b;
}

int find(int a) {
	if (a == Hash[a]) {
		return a;
	}
	return Hash[a] = find(Hash[a]);
}

void uion(int a, int b) {
	int fa = find(a);
	int fb = find(b);
	if (fa != fb) {
		Hash[fb] = fa;
	}
	return;
}



int main() {
	int tmp,cnt = 0;
	res = 0;
	memset(Hash, 0, sizeof(Hash));
	memset(mp, 0, sizeof(mp));
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> val[i];
		Hash[i] = i;
	}
	for (int i = 1; i <= n; i++) {
		cin >> nxt[i];
		uion(nxt[i], i); //相邻合并
	}
	for (int i = 1; i <= n; i++) {
			tmp = find(Hash[i]);  //把值全记录到祖先当中
			mp[tmp] += val[i];
			if (tmp == i) vct.push_back(i);  //将祖先记录下来
	}

	for (int i = 0; i < vct.size(); i++) {
		vct[i] = mp[vct[i]]; //每个集团的总人数
	}
	sort(vct.begin(), vct.end(), Compare);
	for (int i = 0; m > 0 && i < vct.size(); i++, m--) {
		res += vct[i];
	}
	cout << res << endl;
	return 0;
}

E题

解题思路：一个几何题，将球相交部分体积求出来，然后两球体积和-相交部分体积(AUB = A + B - A∩B)

AC代码：

#include<bits/stdc++.h>

using namespace std;
const double PI = acos(-1.0);
typedef long long ll;
const int maxn=2;
struct point {
    double x,y,z;
    point() {}
    void Init(double a, double b,double c){
        x = a;
        y = b;
        z = c;
    }
    point(double a, double b,double c){
        x = a;
        y = b;
        z = c;
    }
    point operator -(const point &b)const {     //返回减去后的新点
        return point(x - b.x, y - b.y,z-b.z);
    }
    point operator +(const point &b)const {     //返回加上后的新点
        return point(x + b.x, y + b.y,z+b.z);
    }
    //数乘计算
    point operator *(const double &k)const {    //返回相乘后的新点
        return point(x * k, y * k,z*k);
    }
    point operator /(const double &k)const {    //返回相除后的新点
        return point(x / k, y / k,z/k);
    }
    double operator *(const point &b)const {    //点乘
        return x*b.x + y*b.y+z*b.z;
    }
};
double dist(point p1, point p2) {       //返回平面上两点距离
    return sqrt((p1 - p2)*(p1 - p2));
}
struct sphere {//球
    double r;
    point centre;
};
void SphereInterVS(sphere a, sphere b,double &v) {
    double d = dist(a.centre, b.centre);//球心距
    if(d>=a.r+b.r)return;
    if(a.r-d>=b.r){
        v+=PI*4.0/3.0*b.r*b.r*b.r;
        return;
    }
    if(a.r<=b.r-d){
        v+=PI*4.0/3.0*a.r*a.r*a.r;
        return;
    }
    double t = (d*d + a.r*a.r - b.r*b.r) / (2.0 * d);//
    double h = sqrt((a.r*a.r) - (t*t)) * 2;//h1=h2，球冠的高
    double angle_a = 2 * acos((a.r*a.r + d*d - b.r*b.r) / (2.0 * a.r*d));  //余弦公式计算r1对应圆心角，弧度
    double angle_b = 2 * acos((b.r*b.r + d*d - a.r*a.r) / (2.0 * b.r*d));  //余弦公式计算r2对应圆心角，弧度
    double l1 = ((a.r*a.r - b.r*b.r) / d + d) / 2;
    double l2 = d - l1;
    double x1 = a.r - l1, x2 = b.r - l2;//分别为两个球缺的高度
    double v1 = PI*x1*x1*(a.r - x1 / 3);//相交部分r1圆所对应的球缺部分体积
    double v2 = PI*x2*x2*(b.r - x2 / 3);//相交部分r2圆所对应的球缺部分体积
     v += v1 + v2;//相交部分体积
}

double x,y,z,r;
double x2,y2,z2,r2;

double Solve(){
    double v=0;
    sphere A,B;
    A.r=r;
    A.centre.Init(x,y,z);
    B.r=r2;
    B.centre.Init(x2,y2,z2);
    SphereInterVS(A,B,v);
    return v;
}

int main(){
    scanf("%lf%lf%lf%lf",&x,&y,&z,&r);
    scanf("%lf%lf%lf%lf",&x2,&y2,&z2,&r2);
    printf("%.7lf\n", 4*PI*(r*r*r + r2*r2*r2)/3 - Solve());
    return 0;
}