文中主要包括如下考点（CF题目做法灵活，只叙述自己赛时做法）
二分 模拟 排序 博弈论 数论 分治
A.Friendly Numbers
数学题，有性质(本题数据范围极小，$[x,x+100]$)
任何整数 $y$ 减去它的各位数字之和 $d(y)$，结果一定是 9 的倍数。
故优先判断是否是9的倍数，如果不是则直接 return
A题代码如下
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
34
| int get_d(int n){
int sum=0;
while(n>0){
sum+=n%10;
n/=10;
}
return sum;
}
void solve(){
int x;
cin>>x;
if(x%9!=0){
cout<<0<<endl;
return;
}
int count=0;
for(int y=x;y<=x+100;y++){
if(y-get_d(y)==x){
count++;
}
}
cout<<count<<endl;
}
signed main() {
fast;
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
B. Array and Permutation
本题需要用排列生成数组，注意到一个数在排列中只能出现一次，故只用查去连续重复后第一次出现时的相对位置，即当前数组中的数字对应的排列中的位置是否合理，记录对应排列位置中的最小值，若当前数组对应位置小于最小值，false.
采用哈希的方式记录位置，即当前值pos[p[i]]=i;
a.erase(unique(a.begin(),a.end()),a.end());
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
| void solve(){
int n;
cin>>n;
vector<int> p(n+1);
vector<int> a(n+1);
vector<int> pos(n+1);
for(int i=1;i<=n;i++){
cin>>p[i];
pos[p[i]]=i;
}
for(int i=1;i<=n;i++){
cin>>a[i];
}
a.erase(unique(a.begin()+1,a.end()),a.end());
bool flag=true;
int minn=0;
for(int i=1;i<a.size();i++){
if(minn>pos[a[i]]){
flag=false;
cout<<"NO"<<endl;
return;
}
minn=pos[a[i]];
}
cout<<"YES"<<endl;
}
|
C. Game with a Fraction
博弈题，放在坐标系中，即检查直线是否能在下方与 $p=2/3q$ 有交点
直线的原因在于，博弈中均采用对自己最有利的方向，二者与对手操作相反，最终形成一条$y=x$的曲线,即从初始位置出发沿y=x下降（建议画图）
为什么不能直接跳过 $p=\frac{2}{3}q$ 到下方保证 Alice 胜利？
假设 $tem = 3 \cdot p - 2 \cdot q$，且目前初始点在 $y=x$ 与 $y=\frac{2}{3}x$ 之间。
此时 Alice 目标是减小后跳过，即 Alice 操作 tem -= 3，Bob 操作 tem += 2。
假如 $tem \% 3 == 1$ 或者 $2$，Alice 可以跳过，但是 Bob 紧接着可以操作 +2。
若 Alice 操作后为 $-1$，则继续拉锯。然而 $p < q$，注定 Alice 先无法操作（因为 $q-p > 1$）。
若不在上述区间内，易得Alice必胜
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
| void solve(){
int p,q;
cin>>p>>q;
if(p*3==2*q){
cout<<"Bob"<<endl;
return;
}
if(p==0&&q==1){
cout<<"Alice"<<endl;
return;
}
if(3*p>2*q&&p<q){
cout<<"Bob"<<endl;
return;
}
else{
cout<<"Alice"<<endl;
return;
}
}
signed main() {
fast;
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
D. Another Problem about Beautiful Pairs
核心在于暴力枚举过程中的分冶优化 根号分治
在任何满足乘积限制的配对中，必然有一个数是非常小的，$ k < \sqrt{N} $，去遍历这个所有可能的小数，根据这个假设的小数可以通过遍历数组，遍历举j的位置推得较大的另一个数的位置，检测当前位置是否为这个小数.
在检测位置时需要留意，$j+$还是$j-$,我们并不知道举出来的二者谁是在左谁是在右
本题数据量在 $ 2 \cdot 10^5 \cdot 2 \cdot 10^5 $, sqrt 优化后可到$ 10^8 $极限通过
解题过程中发现过于极限TLE，摸排后遍历过程中可以同时探测两个方向
- 根号优化：专门针对带有 $x \cdot y = K$ 或者 $x \cdot y \le N$ 这类约束的题目.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void solve(){
int n;
cin>>n;
vector<int> a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
int ans=0;
int tem=sqrt(2*n)+1;
for(int k=1;k<=tem;k++){
for(int j=1;j<=n;j++){
int temp=a[j]*k;
if(temp<j&&a[j]>=k){
int i=j-temp;
if(a[i]==k) ans++;
}
if(j+temp<=n&&a[j]>k){
int m=j+temp;
if(a[m]==k) ans++;
}
}
}
cout<<ans<<endl;
}
|
聂菲斯可爱捏
