Poj 2947 widget factory (高斯消元解同模方程)
2024-09-04 14:12:55
题目连接:
http://poj.org/problem?id=2947
题目大意:
有n种类型的零件,m个工人,每个零件的加工时间是[3,9],每个工人在一个特定的时间段内可以生产k个零件(可以相同种类,也可以不同种类),问每种零件生产一个出来需要的时间?
解题思路:
给出的时间段是从周几到周几,并没有给出具体的时间段,因此在计算过程中要进行取模,还有就是对每个零件要在题目要求的范围内进行枚举。
ps:如果求出来的增广矩阵是n*n的,但是某个零件在[3,9]之间没有合理的解,也是无解的。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = ;
int det[maxn][maxn], res[maxn], var, equ;
char str[][] = {"","MON", "TUE", "WED", "THU", "FRI", "SAT" , "SUN"};
int Day (char s[])
{
for (int i=; i<; i++)
if (strcmp(s, str[i]) == )
return i;
}
int gauss ()
{
int col, k;
for (k=col=; k<equ&&col<var; k++, col++)
{
int Max_i = k;
for (int i=k+; i<equ; i++)
if (abs(det[i][col]) > abs(det[Max_i][col]))
Max_i = i;
if (Max_i != k)
for (int i=col; i<=var; i++)
swap (det[k][i], det[Max_i][i]);
if (det[k][col] == )
{
k --;
continue;
}
for (int i=k+; i<equ; i++)
if (det[i][col])
{
int x = det[i][col];
int y = det[k][col];
for (int j=col; j<=var; j++)
det[i][j] = ((det[i][j]*y - det[k][j]*x) % + ) % ;
}
}
int temp = , i, j;
for (i=; i<equ; i++)
{
for (j=; j<var; j++)
if (det[i][j])
break;
if (j == var)
{
if (det[i][j])
return ;//增广矩阵无解
else if (i < var)//增广矩阵存在不确定变元
temp ++;
}
}
if (temp || var > equ)
return ;//增广矩阵存在不确定变元 for (i=var-; i>=; i--)
{
temp = ;
for (j=i+; j<var; j++)
temp = (temp + det[i][j] * res[j]) % ;
for (j=; j<; j++)//枚举每个零件的加工时长
if ((temp + det[i][i]*j)% == det[i][var])
{
res[i] = j;
break;
}
if (j == )//当有某个零件的加工时长不在[3,9]之间,则不符合题意,无解
return ;
}
return ;
}
int main ()
{
while (scanf ("%d %d", &var, &equ), var+equ)
{
int k, x;
char st[maxn], et[maxn];
memset (det, , sizeof(det));
for (int i=; i<equ; i++)
{
scanf ("%d %s %s", &k, st, et);
while (k --)
{
scanf ("%d", &x);
det[i][x-] ++;
}
det[i][var] = Day(et) - Day(st) + ;
}
for (int i=; i<equ; i++)//这里一定要去次余,如果det[i][j]是7的倍数,在划成阶梯阵的过程中很有可能会错
for (int j=; j<=var; j++)
det[i][j] = (det[i][j] % + ) % ;
int ans = gauss();
if (ans == )
printf ("Inconsistent data.\n");
else if (ans == )
printf ("Multiple solutions.\n");
else
for (int i=; i<var; i++)
printf ("%d%c", res[i], i==var-?'\n':' ');
}
return ;
}
最新文章
- 【Excel】Excel根据单元格背景色求和
- ch6 影响 MySQLServer 性能的相关因素
- 清除 WD MyCloud 自动生成的 .wdmc 目录
- PHP程序员函数注释规格(麻烦大家遵守)
- Android布局_相对布局RelativeLayout
- 记录android5.0更新踩过的坑
- zend studio 9.0.4 安装破解
- angularJS 服务二
- 查看Oracle最耗时的SQL
- rsyslog安装
- Windows Phone 如果你把Pivot控件当成主页面,那么这篇文章你值得看。
- ajax入门之建立XHR对象 (1)
- Q:记学习枚举过程中的一个小问题
- 关于Android SDK Manager更新速度慢的解决方法
- [题解] P2513 [HAOI2009]逆序对数列
- 反素数ant HYSBZ - 1053(数学+dfs)
- 在线预览-Java 使用 Print2Flash 实现Office文档在线阅读
- python random使用方法
- Codeforces Round #538 (Div. 2)
- TypeScript 之 书写.d.ts文件
热门文章
- Java反射常用示例
- Failed to execute &#39;toDataURL&#39; on &#39;HTMLCanvasElement,在canvas.toDataURL()执行时候报错解决方案
- curl -s 不输出统计信息
- Java知识图谱
- [Tools] Create a Chrome Extension
- SQL2012 尝试读取或写入受保护的内存。这通常指示其它内存已损坏
- NYOJ 158 省赛来了
- excel 学习
- lsblk df
- h5ai目录列表优化