文档章节

CF1132.Educational Codeforces Round 61(简单题解)

o
 osc_eul3o28k
发布于 2019/03/06 20:02
字数 1557
阅读 13
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

A .Regular Bracket Sequence

题意:给定“((” , “()” ,  “)(”,  “))”四种,问是否可以组成合法括号匹配

思路:设四种是ABCD,B可以不用管,而C在A或者D存在时可以不考虑,然后就是A=D。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=200010;
ll A,B,C,D,ans;
int main()
{
    scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
    ans=B;
    if(A||D) ans+=C; ans+=2LL*min(A,D);
    if(ans==A+B+C+D) puts("1");
    else puts("0");
    return 0;
}

 

B .Discounts

题意:给定N个物品,Q次询问,每次询问给定P,表示你可以选P个,最便宜的那个不用付款,问最少付款额。

思路:排序,贪心。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,w,v) for(int i=w;i<=v;i++)
using namespace std;
const int maxn=2000010;
ll a[maxn],sum,ans;
int main()
{
    int N,M,x; scanf("%d",&N);
    rep(i,1,N) scanf("%lld",&a[i]),sum+=a[i];
    sort(a+1,a+N+1);
    scanf("%d",&M);
    rep(i,1,M) {
        scanf("%d",&x);
        printf("%lld ",sum-a[N+1-x]);
    }
    return 0;
}

 

C .Painting the Fence

题意:给定长度为N个点,M条线段,问选择M-2条,最多可以覆盖多少个点(N,M<5000)

思路:首先如果点被覆盖数大于2,不用考虑了,一定被覆盖。所以先求出被1个线段覆盖的,被2覆盖的,然后枚举不选的线段,前缀和更新答案即可。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,w,v) for(int i=w;i<=v;i++)
using namespace std;
const int maxn=5100;
int sum[maxn],num[3][maxn],ans,tot; pair<int,int>s[maxn];
int main()
{
    int N,M;
    scanf("%d%d",&N,&M);
    rep(i,1,M){
        scanf("%d%d",&s[i].first,&s[i].second);
        sum[s[i].first]++; sum[s[i].second+1]--;
    }
    rep(i,1,N) sum[i]+=sum[i-1];
    rep(i,1,N){
        if(sum[i]) tot++;
        num[1][i]+=num[1][i-1];
        num[2][i]+=num[2][i-1];
        if(sum[i]==1) num[1][i]++;
        if(sum[i]==2) num[2][i]++;
    }
    sort(s+1,s+M+1);
    rep(i,1,M)
     rep(j,i+1,M){
        if(s[j].first>s[i].second) ans=max(ans,tot-(num[1][s[i].second]-num[1][s[i].first-1])-(num[1][s[j].second]-num[1][s[j].
first-1])); else if(s[j].second<=s[i].second) ans=max(ans,tot-(num[1][s[j].first-1]-num[1][s[i].first-1])-(num[1][s[i].second]-num[1][s[j].second])-(num[2][s
[j].second]-num[2][s[j].first-1])); else ans=max(ans,tot-(num[1][s[j].first-1]-num[1][s[i].first-1])-(num[1][s[j].second]-num[1][s[i].second])-(num
[2][s[i].second]-num[2][s[j].first-1])); } printf("%d\n",ans); return 0; }

D .Stressful Training

题意:有N台电脑,每台电脑初始电量a[],每单位时间掉电b[],现在给一个充电器,这个充电器同一单位时间只能给一个电脑充电,问每单位时间至少充多少,满足每台电脑都至少坚持K时间。

思路:二分X,二分之后这么写呢,是线性的呢。 求出每个人最晚的一些充电时间,然后总量不大于K,然后就是线性的向前摊平,如果同一时间个数大于1,则false。

这两个限制使得每次二分是线性的。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,w,v) for(int i=w;i<=v;i++)
using namespace std;
const int maxn=200010;
ll a[maxn],b[maxn],ans=-1;int N,K,vis[maxn];
bool check(ll x)
{
    int cnt=0; rep(i,1,K) vis[i]=0;
    rep(i,1,N){
        ll L=a[i];
        while(L-b[i]*(K-1)<0){
            int t=L/b[i]+1;
            if(L/b[i]+1<=K) vis[L/b[i]+1]++;
            cnt++; if(cnt==K) return false;
            L+=x;
        }
    }
    for(int i=K;i>1;i--) {
        if(vis[i]) vis[i-1]+=vis[i]-1;
    }
    if(vis[1]>1) return false;
    return true;
}
int main()
{
    ll L=0,R=1e18,Mid;
    scanf("%d%d",&N,&K);
    rep(i,1,N) scanf("%lld",&a[i]);
    rep(i,1,N) scanf("%lld",&b[i]);
    while(L<=R){
        Mid=(L+R)/2;
        if(check(Mid)) R=Mid-1,ans=Mid;
        else L=Mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}

 

E .Knapsack

题意:给定8种物体的个数a[],重量分别对应1到8,给定W,问选处的不超过W的最大重量。 (W<1e18,a<1e16)

思路:二进制拆分物体,然后暴力背包,可能会空间爆炸,用ans减去没用的一些空间就够了。

这样的话,物体要从大到小排序,这样才能保证map的空间,以及减枝效果。

(这是比较暴力的做法了,有更优美的解法

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,bool>mp,tmp;
map<ll,bool>::iterator it;
const int maxn=20000;
ll ans,W,a[maxn],v[maxn],sum[maxn]; int tot,cnt;
int main()
{
    scanf("%lld",&W);
    for(int i=1;i<=8;i++){
        scanf("%lld",&a[i]);
        if(!a[i]) continue; cnt++; ll t=1;
        ans=max(ans,min(W/i,a[i])*i);
        while(1){
            tot++; v[tot]=min(t,a[i])*i;
            a[i]-=min(t,a[i]); t=t*2;
            if(!a[i]) break;
        }
    }
    if(cnt==1){
        printf("%lld\n",ans); return 0;
    }
    sort(v+1,v+tot+1); reverse(v+1,v+tot+1);
    for(int i=tot;i>=1;i--) sum[i]=sum[i+1]+v[i];
    mp[0]=true;
    for(int i=1;i<=tot;i++){
        tmp.clear();
        for(it=mp.begin();it!=mp.end();it++){
            ll x=it->first;
            tmp[x]=true;
            if(x+v[i]<=W) tmp[x+v[i]]=true;
        }
        mp.clear();
        for(it=tmp.begin();it!=tmp.end();it++){
           if(it->first+sum[i+1]<ans) continue;
           mp[it->first]=true;
           ans=max(it->first,ans);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

 

F .Clear the String

题意:给定长度为N的字符串,每次可以删去一段连续的相同字符,求最小删去次数。(N<500)

思路:区间DP,反过来就是“刷墙”这种题:每次可以刷一段,问最少刷的次数。 如果col[L]=col[R],我们可以先刷[L,R],然后去刷[L+1,R-1];如果中间有相同的,还可以分子区间。所以是个需要枚举中间点的O(N^3)区间DP。(比赛的时候想N^2做,WA了。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,w,v) for(int i=w;i<=v;i++)
using namespace std;
const int maxn=510;
int dp[maxn][maxn]; char a[maxn];
int main()
{
    int N,tot=1; scanf("%d%s",&N,a+1);
    rep(i,2,N){
        if(a[i]!=a[i-1]) a[++tot]=a[i];
    }
    N=tot;
    memset(dp,0x3f,sizeof(dp));
    rep(len,1,N){
        rep(L,1,N-len+1){
            int R=L+len-1;
            if(len==1) dp[L][R]=1;
            else if(len==2) dp[L][R]=(a[L]==a[R]?1:2);
            else {
                dp[L][R]=len;
                if(a[L]==a[R]) dp[L][R]=min(dp[L+1][R],dp[L][R-1]);
                else{ dp[L][R]=min(dp[L+1][R],dp[L][R-1])+1;
                   rep(k,L,R) dp[L][R]=min(dp[L][R],dp[L][k]+dp[k][R]-1);
                }
            }
        }
    }
    printf("%d\n",dp[1][N]);
    return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
N简单CMS

N简单CMS能够让网站开发者更快速、灵活、简单的开发网站。 N简单CMS有以下特点: 更简单和自由的模板标签调用 专注于人性化的管理和操作 基于完全php5框架Kohana2.3.4开发 资源调用和消耗更低...

匿名
2013/02/26
3.1K
0
简单邮件联系页面带飞信通知模块

一个简单的“发邮件给我”的页面,支持HTML邮件编辑,支持附件发送,支持飞信短信提醒。里面有很多可以定制的地方,包括邮件的发送方式、前端页面的设计等等。 如果你也跟我一样喜欢通过邮件...

leehorsley
2012/10/22
1.6K
0
简单的广告栏

实现简单的广告栏效果。即: 1、下载图片,点击图片自动打开对应链接。 2、每5秒滚动播放图片。 3、自定义UIPageControl样式,用 icon 自定义 UIPageControl 的点。 [Code4App.com]...

匿名
2012/12/05
2.3K
0
简单CMS

主要修改: 1)增加文章模块,文章列表显示在首页和单品页中; 2)增加店铺模块,店铺显示在首页和瀑布流页中; 3)增加网站地图模块; 4)增加sitemap模块; 5)增加第三方淘宝登录功能; ...

简单CMS
2012/12/25
4.2K
0
OSSIM中主动与被动探测工具(pads+pf0+arpwatch)组合应用

OSSIM中主动与被动探测工具(pads+pf0+arpwatch)组合应用 OSSIM不仅降低了大家涉足IDS的门槛,而且为各种复杂的应用提供了一种快捷的平台,其中核心技术之一就是基于插件的事件提取,系统内...

OSSIM
2015/10/25
613
0

没有更多内容

加载失败,请刷新页面

加载更多

连续数据包采集:数据包——硬盘

nBox Recorder是一个网络流量磁盘记录器应用程序。使用nBox Recorder,您可以从实时网络接口以千兆位速率捕获全尺寸的网络数据包,并将其写入文件中。它的设计和开发主要是因为大多数网络安全...

osc_8ki1usvn
21分钟前
0
0
Docker中级篇|深入探究Docker

简介: 深入探究Docker Docker镜像理解 Docker镜像是什么 镜像是一种轻量级、可执行的独立软件包,用来打包软件运行环境和基于运行环境开发的软件,它包含运行某个软件所需的所有内容,包括代...

阿里云技术博客
22分钟前
0
0
一口气说出 9种 分布式ID生成方式,面试官有点懵了

一、为什么要用分布式ID? 在说分布式ID的具体实现之前,我们来简单分析一下为什么用分布式ID?分布式ID应该满足哪些特征? 1、什么是分布式ID? 拿MySQL数据库举个栗子: 在我们业务数据量不...

漫话编程
今天
0
0
tiktok如何运营

TK的模式 TK 是字节跳动(Byte Dance)公司原创的短视频社交 App,一家成立 8 年、以数据驱动的技术公司。 我们平时用的今日头条、西瓜视频、悟空问答、抖音等等都是字节跳动的产品。 字节跳...

osc_xs2d5ls9
23分钟前
22
0
《OpenCv视觉之眼》Python图像处理三 :Opencv图像属性、ROI区域获取及通道处理

本专栏主要介绍如果通过OpenCv-Python进行图像处理,通过原理理解OpenCv-Python的函数处理原型,在具体情况中,针对不同的图像进行不同等级的、不同方法的处理,以达到对图像进行去噪、锐化等...

osc_tjhvpz8x
24分钟前
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部