Codeforces Round #587 (Div. 3) 题解

小号rating比大号高惨案

wzx真是太强辣，除了我还有人膜它，而且还AK了。

A.Prefixes

题意

给出一个长度 $n(n\le 2\times 10^5)$ 的 $a/b$ 串，要求对于所有的 $k\le \dfrac{n}{2}$ ，$[1,2k]$ 中 $a$ 和 $b$ 个数相等。问至少要修改几个数。

题解

水题，判断下每相邻两个数是否相等即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n;
char s[200005];

signed main()
{
    n=read();
    int ans=0;
    scanf("%s",s+1);
    for (int i=2;i<=n;i+=2)
    {
        if (s[i]==s[i-1] && s[i]=='a') s[i]='b',ans++;
        else if (s[i]==s[i-1]) s[i]='a',ans++;
    }
    return !printf("%d\n%s",ans,s+1);
}

B.Shooting

题意

要求射击所有 $n(n\le 1000)$ 个罐子，第 $x$ 次射击第 $i$ 个罐子的代价为 $a_i\times (x-1)+1$ ，问最小代价。

题解

贪心，先射 $a_i$ 大的即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n;
struct node {
    int s,id;
} s[1005];

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i].s=read(),s[i].id=i;
    sort(s+1,s+n+1,[](node x,node y){ return x.s>y.s; });
    int ans=0,cnt=0;
    for (int i=1;i<=n;i++) ans+=s[i].s*(cnt++)+1;
    printf("%d\n",ans);
    for (int i=1;i<=n;i++) printf("%d ",s[i].id);
    return 0;
}

C.White Sheet

题意

给出三个矩形的左下角和右上角坐标，问后两个矩形（黑）能否完全覆盖第一个矩形（白）。

题解

可以发现要么是一个黑色矩形直接覆盖完，要么是上下、左右覆盖。依次判断即可。

#include<bits/stdc++.h>

using namespace std;

int x1,x2,x3,x4,x5,x6,yy1,y2,y3,y4,y5,y6;

signed main()
{
    cin>>x1>>yy1>>x2>>y2;
    cin>>x3>>y3>>x4>>y4;
    cin>>x5>>y5>>x6>>y6;
    if (x3<=x1 && x4>=x2 && y3<=yy1 && y4>=y2) return 0&puts("NO"); //一个覆盖完
    if (x5<=x1 && x6>=x2 && y5<=yy1 && y6>=y2) return 0&puts("NO");
    if (x3<=x1 && x4>=x2 && x5<=x1 && x6>=x2) //上下覆盖
    {
        if (y4>=y2 && y5<=yy1 && y6>=y3) return 0&puts("NO");
        else if (y6>=y2 && y3<=yy1 && y4>=y5) return 0&puts("NO");
    }
    if (y4>=y2 && y3<=yy1 && y5<=yy1 && y6>=y2) //左右覆盖
    {
        if (x4>=x2 && x5<=x1 && x6>=x3) return 0&puts("NO");
        else if (x6>=x2 && x3<=x1 && x4>=x5) return 0&puts("NO");
    }
    return 0&puts("YES");
}

D.Swords

题意

有 $n(2\le n\le 2\times 10^5)$ 种剑，最开始每种都有 $x$ 把。有 $y$ 个偷剑，每个人偷一种剑的 $z$ 把。

已知最后剩的剑每种有 $a_i$，求 $y$ 的最小值。

题解

要求 $y$ 最小，即要求 $z$ 尽可能大。可以发现 $z$ 由 $a_i$ 之间的差值限定，即所有差值都是 $z$ 的整数倍。

所以将 $a_i$ 从小到大排序，$z$ 即是 $\gcd_{i=2}^n (a_i-a_{i-1})$ ，然后就可以得到 $y$ 了。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

ll n,s[200005];

ll gcd(ll x,ll y) { return y ? gcd(y,x%y) : x; }

signed main()
{
    n=read();
    for (ll i=1;i<=n;i++) s[i]=read();
    sort(s+1,s+n+1);
    if (n==2) return !printf("1 %lld",s[2]-s[1]);
    ll z=gcd(s[2]-s[1],s[3]-s[2]);
    for (ll i=3;i<n;i++) z=gcd(z,s[i+1]-s[i]);
    ll ans=0;
    for (ll i=1;i<n;i++) ans+=(s[n]-s[i])/z;
    return !printf("%lld %lld",ans,z);
}

E.Numerical Sequence

题意

小学奥数题

将 $\forall n\in N \ , \ 1..n$ 的数排列，得到一个形如

$$112123123412345...$$

的无限长数列。

有 $q(q\le 500)$ 次询问，每次询问数列的第 $k(E1: k\le 10^9 \ , \ E2: k\le 10^{18})$ 个数是多少。

题解

对于 $E1$ ，可以发现 $n$ 并不会太大（实验可以发现最多 $20000$ 多），所以可以预处理出 $s[i]$ ，表示当 $n\le i$ 时总共有多少个数。

对于每组询问，可以确定 $k$ 所在的组的 $n$ ，然后不断减数字的位数可以得到 $k$ 所在的数，就能得到答案了。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

ll n,a,s[100005];

inline int f(int x) //x 有几位
{
    int j=0;
    for (int i=1;i<=x;i*=10,j++);
    return j;
}

inline int get(int x,int y) //得到 x 的倒数第 y 位
{
    y--;
    for (;y;y--) x/=10;
    return x%10;
}

signed main()
{
    n=read();
    for (int i=1,cnt=0;cnt<=1e9;i++) //预处理 s[i]
    {
        int cur;
        if (i<=9) cur=i;
        else if (i<=99) cur=9+(i-9)*2;
        else if (i<=999) cur=189+(i-99)*3;
        else if (i<=9999) cur=2889+(i-999)*4;
        else cur=38889+(i-9999)*5;
        cnt+=cur;
        s[i]=cnt;
    }
    while (n--)
    {
        a=read();
        int i=1; for (;s[i]<a;i++); //确定 n
        int now=1,j=a-s[i-1]; //j 是还剩的数的个数
        for (;j-f(now)>0;j-=f(now),now++); //不断减数字的位数可以得到所在的数字 now
        printf("%d\n",get(now,f(now)-j+1)); //第 j 位即倒数第 f(now)-j+1 位
    }
    return 0;
}

对于 $E2$ ，可以预处理 位数为 $i$ 的数字的总长度 $s[i]$ ，如 $s[2]=len(10111213...99)=180$ ，然后二分 $n$ 解决。

代码不想写了，$E1$ 都够恶心了。

F.Wi-Fi

题意

有 $n(n\le 2\times 10^5)$ 个房间，要求每个房间都覆盖网络，覆盖 $i$ 号房间的花费为 $i$。部分房间可以安装路由器，可以覆盖 $[i-k,i+k]$ 的所有房间，花费也为 $i$ 。问最小花费。

题解

可以转化为图论解决。将每个房间看成点，直接覆盖即为从 $i\rightarrow (i+1)$ ，边长为 $i$ ；路由器可以从 $(i-k)\rightarrow (i+k+1)$ ，边长也为 $i$ 。因为可以多次覆盖，所以增加回溯边 $(i+1)\rightarrow i$ ，边长为 $0$ 。

为了统计答案，新建个点 $(n+1)$ 。然后从 $1$ 开始跑最短路即可。

#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pii pair<ll,ll>
 
using namespace std;
 
inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const ll N=200005;
struct Edge {
    ll next,to,w;
} edge[N<<2];
bool vis[N];
ll cnt,head[N],n,k,dis[N];
char s[N];

inline void add(ll u,ll v,ll w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline ll dijkstra()
{
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    priority_queue <pii,vector<pii>,greater<pii> > q;
    q.emplace(mp(0,1));
    while (!q.empty())
    {
        ll x=q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x]=1;
        for (ll i=head[x];i;i=edge[i].next)
        {
            ll y=edge[i].to,w=edge[i].w;
            if (dis[x]+w<dis[y])
            {
                dis[y]=dis[x]+w;
                q.emplace(mp(dis[y],y));
            }
        }
    }
    return dis[n+1];
}

signed main()
{
    n=read(); k=read();
    scanf("%s",s+1);
    for (ll i=1;i<=n;i++)
    {
        add(i,i+1,i);
        add(i+1,i,0);
        if (s[i]=='1') add(max(1ll,i-k),min(n+1,i+k+1),i);
    }
    return !printf("%lld",dijkstra());
}