Codeforces Round 976 (Div. 2) 题解

news/2024/10/3 10:31:31

Codeforces Round 976 (Div. 2) 题解

2020B

一个常见的想法：开关灯=异或，虽然在这道题里没啥用
注意到，第i盏灯的按钮被按的次数就是i的除它本身以外的因子个数
而完全平方数的因子数为奇数，其他数的因子数为偶数

点击查看更多信息

#include<bits/stdc++.h>
using namespace std;
void solve()
{long long k;cin>>k;long long n;if(k<=100)n=1;else n=sqrt(k)-9;while(k>n*(n+1))n++;cout<<n*n+k-n*(n-1)<<endl;}
int main()
{int T;cin>>T;while(T --> 0){solve();}return 0;
}

2020C

大力分类讨论，按位判断，根据b,c,d的值判断a的值是可能存在，不存在还是已确定

查看代码

#include<bits/stdc++.h>
using namespace std;
void solve()
{long long b,c,d,ck=1;cin>>b>>c>>d;long long a=0;for(long long i=0;i<=60;i++){long long tb=b&(1ll<<i);long long tc=c&(1ll<<i);long long td=d&(1ll<<i);if(td==0){if(tb!=0&&tc==0){ck=0;break;}else if(tb!=0){a+=(1ll<<i);}}else{if(tb!=0&&tc==0);else if(tb!=0);else if(tc!=0){ck=0;break;}else{a+=(1ll<<i);}}}if(ck)cout<<a<<endl;else cout<<-1<<endl;}
int main()
{long long T;cin>>T;while(T --> 0){solve();}return 0;
}

2020D

并查集。

注意到：d的范围很小，而我们只需要知道一个数和它的后十个数之间的联通关系就可以知道所有点之间的联通关系。因此我们定义一个n*10的数组，用来储存一个数和它之后的第d个数的联通关系。但是一次操作会影响很多数与它之后的第d个数的关系，我们采用差分的方式进行区间维护

查看代码

#include<bits/stdc++.h>
using namespace std;
int cnt[200005][12];
int f[200005];
int ct[200005];
int find(int x)
{if(f[x]==x)return x;return f[x]=find(f[x]);
}
void solve()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){f[i]=i;ct[i]=0;for(int j=1;j<=10;j++)cnt[i][j]=0;}for(int i=1;i<=m;i++){int a,d,k;cin>>a>>d>>k;cnt[a][d]++;cnt[a+k*d][d]--;}for(int i=1;i<=n;i++){for(int j=1;j<=10;j++){if(i+j>n)continue;if(i>=j)cnt[i][j]+=cnt[i-j][j];if(cnt[i][j]>0)f[find(i)]=find(i+j);}}int ans=0;for(int i=1;i<=n;i++){if(ct[find(i)]==0)ct[find(i)]=1,ans++;}cout<<ans<<endl;
}
int main()
{int T;cin>>T;while(T --> 0){solve();}return 0;
}

2020E

首先我们需要明白，E(X^2) != E(X)E(X) ,而E(XY)=E(X)E(Y)的前提是X，Y独立（X，X显然不独立）

注意到值域很小，而时限很大，那么，我们采用一个暴力的想法，定义f[n][x]为前n个数完成选择后异或和为x的概率，然后所有的f[n][x]xx之和即为答案。

不过这么开数组会mle，我们用一个回滚数组即可

查看代码


#include<bits/stdc++.h>
using namespace std;
int pow(int a,int b,int p)
{int s=1;while(b){if(b%2)s=1ll*s*a%p;a=1ll*a*a%p;b>>=1;}return s;
}
int a[200005],b[200005];
const int p=1e9+7;
int f[2][1024];
void solve()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}int m=pow(10000,p-2,p);for(int i=1;i<=n;i++){cin>>b[i];b[i]=1ll*b[i]*m%p;}for(int j=0;j<=1023;j++){f[1][j]=f[0][j]=0;}f[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=1023;j++){f[1][j]=(1ll*f[0][j^a[i]]*b[i]%p+1ll*f[0][j]*(1-b[i]+p)%p)%p;}for(int j=0;j<=1023;j++){f[0][j]=f[1][j];}}long long ans=0;for(int i=0;i<=1023;i++){ans=(ans+1ll*i*i%p*f[0][i]%p)%p;}cout<<ans<<endl;}
int main()
{int T;cin>>T;while(T --> 0){solve();}return 0;
}