首页 > 其他分享 >TypeDB Forces 2023 C-D

TypeDB Forces 2023 C-D

时间:2023-01-31 01:22:14浏览次数:58  
标签:TypeDB sz int res ans long fa Forces 2023

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

相关文章

  • 【AAAI2023】Ultra-High-Definition Low-Light Image Enhancement
    【AAAI2023】Ultra-High-DefinitionLow-LightImageEnhancement:ABenchmarkandTransformer-BasedMethod代码:https://github.com/TaoWangzj/LLFormer这个论文首......
  • 2023年寒假英语笔记
    Unit1:FoodforThoughtcuisine:\(n.\)astyleofcooking.bacon:\(n.\)meatfromthebackorsidesofapigthathasbeencured,usuallyservedinthinslic......
  • USACO2023 Bronze 题解
    Problem1.Leaders\(\mathcal{Farmer\John}\)共有\(n\)头奶牛,品种用字符\(\mathsf{G}\)或\(\mathsf{H}\)表示。每一头牛有一个管辖区间\([i,E_i]\)称一头......
  • TypeDB Forces 2023 C. Remove the Bracket
    链接:https://codeforces.com/contest/1787/problem/C题意:给定数组a数n和s,再由\(x_i+y_i=a_i\)且\((x_i-s)\cdot(y_i-s)\geq0\)一个式子令其值最小$F=a_1\cdotx_......
  • TypeDB Forces 2023 E. The Harmonization of XOR
    链接:https://codeforces.com/contest/1787/problem/E题意:给定n,有一个数组a,满足其所有元素均为1~n,给定k,问能否将数组拆为k个,其每一组的xor为x。我们发现任意三个xor为k的......
  • Codeforces Round #847 (Div. 3) E. Vlad and a Pair of Numbers(位运算)
    https://codeforces.com/contest/1790/problem/E题目大意:两个正数a和b(a,b>0)。a⊕b=(a+b)/2,a⊕b==x。找到任何合适的a和b,或者不存在"-1"。inputCopy62510......
  • 前缀后缀01背包(牛客2023多校D清楚姐姐学01背包)
    0x1f题目:https://ac.nowcoder.com/acm/contest/46812/D0x2f题意:定义初始背包的最优解\(V_{max}\)定义n个物品去掉任意一个后,最优解为\(V_{max}'\)每一个物品\(w......
  • Codeforces Round #846 (Div. 2) 解题报告
    前情提要:我是沙币比赛链接A.Hayatoand贪心,不大想讲代码写的很丑voidsolve(){ vector<int>a; intn,x; cin>>n; a.push_back(0); for(inti=1;i<=n;++i)......
  • TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)(持续更新)
    Preface猜结论场,很久没打比赛了然后赛前和ztc吹牛说每次隔一段时间来打CF就会有强运加持结果好家伙BCE全部秒出结论(而且我比赛时都证不来),而且写的A~E都是一发入魂凭借这......
  • 2023.1.28~2023.1.30 日寄
    2023.1.28~2023.1.30猜猜看为什么会积压三天?看看前两天在干什么吧。一言(1.28)我会被音乐打动、被诗歌打动,如果有一天我不再被打动了,我就会死。你知道我的意思吗?被打动......