题目链接: 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 ;
}

最新文章

  1. Lua 学习笔记(十一)元表与元方法
  2. delphi Style TBitmapLink
  3. Python.Module.site
  4. .net破解一(反编译,反混淆-剥壳)
  5. UISearchBar和 UISearchDisplayController的使用
  6. javaScript 对json数据按key值排序
  7. php文字水印和php图片水印实现代码(二种加水印方法)
  8. 检测Insert、Capslock、NumLock、ScrollLock状态键的状态
  9. 【Apache ZooKeeper】为ZNode设置watcher
  10. 基于visual Studio2013解决面试题之0707最小元素
  11. Docker部署JavaWeb项目实战(转)
  12. 关于新版本,iOS10的相关内容,兼容iOS 10 资料整理笔记
  13. SpringBoot之旅第二篇-配置
  14. Redis 超时排查
  15. SQL 读取XML到Datatable
  16. CentOS6.8下安装xz命令
  17. Android之 看“马达”如何贯通Android系统 (从硬件设计 --&gt; 驱动 --&gt; HAL --&gt; JNI --&gt; Framework --&gt; Application)
  18. System.Data.SQLite安装的相关问题
  19. 【Django】 积累
  20. (三)Rest风格的资源URL

热门文章

  1. Java中StringHelp
  2. 设置HTML中字体的粗细
  3. 小白学Python(9)——pyecharts 绘制漏斗图 Funnel
  4. jquery遍历table中每个td的值
  5. mybatis resultMap之collection聚集两种实现方式
  6. 利用C51单片机模拟SPI进行双机通信
  7. Java REST Client API
  8. 【改】linux中分区的概念
  9. 树——sum-root-to-leaf-numbers(根到叶节点数字之和)
  10. dialog写进dll调用