本场 Rating：$\textcolor{#00C0C0}{1239} \rightarrow \textcolor{#00C0C0}{1394}(+155)$。
本场表现分：$\textcolor{#C0C000}{2175}$。
今天做的好爽。也许是因为这场是蓝的（雾）。
A Decisive Battle
也许只是简单的字符统计罢了。
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;
int ec=0,wc=0;
for(char c:s){
if(c=='E')ec++;
else wc++;
}
if(ec>wc)puts("East");
else puts("West");
return 0;
}
|
B Crop
找到四个最左、最上、最右、最下的位置，作为边界输出即可。
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
|
#include<bits/stdc++.h>
using namespace std;
string s[55];
int main(){
int h,w;
cin>>h>>w;
getchar();
int up=99,left=99,down=-1,right=-1;
for(int i=1;i<=h;i++){
cin>>s[i];
for(int j=1;j<=w;j++){
if(s[i][j-1]=='#'){
up=min(up,i);
down=max(down,i);
left=min(left,j);
right=max(right,j);
}
}
}
for(int i=up;i<=down;i++){
for(int j=left;j<=right;j++){
cout<<s[i][j-1];
}
cout<<'\n';
}
return 0;
}
|
C Plumage Palette
按天数模拟操作维护当前每种颜色鸟的个数。
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
|
#include<bits/stdc++.h>
using namespace std;
int color[300005];
int a[300005],d[300005],b[300005];
vector<pair<int,pair<int,int>>>change;
int main(){
int n,m,ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d%d",a+i,d+i,b+i);
if(d[i]!=1)change.push_back({d[i],{a[i],b[i]}});
if(d[i]==1){
color[b[i]]++;
if(color[b[i]]==1)ans++;
}
else{
color[a[i]]++;
if(color[a[i]]==1)ans++;
}
}
printf("%d\n",ans);
int pointer=0;
sort(change.begin(),change.end());
for(int day=2;day<=m;day++){
while(change[pointer].first==day){
color[change[pointer].second.first]--;
if(color[change[pointer].second.first]==0)ans--;
color[change[pointer].second.second]++;
if(color[change[pointer].second.second]==1)ans++;
pointer++;
}
printf("%d\n",ans);
}
return 0;
}
|
D Celester
我的 dp 水平终究还是堪比一条蛆。
设计状态：$dp_{i,j}$ 表示考虑到第 $i$ 天，昨天天气为 $j$，从今天及以后的最大幸福度。分类讨论并转移。注意阴 $\rightarrow$ 晴的转移不要写错地方。
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
|
#include<bits/stdc++.h>
#define int long long
using namespace std;
//dp_i,j 表示考虑到第 i 天，上一天为晴/雨时后面的答案
int dp[200005][2];
int x[200005];
int y[200005];
string s;
int n;
int dfs(int p,int w){
if(p==n+1)return 0;
if(dp[p][w]!=-1)return dp[p][w];
if(s[p]=='S'){
return dp[p][w]=max(dfs(p+1,0)+y[p-1]*(w==1),dfs(p+1,1)-x[p]);
}else{
return dp[p][w]=max(dfs(p+1,1),dfs(p+1,0)-x[p]+y[p-1]*(w==1));
}
}
void solve(){
memset(dp,0xff,sizeof(dp));
cin>>n>>s;
s=' '+s;
for(int i=1;i<=n;i++)cin>>x[i];
for(int i=1;i<n;i++)cin>>y[i];
cout<<dfs(1,0)<<'\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--)solve();
return 0;
}
|
E Fill-Rect Query
我不行了。ABC 每场是一定要出一个离线倒序处理的板子吗？
于是满心欢喜地提交：
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>
#define fs first
#define sc second
using namespace std;
pair<pair<int,int>,char> op[200005];
string ans[1000005];
int fg[1000005];
int h,w,q;
int main(){
memset(fg,0xff,sizeof(fg));
cin>>h>>w>>q;
for(int i=1;i<=q;i++){
int r,c;
char x;
cin>>r>>c>>x;
op[i]={{r,c},x};
}
for(int t=q;t>=1;t--){
int r=op[t].fs.fs;
int c=op[t].fs.sc;
char x=op[t].sc;
for(int i=1;i<=r;i++){
for(int j=fg[i]+1;j<c;j++){
fg[i]=j;
ans[i]+=x;
}
}
}
for(int i=1;i<=h;i++){
for(int j=0;j<=fg[i];j++){
putchar(ans[i][j]);
}
for(int j=fg[i]+1;j<w;j++){
putchar('A');
}
putchar('\n');
}
return 0;
}
|
怎么 TLE 了两个点。
仔细研读会发现代码复杂度实际上是 $O(QH)$ 的，当 $Q = 2 \times 10^5,H = 10^6$ 时，无法通过。
于是有一个我称之为根号匀摊的方法：
Upd：其实这个东西就是根号分治。是我错了。我认罪。
当 $H<W$，取 $H$ 作为主维，复杂度 $O(QH)$；
当 $H \ge W$，取 $W$ 作为主维，复杂度 $O(QW)$。
总复杂度 $O(Q \times \min(H,W))=O(Q \times \sqrt{HW})$。可以通过。
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
#include<bits/stdc++.h>
#define fs first
#define sc second
using namespace std;
pair<pair<int,int>,char> op[200005];
string ans[1000005];
int fg[1000005];
int h,w,q;
int main(){
memset(fg,0xff,sizeof(fg));
cin>>h>>w>>q;
for(int i=1;i<=q;i++){
int r,c;
char x;
cin>>r>>c>>x;
op[i]={{r,c},x};
}
if(h<w){
for(int t=q;t>=1;t--){
int r=op[t].fs.fs;
int c=op[t].fs.sc;
char x=op[t].sc;
for(int i=1;i<=r;i++){
for(int j=fg[i]+1;j<c;j++){
fg[i]=j;
ans[i]+=x;
}
}
}
for(int i=1;i<=h;i++){
for(int j=0;j<=fg[i];j++){
putchar(ans[i][j]);
}
for(int j=fg[i]+1;j<w;j++){
putchar('A');
}
putchar('\n');
}
}else{
for(int t=q;t>=1;t--){
int r=op[t].fs.sc;
int c=op[t].fs.fs;
char x=op[t].sc;
for(int i=1;i<=r;i++){
for(int j=fg[i]+1;j<c;j++){
fg[i]=j;
ans[i]+=x;
}
}
}
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(fg[j]>=i-1)putchar(ans[j][i-1]);
else putchar('A');
}
putchar('\n');
}
}
return 0;
}
/*
3 2 3
2 2 B
3 1 C
1 2 D
*/
|
官解是二维前缀和。有我的好想吗？？？？？
Upd：原来只需要倒序扫描。我又唐了。
F Random Vault Heist
我做出来的第一道 F！！！
刻画期望总金额，即 $\sum$ （该箱子的金额 $\times$ 该箱子被打开的概率）。
一个箱子被打开，当且仅当前面所有箱子的总价值 $w(S)<X$，$S$ 是由前面一些箱子组成的一个原箱子集合的子集。
则箱子 $i$ 被打开的概率可以重新描述为所有集合 $S$ 使得 $S$ 为总集去掉 $i$ 得到的集合得到的一个子集，且 $w(S)<X$ 被取到的概率和。
假设已经选好了子集 $S$。剩下所有的箱子总金额就是 $w-w(S)$，恰好为上面那个东西的贡献。但是还要乘上系数 $\frac{1}{N \times \binom{N-1}{S}}$。
这时我们观察到 $N \le 40$，又要枚举子集。和我的折半搜索 + 双指针说去吧。
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
#include<bits/stdc++.h>
using namespace std;
constexpr int mod=998244353;
typedef long long ll;
struct ss{
ll val;
int vmm;//val % mod
bool operator <(ss a){
return val<a.val;
}
};
ll qmi(ll b,ll p){
ll res=1;
b%=mod;
while(p){
if(p&1)res=(res*b)%mod;
b=(b*b)%mod;
p>>=1;
}
return res;
}
ll calcinv(ll n){
return qmi(n,mod-2);
}
ll fact[105],invfact[105];
void init(){
fact[0]=invfact[0]=1;
for(int i=1;i<=100;i++)fact[i]=(fact[i-1]*i)%mod;
invfact[100]=calcinv(fact[100]);
for(int i=99;i>=1;i--)invfact[i]=(invfact[i+1]*(i+1))%mod;
}
ll comb(int n,int r){
if(r<0||r>n)return 0;
return fact[n]*invfact[r]%mod*invfact[n-r]%mod;
}
ll a[50];
ll fm[50];
int main(){
int n;
ll x;
ll sum=0;
scanf("%d%lld",&n,&x);
for(int i=0;i<n;i++){
scanf("%lld",a+i);
sum+=a[i];
}
ll summ=sum%mod;
init();
for(int c=0;c<n;c++){
ll fmi=n*comb(n-1,c)%mod;
fm[c]=calcinv(fmi);
}
int h=n>>1;
vector<vector<ss>>lft(h+1);
vector<vector<ss>>rgt(n-h+1);
for(int msk=0;msk<(1<<h);msk++){
ll w=0;
for(int j=0;j<h;j++){
if((msk>>j)&1)w+=a[j];
}
lft[__builtin_popcount(msk)].push_back({w,w%mod});
}
for(int msk=0;msk<(1<<(n-h));msk++){
ll w=0;
for(int j=0;j<(n-h);j++){
if((msk>>j)&1)w+=a[h+j];
}
rgt[__builtin_popcount(msk)].push_back({w,w%mod});
}
for(int c=0;c<=h;c++){
sort(lft[c].begin(),lft[c].end());
}
for(int c=0;c<=n-h;c++){
sort(rgt[c].begin(),rgt[c].end());
}
ll ans=0;
for(int cntl=0;cntl<=h;cntl++){
for(int cntr=0;cntr<=n-h;cntr++){
auto& suba=lft[cntl];
auto& subb=rgt[cntr];
if(suba.empty()||subb.empty())continue;
int sza=suba.size();
int szb=subb.size();
int rgtptr=0;
ll sumb=0;
ll calcfm=fm[cntl+cntr];
for(int j=sza-1;j>=0;j--){
ll lftm=suba[j].val;
ll lftmm=suba[j].vmm;
ll ava=x-lftm;
while(rgtptr<szb&&subb[rgtptr].val<ava){
sumb+=subb[rgtptr++].vmm;
}
if(rgtptr!=0){
ll q=(summ-lftmm+mod)%mod;
ll fz=((rgtptr*q-(sumb%mod))%mod+mod)%mod;
ans=(ans+fz*calcfm)%mod;
}
}
}
}
printf("%lld",ans);
return 0;
}
|
G Celester 2
惜败。