第一场在线打的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题直接上状压就行，设状态表示当前选取的所有菜的二进制表示是i，并且最后一次选了j这个菜的最大得分。 预处理，以及所有二进制表示的含有1的个数。 总复杂度 代码:
;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
题意: 给定一个序列，有两种操作 第一种将该序列的一段全部修改为一个数。 第二种询问该序列的一段是否满足 解析: 直到现在我还是在疑惑为什么昨天我没写这sb题。 (嘛，算啦算啦 线段树维护一个hash即可。 修改的话打个lazy标记。 查询的话直接拿两段hash值比较。 据说自然溢出会被卡所以mod 998244353 代码:
;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”);}}}
与其临渊羡鱼，不如退而结网。
