Codeforces Round #594 (Div. 2) 题解

在与机房大佬们的合作下，rk89，rating+=140。

题解代码中省略的程序头：

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define ha 1000000007
#define ui unsigned int
#define pii pair<int,int>
#define pid pair<int,double>

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

A.Integer Points

题意

题解

可以发现 $p$ 和 $q$ 奇偶性相同才有贡献，所以统计一下奇偶的个数，相乘即可。

int t,n,m,a;

signed main()
{
    t=read();
    while (t--)
    {
        n=read();
        int cnt1=0,cnt2=0;
        ll ans=0;
        for (int i=1;i<=n;i++)
        {
            a=read();
            if (a&1) cnt1++;
            else cnt2++;
        }
        int c1=0,c2=0;
        m=read();
        for (int i=1;i<=m;i++)
        {
            a=read();
            if (a&1) c1++;
            else c2++;
        }
        ans=1ll*cnt1*c1+1ll*cnt2*c2;
        printf("%lld\n",ans);
    }
    return 0;
}

B.Grow The Tree

题意

题解

显然要让横向距离最大，所以把棍子从大到小排序，取前 $\lfloor \dfrac{n+1}{2} \rfloor$ 个放在横向，其它的放纵向即可。

int n,a[100005];

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1,[](int x,int y){ return x>y; });
    int hf=(n+1)>>1,sum1=0,sum2=0;
    for (int i=1;i<=hf;i++) sum1+=a[i];
    for (int i=hf+1;i<=n;i++) sum2+=a[i];
    ll ans=1ll*sum1*sum1+1ll*sum2*sum2;
    return !printf("%lld",ans);
}

C.Ivan the Fool and the Probability Theory

题意

题解

先考虑只有一行的情况，令斐波那契数列的第 $m$ 项为 $f_m$ ，那么方案数为 $f_m\times 2$ （黑白可以交换）。

如果第一行中不存在同种颜色相邻的情况，有 $2$ 种方案：这时确定了第一列就确定了整个图，所以答案为 $2f_n$ 。

如果第一行存在同种颜色相邻的情况，有 $f_m\times 2-2$ 种方案：这时整张图就确定了，答案为 $2f_m-2$ 。

总的答案即为 $2f_n+2f_m-2$ 。

int n,m,f[100005];

signed main()
{
    n=read(); m=read();
    if (m>n) swap(n,m);
    f[1]=1,f[2]=2;
    for (int i=3;i<=n;i++) f[i]=(f[i-1]+f[i-2])%ha;
    return !printf("%d",(((f[n]+f[m]-1)%ha+ha)%ha)*2%ha);
}

D1.The World Is Just a Programming Task (Easy Version)

题意

题解

如果字符串中 ( 和 ) 的个数不同，那么答案为 $0$ 。

首先 $O(n^2)$ 枚举哪两个数交换，然后 $O(n)$ 统计答案。

用 $cnt$ 表示 ( 与 ) 个数的差值，如对于序列 ()))(( ，$cnt$ 的序列为 $1,0,-1,-2,-1,0$ 。

可以发现从 $cnt$ 最小的 ( 开始遍历，如上例是位置 $5$，就一定可以组成至少一个完美序列。

在遍历的过程中重新记录 $cnt$ ，如果是右括号且 $cnt=0$ ，那么从这里开始遍历也可以，答案 $+1$ 。

int n,ans,l,r;
char s[505];

inline int work()
{
    int mn=n,mni,cnt=0;
    for (int i=1;i<=n;i++)
    {
        if (s[i]=='(') cnt++;
        else cnt--;
        if (s[i]==')') continue;
        if (cnt<mn) mn=cnt,mni=i; //mni为cnt最小的位置
    }
    cnt=0; int res=0;
    for (int i=1,j=mni;i<=n;i++,j=j==n ? 1 : j+1)
    {
        if (s[j]=='(') cnt++;
        else
        {
            cnt--;
            if (!cnt) res++;
        }
    }
    return res;
}

signed main()
{
    n=read();
    scanf("%s",s+1);
    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        if (s[i]=='(') cnt++;
        else cnt--;
    }
    if (cnt) return !printf("0\n1 1"); //无解
    ans=work(); //可以不交换
    l=r=1;
    for (int i=1;i<=n;i++)
    {
        for (int j=i+1;j<=n;j++)
        {
            swap(s[i],s[j]);
            int res=work();
            if (res>ans) //更新答案
            {
                ans=res;
                l=i,r=j;
            }
            swap(s[i],s[j]);
        }
    }
    return !printf("%d\n%d %d",ans,l,r);
}

E.Queue in the Train

题意

有 $n(\le 10^5)$ 个人坐火车，每个人有个想吃泡面的时间点 $t_i$ ，所有人接水所需的时间都是 $p$ 。

在某一时刻 $T$，如果第 $i$ 个人的 $t_i\le T$ ，且编号 $< i$ 的人都没去接水，那么它就会去排队。特别的，如果有多个人同时想接水，那么编号小的先去。

$\forall i$ ，求 $i$ 接完水的时间。

题解

每一次找到 $t_i\geq T$ 且 $i$ 最小的人，假设为 $x$ ，让它去接水。更新 $T$ 后，在 $[1,x]$ 中不断找 $t_i\geq T$ 且 $i$ 最小的 $x$ 去接水，并更新 $T$ 。

不断重复此过程直到所有人都接了水。找最小可以用线段树维护区间最小值。

const int N=100005;
struct Tree {
    ll left,right,mn;
} tree[N<<2];
ll n,p,t[N],ans[N];

inline void pushup(ll x) { tree[x].mn=min(tree[x<<1].mn,tree[x<<1|1].mn); }

void build(ll x,ll l,ll r)
{
    tree[x].left=l;
    tree[x].right=r;
    tree[x].mn=1e9;
    if (r-l==1) tree[x].mn=t[l];
    else
    {
        ll mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid,r);
        pushup(x);
    }
}

void update(ll x,ll l,ll r,ll delta)
{
    if (l<=tree[x].left && r>=tree[x].right) tree[x].mn=t[l]=delta;
    else
    {
        ll mid=(tree[x].left+tree[x].right)>>1;
        if (l<mid) update(x<<1,l,r,delta);
        if (r>mid) update(x<<1|1,l,r,delta);
        pushup(x);
    }
}

ll query(ll x,ll delta) //找 <=delta 的最小编号
{
    if (tree[x].left+1==tree[x].right) return tree[x].left;
    if (tree[x<<1].mn<=delta) return query(x<<1,delta);
    else return query(x<<1|1,delta);
}

ll query2(ll x,ll r) //在 [1,r] 中找最小值的编号
{
    if (tree[x].left>r) return -1;
    if (tree[x].left+1==tree[x].right) return tree[x].left;
    if (tree[x<<1].mn<=tree[x<<1|1].mn) return query2(x<<1,r);
    ll rt=query2(x<<1|1,r);
    if (rt==-1 || t[rt]>=tree[x<<1].mn) return query2(x<<1,r);
    return rt;
}

signed main()
{
    n=read(); p=read();
    for (ll i=1;i<=n;i++) t[i]=read();
    build(1,1,n+1);
    for (ll i=0,cur=0;i<n;)
    {
        cur=max(cur,tree[1].mn); //让当前时刻来到数列最小值
        ll x=query(1,cur);
        ans[x]=cur+=p; i++; //让 x 去接水
        update(1,x,x+1,1e18); //t[x]=inf ，防止重复选取
        for (;x>0;) //不断重复此过程
        {
            x=query2(1,x);
            if (t[x]>cur) break;
            ans[x]=cur+=p; i++;
            update(1,x,x+1,1e18);
        }
    }
    for (ll i=1;i<=n;i++) printf("%lld ",ans[i]);
    return 0;
}