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

2023牛客暑期多校训练营7(C/I/M)

目录

C.Beautiful Sequence

I.We Love Strings 

M.Writing Books


C.Beautiful Sequence

思路:显然若得到了a[1],则整个序列a我们都知道了。所以我们要求出第k大的a[1],这个可以利用序列a为不递减序列的性质来得出。

首先,由题意可得:

a[2]=a[1]^b[1]

a[3]=a[2]^b[2]=(a[1]^b[1])^b[2]

a[4]=a[3]^b[3]=((a[1]^b[1])^b[2])^b[3]

......

得出a[i]=a[1]^(序列b的前缀i异或和)

我们把序列b的前缀i异或和定义为f[i],因为序列a不递减,所以:

a[i]<=a[i+1]

=>   a[1]^f[i-1] <= a[1]^f[i]

首先我们先初始化a[1]二进制位为-1,这代表a[1]的这个位可以是0,也可以是1。然后我们再根据a[1]^f[i-1] <= a[1]^f[i] 这个公式来得出a[1]的哪些位它是确定的,不能是-1。

我们需要从高位往低位贪心,因为如果a[1]^f[i-1]的一个高位如果是1,而a[1]^f[i]的这个位是0,那么低位再怎么变,a[1]^f[i-1]也必然小于a[1]^f[i]。比如两个二进制数1????和0????,就算左边的低位全是1,右边的高位全是0,也就是变成10000和01111,左边依然大于右边。

然后我们从高位到低位怎么贪心呢?找f[i]的f[i-1]的从高位到低位,第一个不同的位即可,我们设这个是第k位。此时a[1]的第k位必须和f[i]第k位的值相同,这样子就能让f[i]^a[1]的第k位是0,f[i+1]^a[1]第k位是1,保证了前者小于后者。在此之前a[i]的第k位必须等于-1或者等于f[i]的第k位,否则输出-1。

此时我们得到了n个-1的值,我们我们最多能表示第2的n次方大的值,此时我们只需将(k-1)拆分成二进制依次填入-1的位置即可。具体实现见代码。

代码:

void solve() {a[1]=0;mem(now,-1);int n,k;cin>>n>>k;for(int i=1; i<n; i++) {cin>>b[i];f[i]=(f[i-1]^b[i]);}for(int i=0; i<n-1; i++) {for(int j=29; j>=0; j--) {if((f[i]>>j&1ll)!=(f[i+1]>>j&1ll)) {//找到高位第一个不相等的二进制位if(now[j]==-1)now[j]=(f[i]>>j&1ll);else if(now[j]==(f[i+1]>>j&1ll)) {//如果该位已经确定,并且与想要填的数相反,则输出-1cout<<-1<<endl;return;}break;//高位比上一个大了之后,就不用再管低位了}}}k--;//去掉初始不变的情况,方便替换-1int maxx=0;for(int i=0; i<30; i++) {if(now[i]==-1)maxx=maxx*2+1;}if(maxx<k) {cout<<-1<<endl;return;}vector<int>v;while(k) {//将k转换为二进制填入v.push_back({k%2});k/=2;}reverse(v.begin(),v.end());for(int i=0; i<30; i++) {if(!v.size())break;//填完了就退出if(now[i]==-1) {//依次填入now[i]=v.back(),v.pop_back();}}for(int i=0; i<30; i++)now[i]=max(now[i],0ll);//把没填的-1变成0for(int i=29; i>=0; i--) a[1]=a[1]*2+now[i];;//得出a[1]的值cout<<a[1]<<" ";for(int i=2; i<=n; i++)cout<<(b[i-1]^a[i-1])<<" ",a[i]=(b[i-1]^a[i-1]);//根据a[1]得出整个序列acout<<endl;
}

I.We Love Strings 

思路:因为字符串长度不相同的字符串,两两之间肯定不能匹配,所以我们根据字符串长度大小来求解。在lenth<=20时我们暴力枚举字符串所有情况进行求解,而在lenth>20的时候我们暴力容斥来求解。

那么为什么这个临界值为20呢?

我们设临界值为N,暴力枚举所有情况的复杂度主要由字符串长度决定,复杂度为:

而容斥的复杂度主要由容斥的集合大小决定,而这个集合的最大大小又由n的最大值和N共同决定,它的复杂度为:

总的复杂度为他们两个相加。

此时N取太大或者取太小,都会使得一方的复杂度过大,此时取400的根号,也就是N=20,是最好的。

具体实现见代码。

代码:

int pp(vector<int>v,string s,int n) {for(int i=0; i<n; i++) {if(s[i]!='?'&&v[i]!=s[i]-'0')return 0;//如果两个串确定有位置不同了,则匹配失败 }return 1;//匹配成功 
}
int f1(int n) {int sum=0;for(int i=0; i<(1<<n); i++) {//枚举这个长度01串的所有可能。 vector<int>s;for(int j=0; j<n; j++) {s.push_back((i>>j&1ll));} //将枚举的串存入vector for(int i=0; i<v[n].size(); i++) {if(pp(s,v[n][i],n)) {//如果有一个串能和这个枚举的串匹配,答案+1 sum++;break;}}}return sum;
}
int f2(int n) {int m=v[n].size(),ans=0;//注意i要从1开始,若从0开始则会使答案增加 for(int i=1; i<(1ll<<m); i++) {//枚举集合内的串int sum=1;for(int j=0; j<n; j++) {//枚举串的每个位 int cnt0=0,cnt1=0;for(int k=0; k<m; k++) {//表示这是集合内第几个串 if((i>>k&1ll)) {if(v[n][k][j]=='0')cnt0++;if(v[n][k][j]=='1')cnt1++;}}if(cnt0&&cnt1) {//若该位上确定的数不一致,则不能进行容斥 sum=0;break;}if(!cnt0&&!cnt1)sum=sum*2%mod;//该位上全是?,贡献*2 }int now=__builtin_popcount(i); if(now%2)ans=(ans+sum)%mod; //进行容斥 else ans=(ans-sum+mod)%mod;}return ans;
}
void solve() {int n,ans=0;cin>>n;for(int i=1; i<=n; i++) {string s;cin>>s;v[(int)s.size()].push_back(s);//将字符串根据长度分类 }for(int i=1; i<=400; i++) {if(!v[i].size())continue;if(i<=20)ans=(ans+f1(i))%mod;//若长度<=20则暴力求解 else ans=(ans+f2(i))%mod;//否则暴力容斥 }cout<<ans<<endl;
}

M.Writing Books

思路:显然1~9对于答案的贡献为1*9,10~99对于答案的贡献为2*90,100~999对于答案的贡献为3*900......。分块求出贡献即可。

代码:

void solve() {int n,l=1,r=10,now=1,ans=0;cin>>n;while(l<=n){if(n>=r-1)ans+=(r-l)*now;else ans+=(n-l+1)*now;now++,l=r,r*=10;}cout<<ans<<endl;
}

http://www.lryc.cn/news/120401.html

相关文章:

  • 阿里云服务器手动搭建FTP教程(Windows操作系统)
  • idea+gradle阅读spring5.2.9源码之源码构建报错解决方案
  • 一文详解Git
  • 【单片机】DS2431英文手册,中文手册,翻译
  • centos7部署openldap开启memberof并接入jumpserver
  • Unity游戏源码分享-仿开心消消乐Match3Jewel
  • 知识图谱基本工具Neo4j使用笔记 四 :使用csv文件批量导入图谱数据
  • [bug修复]状态数据在useEffect初始化时更新无效
  • 使用 API Gateway Integrator 在 Quarkus 中实施适用于 AWS Lambda 的 OpenAPI
  • 【JVM】JVM中的分代回收
  • C# Linq源码分析之Take方法
  • 从后往前读取列表的方法
  • 数据库--数据类型
  • 小型双轮差速底盘机器人实现红外跟随功能
  • TCP协议网络编程 回显服务器,客户端实现
  • 3.4 Spring MVC注解
  • OpenCV实例(八)车牌字符识别技术(三)汉字识别
  • 运维监控学习笔记2
  • 【深度学习】遗传算法[选择、交叉、变异、初始化种群、迭代优化、几何规划排序选择、线性交叉、非均匀变异]
  • 【小吉带你学Git】讲解GitHub操作,码云操作,GitLab操作
  • nginx基础
  • 【Windows API】获取卷标、卷名
  • 通过MATLAB自动产生Hamming编译码的verilog实现,包含testbench
  • swager web服务无法显示问题
  • 代码随想录训练营day18 二叉树
  • 图像的平移变换之c++实现(qt + 不调包)
  • 云原生K8S------Yaml文件详解
  • 测试开发环境安装
  • 微信小程序如何引入Iconfont
  • php使用get和post传递数据出现414 Request-URI Too Large的解决方案