牛客练习赛 98 题解
A.魔圆寄录 by lgswdn
如果 ,那么我们每轮选择五次 Normal 攻击。
否则我们每轮选择五次 Blast 攻击。
得到的答案为 。
#include<bits/stdc++.h> #define int long long using namespace std; inline int read(){ int x=0,f=1;char c=getchar(); for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;} for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15); return x*f; } signed main(void){ int h=read(),a=read(),b=read(); cout<<(h-1)/(5*max(a,3*b))+1<<endl; return 0; }
B.Mentai Cosmic by 云浅
显然,选出数中至多有一个数小于 。否则若 均小于 ,则 ,与题意矛盾。
那么如果 我们肯定就把它选上,接下来再看看剩下的数中最大的那个数是否符合要求即可。
#include<bits/stdc++.h> #define int long long using namespace std; inline int read(){ int x=0,f=1;char c=getchar(); for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;} for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15); return x*f; } const int MN=1e6+5; const int INF=1e9; int n,m,a[MN]; void solve(){ n=read(),m=read();int x=0,mn=INF,mx=0; for(int i=1;i<=n;i++){ a[i]=read(); if(a[i]*2>=m)x++,mn=min(mn,a[i]); else mx=max(mx,a[i]); } cout<<max(1ll,x+(mx+mn>=m))<<endl; } signed main(void){ int tt=read(); while(tt--)solve(); return 0; }
时间复杂度 。
C.AIR Triplet by lgswdn
先考虑单独处理一个查询。首先异或的条件可以转化成 。考虑如何求解:求得一个计数器 表示 在当前序列中出现的个数。考虑枚举 是多少,则答案应为 。
考虑修改一个数对于全局的影响。这个数的位置是无所谓的,我们只关心值。把 修改成 相当于删掉一个 再添加一个 。删掉一个 相当于将 减一,即答案 。添加一个 同理。
所以一次操作(把一个 换成一个 )的步骤应为:
#include<bits/stdc++.h> #define int long long using namespace std; inline int read(){ int x=0,f=1;char c=getchar(); for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;} for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15); return x*f; } const int MN=1e6+5; int n,a[MN],cnt[MN],q; int calc(int x){ return x*(x-1)/2*(x-2)/3; } signed main(void){ n=read(),q=read();int N=1e6,ans=0; for(int i=1;i<=n;i++)cnt[a[i]=read()]++; for(int i=1;i<=N;i++)ans+=calc(cnt[i]); while(q--){ int x=read(),y=read(); ans-=calc(cnt[a[x]]--),ans+=calc(cnt[a[x]]),a[x]=y; ans-=calc(cnt[a[x]]++),ans+=calc(cnt[a[x]]); cout<<ans<<endl; } return 0; }
D.Sonstring by lgsdwn
首先我们把所有数位都变成其模 的余数(奇数是 偶数是 ),然后我们发现这个对 求和相当于不限制划分的子串数量。于是我们转化成了如下问题:
给定一个 字符串,问有多少种划分,使得每一个划分出来的子串的 的个数,组成的序列,是回文的。
这个数据范围比较小,而且这个 的个数组成的序列是回文的条件比较难处理,所以可以考虑硬上区间 DP。由于切的顺序无关,我们可以钦定一种方便我们 DP 的切的顺序:对于一个区间,必须先切外再切里(不断缩小区间)。
转移即枚举如何切 子串(的第一步)。它可以不切,或者切(然后枚举它的回文中心)。
设 为 区间的划分方案数。设 表示区间 的个数,则有
可以发现对于一个确定的 ,满足 的 的取值是一段区间。并且随着 的增大,区间的左右端点的移动都是单调的。
因此可以维护两个指针表示 的取值区间,同时记录 的前缀和即可做到 。
#include<bits/stdc++.h> #define int long long using namespace std; inline int read(){ int x=0,f=1;char c=getchar(); for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;} for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15); return x*f; } const int MN=505,mod=998244353; int n,f[MN][MN],g[MN][MN]; char s[MN]; int sum[MN]; signed main(void){ cin>>(s+1);n=strlen(s+1); for(int i=1;i<=n;i++)f[i][i-1]=1,g[i][i-1]=1; for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(((int)(s[i]-'0'))&1); for(int len=1;len<=n;len++){ for(int i=1,j=len;j<=n;i++,j++){ f[i][j]=1;int p=j,q=j; for(int l=i;l<=j-1;l++){ while(p>=l&&sum[j]-sum[p-1]<=sum[l]-sum[i-1])p--; while(sum[j]-sum[q-1]<sum[l]-sum[i-1])q--; if(q<=l)break; f[i][j]+=(g[l+1][q-1]-g[l+1][p-1]+mod)%mod,f[i][j]%=mod; } g[i][j]=g[i][j-1]+f[i][j],g[i][j]%=mod; } } cout<<f[1][n]%mod<<endl; return 0; }
E.Robotic Girl by 云浅
当然很好做。考虑 时怎么做。
考虑对每一组逆序对算贡献。对于一组逆序对 ,不难发现其被计算的次数就是 。
或者,形式化地:
维护一个树状数组。从前往后处理,处理到 时求一下 的区间和,乘上 并累加;然后在树状数组 的位置处 。注意 最大可以到 ,需要离散化。
时间复杂度 。
现在我们来考虑 较大的情形:仍然考虑一组逆序对 的贡献。
此时相当于要从 与 中分别选出来 个点,但是不记顺序。
形式化地,我们选出的左端点需要满足 ,求满足这个条件的序列 的个数。这是经典排列组合问题,可以发现答案就是
略证:上式等价于 。
因此就相当于从 中不重复地选出 个数,那么答案就是你所熟悉的组合数,。
因此只需要 预处理组合数,然后 计算答案即可。复杂度 。
#include<bits/stdc++.h> #define int long long using namespace std; inline int read(){ int x=0,f=1;char c=getchar(); for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;} for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15); return x*f; } const int MN=1e6+5; const int mod=998244353; int n,k; int a[MN],b[MN],fac[MN],ifac[MN]; int ksm(int y,int z,int p=mod){ y%=p;int ans=1; for(int i=z;i;i>>=1,y=y*y%p)if(i&1)ans=ans*y%p; return ans%p; } int inv(int x,int p=mod){return ksm(x,p-2,p)%p;} int C(int n,int m){ if(n<m)return 0; return fac[n]*ifac[m]%mod*ifac[n-m]%mod; } struct BIT{ int c[MN<<1]; void clear(){memset(c,0,sizeof(c));} int lowbit(int x){return x&(-x);} void add(int x,int k){for(int i=x;i<=n;i+=lowbit(i))c[i]+=k,c[i]%=mod;} int sum(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=c[i],res%=mod;return res;} }tree; void solve(){ n=read(),k=read();int ans=0;tree.clear(); for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i]; sort(b+1,b+n+1);int len=unique(b+1,b+n+1)-b-1; for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+len+1,a[i])-b; for(int i=1;i<=n;i++)ans+=(tree.sum(n)-tree.sum(a[i])+mod)%mod*C(n-i+k,k)%mod,ans%=mod,tree.add(a[i],C(i+k-1,k)); cout<<ans%mod<<endl; } const int N=1e6; signed main(void){ fac[0]=1;for(int i=1;i<=N;i++)fac[i]=fac[i-1]*i%mod; ifac[N]=inv(fac[N])%mod;for(int i=N-1;i>=0;i--)ifac[i]=ifac[i+1]*(i+1)%mod; int tt=read(); while(tt--)solve(); return 0; }
F.Ginga Tetsudou no Penguin by 云浅
考虑一个朴素的 dp:设 表示前 只企鹅选 个,且必须选第 只的最小代价,那么
直接转移复杂度是 的。这显然不行。
我们考虑优化:注意到随着 的增加, 和 都在单调递增。
因此可以使用单调队列优化:用单调队列来记录区间 内的最小值,单次转移就是 了。
这样就做到了 的时间复杂度,但仍然无法面对 的数据范围。
看上去状态数已经是 ,似乎已经达到了极限。
实际上并不然。设 表示选 个时的最小代价,可以证明 是一个凸函数,也就是其相邻两点连线斜率单调。
因此可以二分这个斜率 ,计算 的最小值点(由于没有了 的限制,这就相当于将每个物品的价值减去 ,从而可以在 的时间内计算完毕),根据此时算出的点 来确定斜率的大小。
这样做的时间复杂度为 ,其中 为值域。
#include<bits/stdc++.h> #define int long long using namespace std; inline int read(){ int x=0,f=1;char c=getchar(); for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;} for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15); return x*f; } const int MN=2e5+5; int f[MN],g[MN],n,m,k,a[MN]; deque<int>dmin; const int INF=2e14; #define fi first #define se second #define mk make_pair pair<int,int> calc(int x){ memset(f,63,sizeof(f)),memset(g,0,sizeof(g)); while(dmin.size())dmin.pop_back();f[0]=0,dmin.push_back(0); for(int i=1;i<=n;i++){ while(dmin.size()&&dmin.front()<i-m)dmin.pop_front(); f[i]=a[i]-x,g[i]=1; if(dmin.size())f[i]+=f[dmin.front()],g[i]+=g[dmin.front()]; while(dmin.size()&&f[i]<=f[dmin.back()])dmin.pop_back();dmin.push_back(i); } while(dmin.size()&&dmin.front()<n-m+1)dmin.pop_front(); return mk(f[dmin.front()],g[dmin.front()]); } void solve(){ n=read(),m=read(),k=read(); for(int i=1;i<=n;i++)a[i]=read(); int L=-INF,R=INF,ans=L; while(L<=R){ int mid=(L+R)>>1; auto x=calc(mid); if(x.se<k)L=mid+1; else ans=mid,R=mid-1; } cout<<calc(ans).fi+ans*k<<endl; } signed main(void){ int tt=read();while(tt--)solve(); return 0; }
G.Romantic Misletoe by lgswdn
首先抛开 条件不看,我们可以得到一个 。 表示考虑 子树且 的方案数。。考虑 的前缀和 ,则有 。考虑优化。
看到只有连乘,可以猜想一下 是一个关于 的多项式 。可以归纳证明。叶节点一定是。如果子节点是,那么子节点的前缀和(多项式相加)也必然是,所以多项式相乘也必然是。
所以,我们发现 必然是一个次数不大于 的多项式。因为转移为乘积,多项式的乘积仍然为多项式,并且次数为多项式的次数之和。也就是意味着我们可以得到 然后拉格朗日插值插出 。这部分可以 解决。
然后,我们加入 的条件。套路地,我们使用数论容斥(或者也可以理解为莫比乌斯反演,不过不知道这个也没有关系),对于每个 计算出钦定大家都是 的倍数的条件,容斥系数容易推得为莫比乌斯函数,则有
的取值很少,暴力做即可。
运用拉格朗日插值插出多项式系数后,多项式求值只需要 复杂度。所以总复杂度为 。
#include<bits/stdc++.h> #define int long long using namespace std; inline int read(){ int x=0,f=1;char c=getchar(); for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;} for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15); return x*f; } #define OK puts("OK") const int mod=1e9+7; const int MN=2005; const int MC=3e7+5; int n,m; vector<int>G[MN]; int f[MN][MN],g[MN][MN]; void dp(int u,int fa){ for(int i=1;i<=n+1;i++)f[u][i]=1; for(int v:G[u]){ if(v==fa)continue; dp(v,u); for(int i=1;i<=n+1;i++)f[u][i]=f[u][i]*g[v][i]%mod; } for(int i=1;i<=n+1;i++)g[u][i]=(g[u][i-1]+f[u][i])%mod; } int a[MN],invx[MN],p[MN],q[MN],r[MN],tmp[MN]; int ksm(int x,int y,int p=mod){ int res=1; for(int i=y;i;i>>=1,x=x*x%p)if(i&1)res=res*x%p; return res; } int inv(int x,int p=mod){ return ksm(x,p-2,p); } void Lagrange(){ for(int i=1;i<=n+1;i++)invx[i]=inv(i); p[0]=1; for(int i=1;i<=n+1;i++){ q[0]=mod-i,q[1]=1; for(int j=0;j<i;j++) for(int k=0;k<=1;k++)r[j+k]=(r[j+k]+p[j]*q[k]%mod+mod)%mod; for(int j=0;j<=i;j++)p[j]=r[j],r[j]=0; } for(int i=1;i<=n+1;i++){ int fm=inv(g[1][i])%mod; for(int j=1;j<=n+1;j++)if(j!=i)fm=fm*(i-j+mod)%mod; r[0]=(mod-p[0]*invx[i]%mod+mod)%mod,fm=inv(fm); for(int j=1;j<=n;j++)r[j]=(mod-(p[j]-r[j-1]+mod)%mod*invx[i]%mod+mod)%mod; for(int j=0;j<=n;j++)a[j]=(a[j]+r[j]*fm%mod+mod)%mod; } } int calc(int k){ int res=0; for(int i=n;i>=0;i--)res=(res*k%mod+a[i])%mod; return res; } int mu[MC],pri[1857860]; bool isp[MC]; void pre(){ int N=30000000,cnt=0;mu[1]=1; memset(isp,1,sizeof(isp)); for(int i=2;i<=N;i++){ if(isp[i])pri[++cnt]=i,mu[i]=-1; for(int j=1;j<=cnt;j++){ if(i*pri[j]>N)break; int x=i*pri[j];isp[x]=0; if(i%pri[j]==0){mu[x]=0;break;} mu[x]=-mu[i]; } } for(int i=1;i<=N;i++)mu[i]+=mu[i-1]; } signed main(void){ #ifndef ONLINE_JUDGE freopen("in.in","r",stdin); #endif n=read(),m=read(); for(int i=1;i<=n-1;i++){ int u=read(),v=read(); G[u].push_back(v),G[v].push_back(u); } dp(1,0);pre(),Lagrange(); int ans=0; for(int l=1,r=0;l<=m;l=r+1){ r=m/(m/l); ans=(ans+(mu[r]-mu[l-1]+mod)%mod*calc(m/l)%mod+mod)%mod; } cout<<ans<<endl; return 0; }
update on 5.17
- D 的 做法
抱歉咕了这么久=_=
考虑先找出来原字符串中奇数的位置,设为 。
如果我们选出的 个点分别是 ,由于对每个 ,满足 的 的数量是回文的,因此,对每个 ,满足 的 的数量同样应该是回文的。
可以这么理解:由于每相邻两个划分点之间的奇数个数对称,那么按照奇数的位置划分之后,每一段中的划分点的个数必然是对称的;否则,在不对称的那个位置就会出现「错位」,导致划分出来的奇数个数不对称。
因此,我们可以依次枚举每相邻两个奇数段 ,记 ,那么在这两边选出来的个数需要一样。枚举选出来了多少个,可以发现贡献为
其实直接枚举已经能做到 了。需要特判一下最中间的那一段,若其长度为 ,则其贡献为 。
注意到上式其实就是 ,因此我们还能做到更快,并且支持一些动态修改。在本题中没有必要。
ps:之前能过的一份 被我卡了
- 为什么 F 中的函数是凸的呢
因为和 O(nk) 的暴力 dp 拍了几千组都过了
有一个感性的证明:考虑从 到 的时候,就相当于多选了一个。
由于前面我们已经选过一些数了,因此选出来的这些数对「每 个就需要选一个」这一要求已经做出了一些贡献。这样一来,选择数的限制更松了,那么自然就有 。
全部评论
(6) 回帖