B

数学
有若干区间长度为k的区间,对于第i个区间给定$a_i \;[1,10^k]$,$b_i \; [0,9]$
求一共有多少个数满足第i个区间能被$a_i$整除,不以$b_i$开头的数

原来以为是数位dp,后来发现就是一个简单的统计
对于每个区间,满足被$a_i$整除的有$(10^k - 1)/a[i] + 1$ 个
然后减去以$b_i$开头的有: $(R-L)/a[i] + 1$ 个,其中L为满足条件的大于等于$b_i 10^{k-1}$的第一个数,R为满足条件小于$(b_i+1) 10^{k-1}$ 的第一个数
每个区间是独立的,我们将最后答案乘起来即可。

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
33
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL mod = 1e9 + 7;
const int maxn = 1e5 + 10;
LL a[maxn],b[maxn],p[20];


int main()
{
//freopen("test.txt","r",stdin);
int n,k;
scanf("%d %d",&n,&k);
int t = n/k;
for(int i=0;i<t;++i) scanf("%lld",a+i);
for(int i=0;i<t;++i) scanf("%lld",b+i);
p[0] = 1;
for(int i=1;i<10;++i) p[i] = p[i-1]*10;
LL res = 1;
for(int i=0;i<t;++i)
{
LL cur = (p[k]-1)/a[i]+1;
LL L = (b[i]*p[k-1]/a[i]) * a[i],R = ((b[i]+1)*p[k-1]/a[i]) * a[i];
if(L < b[i]*p[k-1]) L += a[i];
if(R >= (b[i]+1)*p[k-1]) R -= a[i];
if(R-L>=0) cur -= (R-L)/a[i] + 1;
res = res*cur%mod;
if(res == 0) break;
}
printf("%I64d\n",res);
return 0;
}

C

有两个玩家,和n个(n为偶数)互异的位置,两个玩家依次去除一个位置,直到只剩下两个位置
第一个玩家应该使这两个位置尽量近,第二个玩家应该使其尽量远
两个玩家每次都选择去掉最优的位置,问最后的距离是多少

极大极小搜索
博弈

看似是一道很明显的极大极小搜索,然而n太大,然后就是推结论
答案为$min(x_{i+n/2} - x_i)$
证明过程

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int a[maxn];


int main()
{
//freopen("test.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d",a+i);
sort(a,a+n);
int ans = INF;
for(int i=0;i<n;++i)
{
if(i+(n/2) < n) ans = min(ans,a[i+(n/2)]-a[i]);
else break;
}
printf("%d\n",ans);
return 0;
}