Codeforces Round #594 (Div. 2) 题解

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

在与机房大佬们的合作下,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;
}

新评论

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