• 周六. 8月 20th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

Educational Codeforces Round 112 (Rated for Div. 2) ABCDE 解题思路

admin

11月 28, 2021

Educational Codeforces Round 112 (Rated for Div. 2)

只做了ABCDE,但被AE卡了我是没想到的,CE分别一发RE也傻了

comp_rank

A – PizzaForces

题意

做小尺寸的pizza可以切成(6)片,要花(15)​分钟

做中尺寸的pizza可以切成(8)​片,要花(20)​分钟

做大尺寸的pizza可以切成(10)​​片,要花(25)​​分钟

现在Petya家来了(n)位客人,他想让每个客人都至少能吃到一块pizza

问做出符合需求数量的pizza的最少时间

思路

  • 想法

发现如果人数(le 6)人,一定要(15)分钟

而当人数(gt 6)人,发现每增加(2)人就会出现新方案,需要加(5)分钟

所以答案为(max(15,lceilfrac{n}{2}ceil imes 5))

B -Two Tables

题意

现在已知一个(W imes H)的空间

有一个左下角为((x_1,y_1))​,右上角为((x_2,y_2))​的桌子已经放在了这个空间内

现在想再放一个(w imes h)尺寸的桌子

问原桌子至少要移动多少的距离,才能在空余的空间中放下新桌子

始终无法放置则输出(-1)

思路

  • 想法

容易得到新桌子只可能放在左下、右下、左上、右上四个角落,分别判断并取最小距离即可

(x_2-x_1+wgt W)(y_2-y_1+hgt H)​时不存在任何方案

代码

//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}

double W,H;
double xa,ya,xb,yb;
double w,h;

double ck1()
{
    double dx=max(0.0,w-xa);
    double dy=max(0.0,h-ya);
    if(w+xb-xa>W)
        dx=1e18;
    if(h+yb-ya>H)
        dy=1e18;
    return min(dx,dy);
}

double ck2()
{
    double dx=max(0.0,xb-(W-w));
    double dy=max(0.0,h-ya);
    if(w+xb-xa>W)
        dx=1e18;
    if(h+yb-ya>H)
        dy=1e18;
    return min(dx,dy);
}

double ck3()
{
    double dx=max(0.0,xb-(W-w));
    double dy=max(0.0,yb-(H-h));
    if(w+xb-xa>W)
        dx=1e18;
    if(h+yb-ya>H)
        dy=1e18;
    return min(dx,dy);
}

double ck4()
{
    double dx=max(0.0,w-xa);
    double dy=max(0.0,yb-(H-h));
    if(w+xb-xa>W)
        dx=1e18;
    if(h+yb-ya>H)
        dy=1e18;
    return min(dx,dy);
}

void solve()
{
    cin>>W>>H;
    cin>>xa>>ya>>xb>>yb;
    cin>>w>>h;
    double ans=1e18;
    
    ans=min(ans,ck1()); //左下
    ans=min(ans,ck2()); //右下
    ans=min(ans,ck3()); //右上
    ans=min(ans,ck4()); //左上
    
    if(ans==1e18)
        cout<<"-1
";
    else
        cout<<ans<<'
';
}
int main()
{
    closeSync;
    cout<<fixed<<setprecision(9);
    multiCase
    {
        solve();
    }
    return 0;
}

C – Coin Rows

Alice和Bob在一张(2 imes m)的网格里做游戏,每个格子都有一个数字

他们初始时站在((1,1))​​,每个人每步只能向下走或向右走,​并且走过的格子数字清零,直到走到终点((2,m))

Alice先走,走完后Bob走,游戏的得分即为Bob走过的格子的数字和

Alice想最小化得分,Bob想最大化得分,他们两个都按照最优方案进行游戏,问游戏的最终得分

思路

  • 博弈
  • 前后缀和
  • 枚举

每个人只有一次向下走的机会,所以我们假设Alice在位置((1,i))向下走到((2,i))

那么整张网格中有数字的连续快就只有((1,i+1))((1,m)),和((2,1))((2,i-1))两部分

由于Bob想最大化得分,并且这两部分他只能够挑一部分走,所以他肯定会挑和最大的部分

所以对第一行做一次后缀和,第二行做一次前缀和,枚举Alice向下走的列数(i),对于剩余的两块取大,再与答案取小即可

代码

//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}

int a[3][100050];
ll sum[3][100050];

void solve()
{
    int m;
    cin>>m;
    rep(i,1,2)
        rep(j,1,m)
            cin>>a[i][j];
    
    sum[1][m+1]=0;
    per(j,m,1)
        sum[1][j]=sum[1][j+1]+a[1][j];
    
    sum[2][0]=0;
    rep(j,1,m)
        sum[2][j]=sum[2][j-1]+a[2][j];
    
    ll ans=sum[2][m]+a[1][1];
    
    rep(j,1,m)
        ans=min(ans,max(sum[2][j-1],sum[1][j+1]));
    
    cout<<ans<<'
';
}
int main()
{
    closeSync;
    multiCase
    {
        solve();
    }
    return 0;
}

D – Say No to Palindromes

题意

给定一个只有(abc)​​三种字符的字符串

定义一个字符串是beautiful的,当且仅当其不存在长度(ge2)的回文子串

每次给定一个询问区间([l,r])​​​,要求将下标位于该区间内的子串通过最小操作数变成beautiful的,输出最小操作数

每一次操作可以选择任意一个字符,将其变为(abc)当中的任意一个其他字符

思路

  • 前缀和
  • 枚举

如果子串长度为(1),不需要操作

如果子串长度为(2),只有在两字符相同时需要操作(1)

否则,要想让其变为不存在长度(ge2)的回文子串的字符串,只有可能是基于(abc)三个字符的某种排列的循环,即({abc,acb,bac,bca,cab,cba})六种串的循环

所以以三个位置为一个单位,借助(cnt[i][j][k])​记录原字符串前(i)​个位置中,字符(j)​((a=0,b=1,c=2)​)在单位中的位置为(k)​时((kin{0,1,2})​​)出现的次数,前缀和处理一边即可

其后对于每一遍询问,枚举一遍(abc)​的六种排列,存储于(t[0],t[1],t[2])​中

假设当前询问的长度为(len=r-l+1)

那么对于第(1)个字符,出现的次数即(lfloorfrac{len+2}{3}floor)

对于第(2)​个字符,出现的次数即(lfloorfrac{len+1}{3}floor)

对于第(3)​​个字符,出现的次数即(lfloorfrac{len}{3}floor)

分别将应出现的次数减去​​原本在对应位置出现的次数,再相加,就是将([l,r])的子串修改为(t[0]t[1][t[2])循环的字符串的最小操作数

对于所有情况,取小即可

代码

//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}

int n,m;
char s[200050];
int cnt[200050][3][3];
int t[3];

void solve()
{
    cin>>n>>m;
    cin>>s+1;
    
    rep(i,1,n)
    {
        repp(j,0,3)
            repp(k,0,3)
                cnt[i][j][k]=cnt[i-1][j][k];
        cnt[i][s[i]-'a'][i%3]++;
    }
    
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        if(l==r)
            cout<<0<<'
';
        else if(l+1==r)
        {
            if(s[l]==s[r])
                cout<<1<<'
';
            else
                cout<<0<<'
';
        }
        else
        {
            t[0]=0,t[1]=1,t[2]=2;
            
            int ans=INF;
            int len=r-l+1;
            int d0=(len+2)/3,d1=(len+1)/3,d2=len/3;
            
            do
            {
                int tmp=0;
                tmp+=d0-(cnt[r][t[0]][(l)%3]-cnt[l-1][t[0]][(l)%3]);
                tmp+=d1-(cnt[r][t[1]][(l+1)%3]-cnt[l-1][t[1]][(l+1)%3]);
                tmp+=d2-(cnt[r][t[2]][(l+2)%3]-cnt[l-1][t[2]][(l+2)%3]);
                ans=min(ans,tmp);
            }while(next_permutation(t,t+3));
            
            cout<<ans<<'
';
        }
    }
}
int main()
{
    closeSync;
    //multiCase
    {
        solve();
    }
    return 0;
}

E – Boring Segments

题意

(n)​条线段,第(i)条线段覆盖([l_i,r_i])​​​当中的点,权值为(w_i)

只有相交的线段才能够在互相覆盖的位置当中进行移动,即如果从点(1)​出发,选择了([1,2],[3,4])​两条线段,则不能够到达点(4)​;如果选择了([1,2],[2,4])​​​两条线段,则可以到达点(4)

定义一个线段的集合是good的,当且仅当选择了这个集合中的所有线段后,可以从位置(1)开始移动到位置(m)

定义一个good的线段集合的花费即所有线段权值的最大值与最小值之差

问所有good的线段集合中最小的花费

题目保证至少存在一个good的线段集合

思路

  • 线段树(区间修改、区间查询最小值)
  • 双指针

首先,把每个单位区间([x,x+1])​抽象合并成点(x)​​​,以防止后续出现重复加点,所以将每个线段的右端点(-1)​,同时(m)​也应当(-1)

其后,使用线段树来维护([1,m])​内每个点(也就是原来的单位区间)被覆盖的线段数量

所以假设我们选取了一些线段,将每条线段在线段树中对应的区间([l,r])更新,使每个位置(+1)​;然后假如区间查询([1,m])得到的最小值为(0),则说明存在某个或某些单位区间没有被覆盖到,所以选择这些线段无法实现从点(1)移动至点(m)

有了维护的工具与实现方法,现在开始寻找答案

由于花费是最值之差,故考虑将所有线段按照权值从小到大进行排序

借助双指针维护一个区间([l,r])​,一开始时从权值最小的线段开始一直往线段树中添加线段,由于题目保证至少存在一个good的线段集合,所以一定会在添加完某条线段后使得区间查询([1,m])​​得到的最小值不为(0)​​

此时使用到的线段在按权值排序后的区间为([1,r])​,明显现在已经是一个good的线段集合

但我们要使得花费最小,即最值之差尽可能小,故再考虑从头开始删除线段(每个位置(-1)),直到区间查询([1,m])得到的最小值再次变为(0)

假设最后一次删除的线段编号为(l),则表示([l,r])​​​​也是一个good的线段集合,并且此时(w_l)是最小权值,(w_r)是最大权值,花费为(w_r-w_l)

此后,利用双指针持续执行上述步骤,持续向右移动(r)使得区间查询不为(0),再向右移动(l)​使得区间查询重新为(0),再更新答案(w_r-w_l),直到(r)到达最大权值时退出并输出最小答案即可

代码

//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}

const int MAXN=1e6+50;

struct node
{
    int l,r;
    ll lazy,minn;
}tree[MAXN*4];

void push_up(int id)
{
    tree[id].minn=min(tree[id<<1].minn,tree[id<<1|1].minn);
}

void push_down(int id)
{
    if(tree[id].lazy)
    {
        int m=tree[id].r-tree[id].l+1;
        tree[id<<1].lazy+=tree[id].lazy;
        tree[id<<1|1].lazy+=tree[id].lazy;
        tree[id<<1].minn+=tree[id].lazy;
        tree[id<<1|1].minn+=tree[id].lazy;
        tree[id].lazy=0;
    }
}

void buildTree(int l,int r,int id=1)
{
    tree[id].l=l;
    tree[id].r=r;
    tree[id].lazy=0;
    if(l==r)
    {
        tree[id].minn=0;
        return;
    }
    ll mid=(l+r)>>1;
    buildTree(l,mid,id<<1);
    buildTree(mid+1,r,id<<1|1);
    push_up(id);
}

void update(int L,int R,ll val,int id=1)
{
    if(L<=tree[id].l&&R>=tree[id].r)
    {
        tree[id].minn+=val;
        tree[id].lazy+=val;
        return;
    }
    push_down(id);
    int mid=(tree[id].r+tree[id].l)>>1;
    if(L<=mid)
        update(L,R,val,id<<1);
    if(R>mid)
        update(L,R,val,id<<1|1);
    push_up(id);
}

ll query_min(int L,int R,int id=1)
{
    if(L<=tree[id].l&&R>=tree[id].r)
        return tree[id].minn;
    push_down(id);
    int mid=(tree[id].r+tree[id].l)>>1;
    ll ans=0x3f3f3f3f3f3f3f3f;
    if(L<=mid)
        ans=min(ans,query_min(L,R,id<<1));
    if(R>mid)
        ans=min(ans,query_min(L,R,id<<1|1)) ;
    return ans;
}

struct abcd
{
    int l,r,w;
    bool operator < (const abcd& a) const
    {
        return w<a.w;
    }
}ar[300050];

void solve()
{
    int n,m;
    cin>>n>>m;
    m--;
    
    buildTree(1,m);
    rep(i,1,n)
    {
        cin>>ar[i].l>>ar[i].r>>ar[i].w;
        ar[i].r--;
    }
    sort(ar+1,ar+n+1); //按权值排序
    
    int l=1,r=1;
    update(ar[1].l,ar[1].r,1); //先将第一条线段加入
    while(r<n&&query_min(1,m)==0) //持续右移r并加线段,直到每个位置都至少被覆盖一次
    {
        r++;
        update(ar[r].l,ar[r].r,1);
    }
    while(query_min(1,m)>0) //再持续左移l并删线段,直到出现一个位置没被覆盖
    {
        update(ar[l].l,ar[l].r,-1);
        l++;
    }
    
    int ans=ar[r].w-ar[l-1].w; //最后一个删除的线段编号为l-1,则答案为Wr-W(l-1)
    
    while(r<n) //持续进行上述操作
    {
        while(query_min(1,m)==0&&r<n)
        {
            r++;
            update(ar[r].l,ar[r].r,1);
        }
        if(query_min(1,m)==0)
            break;
        while(query_min(1,m)>0)
        {
            update(ar[l].l,ar[l].r,-1);
            l++;
        }
        ans=min(ans,ar[r].w-ar[l-1].w);
    }
    cout<<ans<<'
';
}
int main()
{
    closeSync;
    //multiCase
    {
        solve();
    }
    return 0;
}

https://blog.csdn.net/qq_36394234/article/details/119260385

发表回复

您的电子邮箱地址不会被公开。