Codeforces Round 976 (Div. 2) and Divide By Zero 9.0(A-E)

链接：Dashboard - Codeforces Round 976 (Div. 2) and Divide By Zero 9.0 - Codeforces

A. Find Minimum Operations

思路

可以观察发现这里有个进制的思想，转换为k进制把每位数相加即可

代码

void solve(){int n,k;cin>>n>>k;if(k==1){cout<<n<<"\n";return;}    int cnt=0;while(n){cnt+=n%k;n/=k;}cout<<cnt<<"\n";
}

B. Brightness Begins

思路

很容易可以看出是个二分题，我们可以发现只要是完全平方数灯泡最后的状态就是灭着的，其余一定是亮的，那么这个题就是二分找一下完全平方数的数量，具体现在是 $n$ 个灯泡的话，那么前面有 $\sqrt{n}$ 个灯是灭的， $n-\sqrt{n}$ 个灯泡是亮的，注意要用sqrtl，sqrt的卡了精度不够

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int k;cin>>k;auto check=[&](int x)->bool{if(x-(int)sqrtl(x)>=k) return true;else return false;};int l=1,r=9e18;int ans=0;while(l<=r){int mid=(l+r)>>1;if(check(mid)){ans=mid;r=mid-1;}else{l=mid+1;}}cout<<ans<<"\n";
}
signed main() {vcoistntint _=1;cin>>_;while(_--) solve();return 0;
}

C. Bitwise Balancing

思路

给出的是二进制的运算，那么我们就可以只看一位的所有情况来找规律，

可以发现b，c，d没有出现100或011的情况，其他情况都能找到a的值，直接暴力找一遍即可

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int b,c,d;int a=0;cin>>b>>c>>d;bool flag=true;int t=1;for(int i=0;i<65;i++){int bitb=0,bitc=0,bitd=0;if(b&t) bitb=1;if(c&t) bitc=1;if(d&t) bitd=1;if((!bitb&&!bitc&&bitd)||(bitb&&bitc&&!bitd)){a+=(1ll<<i);}if((bitb&&(!bitc)&&(!bitd))||((!bitb)&&bitc&&bitd)){flag=false;break;}t<<=1;}if(flag){cout<<a<<"\n";}else{cout<<"-1\n";}
}
signed main() {vcoistntint _=1;cin>>_;while(_--) solve();return 0;
}

D. Connect the Dots

思路

很明显这题要用到并查集，如果每次操作都要加入到并查集里面那么肯定会T，细心观察一下发现1<=d<=10，那么我们可以把d相等的操作放在一起，这样就可以大大节省运行时间，然后再用前缀和来优化并查集再次减少时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define lowbit(x) ((x)&-(x))
typedef int itn;
typedef pair<int,int> pll;const int N=2e5+10;
const int INF=0x3f3f3f3f3f3f3f3f;
const int inf=INT_MIN;
const int mod=998244353;
const int base=283;struct DSU {vector<int>p,siz;DSU(int n):p(n),siz(n,1) {iota(p.begin(),p.end(),0);}int find(int x) {while(x!=p[x]) x=p[x]=p[p[x]];return x;}bool same(int x,int y) {return find(x)==find(y);}bool merge(int x, int y) {x=find(x),y=find(y);if (x==y) return false;siz[x]+=siz[y],p[y]=x;return true;}int size(int x) {return siz[find(x)];}
};void solve(){int n,m;cin>>n>>m;DSU dsu(n+10);vector<int> a(m+10),d(m+10),k(m+10);for(int i=1;i<=m;i++){cin>>a[i]>>d[i]>>k[i];} int ans=n;for(int i=1;i<=10;i++){     //因为d[i]<=10暴力查10次vector<int> f(n+10);    //要前缀和的数组for(int j=1;j<=m;j++){if(d[j]==i){f[a[j]]++;f[a[j]+k[j]*i]--;}}for(int j=i;j<=n;j++){f[j]+=f[j-i];       //要相隔i}for(int j=1;j<=n;j++){if(f[j]){ans-=dsu.merge(j,j+i);  //加入成功-1，失败-0}}}cout<<ans<<"\n";
}
signed main() {vcoistntint _=1;cin>>_;while(_--) {solve();}return 0;
}

E. Expected Power

思路

这题也是补了一下午弄懂了两个方法去解决，收获还是蛮大的写一篇题解

令 $p[i]$ 为第i个数插入成功的概率， $q[i]$ 为失败的概率

方法1：

因为a的值域很小，我们可以考虑设 $dp[i][j]$ 为试图将a数组中前i个数插入到 $S$ 中，异或结果 $f(S)=j$ 的概率，那么根据异或的性质得出状态转移方程为

$dp[i][j]=p[i]*dp[i-1][j\bigoplus a[i]]+q[i]*dp[i-1][j]$

所以 $E[f(S)^{2}]=\sum_{j=0}^{1023}dp[n][j]*j^{2}$

注：数组会爆用滚动数组实现

方法2：

我们可以先试着求一下 $f(S)$ 的期望，根据异或的性质 $E[f(S)]=\sum_{i=0}^{9}P(i)*2^{i}$ ，其中 $P(i)$ 为二进制下第i位是1的概率

因为a<1024我们可以把a拆成二进制，设 $dp[i][j][0/1]$ 表示试图插入前i个数，第j位为0/1的概率，那么 $E[f(s)]=\sum_{j=0}^{9}dp[n][j][1]*2^{j}$ ，不妨设x为a[i]二进制下第j位上的值，那么状态转移方程为 $dp[i][j][k]=p[i]*dp[i-1][j][k\bigoplus x]+q[i]*dp[i-1][j][k]$

接下来我们求 $f(S)^{2}$ 的期望，设 $f(S)=\sum_{i=0}^{9}b[i]*2^{i}$ ，所以 $f(S)=\sum_{i=0}^{9}\sum_{j=0}^{9}b[i]*b[j]*2^{i+j}$ ，得 $E[f(S)^{2}]=\sum_{0}^{9}\sum_{0}^{9}P(i,j)*2^{i+j}$ 其中 $P(i,j)$ 为第i位和第j位都为1的概率

那么我们就设 $dp[i][j][k][0/1][0/1]$ 表示前i个，第j位为0/1，第k位为0/1的概率，状态转移方程为 $dp[i][j][k][l][m]=p[i]*dp[i-1][j][k][l\bigoplus x ][m\bigoplus y]+q[i]*dp[i-1][j][k][l][m]$

最后得出 $E[f(S)^{2}]=\sum_{j=0}^{9}\sum_{k=0}^{9}dp[n][j][k][1][1]*2^{j+k}$

同样要用滚动数组

代码

方法1：

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=1e9+7;int ksm(int a,int b){int ans=1;while(b){if(b&1){ans=(ans*a)%mod;}a=((a%mod)*(a%mod))%mod;b>>=1;}return ans;
}void solve(){int n;cin>>n;vi a(n+10);vector<int> p(n+10),q(n+10);for(int i=1;i<=n;i++){cin>>a[i];}	for(int i=1;i<=n;i++){int x;cin>>x;p[i]=(x*ksm(10000,mod-2))%mod;q[i]=10000-x;q[i]=(q[i]*ksm(10000,mod-2))%mod;}vector<int> dp(2000,0);vector<int> tp(2000,0);tp[0]=1;for(int i=1;i<=n;i++){for(int j=0;j<1024;j++){dp[j]=( (p[i]*tp[(j^a[i])])%mod+ (q[i]*tp[j])%mod)%mod;}tp=dp;}int ans=0;for(int i=0;i<=1023;i++){ans=(ans+dp[i]*i*i)%mod;}cout<<ans<<"\n";
}
signed main() {vcoistntint _=1;cin>>_;while(_--) solve();return 0;
}

方法2：

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=1e9+7;int ksm(int a,int b){int ans=1;while(b){if(b&1){ans=(ans*a)%mod;}a=((a%mod)*(a%mod))%mod;b>>=1;}return ans%mod;
}const int bits=11;	//a<1024,二进制最高10位int dp[bits][bits][2][2];
//dp[j][k][0/1][0/1]表示第j位为0/1并且第k位为0/1的概率void solve(){int n;cin>>n;vi a(n+10);for(int i=1;i<=n;i++){cin>>a[i];}vector<int> p(n+10),q(n+10);	//p是插入的概率，q是失败的概率for(int i=1;i<=n;i++){int x;cin>>x;p[i]=(x*ksm(10000,mod-2))%mod;	//逆元取模q[i]=10000-x;q[i]=(q[i]*ksm(10000,mod-2))%mod;}//初始化for(int j=0;j<bits;j++){for(int k=0;k<bits;k++){for(int l:{0,1}){for(int m:{0,1}){dp[j][k][l][m]=0;}}}}for(int j=0;j<bits;j++){for(int k=0;k<bits;k++){dp[j][k][0][0]=1;}}for(int i=1;i<=n;i++){int bin[bits]; //将a的二进制形式存入数组int x=a[i];for(int j=0;j<bits;j++){bin[j]=x&1;x>>=1;}for(int j=0;j<bits;j++){for(int k=0;k<bits;k++){int temp[2][2];		//用于暂存	实现滚动数组for(int l:{0,1}){for(int m:{0,1}){//			如果插入了这个数							如果没有插入这个数temp[l][m]=(( p[i]*dp[j][k][(l^bin[j])][(m^bin[k])] )%mod+( q[i]*dp[j][k][l][m] )%mod)%mod;}}for(int l:{0,1}){for(int m:{0,1}){dp[j][k][l][m]=temp[l][m];}}}}}int ans=0;for(int j=0;j<bits;j++){for(int k=0;k<bits;k++){int pw2= ( 1ll<<(j+k) )%mod;ans=(ans%mod+((pw2%mod)*(dp[j][k][1][1]%mod)%mod))%mod;}}cout<<ans<<"\n";}
signed main() {vcoistntint _=1;cin>>_;while(_--) solve();return 0;
}