首页 > 其他分享 >CF2020(Codeforces Round 976 (Div. 2))

CF2020(Codeforces Round 976 (Div. 2))

时间：2024-10-02 12:22:52浏览次数：1  
标签：int CF2020 ll Codeforces long ans Div dp define

CF2020

A. Find Minimum Operations

难度：红
转换进制，每一位上数字相加。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,n,k,ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>k;
        if(k==1)cout<<n<<'\n';
        else{
            ans=0;
            while(n>=k){
                ans+=n%k;
                n/=k;
            }
            ans+=n;
            cout<<ans<<'\n';
        }
    }
    return 0;
}

B. Brightness Begins

难度：橙
场上临时打了个表找规律。发现 \(n-\lfloor\sqrt{n}\rfloor=k\)。于是过了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,k;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>k;
        if(k==0){
            cout<<1<<'\n';
            continue;
        }
        ll a=sqrtl(k);
        if((a+k)-(ll)sqrtl(a+k)==k)cout<<a+k<<'\n';
        else cout<<a+k+1<<'\n';
    }
    return 0;
}

C. Bitwise Balancing

对于每一位分类讨论。
场上分讨调了好久没出来，悲剧了qwq

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,ans,b,c,d;
ll fj(ll b,ll c,ll d){
    ll ret=0;
    for(ll i=0;i<=62;i++){
        ll nowd=((d>>i)&(1ll)),nowc=((c>>i)&(1ll)),nowb=((b>>i)&(1ll));
        if((nowd==0)&&(nowc==0)&&(nowb==0))ret+=0;
        else if((nowd==0)&&(nowc==0)&&(nowb==1))return -1;
        else if((nowd==0)&&(nowc==1)&&(nowb==0))ret+=(1ll<<i);
        else if((nowd==0)&&(nowc==1)&&(nowb==1))ret+=(1ll<<i);
        else if((nowd==1)&&(nowc==0)&&(nowb==0))ret+=(1ll<<i);
        else if((nowd==1)&&(nowc==0)&&(nowb==1))ret+=0;
        else if((nowd==1)&&(nowc==1)&&(nowb==0))return -1;
        else ret+=0;//if((nowd==1)&&(nowc==1)&&(nowb==1))
    }
    if(ret>(1ll<<61))return -1;
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>b>>c>>d;
        cout<<fj(b,c,d)<<'\n';
    }
    return 0;
}

D. Connect the Dots

难度：黄-绿
首先，直接用并查集维护会T飞。
先把操作记录下来，再遍历 \(1\sim n\) 传递操作，并查集维护一下就行了。

#include<bits/stdc++.h>
#define ll long long
#define mxn 200010
using namespace std;
ll T,n,m,a,d,k,f[mxn],num[mxn][15];
int fnd(int x){
    if(x==f[x])return x;
    return f[x]=fnd(f[x]);
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=10;j++)
            num[i][j]=0;
        f[i]=i;
    }
    for(int i=1;i<=m;i++){
        cin>>a>>d>>k;
        num[a][d]=max(num[a][d],k);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=10;j++){
            if(i<=j)break;
            if(num[i-j][j])f[fnd(i)]=fnd(i-j);
        }
        for(int j=1;j<=10;j++)
            if(num[i][j]>1&&i+j<=n)
                num[i+j][j]=max(num[i+j][j],num[i][j]-1);
    }
    set<int> s;
    for(int i=1;i<=n;i++)
        s.emplace(fnd(i));
    cout<<s.size()<<'\n';
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)solve();
}

E. Expected Power

难度：绿
看见期望我就跑
考虑概率dp。
容易发现不管怎么异或，最终异或和的范围总会在 \([0,1023]\) 内。
定义 \(dp_{i,j}\) 为前 \(i\) 位中异或和为 \(j\) 的概率。
当不选 \(a_i\) 时，有
\(dp_{i,j}=dp_{i,j}+(1-p_i)*dp_{i-1,j}\)
选了 \(a_i\) 时，有
$ dp_{i,j}=dp_{i,j}+p_i*dp_{i-1,j\oplus a_i} $
注意到 \(dp_{i}\) 只由 \(dp{i-1}\) 转移，所以可以省一维。

#include<bits/stdc++.h>
#define ll long long 
#define mod 1000000007
#define mxn 200010
using namespace std;
ll t,n,p[mxn],a[mxn],frac,ans;
ll quickpow(ll a,ll x){
    ll ret=1,base=a;
    while(x){
        if(x&1)ret=ret*base%mod;
        base=base*base%mod;
        x>>=1;
    }
    return ret;
}
void solve(){
    cin>>n;
    ans=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>p[i];
    ll dp[1030][2]={0};
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        ll now=i%2,lst=(i%2)^1;
        for(int j=0;j<1024;j++){
            dp[j][now]=0;
            dp[j][now]=(dp[j][now]+dp[j][lst]*(10000-p[i]))%mod;
            dp[j][now]=(dp[j][now]+dp[j^a[i]][lst]*p[i])%mod;
            dp[j][now]=dp[j][now]*frac%mod;          
        }
    }
    for(ll i=0;i<1024;i++)
        ans=(ans+i*i*dp[i][n%2]%mod)%mod;          
    cout<<ans<<'\n';
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    frac=quickpow(10000,mod-2);
    cin>>t;
    while(t--)solve();
    return 0;
}

注：该代码不保证可过，我交的时候TLE了，后面加了快读快写才过的。

F. Count Leaves

难度：紫
这题实在想不到正解，被迫看solution了qaq

容易发现，叶子数量等于选择 \(d+1\) 个数 \(((a_0,a_1,...,a_d),\) 其中 \(a_d=n,a_i|a_{i+1}(i=0...d-1))\) 的方法数。
定义 \(g(n)=f(n,d),(d\) 已给定)。手推一下发现这是个积性函数，即当 \(p,q\) 互质时，有 \(g(p)*g(q)=g(p*q)\)。
当 \(n\) 为某个素数 \(p\) 的非负整数幂次时（即 \(n=p^b\)），明显 \(a_0,a_1,...,a_d\) 可以写成 \(p_{b_0},p_{b_1},...,p_{b_d}=x(b_0\leq b_1\leq...\leq b_d=b)\)。
于是有 \(g(n)=\tbinom{x+d}{d}\)。

然后官方solution上说是受到 Meissel–Lehmer 算法（一种快速计算质数个数的算法）的启发搞了个dp。
当然关于这个算法的介绍也不用去看，OI-wiki上写的像一坨。

总之是搞了一个dp。令 \(dp(n,x)=\sum^n_{i=1,spf(i)\geq x}g(i)\)，其中 \(spf(i)\) 表示 \(i\) 的最小质因子。
我猜看到这么大一串式子你会懵逼。讲的就是从 \(1..n\) 中选出满足其最小质因子大于等于 \(x\) 的数 \(i\)，求 \(g(i)\) 的和。
于是这里有一大堆式子：

\[dp(n,p)=\left\{ \begin{array}{lcl} 0&&n=0\\ 1&&p>n\\ dp(n,p+1)&&p\ \rm{is\ not\ a\ prime}\\ \displaystyle\sum_{i=0\ to\ p^i\leq n}dp(\lfloor\frac{x}{p}\rfloor,p+1)f(p^{ik},d)&&\rm otherwise \end{array} \right. \]

手推过程略。
明显，\(g(n)=dp(n,2)\)，于是可以求出答案。
时间复杂度 \(O(n^{\frac{2}{3}})\)。

这里就先把官方代码贴上面吧（可读性极高），到时候再补自己的。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define big_lim 1001
#define small_lim 1000001
#define mod 1000000007
#define ncrlim 3500000
using namespace std;
ll powmod(ll base,ll exponent){
	ll ans=1;
	if(base<0)base+=mod;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a,ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
ll primes_till_i[small_lim];
ll primes_till_bigger_i[big_lim];
vector<ll> sieved_primes[small_lim];
vector<ll> sieved_primes_big[big_lim];
vector<int> prime;
int N,k,d;
void sieve(){//普通的埃氏筛
	vector<int> lpf(small_lim);
	ll pw;
	for(int i=2;i<small_lim;i++){
		if(!lpf[i]){
			prime.push_back(i);
			lpf[i]=i;
		}
		for(int j:prime){
			if((j>lpf[i])||(j*i>=small_lim))break;
			lpf[j*i]=j;
		}
	}
	for(int i=2;i<small_lim;i++)
		primes_till_i[i]=primes_till_i[i-1]+(lpf[i]==i);
}
ll count_primes(ll n,int ind){
	if(ind<0)return n-1;
	if(1ll*prime[ind]*prime[ind]>n){
		if(n<small_lim)return primes_till_i[n];
		if(primes_till_bigger_i[N/n])return primes_till_bigger_i[N/n];
		int l=-1,r=ind;
		while(r-l>1){
			int mid=(l+r)>>1;
			if(1ll*prime[mid]*prime[mid]>n)r=mid;
			else l=mid;
		}
		return primes_till_bigger_i[N/n]=count_primes(n,l);
	}
	int sz;
	if(n<small_lim)sz=sieved_primes[n].size();
	else sz=sieved_primes_big[N/n].size();
	ll ans;
	if(sz<=ind){
		ans=count_primes(n,ind-1);
		ans-=count_primes(n/prime[ind],ind-1);
		ans+=ind;
		if(n<small_lim) sieved_primes[n].push_back(ans);
		else sieved_primes_big[N/n].push_back(ans);
	}
	if(n<small_lim) return sieved_primes[n][ind];
	else return sieved_primes_big[N/n][ind];
}
ll count_primes(ll n){
	if(n<small_lim) return primes_till_i[n];
	if(primes_till_bigger_i[N/n]) return primes_till_bigger_i[N/n];
	return count_primes(n,prime.size()-1);
}
int fact[ncrlim];
int invfact[ncrlim];
void init_fact(){
	fact[0]=1;
	for(int i=1;i<ncrlim;i++) fact[i]=(1ll*fact[i-1]*i)%mod;
	invfact[ncrlim-1]=powmod(fact[ncrlim-1], mod-2);
	for(int i=ncrlim-1;i>0;i--) invfact[i-1]=(1ll*invfact[i]*i)%mod;
}
int ncr(int n,int r){
	if(r>n||r<0)return 0;
	int ans=fact[n];
	ans=(1ll*ans*invfact[n-r])%mod;
	ans=(1ll*ans*invfact[r])%mod;
	return ans;
}
ll calculate_dp(ll n,int ind){
	if(n==0)return 0;
	if(prime[ind]>n) return 1;
	ll ans=1,temp;
	if(1ll*prime[ind]*prime[ind]>n){
		temp=ncr(k+d,d);
		temp*=count_primes(n)-ind;
		ans=(ans+temp)%mod;
		return ans;
	}
	ans=0;
	ll gg=1;
	ll mult=d;
	while(gg<=n){
		temp=calculate_dp(n/gg,ind+1);
		temp*=ncr(mult,d);
		ans=(ans+temp)%mod;
		mult+=k;
		gg*=prime[ind];
	}
	return ans;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	sieve();//质数预处理
	init_fact();//组合数预处理
	int t;
	cin>>t;
	while(t--){
        cin>>N>>k>>d;
        cout<<calculate_dp(N,0)<<'\n';
		for(int i=1;i<big_lim;i++){
			primes_till_bigger_i[i]=0;
			sieved_primes_big[i].clear();
		}
	}
	return 0;
}

标签：int,CF2020,ll,Codeforces,long,ans,Div,dp,define
From： https://www.cnblogs.com/nagato--yuki/p/18442684

相关文章

  • [LeetCode] 1497. Check If Array Pairs Are Divisible by k
    Givenanarrayofintegersarrofevenlengthnandanintegerk.Wewanttodividethearrayintoexactlyn/2pairssuchthatthesumofeachpairisdivisiblebyk.ReturntrueIfyoucanfindawaytodothatorfalseotherwise.Example1:Input:arr......
  • pbootcms编辑器过滤div代码解决办法
    在使用PbootCMS建站时，如果需要在专题内容中加入含有HTML代码的文字，但发现编辑器将 div 标签转换成了 p 标签，可以通过以下步骤进行修改。修改步骤修改 ueditor.all.js 文件找到 core->extend->ueditor->ueditor.all.js 文件。在大约第10830行，将 allowDivTransToP......
  • Codeforces Round 956 (Div. 2)
    无法评价，不知道是我傻逼还是题傻逼。A.ArrayDivisibility题意让你构造一个长度为\(n\)的序列，满足对于每一个\(i\)\((i\in[1,n])\)，让\(a_j\)之和为\(i\)的倍数，\(j\)能被\(i\)整除。换句话说，让你构造一个长度为\(n\)的序列，满足\(\sum_{j|i}a_j\)能被\(i\)......
  • Codeforces2014E Rendez-vous de Marian et Robin(分层图最短路)
    题意给定一个无向图，含有\(n\)个点和\(m\)条边。题解点击查看代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;constexpri64inf=1e18;voidsolve(){intn,m,h;cin>>n>>m>>h;vector<vector<......
  • Codeforces Round 974 (Div. 3) - D题
    这道题题意就是你有k个工作，每个工作都有一个时间区间左边界l和右边界r，妈妈和哥哥要来看你，时长为d，题目要求求出1.哥哥看你的这段时间工作时间段重叠最多是多少？2.妈妈看你的这段时间工作时间段重叠最少是多少？这道题如果硬做的话可能就是线段树了（蒟蒻暂时没有想到其他的做法），但如果......
  • Codeforces Round 973 (Div. 2) - D题二分
    首先这道题的一个坑点就是求max(a[1],a[2],...,a[n])和求min(a[1],a[2],...,a[n])是完全独立的，不会相互影响（可能是我读题能力太差，一直卡在这点了。。。）这道题二分是一种很好想的方法，题中提到max和min，我们就可以想到只要让最大值最小，让最小值最大就可以达到我的目的了，二分的......
  • Codeforces Round 976 (Div. 2)
    VP的这一场，真的唐完了。。。A.FindMinimumOperations题意给你一个\(n\)和\(k\)，每次操作可以让\(n\)减去一个\(k\)的\(x\)次方，即\(n-k^x\)。问你最少操作几次能够让\(n\)变成\(0\)。思路我们先考虑如果\(k\)是\(2\)的情况，那么题目就转化成了\(n\)的......
  • Codeforces Round 958 (Div. 2)
    手速前三题，D题想到树形dp但是没做出来。A.SplittheMultiset题意给你一个多集，一开始这个多集里只有一个数字。每次操作可以选择删掉多集里的一个数，然后添加\(k\)个数，并且使得这\(k\)个数的和等于删掉的数。问你最少需要操作多少次多集里的数的个数等于等于\(n\)。思路......
  • codeforces round 975 E(div.2)(lambda表达式实现dfs，min_element函数，一定要优化重复的
    解题历程：看到题目要求要用最少的消除次数让所有叶子深度相同，通过观察，那么就只需要将所有深度都尝试一遍就行了，可是我当时没多想就用dfs记录所有节点的深度，单独将所有叶子和该叶子的深度存起来，记录最大的深度，从最大深度尝试到深度0，对于深度小于当前尝试深度的叶子，用dfs的方式将与......
  • Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
    目录写在前面A签到B数学，模拟C二进制，拆位D暴力，并查集E概率DPF写在最后写在前面补题地址：https://codeforces.com/gym/104128。上大分失败呃呃呃呃有点过载了妈的我现在应该去打会儿游戏。A签到等价于求\(n\)在\(k\)进制下各位之和，写一个类似快速幂的东西。///*By......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99