2022杭电多校3

3. Cyber Language

这个纯纯签到了。

不过借此题学到了 stringstream 操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
void solve(){
string s;
getline(cin,s);
stringstream ss(s);
while(ss>>s)cout<<(char)toupper(s[0]);
cout<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
cin.get();
while(t--)solve();
}

12. Two Permutations

给定两个排列 ,每次操作都可以选择从 中选择最左端的数加入到序列 (刚开始为空)尾部中,最终会形成长度为 的序列 ,问有多少种方案使得

开始的想法是设 表示 中已经选择了前 个, 中已经选择了前 个的方案数。

如果 ,那么 就可以从 转移。

同理,如果 ,那么 就可以从 转移。

那么我们可以写出如下代码:

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;
#define ll long long
constexpr int mo=998244353;
int add(int a,int b){
ll res=0ll+a+b;
return res>mo?res-mo:res;
}
void solve(){
int n;
cin>>n;
vector<int> p(n+1),q(n+1),s(2*n+1);
for(int i=1;i<=n;i++)cin>>p[i];
for(int i=1;i<=n;i++)cin>>q[i];
for(int i=1;i<=2*n;i++)cin>>s[i];

vector<vector<int>> dp(n+1,vector<int>(n+1,0));
dp[0][0]=1;
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
if(i&&p[i]==s[i+j])dp[i][j]=add(dp[i][j],dp[i-1][j]);
if(j&&q[j]==s[i+j])dp[i][j]=add(dp[i][j],dp[i][j-1]);
}
}
cout<<dp[n][n]<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)solve();
}

不过这一份空间时间都是 的代码显然是过不去的。

接下来我们考虑如何优化,回顾题目,我们发现 是两个排列这个条件我们没有用上,是否可以从这里入手呢?仔细一想我们会发现对于每个 中最多匹配一次,那么就考虑 或者 匹配,状态如何转移。

(ps:这样的 只有一个),那么

同理,设 ,那么

这样的话时间上就被降到了 ,而且对于每个 ,最多转移两个 ,所以 数组最多用过 ,那我们就不用数组来保存 了,换成哈希表。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int mo=998244353;
int add(int a,int b){
ll res=0ll+a+b;
return res>mo?res-mo:res;
}
void solve(){
int n;
cin>>n;
vector<pair<int,int>> p(n+1),q(n+1);
vector<int> s(2*n+1);
for(int i=1;i<=n;i++)cin>>p[i].first;
for(int i=1;i<=n;i++)cin>>q[i].first;
for(int i=1;i<=2*n;i++)cin>>s[i];

for(int i=1;i<=n;i++)p[i].second=i;
for(int i=1;i<=n;i++)q[i].second=i;

sort(p.begin()+1,p.end());
sort(q.begin()+1,q.end());

struct cmp{
long long operator()(pair<int,int> x)const{
return 1ll*x.first*300217+x.second;
}
};
unordered_map<pair<int,int>,int,cmp> dp;
dp[{0,0}]=1;
for(int len=1;len<=2*n;len++){
int i=p[s[len]].second,j=len-i;
if(i<=len&&j<=n)dp[{i,j}]=add(dp[{i,j}],dp[{i-1,j}]);
j=q[s[len]].second;i=len-j;
if(j<=len&&i<=n)dp[{i,j}]=add(dp[{i,j}],dp[{i,j-1}]);
}
cout<<dp[{n,n}]<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)solve();
}

这份代码交上去还是T了,哈希表对于这道题来说常数还是有点大。

再来考虑如何优化,我们发现在中 中对于每个位置最多转移两个 ,并且转移的这两个 是上一个位置新转移到的,那么我们就可以像滚动数组那样优化一下就好啦。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int mo=998244353;
int add(int a,int b){
ll res=0ll+a+b;
return res>mo?res-mo:res;
}
void solve(){
int n;
cin>>n;
vector<pair<int,int>> p(n+1),q(n+1);
vector<int> s(2*n+1);

for(int i=1;i<=n;i++)cin>>p[i].first;
for(int i=1;i<=n;i++)cin>>q[i].first;
for(int i=1;i<=2*n;i++)cin>>s[i];

for(int i=1;i<=n;i++)p[i].second=i;
for(int i=1;i<=n;i++)q[i].second=i;

sort(p.begin()+1,p.end());
sort(q.begin()+1,q.end());

struct cmp{
long long operator()(pair<int,int> x)const{
return 1ll*x.first*300217+x.second;
}
};
unordered_map<pair<int,int>,int,cmp> pre,now;
pre[{0,0}]=1;
for(int len=1;len<=2*n;len++){
int i=p[s[len]].second,j=len-i;
if(i<=len&&j<=n)now[{i,j}]=pre[{i-1,j}];
j=q[s[len]].second;i=len-j;
if(j<=len&&i<=n)now[{i,j}]=add(now[{i,j}],pre[{i,j-1}]);
pre=now;
now.clear();
}
cout<<pre[{n,n}]<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)solve();
}
发布于

2022-07-30

更新于

2022-07-31

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...