Codeforces Round #585 (Div. 2) 题解

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

A.Yellow Cards

题意

题解

最少的情况就是先给两个队的每个人 $k-1$ 张,然后还剩几张就是答案。

最多的情况就是只给下场的人,同时还应该先给 $k$ 较小的队伍。

#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 a1,a2,k1,k2,n,ans;

signed main()
{
    a1=read(); a2=read(); k1=read(); k2=read(); n=read();
    printf("%d ",max(0,n-a1*(k1-1)-a2*(k2-1)));
    if (k1>k2) swap(a1,a2),swap(k1,k2);
    if (n/k1<=a1) ans=n/k1;
    else
    {
        n-=a1*k1;
        if (n/k2<=a2) ans=a1+n/k2;
        else ans=a1+a2;
    }
    return !printf("%d",ans);
}

B.The Number of Products

题意

题解

可以只计算一种情况的答案 $x$,另一种情况就是 $\dfrac{n\times (n+1)}{2}-x$ 。为了方便考虑正数。

对于序列 $[l,r]$ ,它的积为正数仅当 $l..r$ 有偶数个负数。所以可以按负数把数列分成多段,并对每一段用 $0/1$ 交替编号,只有编号相同的数可以组成首尾。

枚举 $r$ ,维护当前编号 $cur$ 和两种编号的数的个数,当前贡献即为编号为 $cur$ 的数的个数。注意 $r$ 是负数的话应该算到上一段,但答案需要累积另一种编号的。(以负数作为 $l,r$ 都会多一个负数)

注意开 long long

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

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

C.Swap Letters

题意

题解

如果某种字母的个数是奇数,那么显然无解。

可以发现交换不会涉及已经相等的位,所以把它们去掉。

不相等的也就两种情况,$\begin{matrix} a \\ b \end{matrix}$ 和 $\begin{matrix} b \\ a \end{matrix}$ 。每两个相同情况的位可以用 $1$ 步变成相等的,如:

$$\begin{matrix} a \ a \\ b \ b \end{matrix} \rightarrow \begin{matrix} b \ a \\ b \ a \end{matrix}$$

令两种情况的个数为 $n,m$ ,如果均为偶数那么答案为 $\dfrac{n}{2}+\dfrac{m}{2}$ 。

否则肯定均为奇数,那么还需要两步:

$$\begin{matrix} a \ b \\ b \ a \end{matrix} \rightarrow \begin{matrix} a \ a \\ b \ b \end{matrix} \rightarrow \begin{matrix} b \ a \\ b \ a \end{matrix}$$

#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;
char x[N],y[N];
int n,a[N],b[N],acnt,bcnt;

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

D.Ticket Game

题意

题解

设先手为 $A$ ,后手为 $B$ 。并把数列左右两边剩下的空格个数记为 $a,b$ 。

当左右两边都有的时候,$B$ 就可以复制 $A$ 的操作。

剩下的操作中可以控制每回合的和为 $9$ ,如果刚好补完那么后手就能获得胜利,否则先手就可以阻碍后手获胜。

#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();
    scanf("%s",s+1);
    int a=0,b=0,delta=0;
    for (int i=1;i<=n;i++)
    {
        if ((i<<1)<=n)
        {
            if (s[i]!='?') delta+=s[i]-'0';
            else a++;
        }
        else
        {
            if (s[i]!='?') delta-=s[i]-'0';
            else b++;
        }
    }
    int cur=((a-b)>>1)*9+delta;
    if (cur) return 0&puts("Monocarp");
    return 0&puts("Bicarp");
}

E.Marbles

这题跟 洛谷3694 很像,不过这道复杂一些。这是那道题的题解

题意

题解

状压DP,用 $f[i]$ 表示已经排好的颜色状态为 $i$ 时的最小交换次数。可以发现交换次数就是逆序对的个数。

用 $w[i][j]$ 表示有多少对 $(l,r)$ 满足:$S_l=i,S_r=j,l<r$ ,即两种颜色之间的逆序对数。

枚举当前选择的颜色 $j$ ,方程式为:

$$f[i]=\min (f[i \ xor \ 2^{j-1}] + w[j][k]) \ \ (k\in (i \ xor \ 2^{j-1}))$$

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

const int N=1<<20;
ll n,f[N],s[400005],cnt[25],w[25][25];

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) 
    {
        s[i]=read();
        cnt[s[i]]++;
        for (int j=1;j<=20;j++) w[j][s[i]]+=cnt[j];
    }
    memset(f,0x3f,sizeof(f)); f[0]=0;
    for (int i=1;i<N;i++)
    {
        for (int j=0;j<20;j++) if (i>>j&1)
        {
            ll k=i^(1<<j),cur=0;
            for (int l=0;l<20;l++) if (k>>l&1) cur+=w[j+1][l+1];
            f[i]=min(f[i],f[k]+cur);
        }
    }
    return !printf("%lld",f[N-1]);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空