【HEOI2013】bzoj3168 钙铁锌硒维生素

2023-11-07 19:59

本文主要是介绍【HEOI2013】bzoj3168 钙铁锌硒维生素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

银河队选手名单出来了!小林,作为特聘的营养师,将负责银河队选手参加
宇宙比赛的饮食。众所周知,前往宇宙的某个星球,通常要花费好长好长的时间,人体情况在这之间会发生变化,因此,需要根据每天的情况搭配伙食,来保证营养。小林把人体需要的营养分成了n种,这些营养包括但不限于铁,钙。他准备了2套厨师机器人,一套厨师机器人有n个,每个厨师机器人只会做一道菜,这道菜一斤能提供第i种营养xi微克。想要吃这道菜的时候,只要输入一个数,就能吃到对应数量的这道菜了。为防止摄入过量对身体造成的伤害,每个机器人还有防过量摄入药,只要输入一个数,就能生成一定剂量的药,吃了这些药,就能减少相当于食用对应数目的这道菜提供的营养。
小林之所以准备2套厨师机器人,正是因为旅途漫漫,难以预计,也许某一个厨师机器人在途中坏掉,要是影响了银河队选手的身体,就不好了。因此,第2套厨师机器人被用来做第1套的备用。小林需要为每一个第1套厨师机器人选一个第2套厨师机器人作备份,使得当这个机器人坏掉时,用备份顶替,整套厨师机器人仍然能搭配出任何营养需求,而且,每个第2套厨师机器人只能当一个第1套厨师机器人的备份。
Input

第一行包含一个正整数n。接下来n行,每行n个整数,表示第
1套厨师机器人做的菜每一斤提供的每种营养。再接下来n行,每行n个整数,表示第2套厨师机器人做的菜每一斤提供的每种营养。 Output

第一行是一个字符串,如果无法完成任务,输出“NIE”,否则输
出“TAK”,并跟着n行,第i行表示第i个第1套机器人的备份是哪一个第2套机器人。为了避免麻烦,如果有多种可能的答案,请给出字典序最小的那一组。

对于每一个 bi 求出他能替换哪些向量 aj ,然后就变成了字典序最小的二分图完备匹配问题。
把向量 a 组成矩阵A,然后求 xA=bi ,也就是 bi=x1a1+x2a2++xnan 。如果 xj 不为零, bi 可以替换 aj 。把 b 拼成矩阵B,求出 C=BA1 就是二分图的邻接矩阵。
在二分图上先求出一个完备匹配,然后从小到大考虑每个位置连的边,选择一条最小的而且不会影响之前的匹配的路径进行更换。
原题数据貌似不保证矩阵 A <script type="math/tex" id="MathJax-Element-1193">A</script>可逆,需要判断。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int p=100000007;
int n,f[310],vis[310],ans[310],ok=1;
int pow(int base,int x)
{int ret=1;while (x){if (x&1) ret=(LL)ret*base%p;base=(LL)base*base%p;x>>=1;}return ret;
}
struct mat
{int a[310][310];void rd(){for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)scanf("%d",&a[i][j]);}mat operator * (const mat &m) const{mat ret;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){ret.a[i][j]=0;for (int k=1;k<=n;k++)ret.a[i][j]=(ret.a[i][j]+(LL)a[i][k]*m.a[k][j]%p)%p;}return ret;}mat inv(){mat ret;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)ret.a[i][j]=(i==j);for (int i=1;i<=n;i++){int x;x=-1;for (int j=i;j<=n;j++)if (a[j][i]){x=j;break;}if (x==-1){ok=0;return ret;}if (x!=i)for (int j=1;j<=n;j++){swap(a[i][j],a[x][j]);swap(ret.a[i][j],ret.a[x][j]);}x=pow(a[i][i],p-2);for (int j=1;j<=n;j++){a[i][j]=(LL)a[i][j]*x%p;ret.a[i][j]=(LL)ret.a[i][j]*x%p;}for (int j=1;j<=n;j++)if (j!=i){x=a[j][i];for (int k=1;k<=n;k++){a[j][k]=(a[j][k]-(LL)a[i][k]*x%p+p)%p;ret.a[j][k]=(ret.a[j][k]-(LL)ret.a[i][k]*x%p+p)%p;}}}return ret;}
}a,b,c;
int dfs1(int u)
{for (int v=1;v<=n;v++)if (c.a[v][u]&&!vis[v]){vis[v]=1;if (!f[v]||dfs1(f[v])){f[v]=u;return 1;}}return 0;
}
int dfs2(int u,int from)
{for (int v=1;v<=n;v++)if (c.a[v][u]&&!vis[v]){vis[v]=1;if (f[v]==from||(f[v]>from&&dfs2(f[v],from))){f[v]=u;return 1;}}return 0;
}
int main()
{int cnt=0;scanf("%d",&n);a.rd();b.rd();c=b*a.inv();if (!ok){printf("NIE\n");return 0;}for (int i=1;i<=n;i++){for (int j=1;j<=n;j++) vis[j]=0;if (dfs1(i)) cnt++;}if (cnt<n) printf("NIE\n");else{printf("TAK\n");for (int i=1;i<=n;i++){for (int j=1;j<=n;j++) vis[j]=0;dfs2(i,i);}for (int i=1;i<=n;i++) ans[f[i]]=i;for (int i=1;i<=n;i++) printf("%d\n",ans[i]);}
}

这篇关于【HEOI2013】bzoj3168 钙铁锌硒维生素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/365946

相关文章

【多系统萎缩患者必看】✨维生素补充全攻略,守护你的健康每一天!

亲爱的朋友们,今天我们要聊一个既重要又容易被忽视的话题——‌多系统萎缩患者如何科学补充维生素‌!🌟 在这个快节奏的生活中,健康成为了我们最宝贵的财富,而对于多系统萎缩(MSA)的患者来说,合理的营养补充更是维护身体机能、提升生活质量的关键一步。👇 🌈 为什么多系统萎缩患者需要特别关注维生素? 多系统萎缩是一种罕见且复杂的神经系统疾病,它影响身体的多个系统,包括自主神经、锥体外系、小脑及锥

【舞动生命,不缺营养!】亨廷顿舞蹈症患者必知的维生素补给站

Hey小伙伴们~👋 今天我们来聊聊一个既特别又需要我们温柔以待的话题——亨廷顿舞蹈症(HD)。在这个充满挑战的旅程中,除了医疗团队的精心治疗,合理的饮食与维生素补充也是不可或缺的支持力量哦!🌈 🌿维生素B家族:大脑的守护者 首先,让我们从维生素B家族说起吧!维生素B群,特别是B6、B12和叶酸,对神经系统健康至关重要。🧠 对于亨廷顿舞蹈症患者而言,它们能帮助缓解神经退行性病变带来的不适

【舞动生命,不缺营养!】亨廷顿舞蹈症患者的维生素秘籍✨

Hey小伙伴们~👋 在这个充满色彩的世界里,每个人都是独一无二的舞者,但对于患有亨廷顿舞蹈症的朋友来说,他们的舞蹈却多了几分挑战与不易。💪 今天,就让我带你一起揭秘,那些能够助力亨廷顿舞蹈症患者“舞”动更精彩生活的维生素宝藏吧!🎁 🌈 维生素B群:能量加油站! 首先登场的是我们的维生素B群小伙伴,它们可是神经系统的好帮手!🧠 对于亨廷顿舞蹈症患者来说,维持神经系统的稳定至关重要。维生

万万没想到,原来这些维生素对帕金森有好处!

亲爱的读者朋友们,今天我们要聊一个特别的群体——帕金森病患者。在面对这一神经系统退行性疾病时,除了遵循医嘱进行药物治疗和康复锻炼,合理的饮食和营养补充也显得尤为重要。那么,究竟哪些维生素是他们不可或缺的呢?让我们一起探索,为健康加分! 维生素D:阳光下的护身符 首先,我们要提的是维生素D。它不仅对骨骼健康至关重要,还与多种身体功能相关联。研究表明,维生素D的充足摄入有助于改善帕金森病患

【chemistry 4】维生素和核酸

🌞欢迎来到生物医学的世界  🌈博客主页:卿云阁 💌欢迎关注🎉点赞👍收藏⭐️留言📝 🌟本文由卿云阁原创! 📆首发时间:🌹2024年3月28日🌹 ✉️希望可以和大家一起完成进阶之路! 🙏作者水平很有限,如果发现错误,请留言轰炸哦!万分感谢! 目录 ​ 维生素 核酸 基因指导蛋白质的合成 维生素 脂溶性的维生素是不能吃多的,它在我们的人体内是很难降解的。 核酸 核酸

1,25(OH)2维生素D单克隆抗体丨D2、D3

1,25(OH)2 维生素D起源于25OH维生素D的羟基化,其生成量受PTH调控。1,25(OH)2维生素D检测的重要用途是评估肾病患者的维生素D状态,同时也适用于对肾移植受者、接受1OH维生素D治疗的成人、已知所接受治疗会影响骨矿物质状态的儿童和有骨肿瘤的儿童进行评估,并可用于低磷性佝偻病/骨软化症的诊断。 在酶的作用下,肝脏使用维生素D合成25OH维生素D。它是维生素D的体内储存形式,在

【饮食】如何有效的补充维生素,矿物质?学习笔记(附膳食营养素参考摄入量DRIs)

程序员养生指南之 【饮食】如何有效的补充维生素,矿物质?学习笔记(附膳食营养素参考摄入量DRIs) 文章目录 一、维生素补充1、需要补充维生素的情况2、食补:缺啥补啥3、补充剂(无脑吃) 二、膳食营养素参考摄入量DRIs1、什么是DRIs2、DRIs维生素表+矿物质表(2012版) 3、维生素补充 一、维生素补充 1、需要补充维生素的情况 正常情况下,均衡饮食,膳食中的

多系统萎缩患者应补充的关键维生素

多系统萎缩(Multiple System Atrophy, MSA)是一种进展性神经退行性疾病,影响自主神经系统、锥体外系及小脑功能。在管理MSA的过程中,除了药物治疗和康复训练,适当的维生素补充也是重要的辅助治疗手段。合理的维生素摄入有助于改善患者的神经功能和身体状况,提升生活质量。 维生素B群对于神经系统的健康至关重要。它们参与神经传递物质合成,能够帮助维持正常的神经功能,并支持身体的新陈

【bzoj3165】【HEOI2013】【Segment】【线段树】

Description 要求在平面直角坐标系下维护两个操作:  1.在平面上加入一条线段。记第i条被插入的线段的标号为i。  2.给定一个数k,询问与直线 x = k相交的线段中,交点最靠上的线段的编号。   Input   第一行一个整数n,表示共n 个操作。  接下来n行,每行第一个数为0或1。    若该数为 0,则后面跟着一个正整数 k,表示询问与直线   x = ((k

【bzoj3166】【HEOI2013】【Alo】【set+可持久化trie】

Description Welcome to ALO ( Arithmetic and Logistic Online)。这是一个VR MMORPG , 如名字所见,到处充满了数学的谜题。 现在你拥有n颗宝石,每颗宝石有一个能量密度,记为ai,这些宝石的能量 密度两两不同。现在你可以选取连续的一些宝石(必须多于一个)进行融合,设为  ai, ai+1, …, a j,则融合而成的宝石的能量密度