[jzoj 5230] 队伍统计 {状态压缩DP}

news/2023/12/1 12:20:39

题目

Description
现在有n个人要排成一列,编号为1->n 。但由于一些不明原因的关系,人与人之间可能存在一些矛盾关系,具体有m条矛盾关系(u,v),表示编号为u的人想要排在编号为v的人前面。要使得队伍和谐,最多不能违背k条矛盾关系(即不能有超过k条矛盾关系(u,v),满足最后v排在了u前面)。问有多少合法的排列。答案对10^9+7取模。

Input
输入文件名为count.in。
第一行包括三个整数n,m,k。
接下来m行,每行两个整数u,v,描述一个矛盾关系(u,v)。
保证不存在两对矛盾关系(u,v),(x,y),使得u=x且v=y 。

Output
输出文件名为count.out。
输出包括一行表示合法的排列数。


解题思路

f i , j f_{i,j} fi,j 表示 i i i表示状态, j j j表示违背了的条件个数。
我们可以枚举队头,算出插入队头前的状态 l a s t last last和将插入队头后会违背的条件个数 f l a g flag flag(即判断状态里有多少个一)。
可以这么处理:

int find(int x){int xx=0; while (x) x-=(x&-x),xx++; return xx;}

动态转移方程为: f i , j + = f l a s t , j − f l a g f_{i,j}+=f_{last,j-flag} fi,j+=flast,jflag


代码

#include<cstdio>
#include<algorithm>
#define rep(i,x,y) for (register int i=x;i<=y;i++)
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define N 21
using namespace std;
const int pe=1e9+7; 
int n,m,k,f[1<<N][N],ans,a[N],cnt,last,flag; 
int find(int x){int xx=0; while (x) x-=(x&-x),xx++; return xx;}
int main(){//fre(count);scanf("%d%d%d",&n,&m,&k); int x,y; cnt=1<<n; f[0][0]=1; rep(i,1,m) scanf("%d%d",&x,&y),a[y-1]|=1<<(x-1); rep(i,0,cnt-1) rep(j,0,n-1) if ((i>j)&1){flag=find((last=(i^(1<<j)))&a[j]); rep(q,flag,k) (f[i][q]+=f[last][q-flag])%=pe; } rep(i,0,k) (ans+=f[cnt-1][i])%=pe; printf("%d",ans); 
}    

http://www.ppmy.cn/news/346231.html

相关文章

jzoj5230. 队伍统计 (B组——Day9)

jzoj5230. 队伍统计 &#xff08;B组——Day9&#xff09; 题目 Description 现在有n个人要排成一列&#xff0c;编号为1->n 。但由于一些不明原因的关系&#xff0c;人与人之间可能存在一些矛盾关系&#xff0c;具体有m条矛盾关系(u,v),表示编号为u的人想要排在编号为v的…

hdu 5230 ZCC loves hacking

刚开始滚动数组错了 #include <iostream> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; typedef long long ll; const int MAXN 100005; const int MAXNUM 320; const ll INF 0x3f…

Jzoj5230 队伍统计

现在有n个人要排成一列&#xff0c;编号为1->n 。但由于一些不明原因的关系&#xff0c;人与人之间可能存在一些矛盾关系&#xff0c;具体有m条矛盾关系(u,v),表示编号为u的人想要排在编号为v的人前面。要使得队伍和谐&#xff0c;最多不能违背k条矛盾关系&#xff08;即不能…

在TaiShan200 server 2180 昆鹏920 5230裸服务器上安装 ubuntu18.04

最近客户那边要搭建一个开源异构服务器云平台。 一共有两种不同构架的服务器&#xff0c;一种是x86构架的&#xff0c;另外一种就是arm构架的&#xff08;本文涉及的鲲鹏服务器当时使用时&#xff0c;只有一块1T的SATA硬盘&#xff09;。 在这个网站 http://old-releases.ubun…

hdu 5230 整数划分 dp

题目&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid5230 题意&#xff1a;给定n,c,l,r。求有多少种方法从1~n-1选取任意k数每个数的权重为其下标&#xff0c;使得这些数字之和加上c之后在l,r范围内。 题解&#xff1a;第一反应是计数01包&#xff0c;但是范围给定的n…

【JZOJ5230】队伍统计【状压DP】

题目大意&#xff1a; 题目链接&#xff1a;https://jzoj.net/senior/#main/show/5230 现在有 n n n个人要排成一列&#xff0c;编号为 1 ∼ n 1\sim n 1∼n 。但由于一些不明原因的关系&#xff0c;人与人之间可能存在一些矛盾关系&#xff0c;具体有 m m m条矛盾关系 ( u , …

hdu5230

bc41第三题&#xff1a; 由 1 &#xff5e; n-1 这 n-1 个数组成 l - c 到 r - c 闭区间内的数共有多少种组合方法&#xff1b; 据称本来应该也比较简单吧&#xff0c;xiaoxin说了个五边形数&#xff0c;然后纷纷找了五边形数的模板&#xff0c;虽然并没有来得及AC&#xff0c;…

hdu 5230

ZCC loves hacking 题目描述&#xff1a; 其实就是给了n~100000&#xff0c;c&#xff0c;l&#xff0c;r&#xff0c;其中C≤L≤R 题解&#xff1a; 所有情况数&#xff0c;刚开始一定会想dp【i】【j】用到数i达到和j的背包的算法&#xff0c;但是发现太大了。而且没有很好…

ZCMU--5230: 排练方阵(C语言)

Description 又到了一年一度的白马湖小学运动会了&#xff0c;为了使入场式能顺利进行&#xff0c;小朋友们最近在排练方阵。黄老师和张老师作为二年级&#xff08;1&#xff09;班的班主任和副班主任&#xff0c;却被小朋友的平均身高困扰住了。 方阵是一个n*m的矩阵&#x…

诺基亚5230使用小技巧[转]

转自http://www.shouji138.com/help/info76.htm 前几天有个朋友要买手机&#xff0c;价位在1000至1500之间&#xff0c;我推荐他买诺基亚5230&#xff0c;除了品牌过硬&#xff0c;市场占有率高之外&#xff0c;还有很多优点&#xff0c;全触摸&#xff0c;支持GPS功能&#xf…

Netbackup5230备份一体机重删率异常故障分析日志收集

1.修改bp.conf配置文件显示重删率 BPDBJOBS_COLDEFS JOBID 5 true BPDBJOBS_COLDEFS TYPE 7 false BPDBJOBS_COLDEFS STATE 4 false BPDBJOBS_COLDEFS STATUS 4 false BPDBJOBS_COLDEFS POLICY 35 false BPDBJOBS_COLDEFS SCHEDULE 12 false BPDBJOBS_COLDEFS CLI…

【电路】电路与电子技术基础 课堂笔记 第14章 触发器

触发器是数字电路中的一种记忆部件&#xff0c; 这一章需要关注的焦点是&#xff1a;各种触发器的特点、状态方程、激励表、状态转移图以及时序图等。 14.1 基本触发器 14.1.1 基本触发器的逻辑结构和工作原理 14.1.2 基本触发器功能的描述 1. 状态转移真值表 2. 特征方程&…

面试经典150题:数组/字符串合集

新专栏&#xff0c;预计两个月写完吧&#xff0c;每天下班回来抽空做几道题。会把做题计划顺序记录下来&#xff0c;如果你有缘&#xff0c;刷到这个开篇序列&#xff0c;那就跟着文章去练题吧。初学者可以慢慢来 88. 合并两个有序数组 void merge(vector<int>& nums…

用Python将《青花瓷》的歌词生成词云图

前言 大家早好、午好、晚好吖 ❤ ~欢迎光临本文章 因为上次有小伙伴问我&#xff0c;歌曲的歌词和评论怎么生成词云图&#xff0c;想买代码… 当时我就拒绝了&#xff0c;直接免费送给了他。 所以今天来分享给大家 我们以周董的《青花瓷》为例&#xff0c;要对《青花瓷》歌词…

B+树单表超过2500万行的性能影响

&#xff08;有许多人是用青春的幸福作成功的代价的。——莫扎特&#xff09; B树 关于B树的原理请查看这篇文章 分析 MySQL采用了索引组织表的形式组织数据&#xff0c;叶子节点存储数据&#xff0c;非叶子节点存储主键与页面号的映射关系。若用户的主键长度是8字节时&…

Java中有哪些基本数据类型?

整数类型&#xff08;Integral Types&#xff09;&#xff1a; byte&#xff1a;是Java中最小的整数类型&#xff0c;占用8位&#xff08;1个字节&#xff09;内存。它可表示的值范围是-128到127。short&#xff1a;占用16位&#xff08;2个字节&#xff09;内存。它的值范围为…

L1-039 古风排版(C语言)(测试点2)

题目 L1-039 古风排版 分数 20 作者 陈越 单位 浙江大学 中国的古人写文字&#xff0c;是从右向左竖向排版的。本题就请你编写程序&#xff0c;把一段文字按古风排版。 输入格式&#xff1a; 输入在第一行给出一个正整数N&#xff08;<100&#xff09;&#xff0c;是每一列…

阿里巴巴首次公开4份【并发编程全彩小册】:模型 + 原理 + 应用 + 模式, 四管齐下

相信大家都是知道的&#xff0c;阿里可以说是程序员的“必修地”每一个程序员都渴望去阿里看看&#xff0c;学习进步一下&#xff0c;但是有时候偏偏局限于自己的技术不到位&#xff01; 但是没关系&#xff0c;就算进不来了阿里&#xff0c;但是可以学习他们的技术呀&#xf…

ipad协议823

微信协议就是基于微信IPad协议的智能控制系统&#xff0c;利用人工智能AI技术、云计算技术、虚拟技术、边缘计算技术、大数据技术&#xff0c; 打造出智能桌面系统RDS、 智能聊天系统ACS 、智能插 件系统PLUGIN 、云计算服务CCS 、 任务管理系统TM、设备管理服务DM、 应用管理系…

ipad横屏怎么设置方法,如何使ipad横屏

ipad怎么设置横屏竖屏 具体如下&#xff1a;1.首先打开我们的平板&#xff0c;之后在屏幕上由下往上滑&#xff0c;如图。 请点击输入图片描述请点击输入图片描述2.之后会出现一个菜单设置界面&#xff0c;点击选项右侧的“圆形”按钮&#xff0c;就可以锁定当前屏幕的方向&a…
最新文章