Codeforces Round #608 (Div. 2) 题解

Stella981
• 阅读 596

[TOC]

Codeforces Round #608 (Div. 2) 题解

前言

题目链接:仅仅只是为了方便以题目作为关键字能查找到我的题解而已(逃

Codeforces 1271A

Codeforces 1271B

Codeforces 1271C

Codeforces 1271D

Codeforces 1271E

重要:没有F的题解,想看F题题解的神仙们可以走了

A. Suits

题意

给你$a$条领带,$b$条围巾、$c$件背心、$d$件夹克,有以下两种套装:

  • 一条领带、一件夹克,花费$e$元

  • 一条围巾、一件背心、一件夹克,花费$f$元

求出最多可以卖多少钱(不能单卖)。(奸商)

做法

依题意可得:

假如有$i$种$e$元的套装,那么就是价格是$i \times e + min { d-i, b, c } \times f$元,枚举即可(注意 $i$, $d-i$, $b$, $c$ 中不能出现负数)。

程序

#include<bits/stdc++.h>
using namespace std;

int a,b,c,d,e,f,ans;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>a>>b>>c>>d>>e>>f;
    for(int i=0;i<=min(a,d);i++){//数据范围小,直接暴力枚举
        ans=max(ans,i*e+min((d-i),min(b,c))*f);
    }
    cout<<ans<<endl;

    return 0;
}

B. Blocks

FST的我真的是太菜了

题意

给你一排$n$个方块,每个方块有黑白两种颜色,每次操作可以反转两个相邻的方块的颜色,问能否$3n$次数内反转成一整排都是同一种颜色。

做法

假设序列反转成白色,那么从前到后跑一遍,如果当前方块不是白色就反转它和它后边的方块,最后一个方块如果跑完操作完是白色就OK。黑色同理,假设序列反转成黑色,那么从前到后跑一遍,如果当前方块不是黑色就反转它和它后边的方块,最后一个方块如果跑完操作完是黑色就OK。最后如果都不可以就输出$-1$了。

程序

#include<bits/stdc++.h>
using namespace std;

int n;
char s[205];
vector<int> op;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    cin>>s+1;
    //假设全是白色:
    for(int i=1;i<n;i++){
        if(s[i]=='B'){
            s[i]='W';
            s[i+1]=s[i+1]=='W'?'B':'W';
            op.push_back(i);
        }
    }
    //判断最后一个方块:
    if(s[n]=='W'){
        cout<<op.size()<<endl;
        for(int i=0;i<op.size();i++){
            cout<<op[i]<<' ';
        }
        cout<<endl;
        return 0;
    }
    //假设全是黑色:(此时可以直接再操作同一个序列)
    for(int i=1;i<n;i++){
        if(s[i]=='W'){
            s[i]='B';
            s[i+1]=s[i+1]=='W'?'B':'W';
            op.push_back(i);
        }
    }
    //判断最后一个方块
    if(s[n]=='B'){
        cout<<op.size()<<endl;
        for(int i=0;i<op.size();i++){
            cout<<op[i]<<' ';
        }
        cout<<endl;
        return 0;
    }
    cout<<-1<<endl;

    return 0;
}

C. Shawarma Tent

比B简单

题意

给你一个平面直角坐标系(刚刚数学课学过诶),之后给你一座学校和$n$个学生的坐标(都是整点),问你在一个不同于学校的整点上建一个买Shawarma的帐篷,如果学生从学校到家的某一条神奇路径上经过就会买(当消费者傻子吗),问你最多会有几个学生买,和此时帐篷的坐标(任意一种坐标即可)(奸商)

注:整点指横坐标、纵坐标都是整数的点。神奇路径是只能上下左右移动(平行于横轴或纵轴)的两点间的最短路径(长度就是两点间的曼哈顿距离)(两点间可能有多条)。

做法

显然的,距离学校越近,就会有越多学生从帐篷经过,所以只要枚举学校上下左右的四个点看哪个最优就可以了。

程序

#include<bits/stdc++.h>
using namespace std;

int n,sx,sy;
int x[200005],y[200005];
int l,r,u,d;
//l, r, u, d 分别表示左右上下的帐篷经过的学生个数

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>sx>>sy;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        if(x[i]>sx)r++;
        if(x[i]<sx)l++;
        if(y[i]>sy)u++;
        if(y[i]<sy)d++;
        //对于经过帐篷的学生计数
    }
    if(r>=l&&r>=r&&r>=u&&r>=d){
        cout<<r<<endl;
        cout<<sx+1<<' '<<sy<<endl;
    }else
    if(l>=l&&l>=r&&l>=u&&l>=d){
        cout<<l<<endl;
        cout<<sx-1<<' '<<sy<<endl;
    }else
    if(u>=l&&u>=r&&u>=u&&u>=d){
        cout<<u<<endl;
        cout<<sx<<' '<<sy+1<<endl;
    }else
    if(d>=l&&d>=r&&d>=u&&d>=d){
        cout<<d<<endl;
        cout<<sx<<' '<<sy-1<<endl;
    }
    //这里的u>=u之类只是方便copy&paste罢了

    return 0;
}

D. Portals

题面好长啊,真的不想翻译

题意

你要攻下$n$座城市。一开始你有$k$个士兵。攻下第$i$个城市,你需要$a_i$个士兵(进攻时不损失士兵),攻下后你会抓$b_i$个壮丁扩充你的队伍,攻下后你可以派一个士兵来防守,防守会使得你的分数增加$c_i$,损失一个士兵。防守有两种方式:

  • 你可以防守你所在的第$i$个城市

  • 有$m$个单向的传送门,从$u$到$v$,如果你在$u$,可以派兵防守$v$(必须是直接被传送门连接的城市)

你必须从第$1$座一直攻克到第$n$座城市,如果不能攻克全部城市,你就输了,输出$-1$,如果能赢,求出最大的分数。

做法

贪心的做,计算$req_i = max { a_{i+1} , req_{i+1} - b_{i+1} } | req_n = 0$代表在第$i$个城市攻克并有$b_i$士兵加入后,你完成游戏最少需要的士兵。之后就会有部分士兵空出,第$i$个城市空出士兵个数记为$fr_i$,然后用大根堆来分派士兵到城市就好了。

此时,第$i$个城市的可以守卫它的最后一个城市记为$def_i$,从$1$到$i$的空闲士兵显然都可以守卫它(空闲士兵可以跟着你到下一个城市)。

程序

#include<bits/stdc++.h>
using namespace std;

int n,m,k;
int a[5005],b[5005],c[5005],fr[5005];
vector<int> g[5005];//无用数组
int def[5005],req[5005];
priority_queue<pair<int,int> > pq;
int ans;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
        def[i]=i;
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);//无用语句
        def[v]=max(def[v],u);
    }
    for(int i=n;i>=1;i--){
        req[i]=max(a[i+1],req[i+1]-b[i+1]);cerr<<i<<' '<<req[i]<<endl;
    }
    //计算req[i]
    int cur=k;
    for(int i=1;i<=n;i++){
        if(cur<a[i]){
            cout<<-1<<endl;
            return 0;
        }
        cur+=b[i];
    }
    //↑判断是否能赢↑
    cur=k;
    for(int i=1;i<=n;i++){
        cur+=b[i];
        fr[i]=cur-req[i];cur=req[i];
        pq.push(make_pair(c[i],i));
    }
    //计算fr[i],初始化以重量为第一关键字降序排列的堆
    while(!pq.empty()){
        int val=pq.top().first,x=pq.top().second;
        pq.pop();
        int y=def[x];
        while(!fr[y]&&y>0)y--;
        if(y==0)continue;
        fr[y]--;//贪心地选择最后一个能选的城市的空闲士兵
        ans+=val;
    }
    cout<<ans<<endl;

    return 0;
}

E. Common Number

题意

做到E的人应该都知道吧。。。而且题面很简短我就不写了(逃

做法

定义$k_i$为包含$i$的路径的个数。

首先,奇数和偶数分开考虑,你会发现同一个$n$,同为奇数或偶数时,$y$变大了$k_y$肯定变小,所以具有单调性,可以二分。

我们再来看对于单个的数,如何计算包含它的路径条数:

把路径的计算反过来想,可以得出在路径的反推中,只有偶数可以加一,而所有数都可以乘二。记录有多少个可以通过这种方式得到的数就可以了。但是这样太慢了,所以我们需要一个更快的方法:

通过观察得出,乘二的次数相同时,从最小可达值(只乘过二)到最大可达值(每次乘二后都加一),之间的所有数都是可以达到的,那么我们只要计算最小值和最大值就好了,复杂度--。由于乘二肯定比加一增长得快,所以对于每一种乘以二的次数,把这个区间的长度加到路径条数就可以了。

程序

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n,k;

bool check(ll m){
    ll l=m,r=m,res=0;
    if(!(m&1)){r++;}//当m是偶数时给r增加1
    for(int i=1;;i++){//其实i没有什么用
        res+=min(n,r)-l+1;//添加区间长度到返回值
        //for(int j=l;j<=min(r,n);j++)cerr<<j<<' ';
        l<<=1;
        r=(r<<1)+1;//计算下一个l和r
        if(l>n)break;//当l大于n时就没有计算的必要了,直接退出
        
    }//cerr<<endl;
    return res>=k;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>k;
    //for(int i=1;i<=n;i++)check(i);
    ll l=1,r=(n+1)/2,m,ans;//二分奇数
    while(l<=r){
        m=(l+r)>>1;
        if(check(2*m-1)){
            ans=2*m-1;
            l=m+1;
        }else{
            r=m-1;
        }
    }
    l=1;r=n/2;//二分偶数
    while(l<=r){
        m=(l+r)>>1;
        if(check(2*m)){
            ans=max(ans,2*m);//由于ans已经取了奇数的值,所以这里是max
            l=m+1;
        }else{
            r=m-1;
        }
    }
    cout<<ans<<endl;

    return 0;
}

结束语

点个在看吧!

很抱歉不会F题不能帮到部分人,所以我(逃

点赞
收藏
评论区
推荐文章
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Stella981 Stella981
3年前
Jenkins的错误“error fetching remote repo origin”的问题解决
Jenkins的错误“errorfetchingremoterepoorigin”的问题解决参考文章:(1)Jenkins的错误“errorfetchingremoterepoorigin”的问题解决(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww
Stella981 Stella981
3年前
LeetCode 第225场周赛题解
【GiantPandaCV导语】这是LeetCode的第225场周赛的题解,本期考察的知识点有暴力,前缀和,推导等等。比赛链接https://leetcodecn.com/contest/weeklycontest225/题目一:替换隐藏数字得到的最晚时间!(h
Stella981 Stella981
3年前
IE7、IE8、IE9对min
问题:    IE7、IE8、IE9对minheight不识别,其他无问题解决:   box{width:100px;height:35px;}   htmlbodybox{width:auto;height:auto;width:100px;minheight:35px;} 实例:
Wesley13 Wesley13
3年前
MySQL远程连接丢失问题解决方法(Lost connection to MySQL server)
MySQL远程连接丢失问题解决方法(LostconnectiontoMySQLserver)参考文章:(1)MySQL远程连接丢失问题解决方法(LostconnectiontoMySQLserver)(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww
Wesley13 Wesley13
3年前
Mysql mysql lost connection to server during query 问题解决方法
Mysqlmysqllostconnectiontoserverduringquery问题解决方法参考文章:(1)Mysqlmysqllostconnectiontoserverduringquery问题解决方法(https://www.oschina.net/action/GoToLink?urlhtt
Wesley13 Wesley13
3年前
2019 计蒜之道 复赛
A题:外教Michale变身大熊猫题目链接:https://nanti.jisuanke.com/t/39611题解:!(https://oscimg.oschina.net/oscnet/524b48bae944081e081d77231d2ed30537a.png)!(https://oscimg.oschina.net/os
Stella981 Stella981
3年前
LOJ6500. 「雅礼集训 2018 Day2」操作(哈希+差分)
题目链接https://loj.ac/problem/6500(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Floj.ac%2Fproblem%2F6500)题解区间取反$01$串的经典套路是差分。我们令$b\_ia\_i\\{\\rmxor
Wesley13 Wesley13
3年前
BZOJ3168. [HEOI2013]钙铁锌硒维生素(线性代数+二分图匹配)
题目链接https://www.lydsy.com/JudgeOnline/problem.php?id3168(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.lydsy.com%2FJudgeOnline%2Fproblem.php%3Fid%3D3168)题解
Stella981 Stella981
3年前
Android应用签名详解(INSTALL_PARSE_FAILED_NO_CERTIFICATES问题解决)
Android应用签名详解(INSTALL\_PARSE\_FAILED\_NO\_CERTIFICATES问题解决)参考文章:(1)Android应用签名详解(INSTALL\_PARSE\_FAILED\_NO\_CERTIFICATES问题解决)(https://www.oschina.net/action/GoToLink?url