2022牛客多校第四场

N Particle Arts

题意：

有n个粒子携带焦耳能量，它们之间会发生随机碰撞。碰撞的两个粒子分别带a,b的焦耳能量，会湮灭并且产生两个新的粒子携带和$a\mathrm{\mid }ba|b$的能量，求粒子能量收敛时的方差。

思路：

我们可知,两个粒子碰撞可看作把二进制上的每一位上1和0分散到两个粒子。而达到收敛的情况则是把任意粒子碰撞能量不变，现在就是构造最终状态的粒子。统计每一位的1，然后然后按每一位有就加，重新组成n个粒子。

本题卡数据范围要用__int128,算期望的公式用他给的会溢出

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int __int128
const int N=1e5+7;
ll gcd(ll a,ll b) {
    return b>0 ? gcd(b,a%b):a;
}
void write(ll x) {
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
ll a, n;

ll b[N],w[20];
signed main(){
    cin>>n;
    ll s=0,ans=0;
    for(int i=1;i<=n;i++){
     cin>>a;
        s+=a;
        for(int j=0;j<16;j++){
            if((a>>j)&1) w[j]++;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<16;j++){
            if(w[j]>0) {
                b[i]+=(1<<j);
                w[j]--;
            }
        }
        ans+=b[i]*b[i];
       
    }
    ans=ans*n-s*s;
    ll d=n*n;
    ll g=gcd(ans,d); 
    
    ans/=g;
    d/=g;

    if(ans==0) d=1;

   write(ans);
    putchar('/');
   write(d);

}

K NIO's Sword

题意：

玩家有把攻击力为0的剑，有n个怪物，第$ii$个怪物的生命值为$ii$,宝剑可以升级攻击力A，每次升级即$A\ast 10+x(0\le x\le 9)A*10+x(0\backslash le\; x\le 9)$,打一个怪可以多次升级，使得攻击力的模n与i同余才能杀死第i个怪，问最少升级多少次才能杀死所有的怪物。

思路：

思维题，打第i个怪时，此时攻击力A与i-1同余。问题不关心x的取值，题目等价为$(i-1)\ast 10^k(i-1)*10^k$+x%n=i%n。从小到大枚举k,找到合适的x。注意特判1时答案为0。

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,ans;
long long a[10]={1,10,100,1000,10000,100000,1000000};
int main(){
    
    scanf("%lld",&n);
    if(n==1) puts("0");
    else{
         for(int i=1;i<=n;i++){
             int j=1;
            for( ;j<=6;j++){
                long long x=(i-(i-1)*a[j]%n+n)%n;
                if(x<a[j]) break;
            }
             ans+=j;
        }
       printf("%lld\n",ans);
    }
   
}