A. 误报（False Alarm）
A. 误报（False Alarm）
https://codeforces.com/contest/2117/problem/A
时间限制：1 秒
内存限制：256 兆字节
Yousef 站在一个长走廊的入口处，面前有 n 扇门 ，排成一排，编号从 1 到 n。他需要按顺序依次通过这些门，最终到达出口（在第 n 扇门之后）。
每扇门都有一个状态：开启或关闭 。
-
如果门是开启的 ，Yousef 可以用 1 秒穿过它；
-
如果门是关闭的 ，Yousef 不能直接穿过 。
不过，Yousef 拥有一个特殊按钮 ，他最多可以使用一次。一旦按下按钮，所有关闭的门都会打开，并持续 x 秒 。
你的任务是判断：如果 Yousef 最多只能使用一次按钮，他是否能够顺利通过所有的门并到达出口？
输入格式：
输入的第一行是一个整数 t （1≤t≤1000 ）—— 测试用例的数量。
每个测试用例包含两行：
-
第一行是两个整数 n, x （1≤n,x≤10 ）—— 门的数量和按钮持续的时间；
-
第二行是 n 个整数 a1,a2,...,an ，其中 ai∈{0,1} ：
-
0 表示门是开启的；
-
1 表示门是关闭的。
-
保证每个测试用例中至少有一扇门是关闭的。
输出格式：
对每个测试用例，输出一行：
-
如果 Yousef 能够顺利通过所有门，输出 YES ；
-
否则输出 NO 。
你可以以任意大小写形式输出（例如 "YES", "Yes", "yEs" 都算正确）。
示例输入：
7
4 2
0 1 1 0
6 3
1 0 1 1 0 0
8 8
1 1 1 0 0 1 1 1
1 2
1
5 1
1 0 1 0 1
7 4
0 0 0 1 1 0 1
10 3
0 1 0 0 1 0 0 1 0 0示例输出：
YES
NO
YES
YES
NO
YES
NO示例解释：
第一个测试用例： 门的状态是 [0, 1, 1, 0]，按钮持续时间为 2 秒。
-
时间 0：第一扇门是开的，通过。
-
时间 1：第二扇门是关的，按下按钮，门打开。
-
时间 2：按钮效果还在，第三扇门也打开了。
-
时间 3：按钮效果结束，但第四扇门是开的，可以通过。
所以 Yousef 成功通过所有门，输出 YES。
第二个测试用例： 虽然按钮能维持 3 秒，但连续有太多关闭的门，不足以全部通过。
第三个测试用例： 可以在开始前就按下按钮，这样所有门都保持开启直到时间 x 结束，足够 Yousef 走完全程。
#include<stdio.h>
int main() {int N;scanf("%d",&N);while(N--){int n,x;scanf("%d %d",&n,&x);int a[n];for(int i=0;i<n;i++){scanf("%d",&a[i]);}int tag=0,flag=1;for(int i=0;i<n;i++){if(a[i]==1){if(tag==0||x>0){tag=1;}else {flag=0;break;}}if(tag==1)x--;}if(flag==1)printf("Yes\n");else printf("No\n");}return 0;
}B. 收缩操作
B. 收缩操作https://codeforces.com/contest/2117/problem/B
每个测试点的时间限制：2 秒
内存限制：256 兆字节
对于一个大小为 m 的数组 a，定义一次“收缩操作”如下：
-
选择一个下标 i（满足 2 ≤ i ≤ m−1），使得 a[i] > a[i−1] 且 a[i] > a[i+1]；
-
将 a[i] 从数组中删除。
我们将一个排列 p 的 得分 定义为：可以在该排列上最多执行多少次这种收缩操作。
Yousef 给了你一个整数 n。请你构造一个长度为 n 的排列 p，使得它的得分尽可能大。如果有多个答案，你可以输出任意一个。
注：排列（permutation）是指由 n 个不同的整数构成的数组，这些整数是从 1 到 n 的所有数字的一个排列。例如 [2,3,1,5,4] 是一个排列，但 [1,2,2] 不是（因为有重复元素），[1,3,4] 也不是（n=3，但包含了一个 4）。
输入格式：
输入的第一行是一个整数 t（1 ≤ t ≤ 10³）—— 测试用例的数量。
接下来 t 行，每行一个整数 n（3 ≤ n ≤ 2×10⁵）—— 排列的长度。
保证所有测试用例的 n 总和不超过 2×10⁵。
输出格式：
对每个测试用例，输出一行表示满足条件的排列 p₁, p₂, ..., pₙ。如果有多个解，可以输出任意一个。
示例输入：
2
3
6示例输出：
1 3 2
2 3 6 4 5 1示例解释：
第一个测试用例：
我们选择排列 p = [1, 3, 2]。
-
选择索引 2（值为 3），满足 a[i] > a[i−1] 且 a[i] > a[i+1]，将其删除，数组变成 [1, 2]。
-
此时不能再进行任何收缩操作。
这个排列的得分为 1，是最大可能值。另一个合法的答案是 [2, 3, 1]。
第二个测试用例：
我们选择排列 p = [2, 3, 6, 4, 5, 1]。
依次进行如下操作：
-
删除索引 5（值为 5），数组变为 [2, 3, 6, 4, 1]
-
删除索引 3（值为 6），数组变为 [2, 3, 4, 1]
-
删除索引 3（值为 4），数组变为 [2, 3, 1]
-
删除索引 2（值为 3），数组变为 [2, 1]
总共进行了 4 次收缩操作，这是最大可能值。
#include<stdio.h>
int main() {int N;scanf("%d",&N);while(N--){int a;scanf("%d",&a);int b[a];for(int i=0,j=2;j<=a;i++,j+=2){b[i]=j;}for(int i=a-1,j=1;j<=a;j+=2,i--){b[i]=j;}for(int i=0;i<a;i++){printf("%d ",b[i]);}printf("\n");}return 0;
}| C | 小红的数组查询（二） |
题目描述
小红拿到了一个长度为 10^100 的数组，其构成如下：
-
数组的第一个元素 a1=1 ；
-
对于 2≤i≤10^100 ，有：
ai=(ai−1+d)modp
换句话说，这个数组是一个以 1 为起点、公差为 d 、模 p 的线性同余序列（即类似于伪随机数生成器的形式）。
现在你需要回答 q 次查询：每次给出一个区间 [l,r] ，求出该区间内所有数组元素中有多少种不同的值 。
输入格式
第一行输入两个整数 d,p （1≤d,p≤10^9 ），表示数组的公差和模数。
第二行输入一个整数 q （1≤q≤10^5 ），表示查询次数。
接下来 q 行，每行两个整数 li,ri （1≤li≤ri≤10^18 ），表示每次查询的区间范围。
输出格式
对每个查询，输出一行一个整数，表示该区间内不同元素的数量。
示例输入
3 4
2
1 2
1 100000000000示例输出
2
4示例说明
第一次询问区间是 [1,2] ：
-
a1=1
-
a2=(1+3)mod4=0
所以有两个不同的元素：0 和 1。
第二次询问区间是 [1,10100] ，可以证明共有 4 种不同的元素。
#include<stdio.h>// 计算最大公约数
long long gcd(long long a, long long b) {if (b == 0) return a;return gcd(b, a % b);
}int main() {long long d, p;int q;scanf("%lld %lld %d", &d, &p, &q);// 计算循环节长度 Tlong long g = gcd(d, p);long long T = p / g;while (q--) {long long l, r;scanf("%lld %lld", &l, &r);long long len = r - l + 1;if (len >= T) {// 区间长度大于等于循环节，覆盖所有不同元素printf("%lld\n", T);} else {// 计算起始和结束位置在循环节中的偏移long long L0 = (l - 1) % T;long long R0 = (r - 1) % T;if (L0 <= R0) {// 区间在循环节内连续printf("%lld\n", R0 - L0 + 1);} else {// 区间跨越循环节边界printf("%lld\n", (T - L0) + (R0 + 1));}}}return 0;
}
