当前位置:网站首页>Delete subsequence < daily question >
Delete subsequence < daily question >
2022-07-06 04:31:00 【CTGU-Yoghurt】
subject :
Topic link : Sign in — major IT Written interview preparation platform _ Cattle from
The question is s Can delete t The maximum number of times
It's actually greedy Thought
Ideas 1: about s Take the largest in the string t character string
We can use an array to record t In a string
The order in which each character appears
Re traversal s Array
about s Each in the array t Some characters in
Count the number of occurrences
But pay attention to the design constraints
When traversing s Every time s The characters of
The number of occurrences should be less than that in
t The number of characters before the position in
In this way, we can count all the results that meet the conditions
( reason : It is equivalent to following t The order of strings is counted )
Ideas 2: Suppose we were s The string can be deleted at most n Substring
So how can we delete to achieve deletion n Secondary string Le
The answer is from No n The secondary string starts to be deleted
And No n All characters after the secondary character can be deleted ( It has no effect on the number of times )
Then delete n-1 Second string
Then delete it one by one
In this way, you can ensure that you can delete n All strings at once
( reason : Every deletion from the back to the front ensures
It will not affect the strings that meet the conditions above
Deleting in turn can ensure the maximum number of deletes )
Ideas 1 Code details :
#include<stdio.h>
#include<iostream>
using namespace std;
typedef long long ll;
#include<string.h>
using namespace std;
int n, m;
int pos[30], ans[30];
string s, t;
int main()
{
int ts;
cin >> ts;
while (ts--)
{
scanf("%d%d", &n, &m);
memset(pos, -1, sizeof(pos));
memset(ans, 0, sizeof(ans));// Each sample needs to initialize the array
cin >> s >> t;
for (int i = 0; i < m; i++) pos[t[i] - 'a'] = i;// Record t The order in which each character appears in the array
for (int i = 0; i < n; i++)
{
if (s[i] == t[0]) ans[0]++;// about t Count the number of the first character of
else
{
int step = pos[s[i] - 'a'];
if (step!= -1 && ans[step] < ans[step - 1])
ans[step]++;// Code key ! If s The character in exists in t in , And the number of occurrences is less than that of the character in t The previous character in . Then the number can be increased 1
}
}
printf("%d\n", ans[m - 1]);// The output finally meets t Number of strings of sequence conditions
}
return 0;
}
Ideas 2 Code ( Official code ):
#include <bits/stdc++.h> typedef unsigned long long ull; typedef long long ll; #define inf 0x3f3f3f3f #define rep(i, l, r) for (int i = l; i <= r; i++) #define nep(i, r, l) for (int i = r; i >= l; i--) void sc(int &x) { scanf("%d", &x); } void sc(int &x, int &y) { scanf("%d%d", &x, &y); } void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); } void sc(ll &x) { scanf("%lld", &x); } void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); } void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); } void sc(char *x) { scanf("%s", x); } void sc(char *x, char *y) { scanf("%s%s", x, y); } void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); } void out(int x) { printf("%d\n", x); } void out(ll x) { printf("%lld\n", x); } void out(int x, int y) { printf("%d %d\n", x, y); } void out(ll x, ll y) { printf("%lld %lld\n", x, y); } void out(int x, int y, int z) { printf("%d %d %d\n", x, y, z); } void out(ll x, ll y, ll z) { printf("%lld %lld %lld\n", x, y, z); } void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);} using namespace std; const int N=1e6+5,mod=998244353; int n,m; char s[N],t[N]; int main() { // freopen("1.in", "r",stdin); // freopen("1.out", "w", stdout); int ts;sc(ts);ast(ts,1,10000); int sum=0; while(ts--) { scanf("%d%d",&n,&m); sc(s+1);sc(t+1); ast(n,1,1000000);ast(m,1,min(n,26)); sum+=n; ast(sum,1,1000000); assert(strlen(s+1)==n);assert(strlen(t+1)==m); rep(i,1,n) ast(s[i],'a','z'); rep(i,1,m) ast(t[i],'a','z'); for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++) assert(t[i]!=t[j]); vector<int>vc[26]; rep(i,1,n) vc[s[i]-'a'].emplace_back(i); int ans=0; while(true) { bool flag=true; int las=n+1; for(int i=m;i>=1;i--) { while(vc[t[i]-'a'].size()&&vc[t[i]-'a'].back()>=las) vc[t[i]-'a'].pop_back(); if(vc[t[i]-'a'].empty()){flag=false;break;} las=vc[t[i]-'a'].back(); vc[t[i]-'a'].pop_back(); } if(!flag) break; ans++; } out(ans); } }
PS: The life and death of Gouli country depend on , Is it because of misfortune or good fortune !____ Lin Zexu 《 Go to the garrison entrance to occupy the family · second 》
边栏推荐
- [Chongqing Guangdong education] Suzhou University English film and Television Appreciation reference materials
- Implementation of knowledge consolidation source code 2: TCP server receives and processes half packets and sticky packets
- P2102 floor tile laying (DFS & greed)
- 1291_Xshell日志中增加时间戳的功能
- Sorting out the latest Android interview points in 2022 to help you easily win the offer - attached is the summary of Android intermediate and advanced interview questions in 2022
- How to solve the problem of slow downloading from foreign NPM official servers—— Teach you two ways to switch to Taobao NPM image server
- CertBot 更新证书失败解决
- The value of two date types is subtracted and converted to seconds
- The implementation of the maize negotiable digital warehouse receipt standard will speed up the asset digitization process of the industry
- Guitar Pro 8.0最详细全面的更新内容及全部功能介绍
猜你喜欢
CADD course learning (8) -- virtual screening of Compound Library
The implementation of the maize negotiable digital warehouse receipt standard will speed up the asset digitization process of the industry
电脑钉钉怎么调整声音
Jd.com 2: how to prevent oversold in the deduction process of commodity inventory?
查询mysql数据库中各表记录数大小
Etcd database source code analysis -- etcdserver bootstrap initialization storage
Meet diverse needs: jetmade creates three one-stop development packages to help efficient development
Implementation of knowledge consolidation source code 1: epoll implementation of TCP server
Redis - redis in action - redis actual combat - actual combat Chapter 1 - SMS login function based on redis - redis + token shared session application - with code
Recommendation system (IX) PNN model (product based neural networks)
随机推荐
Deep learning framework installation (tensorflow & pytorch & paddlepaddle)
Fedora/rehl installation semanage
Tengine kernel parameters
Is the mode of education together - on campus + off campus reliable
P3033 [usaco11nov]cow steelchase g (similar to minimum path coverage)
2327. 知道秘密的人数(递推)
Patent | subject classification method based on graph convolution neural network fusion of multiple human brain maps
Figure application details
电脑钉钉怎么调整声音
[face recognition series] | realize automatic makeup
Unity中几个重要类
Canal synchronizes MySQL data changes to Kafka (CentOS deployment)
软考 系统架构设计师 简明教程 | 总目录
Hashlimit rate control
Lombok原理和同时使⽤@Data和@Builder 的坑
颠覆你的认知?get和post请求的本质
1008 circular right shift of array elements (20 points)
R note prophet
P2102 floor tile laying (DFS & greed)
JVM garbage collector concept