口胡笔记_ AtCoder ARC 091 [清奇脑回路, 数学]

据说这是一场数学大赛

C

线段树套线段树矩形异或求和

水题…画个图就明白了, 对一个点早成影响的只有9个点, 然后xjb分类讨论一下

稍微一画就明白了...

注意特判只有一个格子的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
int main()
{
LL n, m;
scanf("%lld%lld", &n, &m);
if (n == 1 && m == 1)
puts("1");
else if (n == 1 || m == 1)
printf("%lld", max(0ll, n * m - 2));
else
printf("%lld", (max(0ll, n - 2) * max(0ll, m - 2)));
return 0;
}

D

水题+1

枚举除数, 对于每一个除数$b$我们可以把被除数$a$可能出现的范围划分为$\lfloor n /b \rfloor$个区间, 而在每个区间都有一些合法的$a$, 而且他们是连续的(因为余数大于等于$k$, 所以$a$可能的区域就是 [每一个区间的左端点$ + k, $右端点​] ), 那么我们就可以直接枚举每一个可能的除数, 然后计算每一个被除数可能对应的除数了

看看这个就明白了...

最后别忘了还有没有除尽的零散块, 以及$k = 0$的时候要特判一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
int main()
{
freopen("in.in", "r", stdin);
int n, k;
LL ans = 0;
scanf("%d%d", &n, &k);
for (int i = k + 1; i <= n; i++) // 枚举的是除数
ans += (n / i) * (i - k) + max(0, ((n % i) - (k == 0 ? k : (k - 1)))); // n / i: 一共可以分成多少个格子, (n % i - k): 最后那个零散的格子提供的贡献
printf("%lld", ans);
return 0;
}

/*
10: 0
9: 1
8: 2
7: 3
6: 4
5: 5
4: 6
3: 7
2: 8
1: 9
0: 10
*/

E

待填

F

待填

By Cansult