C. Remove the Bracket
题链
首先这个x y不能为负数
并且s一定的情况下 一定是有一种分法的
肯定我们最喜欢的看到的就是 x=ai y=0 这种有0的分法
我们不妨猜测对于每个ai的分法都是一大一小这种极限的分法
我这里是直接二分的最小可以为多少 当然也有O1的
之后就很简单了 这种小小大大的贪心显然不对
我们用01dp即可
//其实我觉得C>>D 可能是我不太会猜结论
int f(int x,int s){
int l=0,r=x/2;
while(l<r){
int mid=l+r>>1;
if((mid-s)*((x-mid)-s)>=0)r=mid;
else l=mid+1;
}
return l;
}
void solve(){
int n,s;cin>>n>>s;
vector<int>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
int dp[n+1][2],sd,sx;
memset(dp,0x3f3f,sizeof dp);
for(int i=2;i<=n;i++){
int x=f(a[i],s),d=a[i]-x;
if(i==2){
dp[i][0]=a[1]*x;
dp[i][1]=a[1]*d;
}else if(i==n){
dp[n][0]=min(dp[i-1][0]+sd*a[n],dp[i-1][1]+sx*a[n]);
}else{
dp[i][0]=min(dp[i-1][0]+x*sd,dp[i-1][1]+x*sx);
dp[i][1]=min(dp[i-1][0]+d*sd,dp[i-1][1]+d*sx);
}
sd=d,sx=x;
}
cout<<dp[n][0]<<endl;
}
D. Game on Axis
D就很轻松了
我们考虑连边
连完边之后我们会发现会分成一颗与出口我们假设为0为根节点的一颗树
以及一些基环树
我们之后分类讨论
要是1本来就能出去
我们1到0的链上 相当于对该节点u 本来连他父节点的边重新选择 显然我们这个重新选择只用不选基环树还有自己的子树即可
处理完这个链之后剩下的都是一样的 随便选都可以反正不影响了
要是我们1本来就不能出去 那么我们1构成的一个类似环(也有可能1不在环内 挂在一个链上)
这几个点必须去连到我们能出去的任意一个点上就能出去了
当然我们这里每个点本来就可以直接跳出去 写的时候直接加上即可
int n,sz[N],a[N],fa[N];
vector<int>g[N];
void dfs(int u){
sz[u]=1;
for(auto v:g[u]){
dfs(v);
sz[u]+=sz[v];
}
}
void solve(){
cin>>n;
for(int i=0;i<=n;i++){
g[i].clear();
sz[i]=0;
}
for(int i=1;i<=n;i++){
cin>>a[i];
if(i+a[i]<1||i+a[i]>n){
g[0].push_back(i);
fa[i]=0;
}else{
g[i+a[i]].push_back(i);
fa[i]=i+a[i];
}
}
dfs(0);
long long ans=0,h=n-sz[0]+1;
if(sz[1]){
//他出的去
int p=1,res=0;
while(p){
ans+=2ll*n+1ll-(sz[p]+h);
p=fa[p];
res++;
}
ans+=(long long)(n-res)*(2ll*n+1ll);
}else{
vector<bool>v(n+1,0);
//1不一定在环上 可能挂在环上
int p=1,res=0;
while(!v[p]){
v[p]=1;
p=fa[p];
res++;
}
ans+=(long long)(res)*(sz[0]+n);
}
cout<<ans<<endl;
}
标签:TypeDB,sz,int,res,ans,long,fa,Forces,2023
From: https://www.cnblogs.com/ycllz/p/17077652.html