everyday two problems / 3.11

7日共14题，因为3.14两题相同，所以实际总共13题

13道题分为难易两部分，没有按照时间顺序排列题目

A.易:

1.覆盖数字的数量

题意:

给出一段从A - B的区间S（A，B为整数）

这段区间内的整数可以随便使用任意次

再给出一段从X - Y的区间T

问用区间S中的整数做加法

可以覆盖区间T中多少个不同的整数

1<= A, B, X, Y <= 1e18

解法:

没有什么想法，我们观察样例

A = 8 B = 10 X = 3 Y = 20

由区间S凑成的整数为

8 9 10

16 17 18 19 20

我们继续列举发现继续凑成的整数为

24 25 26 27 28 29 30

32 33 34 35 36 37 38 39 40

可以发现会凑成许多段连续区间

每段区间的长度呈等差数列

并且如果A != B无限枚举下去最后一定会存在N

当Z >= N时，是一定可以凑出Z的

样例中的 N 即为40

我们继续思考可以发现 N 是满足下面条件的最小的数

N / A = N / B + 1

反映到上面列举的区间，即第4段中的40同时出现在了第5段中

那么必然有第5段中的某个数Z也出现在了第6段中 ......

所以后面所有Z >= 40都是能够被凑出来的

于是直接二分找出N，再算一下等差数列求和即可

 1 #include <cstdio>
 2 
 3 typedef long long ll;
 4 
 5 int Case;
 6 
 7 ll l, r, a, b, d, ans;
 8 
 9 ll max(ll x, ll y) {
10     return x > y ? x : y;
11 }
12 
13 ll calc(ll x) {
14     ll L = 1, R = 1e18, mid, N, res = 0;
15     while(L <= R) {
16         mid = (L + R) >> 1;
17         if(mid / a > mid / b) N = mid, R = mid - 1;
18         else L = mid + 1; 
19     } 
20     if(x >= N) res += x - N, x = N;
21     res += ((x / b + 1) * d + 2) * (x / b) / 2 + max(0ll, x - (x / b + 1) * a);
22     return res;
23 }
24 
25 int main() {
26     scanf("%d", &Case);
27     while(Case --) {
28         scanf("%lld %lld %lld %lld", &a, &b, &l, &r);
29         d = b - a, printf("%lld
", calc(r) - calc(l - 1));
30     }
31     return 0;
32 }

View Code

2.Lucky Permutation Triple

题意:

对0到(n-1)这n个数进行全排列

请找出三个全排列a、b、c

使得“a与b的对应元素的和”与“c的对应元素”对模n同余

无解输出-1

解法:

纯靠手感or脑洞

若n为奇数，则2, 4, 6, ..., 2n

在膜n意义下为2, 4, ..., n - 1, 1, 3, ... n - 2, 0

这样就直接凑出了0 - (n - 1)

若n为偶数，注意到题意

设Sa, Sb, Sc为abc三个排列的元素之和

此时应满足 (Sa + Sb) % n = Sc % n

然而Sa = Sb = Sc = (n - 1) * n / 2

此时等式左侧为0，右侧要想为0，必须使n - 1为偶数

因为n为偶，所以n - 1为奇数，右侧不可能为0

所以此时无解输出 -1

 1 #include <cstdio>
 2 
 3 int n;
 4 
 5 int main() {
 6     scanf("%d", &n);
 7     if(n & 1) {
 8         for(int i = 0;i < n;i ++)
 9             printf("%d ", i);
10         printf("
");
11         for(int i = 0;i < n;i ++)
12             printf("%d ", i);
13         printf("
");
14         for(int i = 0;i < n;i ++)
15             printf("%d ", 2 * i % n);
16     }
17     else puts("-1");
18     return 0;
19 }

View Code