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

AT_agc012_c [AGC012C] Tautonym Puzzle 题目分析

题目

AT_agc012_c [AGC012C] Tautonym Puzzle

题目描述

当字符串 $ x $ 满足以下条件时,称 $ x $ 为好字符串

  • 条件:$ x $ 可以表示为某个长度不少于 $ 1 $ 的字符串 $ y $ 重复两次所得的字符串 $ yy $。

例如,aabubobubo 等是好字符串,而空字符串、aabcabcabcabba 等都不是好字符串。

“ワシ”与猫头鹰设计了关于好字符串的谜题。请找出一个满足下列条件的字符串 $ s $。在本题的约束条件下,一定存在这样的字符串。

  • $ 1\leq |s|\leq 200 $
  • $ s $ 仅由用 $ 1 $ 至 $ 100 $ 的整数表示的 $ 100 $ 种字符构成。
  • $ s $ 的 $ 2^{|s|} $ 个子序列中,成为好字符串的子序列有 $ N $ 个。

题目分析

这显然是一道构造题目,高质量的构造题目。

我们注意到填什么似乎并不重要,重要的是种类不同。

因此有 \(200\) 个位置,我们先用 \(100\) 个位置从左到右依次放置 \(1,\dots,100\)

我们考虑后半部分怎么与前面的匹配出 \(n\) 个合法的。

首先考虑一个最大的 \(k\) 使得 \(2^k-1\leq n\),将 \(n\) 分为 \(2^k-1\)\(rest=n-2^k+1\) 两个部分进行计算。

第一个部分,我们可以只需要按顺序放置 \(k\) 个数就可以了,至于是什么得看第二个部分。

对于第二个部分,我们试图将其与 \(rest\) 的二进制扯上关系,如果说第 \(x\) 位(从后往前,从 \(0\) 开始)为 \(1\),我们希望多产生 \(2^x\) 的贡献,怎么弄呢?

要产生 \(2^x\) 的贡献其中一个方法就是当前在末尾放置一个数 \(a\),使得前面比它小的数有 \(x\) 个即可。

这个的方法不同,其中一种比较简单的方法是:前面直接放置偶数就可以了(\(\{2,4,6,\dots\}\)),然后后面补充奇数,比如说对于 \(rest=(101)_2\),得到后半部分的序列的第二部分为:\(\{5,1\}\)

注意遍历的时候要从高位开始遍历,否则小奇数对大奇数也有可能产生贡献。

真是一道好题!

代码

时间复杂度 \(\mathcal{O}(len)\),其中 \(len\) 为最后答案的长度。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define int long long
// #define N 
using namespace std;
int n;
vector<int> ans;
signed main(){cin >> n;// cout << 200 << '\n';// for (int i = 1;i <= 100;i ++) cout << i << ' ';for (int i = 1;i <= 100;i ++) ans.push_back(i);int k = 0;for (;(1ll << k + 1) - 1ll <= n;k ++);for (int i = 1;i <= k;i ++) ans.push_back(i * 2);int rest = n - (1ll << k) + 1ll;for (int i = k - 1;i >= 0;i --)if ((rest >> i) & 1) ans.push_back(i * 2 + 1);cout << ans.size() << '\n';for (auto i : ans) cout << i << ' ';return 0;
}
http://www.hskmm.com/?act=detail&tid=16982

相关文章:

  • 详细介绍:回调函数与错误处理
  • Django系列(七)HttpRequest(请求)和HttpResponse(响应)对象
  • 工业主板:智能制造与严苛环境的坚实基石
  • 课上测试:C编程工具测试(AI)
  • 标题。
  • 虚拟机下的麒麟V10SP1与SP2进行iSCSI连接——基于MobaXterm
  • 中断的基本概念
  • AT_arc173_e [ARC173E] Rearrange and Adjacent XOR
  • 修复gradle8使用Transform第一个构建中断第二次构建失败的问题:java.io.IOException: Unable to delete directory xxxx\build
  • .NET操作Word/WPS打造专业文档 - 页面设置与打印控制完全指南
  • NORDIC蓝牙6.0新品NRF54L15多协议超低功耗高性能BLE芯片 - 动能世纪
  • 记录:git、.${index}. 滚动条
  • 使用springboot开发一个宿舍管理系统练习项目 - 实践
  • 元组
  • CF1542
  • Manim实现涟漪扩散特效
  • CRMEB标准版PHP移动订单功能深度解析:多端同步方案
  • CICD流程建设之持续测试实践指南
  • Xcode 26.0.1 (17A400) 发布 - Apple 平台 IDE
  • Tenable Nessus 10.10 (macOS, Linux, Windows) - 漏洞评估解决方案
  • CNN+MNIST - 实践
  • SonarQube Server 2025 Release 5 (macOS, Linux, Windows) - 代码质量、安全与静态分析工具
  • 超快轻量级离线翻译服务器MTranServer在腾讯云轻量应用服务器上的全流程部署指南 - 实践
  • 微算法科技(NASDAQ: MLGO)利用高级 Blowfish 加密标准实现区块链集成信息共享
  • 专业讲解大模型登记(纯干货)
  • Docker常用命令速查
  • 离线安装docker
  • MX 练石 2025 NOIP #9
  • dockerfile
  • PostgreSQL 的索引Ooracle、Mysql索引的类型对比和说明