BZOJ 1407: [Noi2002]Savage( 数论 )

BZOJ 1407: [Noi2002]Savage( 数论 )

枚举答案, 然后O(N^2)枚举野人去判他们是否会在有生之年存在同山洞. 具体做法就是: 设第x年相遇, 则 Ci+x*Pi=Cj+x*Pj (mod M), 然后解同余方程. 复杂度应该是O(ans*N^2log(ans)), 但是实际远小于....能够AC

--------------------------------------------------------------------

#include<cstdio>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
const int maxn = 20;
 
int N, p[maxn], c[maxn], l[maxn], ans;
 
void Init() {
ans = 0;
scanf("%d", &N);
for(int i = 0; i < N; i++) {
scanf("%d%d%d", c + i, p + i, l + i);
ans = max(ans, c[i]);
}
}
 
void Gcd(int a, int b, int &d, int &x, int &y) {
if(!b) {
d = a;
x = 1;
y = 0;
} else {
Gcd(b, a % b, d, y, x);
y -= x * (a / b);
}
}
 
bool chk() {
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++) if(p[i] > p[j]) {
int d, x, y;
Gcd(p[i] - p[j], ans, d, x, y);
if((c[j] - c[i]) % d)
continue;
int t = ans / d;
x *= (c[j] - c[i]) / d;
while(x >= 0) x -= t;
while(x < 0) x += t;
if(x <= l[i] && x <= l[j])
return false;
}
return true;
}
 
void Work() {
while(!chk())
ans++;
printf("%d\n", ans);
}
 
int main() {
Init();
Work();
return 0;
}

--------------------------------------------------------------------

1407: [Noi2002]Savage

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1102  Solved: 501
[Submit][Status][Discuss]

Description

BZOJ 1407: [Noi2002]Savage( 数论 )

Input

第1行为一个整数N(1<=N<=15),即野人的数目。第2行到第N+1每行为三个整数Ci, Pi, Li (1<=Ci,Pi<=100, 0<=Li<=106 ),表示每个野人所住的初始洞穴编号,每年走过的洞穴数及寿命值。

Output

仅包含一个数M,即最少可能的山洞数。输入数据保证有解,且M不大于106。

Sample Input

3
1 3 4
2 7 3
3 2 1

Sample Output

6

该样例对应于题目描述中的例子。

HINT

Source

上一篇:bzoj 1407: [Noi2002]Savage


下一篇:Hadoop、Zookeeper、Hbase分布式安装教程