Codeforces Round #592 (Div. 2) 题解

题解 比赛-Codeforces
题目链接 编辑文章

赛前,ljq:不得了,6个人开黑,上紫稳了啊。

10+min过去,大家都A了2道,ljq:这场怕不是要AK。

最后

辣鸡C题,毁我青春。

不过还是得怪做题策略有问题,如果直接跳过C去做DE应该都能A掉,这次就算是用rating买教训了。

A.Pens and Pencils

过水已略

B.Rooms and Staircases

题意

我相信过不了多久洛谷上就会有翻译了

题解

可以发现答案一定是从某一端出发,到达最远的梯子,然后到另一端并返回。我代码还写复杂了点。

#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 t,n;
char s[1005];

signed main()
{
    t=read();
    while (t--)
    {
        n=read();
        scanf("%s",s+1);
        int ans=n,i=n;
        for (;i && s[i]=='0';i--);
        if (!i) { printf("%d\n",ans); continue; } //没梯子
        ans=max(ans,i+max(n-i+1,i)); //从左出发
        for (i=1;i<=n && s[i]=='0';i++);
        ans=max(ans,(n-i+1)+max(n-i+1,i)); //右
        printf("%d\n",ans);
    }
    return 0;
}

C.The Football Season

题意

求解方程

$$w\times x+d\times y=p$$

要求 $x+y\le n$ 。

$1\le n\le 10^{12},0\le p\le 10^{17},1\le d < w\le 10^5$ 。

题解

我:C题题意是啥?

ljq:就是解那个方程的非负整数解,exgcd裸题

然后我就敲了exgcd,因为 $w > d$ ,所以让 $y$ 尽可能小肯定最优。

WA了。后来发现 $p\le 10^{17}$ ,直接 $\times \frac{p}{\gcd (w,d)}$ 显然会爆。

那总不可能写高精吧,去看status发现无数老哥交 Pypy3 ,于是我就开始改python,中途因为 //= 写成 /= 等原因一共WA了7发,最后A的时候就只剩500多分了。另外3个人去改我的变量名分都比我高虽然有两个被skip掉了

n,p,w,d=[int(i) for i in input().split(" ")]

def exgcd(a,b):
    if b==0:
        return (1,0)
    tx,ty=exgcd(b,a%b)
    return (ty,tx-a//b*ty)

def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)

x,y=exgcd(w,d)
g=gcd(w,d)
if p%g!=0:
    print("-1")
    exit()
p//=g
x*=p
y*=p
w//=g
d//=g
if x<0: #把 x 变成非负
    tmp=(-x+d-1)//d
    x+=tmp*d
    y-=tmp*w
if y<0: #把 y 变成非负
    tmp=(-y+w-1)//w;
    y+=tmp*w
    x-=tmp*d
if x<0:
    print("-1")
    exit()
if y>=w: #让 y 尽可能小
    tmp=y//w
    y-=tmp*w;
    x+=tmp*d;
if x+y>n:
    print("-1")
    exit()
print(int(x),int(y),int(n-x-y))

赛后看其他人的写法,发现其实并不需要用 exgcd 来解方程。$y$ 的最小值就是 $\dfrac{p}{d}\mod w$ ,然后 $x=\dfrac{p-d\times y}{w}$ 。

不过还是需要 exgcd 来求个逆元。

#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,p,w,d;

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

ll exgcd(ll l,ll r,ll &x,ll &y)
{
    if (!r)
    {
        x=1; y=0;
        return l;
    }
    ll ans=exgcd(r,l%r,y,x);
    y-=l/r*x;
    return ans;
}

inline ll inv(ll a,ll ha)
{
    ll x=0,y=0;
    exgcd(a,ha,x,y);
    return (x+ha)%ha;
}

signed main()
{
    n=read(); p=read(); w=read(); d=read();
    ll g=gcd(w,d);
    if (p%g) return 0&puts("-1"); //无解
    p/=g; w/=g; d/=g; //除了gcd方程等价
    ll y=p%w*inv(d,w)%w,x=(p-y*d)/w; //直接算出 x,y
    if (x<0 || x+y>n) return 0&puts("-1"); //无解
    return !printf("%lld %lld %lld",x,y,n-x-y);
}

D.Paint the Tree

题意

用 $3$ 种颜色给一棵 $n(\le 10^5)$ 个点的树染色,每个点染不同的颜色有不同的代价。要求由任意 $3$ 个点组成的链上颜色都不相同,求代价的最小值。

题解

可以发现如果不是链就无解。

证明:从树的直径出发,如果染了前两个点,那么直径上后面的颜色都是确定的。如果不是链的话那一定会有分叉,假设形如下图,其中 a--b--c 是直径:

a--b--c
   |
   d

ac 的颜色一定不同,所以 d 不管染什么颜色都不满足题解。

所以就枚举前两个点的颜色,依次遍历链上每一个点即可。

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

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;
}

const int N=100005;
struct Edge {
    int next,to;
} edge[N<<1];
vector <int> v;
ll ans=1e18;
int n,a,b,cnt,head[N],c[4][N],deg[N],colRes[N],colAns[N];

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

signed main()
{
    n=read();
    for (int i=1;i<=3;i++) for (int j=1;j<=n;j++) c[i][j]=read();
    for (int i=1;i<n;i++)
    {
        a=read(); b=read();
        add(a,b); add(b,a);
        deg[a]++; deg[b]++;
    }
    for (int i=1;i<=n;i++) if (deg[i]==1) v.push_back(i);
    if (v.size()!=2) return 0&puts("-1"); //不是链则无解
    int x=v[0],y; //链上的一端
    y=edge[head[x]].to; //第二个点
    for (int j=1;j<=3;j++) //第一个点染的颜色
    {
        for (int k=1;k<=3;k++) //第二个点的颜色
        {
            if (j==k) continue;
            colRes[x]=j; colRes[y]=k;
            ll res=c[j][x]+c[k][y]; //当前答案
            int cur=y,fa=x,last1=j,last2=k; //当前点,父节点,前两个点的颜色
            for (int i=3;i<=n;i++)
            {
                int nxt;
                for (int p=head[cur];p;p=edge[p].next) if ((nxt=edge[p].to)!=fa) break; //nxt 是下一个点
                fa=cur; cur=nxt;
                int col=1; for (;col==last1 || col==last2;col++); //找到符合要求的颜色
                res+=c[col][cur];
                colRes[cur]=col;
                last1=last2; last2=col;
            }
            if (res<ans) //更新答案
            {
                ans=res;
                memcpy(colAns,colRes,sizeof(colRes));
            }
        }
    }
    printf("%lld\n",ans);
    for (int i=1;i<=n;i++) printf("%d ",colAns[i]);
    return 0;
}

E.Minimizing Difference

题意

给出 $n(\le 10^5)$ 个数,可以进行 $k$ 次操作,每次可以把一个数 $+1$ 或 $-1$ 。求操作后 最大数和最小数差值 的最小值。

题解

可以发现最优的操作就是把两端的最值不断往中间靠近。而最值的点可能有多个,假设有 $x$ 个,那么每消耗 $x$ 才能使答案 $-1$ ,所以每次都选择个数较少的一端进行操作。

需要离散化得到各个数值的个数。因为我比较懒所以操作的过程就写的优先队列。

#include<bits/stdc++.h>
#define mp make_pair
#define pii pair<ll,ll>
#define pip pair<ll,pii>
#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;
}

const ll N=100005;
struct node {
    ll s,cnt;
} s[100005];
ll n,m,k,ans=1e9,a[100005];
priority_queue <pip,vector<pip>,greater<pip> > q;

signed main()
{
    n=read(); k=read();
    for (ll i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1);
    for (ll i=1;i<=n;i++) //离散化
    {
        if (a[i]!=a[i-1]) s[++m].s=a[i],s[m].cnt=1;
        else s[m].cnt++;
    }
    if (m==1) return 0&puts("0"); //只有一个值
    q.push(mp(s[1].cnt,mp(1,0))); //左端
    q.push(mp(s[m].cnt,mp(m,1))); //右端
    for (ll l=1,r=m;!q.empty();q.pop())
    {
        ll x=q.top().second.first,y=q.top().first;
        bool p=q.top().second.second; //在哪一端
        ll delta=p ? s[x].s-s[x-1].s : s[x+1].s-s[x].s; //差值
        if (delta*y<=k) //如果能直接靠近到下一个数值
        {
            k-=delta*y;
            if (p) //在右端
            {
                r--;
                q.push(mp(y+s[r].cnt,mp(r,1)));
            }
            else
            {
                l++;
                q.push(mp(y+s[l].cnt,mp(l,0)));
            }
            if (l==r) { ans=0; break; }
        }
        else //否则能靠近多少算多少
        {
            ll maxd=k/y; //最多能靠近的值
            ans=s[r].s-s[l].s-maxd;
            break;
        }
    }
    return !printf("%lld",ans);
}

F.Chips

题意

题解

看题解看到的神仙做法。

有两个结论:

  1. 当前回合没被修改的点,设为 $x$ ,以后都不会被修改
  2. 与 $x$ 相邻的点在下一回合也不会修改

第 $1$ 个结论比较显然。对于第 $2$ 个结论,因为 $x$ 没变,所以它左右两个也不会变。

开个队列,把不需要修改的节点不断入队,并标记它第一次没被修改的操作为 $vis[x]$ 。最后通过 $vis[x]$ 的奇偶性即可判断答案。

#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;
}

const int N=200005;
queue <int> q;
char s[N],f[N];
int n,k,vis[N];

signed main()
{
    f[0]='B'; f[1]='W';
    n=read(); k=read();
    scanf("%s",s+1);
    for (int i=1;i<=n;i++) s[i]=s[i]=='B' ? 0 : 1; //转为 0/1 序列
    for (int i=1;i<=n;i++)
    {
        int l=i==1 ? n : i-1;
        int r=i==n ? 1 : i+1;
        if (s[i]==s[l] || s[i]==s[r]) vis[i]=1,q.push(i); //最初不用修改的点
    }
    while (!q.empty())
    {
        int x=q.front(); q.pop();
        if (vis[x]==k) break;
        int l=x==1 ? n : x-1;
        int r=x==n ? 1 : x+1;
        if (!vis[l]) vis[l]=vis[x]+1,q.push(l);
        if (!vis[r]) vis[r]=vis[x]+1,q.push(r);
    }
    for (int i=1;i<=n;i++)
    {
        if (!vis[i]) printf("%c",f[s[i]^(k&1)]); //一直被修改,以 k 的奇偶性判断 
        else printf("%c",f[s[i]^((vis[i]-1)&1)]); //vis[i]-1 是被修改的次数
    }
    return 0;
}

G.Running in Pairs

逆序开题或成最大赢家。 ——洛谷某大佬(忘了是谁了)

为什么要把这题放G啊!

题意

数列 $a={1,2,3,...,n}$ ,求一个 $1..n$ 的排列 $b$ ,使得 $\sum_{i=1}^n \max (a_i,b_i)$ 最大,且 $\le k$ 。

题解

令 $sum=\dfrac{n\times (n+1)}{2}$ ,显然无解的情况就是 $k < sum$ 。

然后依次遍历每一位 $i$,设没有用过的数的区间为 $[L,R]$ 。如果 $sum+R-i\le k$ ,那么就填 $R$ ,否则填 $L$ 。

这个构造的正确性比较显然。当前数填 $R$ 肯定比之后的数填贡献大,所以合法的话就尽量填 $R$ ;如果没法填 $R$ ,那么填其它的 $> L$ 的数也不比后面填优。

#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 k,sum;
int n,ans[1000005];

signed main()
{
    n=read(); k=read();
    if (k<(sum=1ll*(n+1)*n/2)) return 0&puts("-1");
    for (int i=1,l=1,r=n;i<=n;i++)
    {
        if (r<=i) { ans[i]=r--; continue; } //r<=i ,随便填
        if (sum+r-i<=k) sum+=r-i,ans[i]=r--;
        else ans[i]=l++;
    }
    printf("%lld\n",sum);
    for (int i=1;i<=n;i++) printf("%d ",i);
    puts("");
    for (int i=1;i<=n;i++) printf("%d ",ans[i]);
    return 0;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空
    bwt
    2019-10-14 19:45

    然后机皇 llf 虐场了(

      Llf0703
      2019-10-15 09:29

      要不是括号没删我就删评了