NOI2002 荒岛野人

题目

Luogu P2421

克里特岛以野人群居而著称。岛上有排列成环行的 (m) 个山洞。这些山洞顺时针编号为 (1,2,dots ,m) 。岛上住着 (n) 个野人,一开始依次住在山洞 (C_1,C_2,dots ,C_n) 中,以后每年,第 (i) 个野人会沿顺时针向前走 (P_i) 个洞住下来。

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

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

img

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

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

分析

若在第 (k) 年,野人 (i) 和野人 (j) 所处的山洞重合,那么有:

[C_i+kP_i equiv C_j+kP_j pmod{M} ]

移项得:

[k(P_i-P_j) equiv C_j-C_i pmod{M} ]

(M) 已知,那我们可以用EXGCD求出上面的同余方程的一个解,进而求出最小正整数解,若最小正整数解 (k leq min(L_i,L_j)) 则会发生山洞重合的情况,野人会发生冲突,否则不会

已知 (M) 的范围并不大,所以可以从小到大枚举

代码

#include<bits/stdc++.h> #define ll long long using namespace std;  int n; int c[20], p[20], l[20];  ll gcd(ll a, ll b) {     return a % b == 0 ? b : gcd(b, a % b); }  ll exgcd(ll a, ll b, ll & x, ll & y) {     if(b == 0) {         x = 1;         y = 0;         return a;     }     ll d = exgcd(b, a % b, y, x);     y -= a / b * x;     return d; }  bool check(int m) {     for(int i = 1; i <= n; i++) {         for(int j = i + 1; j <= n; j++) {             int a = ((p[j] - p[i]) % m + m) % m;             int b = ((c[i] - c[j]) % m + m) % m;             ll d = gcd(a, m);             if(b % d != 0)                 continue;             ll x, y, t;             exgcd(a, m, x, y);             t = m / d;             x = (x * b / d % t + t) % t;             if(x <= min(l[i], l[j]))                 return false;         }     }     return true; }  int main() {     cin >> n;     int minn = n;     for(int i = 1; i <= n; i++) {         cin >> c[i] >> p[i] >> l[i];         minn = max(minn, c[i]);         c[i]--;     }     for(int m = minn; m <= 1000000; m++) {         if(check(m)) {             cout << m << endl;             break;         }     }     return 0; } 

推荐这些技术文章:

[NOI2002] 荒岛野人

link
二十年前的NOI是如此淳朴……
题并不难,主要是我对扩欧理解不深,再加上许久没写了,于是乎写得一塌糊涂……
考虑枚举洞穴个数 \(k\) ,并验证个数是否合法,很明显可以列出式子(假如两个野人 \(s\) 年后相遇):
\[c_1+p_1s\equiv c_2+p_2s\pmod{k}
\]变形可得:
\[(p_1-p_2)s-rk=c_2-c_1
\]可以发现这就是一个 \(a=p_...

【Coel.解题报告】【推柿子的基本思路】[NOI2002] 荒岛野人

题前碎语
还有13天就要期考了,可我还是在机房颓题目。
其实我本来不是很想颓的,可是这道题对于学习扩欧来说很重要,所以还是放进来一下。
题目简介
洛谷传送门
题目描述
克里特岛以野人群居而著称。岛上有排列成环行的 \(m\) 个山洞。这些山洞顺时针编号为 \(1,2,\dots ,m\) 。岛上住着 \(n\) 个野人,一开始依次住在山洞 \(C_1,C_2,\dots ,C_n\)中,以后每年...

NOI 2002 荒岛野人

人生第一次做NOI的题祭!!!
大概是NOI最简单的一道题

克里特岛以野人群居而著称。岛上有排列成环行的M个山洞。这些山洞顺时针编号为1,2,…,M。岛上住着N个野人,一开始依次住在山洞C1,C2,…,CN中,以后每年,第i个野人会沿顺时针向前走Pi个洞住下来。
每个野人i有一个寿命值Li,即生存的年数。
下面四幅图描述了一个有6个山洞,住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依...

牛客挑战赛60

比较简单的签到题

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
int T;
ll gcd(ll aa,ll bb){
if(bb)return gcd(bb,aa%bb);
return aa;
}
int main(...

2019-2020 XX Open Cup, Grand Prix of Korea

2019-2020 XX Open Cup, Grand Prix of Korea
比赛收获
本场贡献:et3_tsy :G提供了思路,过了H,H爆了int,贡献WA一发,J有想法,调了1hr后,发现在特例情况复杂度退化,假了
​ 1427314831a:过了A
​ Ryker0923 :过了G,提供了A的思路
一共三道题
总结:本场暴露两个问题:
1)后期乏力
前两个小时过了...

Educational Codeforces Round 129(补题)

C. Double Sort
题意
让我们对两个数组进行排序,每次进行排序要同时将a,b数组同时进行排序,问能不能将数组变为非递减数组
算法(前缀和+手动模拟排序)
我们先找出每个数在数组的位置的范围,每个数在分别的数组上面的位置相对是稳定的,如果对应位置的ai,bi范围相交,那么我们就可以去max(l1,l2),即可。找位置可以使用前缀和找出。
C++
// Problem: C. Doubl...

Educational Codeforces Round 129 (Rated for Div. 2) A - D 题解

传送门
A. Game with Cards
看最大的在谁那,谁就赢
如果最大的都一样,则先手赢
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#i...

【2022neuoj刷题打卡】2581~2590

最近neuoj加了一些atcoder的题,正好在刷题,存一下代码
2581

点击查看代码
//Author:Fczhao
//Language:cpp
#include <bits/stdc++.h>
using namespace std;
signed main(){
#ifdef FCZHAO
freopen("1.in", "r", stdin);
freope...

王道机试指南题解(C/C++版)

第 2 章 经典入门
一 排序
例 2.1 排序

代码 2.1
冒泡排序(时间复杂度 \(O(n^2)\))
#include <iostream>
using std::cin; using std::cout; using std::endl;

#include <vector>
using std::vector;

#include <algorith...

UVA1589 象棋 Xiangqi

这题考察我们的大脑体力,非常难调,我花了2小时,要是在区域赛里做着题,我碰都不碰,没有大样例非常难受。
分析如下:

中国象棋,见百度百科
就是考虑当前情况下将军是不是已经给将死了

考虑:

飞将
将军吃掉了红色棋子的情况
马脚问题
将军只能在一定的区域内移动
注意边界情况
善用工具来debug,我用了udebug,里面有一个大样例,cmd我是可以看到输入的,但吞了我一部分输出,搞得我虚空调试...

文章标题:NOI2002 荒岛野人
文章链接:https://www.dianjilingqu.com/3066.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>