洛谷P2421 [NOI2002]荒岛野人(扩展欧几里得)

题目背景

原 A-B数对(增强版)参见P1102

题目描述

克里特岛以野人群居而著称。岛上有排列成环行的M个山洞。这些山洞顺时针编号为1,2,…,M。岛上住着N个野人,一开始依次住在山洞C1,C2,…,CN中,以后每年,第i个野人会沿顺时针向前走Pi个洞住下来。

每个野人i有一个寿命值Li,即生存的年数。

下面四幅图描述了一个有6个山洞,住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为1,2,3;每年要走过的洞穴数依次为3,7,2;寿命值依次为4,3,1。

奇怪的是,虽然野人有很多,但没有任何两个野人在有生之年处在同一个山洞中,使得小岛一直保持和平与宁静,这让科学家们很是惊奇。他们想知道,至少有多少个山洞,才能维持岛上的和平呢?

输入输出格式

输入格式:

第1行为一个整数N(1<=N<=15),即野人的数目。

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

输出格式:

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

输入输出样例

输入样例#1: 复制

3
1 3 4
2 7 3
3 2 1

输出样例#1: 复制

6

说明

对于50% 的数据:N 的范围是[1…1,000]。

对于另外50% 的数据:N 的范围是[1…100,000]。

对于100% 的数据:C 的范围是[1…1,000,000,000],N 个整数中每个数的范围是:[0…1,000,000,000]。

我居然切了一道紫题??!!好开心qwq

设第$i$个人的寿命为$x_i$,每次走$y_i$,刚开始在$a$,

若洞穴数为$b$,那么我们需要找到最小的$b$满足对于任意的两个野人$i,j$

$a_i+y_i * T_i \not \equiv a_j + y_j + T_j \pmod b$,$T$表示第几年。

然后这个是个标准的欧几里得式子

枚举一个$b$,判断就好了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 16, B = 31;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N;
struct Node {
    int bg, step, life;
    bool operator < (const Node &rhs) const {
        return this -> step < rhs.step;
    }
}a[MAXN];
int x, y;
int exgcd(int a, int b, int &x, int &y) {
    if(b == 0) {
        x = 1, y = 0; return a;
    }
    int r = exgcd(b, a % b, x, y);
    int tmp = x; x = y, y = tmp - (a / b) * y;
    return r;
}
bool check(int X) {
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= i - 1; j++) {    
            int B = X;
            int A = a[i].step - a[j].step, C = a[j].bg - a[i].bg, r = __gcd(A, B);
            if(C % r != 0) continue;
            A = A / r; B = B / r; C = C / r;
            exgcd(A, B, x, y);
            x = (x * C) % B;
            while(x < 0) x += B;
            if(x <= a[i].life && x <= a[j].life) return 0;
        }
    }
    return 1;
}
main() { 
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    N = read();
    int fuck = 0;
    for(int i = 1; i <= N; i++) 
        a[i].bg = read(), a[i].step = read(), a[i].life = read(),
        fuck = max(fuck, a[i].bg);
    sort(a + 1, a + N + 1);
    for(int i = fuck; i <= 1e6; i++)//一定要从最大值开始,,好坑。。 
        if(check(i))
            {printf("%d\n", i); exit(0);}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏GIS讲堂

Arcgis for Js之Graphiclayer扩展详解

在前两节,讲到了两种不同方式的聚类,一种是基于距离的,一种是基于区域范围的,两种不同的聚类都是通过扩展esri/layers/GraphicsLayer方法来实...

24030
来自专栏偏前端工程师的驿站

JS魔法堂:不完全国际化&本地化手册 之 理論篇

前言  最近加入到新项目组负责前端技术预研和选型,其中涉及到一个熟悉又陌生的需求——国际化&本地化。熟悉的是之前的项目也玩过,陌生的是之前的实现仅仅停留在"有"...

26180
来自专栏深度学习之tensorflow实战篇

计算机常用算法对照表整理

常用对照: NLP CRF算法: 中文名称条件随机场算法,外文名称conditional random field algorithm,是一种数学算法,是2...

54650
来自专栏数据小魔方

教你如何优雅的用R语言调用有道翻译

最近刚发现了个有趣的包,一个R语言发烧友开发了R语言与有道在线翻译的接口,可能这位大神也是一个受够了每天打开网页狂敲键盘查词的罪,索性自己动手,从此丰衣足食。 ...

27330
来自专栏计算机视觉与深度学习基础

模拟猜单词游戏

模拟实现猜单词游戏,纯模拟,不涉及图形界面,注释很详细,虽然本人代码写得丑,但是希望可以给大家提供帮助 #include<algorithm> #include...

220100
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(八)No.60

今天跟小伙伴们聊聊另外一个统计算法, Roaring BitMaps。 这个该怎么翻译呢??咆哮的位图?s?我翻译不出来,但是小蕉头一歪,就给它起了一个狂拽酷霸...

28270
来自专栏小樱的经验随笔

Codeforces Round #336 (Div. 2)【A.思维,暴力,B.字符串,暴搜,前缀和,C.暴力,D,区间dp,E,字符串,数学】

A. Saitama Destroys Hotel time limit per test:1 second memory limit per test:256...

42270
来自专栏AI派

如何使用Python伪造一点也不假的假数据呢

工作中,有时候我们需要伪造一些假数据,如何使用 Python 伪造这些看起来一点也不假的假数据呢?

23530
来自专栏跟着阿笨一起玩NET

采用左右值编码来存储无限分级树形结构的数据库表设计

该设计方案的优点是:只用一条查询语句即可得到某个根节点及其所有子孙节点的先序遍历。由于消除了递归,在数据记录量较大时,可以大大提高列表效率。但是,这种编码方案由...

63910
来自专栏恰童鞋骚年

设计模式的征途—9.组合(Composite)模式

树形结构在软件中随处可见,比如操作系统中的目录结构,公司组织结构等等,如何运用面向对象的方式来处理这种树形结构是组合模式需要解决的问题。组合模式通过一种巧妙的设...

15940

扫码关注云+社区

领取腾讯云代金券