Codeforces Round #590 (Div. 3) 题解

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

A.Equalize Prices Again

过水已略。

B.Social Network

题意

题解

用一个队列维护显示的消息,再开个 map 记录是否在队列中即可。

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

map <int,int> mp;
int n,k,s,l,r,q[400005];

signed main()
{
    n=read(); k=read();
    l=1; r=0;
    for (int i=1;i<=n;i++)
    {
        s=read();
        if (mp[s]) continue;
        if (r>=k) mp[q[l++]]=0;
        q[++r]=s;
        mp[s]=1;
    }
    printf("%d\n",r-l+1);
    for (int i=r;i>=l;i--) printf("%d ",q[i]);
    return 0;
}

C.Pipes

题意

题解

从 $1$ 开始递推,用 $j$ 记录当前在上/下面。如果是弯的管道,那么需要改变状态,如果改变状态后是直的就无解。最后再判断下是不是在下面即可。

#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[2][200005];

signed main()
{
    t=read();
    while (t--)
    {
        n=read();
        scanf("%s",s[0]+1);
        scanf("%s",s[1]+1);
        int j=0; bool flag=0;
        for (int i=1;i<=n;i++)
        {
            if (s[j][i]>'2')
            {
                j^=1;
                if (s[j][i]<='2') { flag=1; break; }
            }
        }
        if (flag || !j) puts("NO");
        else puts("YES");
    }
    return 0;
}

D.Distinct Characters Queries

题意

题解

树状数组裸题,开 $26$ 个直接怼。

#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=100005;
char s[N],d[5];
int n,m,a,b,c,t[26][N];

inline void add(int x,int y,int z) { for (;x<=n;x+=x&-x) t[z][x]+=y; }

inline int query(int x,int z)
{
    int ans=0;
    for (;x;x-=x&-x) ans+=t[z][x];
    return ans;
}

signed main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    for (int i=1;i<=n;i++) add(i,1,s[i]-'a');
    m=read();
    while (m--)
    {
        a=read(); b=read();
        if (a==1)
        {
            scanf("%s",d);
            add(b,-1,s[b]-'a');
            s[b]=d[0];
            add(b,1,s[b]-'a');
        }
        else
        {
            c=read();
            int ans=0;
            for (int i=0;i<26;i++) ans+=(bool)(query(c,i)-query(b-1,i));
            printf("%d\n",ans);
        }
    }
    return 0;
}

E.Special Permutations

题意

题解

考虑每一个数对 $x_k,x_{k+1}$ 对 $i$ 的贡献,令数对中较小值为 $l$ ,较大值为 $r$ :

  1. $i < l$ ,移动不对数对产生影响,贡献还是 $r-l$
  2. $i = l$ ,$l\rightarrow 1$ ,$r > l$ 所以不变,贡献为 $r-1$
  3. $i\in (l,r)$ ,中间会被移走一个数,所以贡献为 $r-l-1$
  4. $i = r$ ,$r\rightarrow 1$ ,$l < r$ 所以向后移动一位,贡献为 $l+1-1=l$
  5. $i > 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;
}

const ll N=200005;
ll n,m,x[N],s[N];

inline void add(ll l,ll r,ll w)
{
    s[l]+=w;
    s[r+1]-=w;
}

signed main()
{
    n=read(); m=read();
    for (ll i=1;i<=m;i++) x[i]=read();
    for (ll i=1;i<m;i++)
    {
        ll l=x[i],r=x[i+1];
        if (l==r) continue;
        if (l>r) swap(l,r);
        add(1,l-1,r-l);
        add(l,l,r-1);
        if (r-l>1) add(l+1,r-1,r-l-1);
        add(r,r,l);
        add(r+1,n,r-l);
    }
    for (ll i=1;i<=n;i++) printf("%lld ",s[i]+=s[i-1]);
    return 0;
}

F.Yet Another Substring Reverse

题意

仔细分析可以发现所谓的翻转子串,就是任意合并两个子串。坑死了

然后可以发现字符数 $\le 20$ ,考虑状压。用 $f(S)$ 表示字符状态为 $S$ 时子串的最长长度,最后枚举两个互斥的状态相加取最大值即是答案。

合法的子串最长为 $20$ ,所以可以扫一遍找到所有合法状态的长度,然后更新所有状态的最大值。

#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=1<<20;
int n,ans,f[N];
char s[1000005];

signed main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    for (int i=1;i<=n;i++) s[i]-='a';
    for (int i=1;i<=n;i++)
    {
        int maxj=min(n,i+19),cur=0;
        for (int j=i;j<=maxj;j++)
        {
            if (cur>>s[j]&1) break;
            cur|=1<<s[j];
            f[cur]=j-i+1; //状态为 cur 的长度
        }
    }
    for (int i=0;i<N;i++) for (int j=0;j<20;j++)
    {
        if (i>>j&1) continue;
        f[i|(1<<j)]=max(f[i|(1<<j)],f[i]); //更新所有状态
    }
    for (int i=0;i<N;i++)
    {
        int j=(N-1)^i; //选互斥的集合
        ans=max(ans,f[i]+f[j]);
    }
    return !printf("%d",ans);
}

新评论

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