// Problem: // P1712 [NOI2016] 区间// // Contest: Luogu// URL: https://www.luogu.com.cn/problem/P1712// Memory Limit: 250 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpedit

题目 题意 在数轴上有 n n n 个闭区间从 1 1 1 至 n n n 编号，第 i i i 个闭区间为 [ l i , r i ] [l_i,r_i] [li​,ri​]现在要从中选出 m m m 个区间，使得这 m m m 个区间共同包含至少一个位置。换句话说，就是使得存在一个 x x x ，使得对于每一个被选中的区间 [ l i , r i ] [l_i,r_i]

测试时已经想到是二分了 可是想了很长时间贪心最后都被自己否定了 正解是 dp 不难想的样子? 有二分的代码不好调...... #include <cstdio>#include <cstring> #include <iostream>#include <algorithm>using namespace std;const int MAXN = 2e5+10;i

【NOI2016模拟6.20】没有强联通分量的无聊世界 Description Input Output Sample Input 3 4 1 2 1 3 2 3 3 1 Sample Output 1 Data Constraint 题解 可以将它拓扑出来，然后然后~~ 就没有然后了 所以，我们要换一种思路。 注意 性质 DAG的性质是：一个点的拓扑序只会向比它编号大连边

传送门 比较容易想到的是, l[i], r[i] 表示 i 的左右 有多少个 AA 串 那么答案就是  , 于是已经可以 n^2 过 95 了 我们考虑批量处理长度为 L 的AA串, 每隔 L 个位置打一个标记 然后对于两两标记之间前后求一个 LCP(Hash + 二分) 画个图, 就可以看出, 哪些区间是有贡献的, 差分一下就可以了 #include<bits/stdc++.h>#

传送门 考虑什么样的 x y \frac{x}{y} yx​ 可以成为纯循环小数 设其循环节为 L L L，那么有 x y ∗ k L − x y \frac{x}{y}*k^L-\frac{x}{y} yx​∗kL−yx​ 为整数 每一对贡献在 g c d ( x , y ) = 1 gcd(x,y)=1 gcd(x,y)=1 的时候统计，于是上面这个条件可以转换为 ∃ L , s

Description Input Output 第i行一个整数表示第i个询问的答案 Sample Input 6 3 3 aaabbb 2 3 2 5 7 10 1 2 1 3 2 4 2 5 3 6 1 3 2 2 3 1 Sample Output 362 161 22 Data Constraint n<=100000,s<=5,t<=16

Description 在数轴上有 n个闭区间 [l1,r1],[l2,r2],…,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。 对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li