作品 上海高端网站设计,深圳市龙岗区住房和建设局,用微信小程序怎么做网站,合肥工程建设信息平台一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
739A - Alyona and mex 二、解题报告
1、思路分析
我们考虑区间mex运算的值最大也就是区间长度#xff0c;所以我们最大值的上界就是所有区间中的最小长度#xff0c;假如记为mi
我们一定可以构造出答案…一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
739A - Alyona and mex 二、解题报告
1、思路分析
我们考虑区间mex运算的值最大也就是区间长度所以我们最大值的上界就是所有区间中的最小长度假如记为mi
我们一定可以构造出答案为mi的解吗
可以
我们让[0, mi - 1]这个序列循环直到构造出长度为n的数组arr
那么对于arr任意长度 mi 的区间的mex值都是mi
那么这道题就解决了
2、复杂度 时间复杂度 O(N M)空间复杂度O(1) 3、代码详解
#include bits/stdc.h
using i64 long long;
using i128 __int128;
using PII std::pairint, int;
const i64 inf 1e18 7, P 1e9 7;/*
min { r - l 1 }
*/
void solve() {int n, m;std::cin n m;int mi 1e9;for (int i 0, l, r; i m; i ) std::cin l r, mi std::min(mi, r - l 1);std::cout mi \n;for (int i 0; i n; i )std::cout (i % mi) \n[i n - 1];
}int main(int argc, char** argv) {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int _ 1;// std::cin _;while (_ --)solve();return 0;
}
