注意到 Eason_Tao 在本周四说过：
abc 的质量越来越低了，要想打可以去 VP 之前的六题场。
― tyx
坏了是真的。
本场 Rating: $800 \rightarrow 965(+165)$。
Fun Fact：本场比赛所有题目均以字母 C 开头。
A Chompers
你不过 T1 你过啥题啊。
1
2
3
4
5
6
7
8
9
|
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
int t;
cin>>s>>t;
for(int i=t;i<s.length()-t;i++)putchar(s[i]);
return 0;
}
|
B Count Adjacent Cells
我说这题有数论做法有没有懂的。
但由于上次被 J 组 T2 的模拟 or 数论整怕了，我还是模拟吧。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include<bits/stdc++.h>
using namespace std;
int h,w;
int chk(int x,int y){
if(x>=1&&x<=h&&y>=1&&y<=w)return 1;
return 0;
}
int main(){
cin>>h>>w;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
int cnt=0;
cnt+=chk(i+1,j);
cnt+=chk(i,j+1);
cnt+=chk(i-1,j);
cnt+=chk(i,j-1);
printf("%d ",cnt);
}
putchar('\n');
}
return 0;
}
|
C C Stands for Center
注意到每个中心为 C 的子串都是以一个 C 为中心向外扩展的。对于每个 C 统计可以扩展到的字符串个数即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
long long ans=0;
for(int i=0;i<s.length();i++){
if(s[i]=='C'){
ans+=min(i+1,(int)s.length()-i);
}
}
printf("%lld",ans);
return 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
|
#include<bits/stdc++.h>
using namespace std;
priority_queue<int>xd;
priority_queue<int,vector<int>,greater<int>>dd;
int main(){
int x;
scanf("%d",&x);
xd.push(x);
int q;
scanf("%d",&q);
while(q--){
int a,b;
scanf("%d%d",&a,&b);
if(a<xd.top())xd.push(a);
else dd.push(a);
if(b<xd.top())xd.push(b);
else dd.push(b);
while(dd.size()>xd.size()){
xd.push(dd.top());
dd.pop();
}
while(xd.size()-dd.size()>1){
dd.push(xd.top());
xd.pop();
}
printf("%d\n",xd.top());
}
return 0;
}
|
E Count 123
容斥典题。
容易建模为一个插板的模型： $X_2$ 个 $2$ 隔出了 $X_2+1$ 个段，每个段里只有 $1$ 或 $3$。
再结合惊人的注意力，得到答案为
$$\sum_{i=0}^{\min(X_1,X_2+1,X_3)} (-1)^i \binom{X_2+1}{i} \binom{X_1+X_2-i}{X_2} \binom{X_2+X_3-i}{X_2}$$我真牛。
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
|
#include<bits/stdc++.h>
using namespace std;
constexpr int mod=998244353;
typedef long long ll;
ll qmi(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll fact[2000005],invfact[2000005];
ll comb(int n,int k){
if(k<0||k>n)return 0;
return fact[n]*invfact[k]%mod*invfact[n-k]%mod;
}
int main(){
int x1,x2,x3;
scanf("%d%d%d",&x1,&x2,&x3);
int maxt=max({x1+x2,x2+x3});
fact[0]=1;
for(int i=1;i<=maxt;i++)fact[i]=fact[i-1]*i%mod;
invfact[maxt]=qmi(fact[maxt],mod-2);
for(int i=maxt-1;i>=0;i--)invfact[i]=invfact[i+1]*(i+1)%mod;
int lim=min({x1,x2+1,x3});
ll ans=0;
for(int i=0;i<=lim;i++){
ll t=comb(x2+1,i)*comb(x1+x2-i,x2)%mod*comb(x2+x3-i,x2)%mod;
if(i&1)ans=(ans-t+mod)%mod;
else ans=(ans+t)%mod;
}
printf("%lld",ans);
return 0;
}
|
F Critical Misread
abc 考 AC 自动机是何意味呢。
G Children Yearn for the Evil Kindergarten
abc 考斜率优化是何意味呢。