2022牛客多校训练营04

L-Black Hole

来源: 牛客多校训练营4 算法: 模拟, 计算几何 补完: Yes 完成时间: August 16, 2022

题解

有一个正\(n\)面体, 初始边长为\(a\), 做\(k\)次操作:

取正\(n\)面体的中心, 求它们的凸包, 得到新的正\(n'\)面体.

求最终正\(n'\)面体的面数\(n'\)和边长\(a'\).

正\(n\)面体一共只有五种, 且有以下性质

名称	面	对偶多面体
正四面体	正三角形	正四面体
正六面体	正方形	正八面体
正八面体	正三角形	正六面体
正十二面体	正五边形	正二十面体
正二十面体	正三角形	正十二面体

当知道多面体的中心到棱长的距离\(l\)和二面角\(\alpha\)时, 可以求得对偶多面体的棱长\(a'\)

\[ a'=\sqrt{2l^2(1-\cos\alpha)} \]

已知多面体的面时, 就可求\(l\)

对正方形

\[ l=\frac 12 a \]

对正三角形

\[ l=\frac{\sqrt 3}{6}a \]

对正五边形

\[ l=\frac{\sqrt{25+10\sqrt{5}}}{10}a \]

多面体二面角查资料得,

名称	二面角
正四面体	\(\arccos{\frac{1}{3}}\)
正六面体	\(\arccos{0}\)
正八面体	\(\arccos{-\frac{1}{3}}\)
正十二面体	\(\arccos{-\frac{\sqrt{5}}{5}}\)
正二十面体	\(\arccos{-\frac{\sqrt{5}}{3}}\)

最终有

名称	对偶多面体	对偶多面体棱长棱长
正四面体	正四面体	\(\frac{1}{3}a\)
正六面体	正八面体	\(\frac{1}{\sqrt{2}}a\)
正八面体	正六面体	\(\frac{\sqrt{2}}{3}a\)
正十二面体	正二十面体	\(\frac{5+3\sqrt{5}}{10}a\)
正二十面体	正十二面体	\(\frac{1+\sqrt{5}}{6}a\)

参考

高度对称的多面体和它们的对偶多面体

****五种正多面体的二面角以及体积的计算****

代码

#include<bits/stdc++.h>

using namespace std;

double a;
int n,k;

bool duiou(){
    switch (n) {
    case 4:
        n = 4;
        a = a/3;
        return 1;
    case 6:
        n = 8;
        a = a/sqrt(2);
        return 1;
    case 8:
        n = 6;
        a = a*sqrt(2)/3;
        return 1;
    case 12:
        n = 20;
        a = a*(5+3*sqrt(5))/10;
        return 1;
    case 20:
        n = 12;
        a = a*(1+sqrt(5))/6;
        return 1;
    default:
        return 0;
    }
}

void solve() {
    cin>>n>>a>>k;
    while(duiou()&&--k);//不合法或操作次数完就退出循环
    if(k)printf("impossible \n");//未操作完即为不合法
    else printf("possible %d %.15lf\n",n,a);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

N-Particle Arts

来源: 牛客多校训练营4 算法: 位运算 题目链接: https://ac.nowcoder.com/acm/contest/33189/N 补完: Yes 完成时间: July 30, 2022

题解

发现两粒子碰撞之后能量和不变, 但能量差更大.

\[ 0011\to AND~0001\\ 0101\to OR~~~~~0111 \]

则收敛的稳定值为总体能量差最大的情况.

用桶提取每个粒子的每个二进制位上的能量, 然后再组合成尽可能大能量的粒子.

要求输出真分数, 故不能在计算时直接除, 要保留分子\(z\)分母\(m\)到最后, 最后用\(GCD\)处理后输出.

计算公式如下转换

\[ σ^2=\frac1n∑_{i=1}^n(x_i−μ)^2\\μ=\frac 1n∑_{i=1}^nx_i\\ sum=∑_{i=1}^nx_i \]

\[ σ^2=\frac1n∑_{i=1}^n(\frac{nx_i}{n}−\frac{sum}{n})^2 \]

$$ σ^2=1n∑_{i=1}^n({}−{}+{})

$$

$$ σ^2=n{n2}∑{i=1}^n{x_i2}−{}∑{i=1}^nx_i+{}∑_{i=1}^n1

$$

$$ σ^2=n{n2}∑_{i=1}^n{x_i2}−{}+{}

$$

$$ σ^2=

$$

注意数据范围\(n≤1e5\), \(n*n\)就爆int了.

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll num[15];
ll temp,sum;
ll z,m;
void solve(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>temp;
        for(int j=0;j<15;j++){
            if(temp&(1<<j))num[j]++;
        }
        sum += temp;
    }
    for(int i=0;i<n;i++){
        int temp=0;
        for(int j=0;j<15;j++){
            if(num[j])temp|=(1<<j),num[j]--;
        }
        z += temp*temp;
    }
    z = z*n - sum*sum;
    m = (long long)n*n;
    ll g = __gcd(z,m);
    printf("%lld/%lld\n",z/g,m/g);
}
int main(){
    int T = 1;
    // cin>>T;
    while(T--)solve();
    return 0;
}