Gym 100917M Matrix, The
2024-10-07 12:24:34
题目链接: http://codeforces.com/gym/100917/problem/M
----------------------------------------------------------------------------
每次写$dp$都因为思路还不成熟就上了导致经常写出状态冗余的代码
这题看数据范围显然是状压$dp$
然后注意优雅地使用位运算来减少代码长度就好了
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int ans[], way[ << ];
long long f[][ << ][ << ];
int n, a, b, q, cnt;
long long dfs(int r, int sta, int mask)
{
long long &re = f[r][sta][mask];
if(re != -)
return re;
if(r == n)
return re = (mask == ( << n) - );
re = ;
for(int i = ; i <= cnt; ++i)
if(!((~sta) & way[i] & mask))
re += dfs(r + , way[i], way[i] | mask);
return re;
}
bool dfs2(long long x, int r, int sta, int mask)
{
if(r == n)
return ;
for(int i = ; i <= cnt; ++i)
if(!((~sta) & way[i] & mask))
{
if(x > f[r + ][way[i]][way[i] | mask])
x -= f[r + ][way[i]][way[i] | mask];
else
{
ans[r + ] = way[i];
return dfs2(x, r + , way[i], way[i] | mask);
}
}
return ;
}
int calc1(int x)
{
int re = ;
for(; x; x -= x & -x, ++re);
return re;
}
void output(int x)
{
for(int i = n - ; i >= ; --i)
printf("%d", (x & ( << i)) != );
puts("");
}
int main()
{
memset(f, -, sizeof f);
scanf("%d%d%d%d", &n, &a, &b, &q);
for(int i = ; i < ( << n); ++i)
{
int tmp = calc1(i);
if(tmp >= a && tmp <= b)
way[++cnt] = i;
}
long long x;
dfs(, , );
while(q--)
{
scanf("%lld", &x);
if(dfs2(x, , , ))
{
for(int i = ; i <= n; ++i)
output(ans[i]);
}
else
puts("No such matrix.");
puts("");
}
return ;
}
最新文章
- Lua 学习笔记(十一)元表与元方法
- delphi Style TBitmapLink
- Python.Module.site
- .net破解一(反编译,反混淆-剥壳)
- UISearchBar和 UISearchDisplayController的使用
- javaScript 对json数据按key值排序
- php文字水印和php图片水印实现代码(二种加水印方法)
- 检测Insert、Capslock、NumLock、ScrollLock状态键的状态
- 【Apache ZooKeeper】为ZNode设置watcher
- 基于visual Studio2013解决面试题之0707最小元素
- Docker部署JavaWeb项目实战(转)
- 关于新版本,iOS10的相关内容,兼容iOS 10 资料整理笔记
- SpringBoot之旅第二篇-配置
- Redis 超时排查
- SQL 读取XML到Datatable
- CentOS6.8下安装xz命令
- Android之 看“马达”如何贯通Android系统 (从硬件设计 -->; 驱动 -->; HAL -->; JNI -->; Framework -->; Application)
- System.Data.SQLite安装的相关问题
- 【Django】 积累
- (三)Rest风格的资源URL