牛客练习赛5
A. Split
贪心，很明显分得要尽量均匀。
二分分成几段（即答案），可以$O(n)$判断，也可$O(1)$判。
时间复杂度O(log(n))
#include<bits/stdc++.h>
using namespace std;
#define int long long
int s,m,l,r,ans,mid,a,b;
bool pd(int x)
{
a=s/x;b=s%x;
return(s*s-a*a*(x-b)-(a+1)*(a+1)*b)/2>=m;
}
signed main()
{
scanf("%lld%lld",&s,&m);
l=1;r=s;
while(l<=r)
{
mid=(l+r)/2;
if(pd(mid))ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans-1;
return 0;
}
B.Xor
这个题目有两个限制：一个是𝑥𝑜𝑟和相等，第二个是b[i]小于等于a[i]
我们先分析第二个限制，我们从高位往低位考虑。对于一个方案，肯定有一个位它的上限为1，但方案中选为0
当一个数有一位上限为1但实际为0时，显然低位是可以随便乱选的，怎么选都小于原上限
f[i][j][k]表示前𝑖个数，当前位𝑥𝑜𝑟和为𝑗，是否有数小于上限的方案数
当a[i] and (1<<j)==1时
f[i][k^1][p]=(f[i][k^1][p]+f[i-1][k][p]*(a[i]+1)%mod)%mod;
f[i][k][1]=(f[i][k][1]+f[i-1][k][p]*(1<<j)%mod)%mod;
当a[i] and (1<<j)==0时
f[i][k][p]=(f[i][k][p]+f[i-1][k][p]*(a[i]+1)%mod)%mod;
最后把𝑓[𝑛][𝑠𝑢𝑚][1]/(2^(𝑝−1)) 累加到答案即可
时间复杂度𝑂(𝑛 * 𝑙𝑜𝑔(𝑎[𝑖]))
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int mod=1000000009;
int n,sum,t,ans,a[N],f[N][2][2];
int kuai(int a,int b)
{
if(b==1)return a;
int x=kuai(a,b/2);
if(b%2==0)return x*x%mod;
return x*x%mod*a%mod;
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int j=29;j>=0;j--)
{
memset(f,0,sizeof(f));
f[0][0][0]=1;
t=0;
for(int i=1;i<=n;i++)
{
if(a[i]&(1<<j))
{
t^=1;
a[i]-=(1<<j);
for(int k=0;k<=1;k++)
for(int p=0;p<=1;p++)
{
f[i][k^1][p]=(f[i][k^1][p]+f[i-1][k][p]*(a[i]+1)%mod)%mod;
f[i][k][1]=(f[i][k][1]+f[i-1][k][p]*(1<<j)%mod)%mod;
}
}
else{
for(int k=0;k<=1;k++)
for(int p=0;p<=1;p++)
f[i][k][p]=(f[i][k][p]+f[i-1][k][p]*(a[i]+1)%mod)%mod;
}
}
ans=(ans+f[n][t][1]*kuai(1<<j,mod-2)%mod)%mod;
}
cout<<(ans+1)%mod;
return 0;
}
D. Aria
稍微简单一点，因为数据不大，直接暴力，十进制拆分后全排列（感到c++的好处）爆搜
#include<bits/stdc++.h>
using namespace std;
int n,ans,a[10];
bool vis[10][100005];
void dfs(int k,int sum)
{
if(k==n+1)
{
ans=max(ans,sum);
return;
}
if(vis[k][sum])return;
vis[k][sum]=true;
sum+=a[k];
int tot=0,b[10],c[10];
while(sum>0)
{
b[++tot]=sum%10;
sum/=10;
}
for(int i=1;i<=tot;i++)c[i]=i;
do
{
int sum=0;
for(int i=1;i<=tot;i++)
sum=sum*10+b[c[i]];
dfs(k+1,sum);
}
while(next_permutation(c+1,c+tot+1));
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
dfs(1,0);
cout<<ans;
return 0;
}
E.Task
我看了很久后，感觉就是个积木大赛，我又想到了我noip2018TG的悲惨（考前没做过原题，考试没想到正解，写了个线段树，写萎调了两个半小时），一交，wa，突然发现这是积木大赛的升级版
我们发现这题它既能横涂，有能竖涂。横涂，我们还是用积木大赛的方法，找到最短的，左右分治。
但还有竖涂，怎么办？
有了，我们发现，一段木板，有且只有3种可能，全竖涂，全横涂，又竖涂又横涂。
全竖涂我们可以直接计算，方案为$r-l+1$
全横涂 和 又竖涂又横涂 这两种情况，我们发现都要横涂，那我们用积木大赛的方法（最优的）横涂，再分治
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[100005];
int solve(int l,int r,int minn)
{
if(l>r)return 0;
if(l==r)return 1;
int mn=1e18;
for(int i=l;i<=r;i++)mn=min(mn,a[i]);
int L=l,R=l,k=l,res=0;
while(L<=r)
{
if(a[L]==mn)
{
res+=solve(k,L-1,mn);
while(L<=r&&a[L]==mn)L++;
k=L;
L--;
}
L++;
}
res+=solve(k,r,mn);
return min(mn-minn+res,r-l+1);
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
cout<<solve(1,n,0);
return 0;
}