当前位置: 首页 > news >正文

赛前训练6 状压

A

简单树上差分.

B

维护 \(d_{i,j}\) 表示人 \(i\) 在第 \(j\) 位与哪些人有区别.预处理即可.

对于每个人,枚举提问的二进制状态;对于提问的每个二进制位,将它们的 \(d\) 全部拼起来,若能拼成 ((1<<n)-1)^(1<<i),则产生 \(c(j)\) 的贡献,其中 \(c(x)\) 代表 \(x\) 在二进制下 \(1\) 的个数, \(j\) 表示当前提问状态.

实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
//#define int long long
using namespace std;const int N=25;
int n,m;
int a[N][N],diff[N][N];signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>a[i][j];for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<m;k++)if(a[i][k]!=a[j][k])diff[i][k]|=(1<<j);for(int i=0;i<n;i++){int ans=1e9;for(int j=0;j<(1<<m);j++){int cnt=0,person=0;for(int k=0;k<m;k++)if((j>>k)&1)person|=diff[i][k],cnt++;//cout<<person<<'\n';if((person|(1<<i))==(1<<n)-1)ans=min(ans,cnt);}cout<<(ans==1e9?-1:ans)<<' ';}return 0;
}

C

\(n \le 16\),直接状压 dp.

\(dp_i\) 表示字符串选取情况为 \(i\) 时的 trie 树节点最小值.

初始 \(dp_{1<<i}=|s_i|\),答案 \(dp_{(1<<n)-1}\).

转移考虑两棵 trie 树合并成 \(i\),易得 \(dp_i=dp_j+dp_{i \oplus j}-len(i)\).其中 \(len(i)\) 表示 \(i\) 状态下的 LCP.

这东西如何维护?我们发现,一堆字符串重排之后的 LCP,是由它们每种字母的最小出现次数决定的.于是可以维护 \(lcp(i,j)\) 表示 \(i\) 状态下字母 \(j\) 的最小出现次数.要维护 \(lcp(i,j)\),则必然还需要维护 \(cnt(i,j)\) 表示 \(s_i\) 中字母 \(j\) 的出现次数.这样,统计出 \(cnt\) 后,\(lcp\) 只需要枚举状态然后对它们取 \(\min\),而 \(len(i)\) 只需要加上 26 个字母的 \(lcp\) 即可.

实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
using namespace std;const int N=1<<17,M=48,K=1e6+5;
int n;
int len[N],lcp[N][M],cnt[K][M],dp[N];
string s[M];signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;memset(dp,0x3f,sizeof dp);memset(lcp,0x3f,sizeof lcp);for(int i=0;i<n;i++){cin>>s[i];dp[1<<i]=s[i].size();for(int j:s[i])cnt[i][j-'a']++;}for(int i=0;i<(1<<n);i++){for(int j=0;j<n;j++)if((i>>j)&1)for(int k=0;k<26;k++)lcp[i][k]=min(lcp[i][k],cnt[j][k]);for(int j=0;j<26;j++)len[i]+=lcp[i][j];}for(int i=0;i<(1<<n);i++)for(int j=i;j;j=i&(j-1))dp[i]=min(dp[i],dp[j]+dp[i^j]-len[i]);cout<<dp[(1<<n)-1]+1;return 0;
}

D

见往期笔记.

总结

状压:

题型识别:见字符集想到状压见数据范围想到状压

集合观念:二进制状态表示集合枚举子集进行 dp

其他技巧:预处理思想异或提取子区间

以上.

http://www.hskmm.com/?act=detail&tid=25534

相关文章:

  • 排序综合
  • NKOJ全TJ计划——NP11745
  • InfinityFree教程 ——免费搭建属于你的网站
  • 关于调和级数估算前n项的和
  • 10.6 模考 T4(QOJ 1836)
  • 实用指南:【Node.js 深度解析】npm install 遭遇:npm ERR! code CERT_HAS_EXPIRED 错误的终极解决方案
  • 顺序结构
  • Windows漏洞利用技巧:虚拟内存访问陷阱(2025更新)
  • Python编译期优化:隐藏在代码背后的效率魔法
  • 一篇文章带你了解 WGCLOUD运维监控系统的部署与应用
  • 选择结构
  • Python函数默认参数陷阱:可变对象的共享问题深度解析
  • 无需安装的Photoshop:网页版完整使用指南与在线图片编辑技巧
  • 求阶
  • gin 框架 - 教程
  • 赛前训练 5 树形 dp
  • 递推求解逆元
  • 一些做题记录(2025 2-3)
  • 智慧决策的透明化路径:“空白金兰契”架构下的“悟空备案制”研究
  • 笔记:寻找适合自己的简历工具(YAMLResume)
  • 实用指南:Linux 权限管理入门:从基础到实践
  • vue插槽
  • Magnet Axiom 9.6 新增功能概览 - 数字取证与分析
  • Windows 11 24H2 中文版、英文版 (x64、ARM64) 下载 (2025 年 9 月发布)
  • Windows 11 25H2 正式版发布,新增功能简介
  • 无法定时发送
  • 计算能力的重要性:从内存配置到进程迁移的未来展望
  • MongoDB财报超预期,文档数据库技术解析
  • 深入解析:【RabbitMQ】- Channel和Delivery Tag机制
  • 2020CSPS T1 儒略日题解