2022年牛客多校第四场题解

N-Particle Arts

题目大意:
给定\(n\)个数字,每一次选两个数字\(a,b\),将\(a,b\)两个数字变成\(a \& b\)和\(a \vert b\) 多次进行,一直到这些数字趋于一个稳定值,然后算这些数字的方差是多少.
方差公式:

• \(\sigma^{2}=\frac{1}{n} \sum_{i=1}^{n}\left(x_{i}-\mu\right)^{2}\)
  where \(\mu=\frac{1}{n} \sum_{i=1}^{n} x_{i}\)
  题解:
    一开始我们想到给定\(a,b,c\)三个数字,然后当\(a\)和\(b\) 发生反应之后(就是变成了\(a\&b\)与\(a \vert b\)之后,\(a\)的值会变小,一个值会相对来说变小,一个值会相对来说变大,然后假设\(a\)变大,假设\(b\)变小,然后继续发生反应,一个值更大,一个值更小,然后小的和小再反应,这样一直反应,于是猜测最后会变成\(n-1\)个\(a\&b\)和\(1\)个\(a \vert b\),然后计算方差就可以了,但是发现样例就寄了.)
   随后可以发现举例子,将样例的\(1,2,3,4,5\)的二进制表示出来,发现随着反应发生所有的1 都会提前,然后形成\(0,0,1,7,7\),然后就是这些数字的方差
  

code

//第一种写法 使用__int128进行重载然后暴力求解,麻了
#include<bits/stdc++.h>
using namespace std;
#define ll long long
__int128 read()
{
    __int128 x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')f=-1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}
void print(__int128 x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10); 
    putchar(x%10+'0');
}
__int128 gcd(__int128 a,__int128 b)
{
    return b?gcd(b,a%b):a;
}
__int128 lcm(__int128 a,__int128 b)
{
    return a/gcd(a,b)*b;
}
struct Frac{
    __int128 fenzi,fenmu;
    Frac operator+(Frac other)
    {
        Frac res;
        // res.fenmu=lcm(fenmu,other.fenmu);
        res.fenmu=fenmu*other.fenmu;
        // res.fenzi=fenzi*res.fenmu/fenmu+other.fenzi*res.fenmu/other.fenmu;
        res.fenzi=fenzi*other.fenmu+fenmu*other.fenzi;
        return res;
    }
    Frac operator-(Frac other)
    {
        Frac res;
        res.fenmu=fenmu*other.fenmu;
        res.fenzi=fenzi*other.fenmu-fenmu*other.fenzi;
        return  res;
    }
    Frac operator*(Frac other)
    {
        Frac res;
        res.fenmu=fenmu*other.fenmu;
        res.fenzi=fenzi*other.fenzi;
        return res;
    }
    Frac operator/(__int128 x)
    {
        Frac res;
        res.fenmu=fenmu*x;
        res.fenzi=fenzi;
        return res;
    }
};

void solve(){
    int n;
    cin>>n;
    vector<__int128> a(n);
    for(int i=0;i<n;i++) a[i]=read();
    vector<bitset<64>> bit(n,bitset<64>());
    for(int i=0;i<n;i++)bit[i]=a[i];
    vector<int> cnt(64,0);
    for(int i=0;i<64;i++){
        for(auto j:bit)cnt[i]+=j[i];
    }
    vector<int> ans(n,0);
    for(int i=0;i<n;i++){
        for(int j=0;j<64;j++){
            if(cnt[j]){
                cnt[j]--;
                ans[i]|=1<<j;
            }
        }
    }
    Frac u{0,1},sigma{0,1};
    for(auto &i:ans)u=u+(Frac){i,1};
    u=u/n;
    for(auto &i:ans){
        auto temp=((Frac){i,1}-u)*((Frac){i,1}-u);
        sigma=sigma+temp;
        __int128 tt=gcd(sigma.fenmu,sigma.fenzi);
        if(tt==0) continue;
        sigma.fenmu/=tt;
        sigma.fenzi/=tt;
    }
    sigma=sigma/n;
    __int128 tt=gcd(sigma.fenmu,sigma.fenzi);
    if(tt==0)
    {
        cout<<"0/1"<<'\n';
        return;
    }
    print(sigma.fenzi/tt);
    cout<<"/";
    print(sigma.fenmu/tt);
}
int main(){
    int t=1;
    while(t--)solve();
}

//第二种写法,既然需要通分啥的,就不通分,直接往上搞,然后算
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define eps 1e-8
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a/gcd(a,b)*b
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define int128 __int128
#define debug(x...) do { cout<< #x <<" -> "; re_debug(x); } while (0)
void re_debug() { cout<<'\n'; }
template<class T, class... Ts> void re_debug(const T& arg,const Ts&... args) { cout<<arg<<" "; re_debug(args...); }
void cut(){ cout<<'\n'<<"------------"<<'\n';}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const ll LNF=0x3f3f3f3f3f3f3f3fll;
const double PI=acos(-1.0);
__int128 read()
{
    __int128 x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')f=-1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}
void print(__int128 x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10); 
    putchar(x%10+'0');
}
__int128 gcd(__int128 a,__int128 b)
{
    return b?gcd(b,a%b):a;
}
void solve()
{
    int n;
    cin>>n;
    vector<int128> q(n);
    for(int i=0;i<n;i++) q[i]=read();
    vector<int> cnt(32,0);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<32;j++)
        {
            if(q[i]&(1<<j))
            {
                cnt[j]++;
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        int k=0;
        for(int j=31;j>=0;j--)
        {
            if(cnt[j])
            {
                cnt[j]--;
                k|=(1<<j);
            }
        }
        q[i]=k;
    }
    int128 sum_x=0;
    for(int i=0;i<n;i++) sum_x+=q[i];
    int128 fenzi=0;
    for(int i=0;i<n;i++) fenzi+=(n*q[i]-sum_x)*(n*q[i]-sum_x);
    int128 fenmu=(int128)n*n*n;
    int128 t=gcd(fenzi,fenmu);
    print(fenzi/t);
    cout<<"/";
    print(fenmu/t);
}
int main()
{
    // IOS;
    int T=1;
   // cin>>T;
    while(T--) solve();
    return 0^0;
}

K-NIO's Sword

题意:有\(n\)个敌人,为\(1,2,3,到n\),只能一次顺序消灭,当前仅当\(A\equiv i \pmod{n}\),初始攻击力只有0,每一次可以增加伤害相当于在攻击力末尾加上\(x,x的范围是(0\le x\le 9)\)相当于\(10×A+x\).

题解:每一次我们可以暴力枚举\(l,r\),枚举这一次能枚举的范围,然后看这个i是否可以在这个范围内表示出来,就可以了,里面需要一些加速手段

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define eps 1e-8
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a/gcd(a,b)*b
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define debug(x...) do { cout<< #x <<" -> "; re_debug(x); } while (0)
void re_debug() { cout<<'\n'; }
template<class T, class... Ts> void re_debug(const T& arg,const Ts&... args) { cout<<arg<<" "; re_debug(args...); }
void cut(){ cout<<'\n'<<"------------"<<'\n';}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const ll LNF=0x3f3f3f3f3f3f3f3fll;
const double PI=acos(-1.0);
ll A=0;
int n;
ll qmi(ll a,ll b)//快速幂
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
ll get(int i,int j)//得到最大的数字 就是相当于在这个数字后面加9
{
    ll ans=i;
    for(int k=0;k<j;k++)
    {
        ans*=10;
        ans+=9;
        // ans*=10;
        
    }
    return ans;
}
bool check(ll i,ll j)
{
    //A在mod n的情况下与i同余,可以认为i+n+n+n是否在这个能表示的范围里面
    //j是倍数,i是当前要搞的值
    //l 和r是能表示左右区间
    ll l=A*qmi(10,j),r=get(i-1,j);
    i+=(l-1)/n*n;//将前面的数字快速加上,要不然TLE
    while(true)
    {
        if(i>r) return false;//超了
        if(l<=i&&i<=r) return true;
        i+=n;//每一次都+n+n,判断
    }
}

void solve()
{
    cin>>n;
    if(n==1)
    {
        cout<<0<<'\n';
        return;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=10;j++)//最多枚举10下,
        {
            if(check(i,j))
            {
                A=i;
                // debug(A);
                // debug(j);
                ans+=j;
                break;
            }
        }
    }
    cout<<ans<<'\n';
}
int main()
{
    IOS;
    int T=1;
    //cin>>T;
    while(T--) solve();
    return 0^0;
}