2022年牛客多校第四场题解
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
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(x9)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 a(n);
for(int i=0;i> bit(n,bitset());
for(int i=0;i cnt(64,0);
for(int i=0;i ans(n,0);
for(int i=0;i
//第二种写法,既然需要通分啥的,就不通分,直接往上搞,然后算
#include
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< void re_debug(const T& arg,const Ts&... args) { cout< 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(x9)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 q(n);
for(int i=0;i cnt(32,0);
for(int i=0;i=0;j--)
{
if(cnt[j])
{
cnt[j]--;
k|=(1<>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
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< void re_debug(const T& arg,const Ts&... args) { cout< 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;kr) return false;//超了
if(l>n;
if(n==1)
{
cout<>T;
while(T--) solve();
return 0^0;
}
Original: https://www.cnblogs.com/Meteor-Z/p/16536234.html
Author: Meteor_Z
Title: 2022年牛客多校题第四场题解
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604199/
转载文章受原作者版权保护。转载请注明原作者出处！