本场 Rating：$\textcolor{#00C0C0}{1484} \rightarrow \textcolor{#00C0C0}{1591}(+107)$。
本场表现分：$\textcolor{#C0C000}{2206}$。
下场好像要上蓝了。
成功连续做出来三场 F。简称：三连击。
注意 ABC464F > ABC465F > ABC466F。
A Compromise
你说的对，但是 $0$ 不是负数（？）。
:::success[code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d",&n);
while(n--){
int t;
scanf("%d",&t);
if(t>=0){
puts("No");
return 0;
}
}
puts("Yes");
return 0;
}
|
:::
B Representative Balls
出出原。Auto timu Copying.
:::success[code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include<bits/stdc++.h>
using namespace std;
int clr[105];
int main(){
int n,m;
scanf("%d%d",&n,&m);
memset(clr,0xff,sizeof(clr));
for(int i=1;i<=n;i++){
int c,s;
scanf("%d%d",&c,&s);
clr[c]=max(clr[c],s);
}
for(int i=1;i<=m;i++){
printf("%d ",clr[i]);
}
return 0;
}
|
:::
C Count Close Pairs
交互出现在 abc 的 C 里，我怎么会做这样的梦。
如果你做过 Practice Contest 的 B Interactive Sorting，那你一定记得其中有一句话：
哎呦我去这个红字放在这里好吓人。
Please note that these are not beginner questions.
祖宗之法可以变！
由于点的位置单调递增，所以对于每个点，最后一个距离在 $1$ 以内的点的位置一定单调不降。维护一个双指针就可以做到线性。
:::success[code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n;
cin>>n;
int rgt=2,ans=0;
for(int i=1;i<=n-1;i++){
rgt=max(rgt,i+1);
while(rgt<=n){
cout<<"? "<<i<<" "<<rgt<<endl;
string s;
cin>>s;
if(s=="No")break;
rgt++;
}
ans+=rgt-i-1;
}
cout<<"! "<<ans<<endl;
//1.2 1.3 1.4 1.k
//2.k
return 0;
}
|
:::
D Placing Rooks
有史以来最简单的 D？
由于在添加之前要移除所有当前行和当前列的点，于是每行、每列最多只有一个点。暴力维护即可。也算是对神秘 C 的补偿吧。
:::success[code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<bits/stdc++.h>
using namespace std;
int col[300005];
int row[300005];
int main(){
memset(col,0xff,sizeof(col));
memset(row,0xff,sizeof(row));
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int r,c;
scanf("%d%d",&r,&c);
//找到当前列对应的行并清除
row[col[c]]=-1;
col[row[r]]=-1;
row[r]=c;
col[c]=r;
}
int ans=0;
for(int i=1;i<=n;i++)if(col[i]!=-1)ans++;
printf("%d",ans);
return 0;
}
|
:::
E Range Flip
如此小的 $K$ 很难让人不想到 $(N2^K)$ 级的做法，但是 $2 \times 10^5$ 摆在那里。
又根据 AtCoder 的传统，总复杂度一般是 $10^6 \sim 10^7$ 量级的。匹配到 $O(NK)$。
因此，考虑 DP。
设出状态 $dp_{i,j,k}$ 表示考虑到第 $i$ 张卡，已经有 $j$ 次反转，当前是否在一个被反转的段中。
:::success[code]
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
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
int a[200005],b[200005];
ll delta[200005];
ll dp[200005][11][2];//dp i,j,k:处理到第i张卡片，已反转j次，且不在/在某段里
int main(){
scanf("%d%d",&n,&k);
ll sum=0;
for(int i=1;i<=n;i++){
scanf("%d%d",a+i,b+i);
delta[i]=b[i]-a[i];
sum+=a[i];
}
memset(dp,-0x3f,sizeof(dp));
dp[0][0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);//不选
//选
if(j!=0)dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0])+delta[i];
}
}
ll ans=sum;
for(int i=0;i<=k;i++)ans=max(ans,max(dp[n][i][0],dp[n][i][1])+sum);
printf("%lld",ans);
return 0;
}
|
:::
F Many Mod Calculation
首先注意到 $a$ 只有单调递减的那一部分才有意义，否则若 $a_i \geq a_{i-1}$，那么前面模过来已经小于 $a_i$ 了，没有用。
设过滤后的 $a$ 数组为 $b$，其中 $|b|=k$。
我们写一个搜索函数 dfs(ll v,int i) 表示在值域 $[0,v]$ 中满足 $x \mod b_{i+1} \mod b_{i+2} \mod \ldots \mod b_{k} = 0$ 的个数。令 $dp_i$ 表示 dfs(b[i]-1,i)。
由于单调递减，不妨使用二分向后找到第一个可能产生有效模的位置。
则 $v+1$ 个数会被分为 $\lceil \frac{v+1}{b_j} \rceil$ 组。
其中 $\lfloor \frac{v+1}{b_j} \rfloor$ 是完整的几个以 $b_j$ 作为循环节的区间，每个区间答案即 $dp_j$。
剩下一个零块递归搜索。
由于每次都会进行取模，因此 dfs 运行一次的复杂度应当只有 $O(\log k \log V)$，足够快了。
:::success[code]
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
35
36
37
38
39
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>b;
int n;
ll x;
int k;
ll dp[200005];
//[0,V]中满足x%b[i]的%%%%%b[k-1]=0的个数
ll dfs(ll v,int i){
if(v<0)return 0;
if(i>=k)return 1;//到头了
auto it=lower_bound(b.begin()+i,b.end(),v,greater<ll>());
if(it==b.end())return 1;//%不了
int j=it-b.begin();
ll ans=(v+1)/b[j]*dp[j]+dfs((v+1)%b[j]-1,j+1);
return ans;
}
void solve(){
scanf("%d%lld",&n,&x);
b.clear();
for(int i=1;i<=n;i++){
ll ai;
scanf("%lld",&ai);
if(b.empty()||ai<b.back())b.push_back(ai);
}
k=b.size();
dp[k-1]=1;//0
for(int j=k-2;j>=0;j--)dp[j]=dfs(b[j]-1,j+1);
printf("%lld\n",dfs(x,0)-1);
}
int main(){
int T;
scanf("%d",&T);
while(T--){
solve();
}
return 0;
}
|
:::
G Segment Sum Constraints
怎么会是数位 DP 呢？