9-17 模拟赛

Hisaishi_Kanade · 2023-09-17 20:56:45 · 个人记录

四十多分钟阿克了，然后赢麻了。然后借着打模拟赛的名义开始看番（

A

小明最近在上化学课，他需要使用到 n 种化学物质来进行他的实验。在做实验的时候，他需要将所有化学物质放在桌面上，按次序排成一条直线。 然而每一种化学物质都是危险品，对于第 i 个化学物质，如果有另外一个化学物质距离它的距离小于 a_i，那么就会发生爆炸。 小明想知道如果要安全的完成他的实验，桌子最短可以多短。注意：物品要按原来的次序摆放。

非常 ez，答案显然是 \sum\limits_{i=2}^n \max\{a_i,a_{i-1}\}。

#include <bits/stdc++.h>
#define rep(i, l, r) for(i=l; i<=r; ++i)
#define req(i, r, l) for(i=r; i>=l; --i)
using namespace std;
using ll=long long;
static const int Buf_size=1<<25;
static char _c; static int _x;
static const signed int base_10=10, zero(48), nine(57), flag_signed(45);
static char buf[Buf_size], *p1=buf, *p2=buf;
#define digit() (zero<=_c&&_c<=nine)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,Buf_size,stdin),p1==p2)?EOF:*p1++)
inline int read(){_x=0;_c=getchar();while(!digit()){_c=getchar();}while(digit()){_x=_x*10+(_c^zero);_c=getchar();}return _x;}
const int N=3e5+5, inf=2e9;
const ll illf=1e18;
int a[N];
int qt, n, i, j, k;
int main()
{
    n=read(); rep(i, 1, n) a[i]=read();
    ll res=0; rep(i, 2, n) res+=max(a[i-1], a[i]);
    printf("%lld", res);
}

B

小可可上初中了，初中真好啊，有很多自修课哦。很多同学喜欢在自修课时到教室外面去，说是到老师那问问题。 学校规定，自修课到教室外去的每个同学都必须做好登记，每次进出教室的登记是以一对整数 a 和 b 来描述的，表示某一个同学在时刻 a 时到教室外面，在时刻 b 以后回到教室内。也就是说在时刻 a 至时刻 b 的这段时间中，这个登记的同学一直在教室外面。 校长想知道最多有多少同学在同一时刻都在教室外面，但同学们进进出出教室的记载实在很乱，于是校长请参加信息学兴趣小组的小可可来统计。

简单差分题。

#include <bits/stdc++.h>
#define rep(i, l, r) for(i=l; i<=r; ++i)
#define req(i, r, l) for(i=r; i>=l; --i)
using namespace std;
using ll=long long;
static const int Buf_size=1<<25;
static char _c; static int _x;
static const signed int base_10=10, zero(48), nine(57), flag_signed(45);
static char buf[Buf_size], *p1=buf, *p2=buf;
#define digit() (zero<=_c&&_c<=nine)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,Buf_size,stdin),p1==p2)?EOF:*p1++)
inline int read(){_x=0;_c=getchar();while(!digit()){_c=getchar();}while(digit()){_x=_x*10+(_c^zero);_c=getchar();}return _x;}
const int N=3e5+5, V=1e8, inf=2e9;
const ll illf=1e18;
int a, b, d[V+5];
int qt, n, i, j, k, res;
int main()
{
    n=read();
    rep(i, 1, n)
    {
        a=read(); b=read();
        ++d[a]; --d[b+1];
    }
    rep(i, 1, V) d[i]+=d[i-1];
    rep(i, 1, V) res=max(res, d[i]);
    printf("%d\n", res);
}

C

求 \max\limits_{r-l\ge k} \gcd(a_l, a_r)。是学长 1kri 出的题！