Codeforces Round #321 (Div. 二) 简要记录

Codeforces Round #321 (Div. 2) 简要记录

第一场在线打的cf….

A - Kefa and First Steps

题意:
求一个长度不超过10^5的序列的最长连续不下降子序列。
解析:
md大晚上脑残神志不清看错题+神TM开小数组
这题居然-2？
然后结果这场就差3rating上1700简直….
扫一遍出解
代码:略

B - Kefa and Company

题意:
给出两个键值，求一个子集使得第一键值之差小于d，问该子集最大的第二键值和是多少。
解析:
SB题排一个序即可。
代码:略

C - Kefa and Park

题意:
一棵树，有些节点被染成红色，求有多少个叶节点，使得根节点到该叶节点的路径上没有连续的超过m个被染红的节点。
解析:
SB题直接爆搜，n<=10^5不会爆栈。
代码:略

D - Kefa and Dishes

题意:
n个菜中选m个，每个菜有权值，并且有k个额外加分条件。
即在某种特定的菜之后立即点另一个菜可能会加分。
求最大得分。
解析:
SB题直接上状压就行，设状态 $f[i][j]$ 表示当前选取的所有菜的二进制表示是i，并且最后一次选了j这个菜的最大得分。
预处理 $f[1<<(i-1)][i]=a[i];$ ，以及所有二进制表示的含有1的个数。
总复杂度 $O(2^n*n*n)$
代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 19
#define S 262150
using namespace std;
typedef long long ll;
int n,m,k;
ll a[N];
ll map[N][N];
ll f[S][N];
int has[S];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<(1<<n);i++)
    {
        int tmp=i,cnt=0;
        while(tmp)
        {
            if(tmp&1)cnt++;
            tmp>>=1;
        }
        has[i]=cnt;
    }
    for(int i=1;i<=n;i++)scanf("%I64d",&a[i]),f[1<<(i-1)][i]=a[i];
    for(int i=1;i<=k;i++)
    {
        int x,y;
        ll c;
        scanf("%d%d%I64d",&x,&y,&c);
        map[x][y]=c;
    }
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i&(1<<(j-1)))
            {
                for(int k=1;k<=n;k++)
                {
                    if(!(i&(1<<(k-1))))
                        f[i|(1<<(k-1))][k]=max(f[i|(1<<(k-1))][k],f[i][j]+map[j][k]+a[k]);
                }
            }
        }
    }
    ll ans=0;
    for(int i=0;i<(1<<n);i++)
    {
        if(has[i]==m)
        {
            for(int j=1;j<=n;j++)
                ans=max(ans,f[i][j]);
        }
    }
    printf("%I64d\n",ans);
}

E - Kefa and Watch

题意:
给定一个序列，有两种操作
第一种将该序列的一段全部修改为一个数。
第二种询问该序列的一段是否满足 $s[l,r-d]==s[l+d,r]$
解析:
直到现在我还是在疑惑为什么昨天我没写这sb题。
(嘛，算啦算啦
线段树维护一个hash即可。
修改的话打个lazy标记。
查询的话直接拿两段hash值比较。
据说自然溢出会被卡所以mod 998244353
代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define base 13131
#define mod 998244353
#define N 100100 
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
typedef unsigned long long ull;
int n,m,k;
char s[N];
ull pow[N],sum[N];
ull hash[N<<2];
int col[N<<2];
void init()
{
    pow[0]=sum[0]=1;
    for(int i=1;i<=n;i++)
    {
        pow[i]=pow[i-1]*base%mod;
        sum[i]=(sum[i-1]+pow[i])%mod;
    }
    memset(col,-1,sizeof(col));
}
void pushup(int rt,int l,int r)
{
    int mid=(l+r)>>1;
    hash[rt]=(hash[rt<<1]*pow[r-mid]+hash[rt<<1|1])%mod;
}
void pushdown(int rt,int l,int r)
{
    if(col[rt]!=-1)
    {
        int mid=(l+r)>>1;
        col[rt<<1]=col[rt];
        hash[rt<<1]=col[rt]*sum[mid-l]%mod;
        col[rt<<1|1]=col[rt];
        hash[rt<<1|1]=col[rt]*sum[r-mid-1]%mod;
        col[rt]=-1;
    }
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        hash[rt]=s[l]-'0';
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt,l,r);
}
void update(int v,int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        col[rt]=v;
        hash[rt]=v*sum[r-l]%mod;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(rt,l,r);
    if(L<=mid)update(v,L,R,lson);
    if(R>mid)update(v,L,R,rson);
    pushup(rt,l,r);
}
ull query(int L,int R,int l,int r,int rt)
{
    ull ret=0;
    if(L<=l&&r<=R)
    {
        return hash[rt];
    }
    int mid=(l+r)>>1;
    pushdown(rt,l,r);
    if(L>mid)ret=query(L,R,rson);
    else if(R<=mid)ret=query(L,R,lson);
    else ret=(query(L,mid,lson)*pow[R-mid]%mod+query(mid+1,R,rson))%mod;
    return ret;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s",s+1);
    init();
    build(1,n,1);
    for(int i=1;i<=m+k;i++)
    {
        int opt,l,r,g;
        scanf("%d%d%d%d",&opt,&l,&r,&g);
        if(opt==1)
        {
            update(g,l,r,1,n,1);
        }else
        {
            if(g>r-l+1){puts("NO");continue;}
            if(g==r-l+1){puts("YES");continue;}
            ull tmp1=query(l+g,r,1,n,1);
            ull tmp2=query(l,r-g,1,n,1);
            if(tmp1==tmp2)puts("YES");
            else puts("NO"); 
        }
    }
}