当前位置：首页 > article >正文

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

article 2025/1/15 19:06:47

链接：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() {
    vcoistnt
    int _=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() {
    vcoistnt
    int _=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() {
    vcoistnt
    int _=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() {
	vcoistnt
	int _=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() {
	vcoistnt
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}

查看全文

http://www.kler.cn/a/503974.html