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

题解:qoj7979 棋盘

为数不多自己能乱搞出来的构造题。

题意:现有一个平面,在 \((1,1)\) 处有一个棋子。棋盘上有若干处被标记,\((1,1)\) 处必须被标记,记 \(f_{i,j}\) 为棋子到达 \((i,j)\) 且只能经过被标记的点的方案数。

现在要求你给出一种标记方式,同时给出 \(Q\) 次询问,每次询问从你标记的点中选若干个出来,满足这些点的 \(f\) 之和等于询问的 \(x\)

范围:标记的点数 \(X\le 960\),选出的点数 \(Y\le240\),询问次数 \(Q\le 10^4\),询问的 \(x \le 10^{100}\)

做法:

首先手玩几下,可以很容易先搓出来一个二进制的构造:

这样我们可以以 \(3\) 的代价使我的数乘 \(2\),可以做到 \(X=3\log_2{10^{100}} \approx 996\),但是这时候 \(Y = \log_{2}{10^{100}} \approx 332\)。可以过前三个 sub。

然后既然有二进制那么就有三进制等等,但是尝试之后发现 \(Y\) 都比较大压不进去,所以我们考虑其他东西,比如斐波那契数。

两个两个这样交错构造。

因为 \(f_n\)\(O(\phi^n)\) 级别的,这里 \(\phi = \frac{1+\sqrt 5}{2}\),所以我们可以做到 \(X=2\log_{\phi}10^{100} < 960\),然后因为每个数都有唯一的斐波那契分解,且相邻两个都不会同时取,所以 \(Y<480\)。按上述构造即可。

代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
struct Big_int {vector<int> a;Big_int() {}Big_int(int x) {while(x) {a.push_back(x % 10);x /= 10;}}Big_int(string s) {reverse(s.begin(), s.end());for (int i = 0; i < s.size(); i++)a.push_back(s[i] - '0');}void resize(int N) {a.resize(N);}void pop_back() {a.pop_back();}void push_back(int x) {a.push_back(x);}int& operator[](int x) {return a[x];}int size() {return a.size();}friend Big_int operator+(Big_int x, Big_int y) {int d = max(x.size(), y.size());x.resize(d), y.resize(d);for (int i = 0; i < d; i++)x[i] = x[i] + y[i];for (int i = 0; i < d - 1; i++)x[i + 1] += x[i] / 10, x[i] %= 10;while(x[d - 1] >= 10) {x.push_back(x[d - 1] / 10);x[d - 1] %= 10, d++;}return x;}friend Big_int operator-(Big_int x, Big_int y) {int d = max(x.size(), y.size());x.resize(d), y.resize(d);for (int i = 0; i < d; i++) {if(x[i] < y[i])x[i] += 10, x[i + 1] -= 1;x[i] -= y[i];}while(x.size() && x[x.size() - 1] == 0)x.pop_back();return x;}friend bool operator<=(Big_int x, Big_int y) {if(x.size() != y.size())return x.size() < y.size();for (int i = x.size() - 1; i >= 0; i--)if(x[i] != y[i])return x[i] < y[i];return 1;}void print() {for (int i = a.size() - 1; i >= 0; i--)cout << a[i];cout << endl;}
} f[maxn];
int k, q, x, y;
struct node {int x, y;
} ;
int id[maxn];
int vis[maxn];
int main() {cin >> k >> q >> x >> y;f[1] = 1, f[2] = 1; for (int i = 3; i <= 480; i++)f[i] = f[i - 1] + f[i - 2];vector<node> v;for (int i = 1; i <= 480; i++) {if(i % 2)v.push_back(node{i / 2 + 1, i / 2 + 1}), v.push_back(node{i / 2 + 1, i / 2 + 2}), id[i] = v.size() - 1;elsev.push_back(node{i / 2 + 1, i / 2}), v.push_back(node{i / 2 + 2, i / 2}), id[i] = v.size() - 1;}cout << v.size() << endl;for (int i = 0; i < v.size(); i++)cout << v[i].x << " " << v[i].y << endl;while(q--) {string s;cin >> s;Big_int x(s);memset(vis, 0, sizeof(vis));for (int i = 480; i >= 1; i--) {if(f[i] <= x)x = x - f[i], vis[id[i]] = 1;}x = Big_int(0);for (int i = 1; i <= 960; i++) {cout << vis[i];if(vis[i])x = x + f[(i + 1) / 2];}cout << endl;//	x.print();}return 0;
}
http://www.hskmm.com/?act=detail&tid=28122

相关文章:

  • 氧化铝
  • 2025 最新不锈钢管厂家推荐排行榜 权威发布:304/316L/2205 等材质焊管无缝管优质企业精选
  • 2025 年最新推荐微波干燥设备生产厂家排行榜,覆盖多行业高效干燥解决方案权威推荐黄粉虫/黑水虻/中药材/茶叶微波干燥设备厂家推荐
  • 控制台
  • 2025 年高强钢板厂家最新推荐排行榜:聚焦国内优质企业,助力采购者精准选品的权威榜单合金/HG785D/Q690D/S960QL/700L高强钢板厂家推荐
  • (数论大杂烩)古代猪文
  • 滥用ACL权限覆盖其他用户S3存储桶中的文件/视频
  • 2025 年最新三维扫描仪厂家权威排行榜:聚焦高精度与多场景适配,为企业与个人用户精选优质品牌推荐高精度/专业/手持激光/工业/便携式三维扫描仪厂家推荐
  • 后端基础-输入/输出件
  • 2025 年净化工程服务商最新权威推荐排行榜:医院净化工程 / 制药厂 / 化工厂 / 实验室 / 无尘车间优选净化工程设计安装施工公司
  • 2025 年最新推荐!国内优质充电桩厂家排行榜,涵盖多场景适配产品,助用户精准选靠谱品牌智能/新能源/电动车/重卡/电动车直流充电桩厂家推荐
  • 实用指南:【图像算法 - 28】基于YOLO与PyQt5的多路智能目标检测系统设计与实现
  • KingView 组态王 6.5下载地址与安装教程
  • 常用接口对比
  • 工具网站网址
  • linux执行脚本命令报错$\r:未找到命令的解决方法
  • 2025 电缆回收推荐榜:广州龙耀 5 星领跑,这些企业适配绿色循环需求
  • 基于最小二乘法的离散数据曲面拟合MATLAB实现方法
  • 20251010——读后感1
  • MOE模型
  • 2025航空插头厂家最新推荐榜:M8 航空插头, m12航空插头, 航空插头公母对接, 航空插头5芯, 航空插头三芯, 航空插头4芯, 航空插头12芯等类型全覆盖,专业定制与可靠品质
  • go使用root用户进行调试
  • 如何反制免费项目管理软件的套路
  • 智能技术与先进制造国际会议(ITAM 2025)
  • 2025智慧工地工程协同项目交付管理软件系统平台公司推荐榜:项目全周期的智能中枢,助力建筑行业数字化转型
  • 1、在pyhcarm中安装包和指定镜像源
  • iOS 26 系统流畅度深度剖析,Liquid Glass 视效与界面滑动的实际测评 - 指南
  • 重庆初阳科技车辆计数厂家:多维度赋能城市建设与工程精细化管理
  • 使用testcenter打出动态流量
  • coze手册