Day6总结

T1:

题目：

给你一个字符串s,t。s比t在某个位置多一个字符（其它的都相同），请你找出所有可能的位置。

思路：

先求两个字符串的hash数组，再枚举删除点，看s和t左右的哈希值是否均相同。若相同，则记录答案。

代码：

#include<bits/stdc++.h>
using namespace std;
unsigned long long BASE=131;
string s,t;
vector<int>ans;
unsigned long long a[1000005],b[1000005],pw[1000005];
int main(){
    cin>>s>>t;
    int n=s.size();
    s=" "+s;
    t=" "+t;
    pw[0]=1;
    for(int i=1;i<=n;i++)pw[i]=pw[i-1]*BASE;
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]*BASE+s[i];
        b[i]=b[i-1]*BASE+t[i];
    }
    for(int i=1;i<=n;i++){
        unsigned long long l=(a[i-1]);
        unsigned long long r=(a[n]-a[i]*pw[n-i]);
        unsigned long long ll=(b[i-1]);
        unsigned long long rr=(b[n-1]-b[i-1]*pw[n-i]);
        if(l!=ll||r!=rr){
        } else{
            ans.push_back(i);
        }
    }
    cout<<ans.size()<<"\n";
    for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";
    return 0;
}

T2:

题目：

给定一个仅由小写英文字母组成的字符串s，请你找出最长的字符串t，t要满足以下条件：

• t的长度不超过s的长度

• t回文

• t=a+b,a是s的前缀，b是s的后缀，且它们在s中没有重叠部分

思路：

可以把s分成三部分。x+mid+y,其中x+y可以组成一个回文串

现在要看是否可以在mid中扩展。

• 求mid的最长的回文前缀p1(暴力枚举，O(n^2),n<=5000,能过),最长回文后缀p2,看p1和p2那个更长，更长的记录为p.

答案为x+p+y

#include<bits/stdc++.h>
using namespace std;
int T;
string s;
void solve(){
    string s;
    cin>>s;
    int n=s.size();
    s=" "+s;
    int l=1,r=n;
    while(s[l]==s[r]&&l<r){
        l++;
        r--;
    }
    if(l>=r){
        for(int i=1;i<=n;i++)cout<<s[i];
        cout<<"\n";
        return;
    }
    int ansl=-1,ansr=-1;
    for(int i=l;i<=min(r,n);i++){
        int ll=l,rr=i;
        bool flag=1;
        while(ll<rr){
            if(s[ll]!=s[rr]){flag=0;break;}
            ll++;
            rr--;
        }
        if(flag){
            if(ansl==-1&&ansr==-1){
                ansl=l;
                ansr=i;
            } else{
                if(i-l+1>ansr-ansl+1){
                    ansl=l;
                    ansr=i;
                }
            }
        }
    }
    for(int i=r;i>=max(l,1);i--){
        int ll=i,rr=r;
        bool flag=1;
        while(ll<rr){
            if(s[ll]!=s[rr]){flag=0;break;}
            ll++;
            rr--;
        }
        if(flag){
            if(ansl==-1&&ansr==-1){
                ansl=i;
                ansr=r;
            } else{
                if(r-i+1>ansr-ansl+1){
                    ansl=i;
                    ansr=r;
                }
            }        
        }
    }
    for(int i=1;i<=n;i++){
        if(i<=l-1){
            cout<<s[i];continue;
        }
        if(i>=ansl&&i<=ansr){
            cout<<s[i];
            continue;
        }
        if(i>=r+1){
            cout<<s[i];
            continue;
        }
    }
    cout<<endl;
} 
int main(){
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
} 

T3:

题目：

给你n个字符串（只包含小写字母），找出有多少个(i,j)可以让s[i]+s[j]重排后能组成一个回文串。

思路：

两个字符串重排后能组成一个回文串，那么这26个字母的数量最多有一个为奇数。我们用pi来表示s[i]的26个字母的数量的奇偶性。

用异或更新即可。

再开一个map < int,long long >。

ans+=map[pi],这是和s[i]一样的数量都要加起来，但是不能重复。

map[pi]++

接下来枚举26个字母为奇数的情况，设枚举到了第c个字符，

ans+=mp[pi^(1<<c)],注意用unordered_map.

代码：

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100005]; 
unordered_map <int ,long long > mp;
long long ans = 0;
string s;
int main(){
	cin >> n;
	for(int i = 1 ;i <= n ;i++) {
		cin >> s;
		int now=0; 
		for(int j = 0;j < (int)s.size(); j++) {
			now = now ^ (1<<(s[j]-'a')); 
		}
		ans += mp[now];
        for(int c=0; c < 26; c++){
			ans += mp [now ^ (1<<c) ];
		}
		mp[now] ++; 
	}
	cout << ans;
	return 0;
} 

T4：

T5:

思路：对于输入的每一个排列求一个排列后的数组p，然后把这个数组存到set[j]中。对于每一个1~m,把数组p的第1~i存到set[j]中，方便后面查找。

对于每一个i,枚举美丽值j,看(a[1]...a[j])是否在set[j]中出现，如果出现，则记录答案并输出。

然后跳出循环。

出现的判断是：st[j].find(a[j][1]..a[j][i])!=st[j].end()

代码：

#include<bits/stdc++.h>
using namespace std;
int T;
int n,m;
int l[50005];
int a[50005][20];
int p[20];

int main(){
cin>>T;
while(T--){
    cin>>n>>m;
    set<vector<int> >st[20];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];p[a[i][j]]=j;
        }
        for(int j=1;j<=m;j++){

            st[j].emplace(p+1,p+j+1);
        }
    }
        for(int i=1;i<=n;i++){
            int q;
            q=0;
            for(int j=m;j!=0;j--)
                if(st[j].find(vector<int>(a[i]+1,a[i]+j+1))!=st[j].end())
                {
                    q=j;
                    break;
                }
            cout<<q<<" ";
        }
        cout<<"\n";
}
    return 0;
}

T6

代码：

#include<bits/stdc++.h>
using namespace std;
string s;
int ans;
int main(){
    cin>>s;
    bool flag=1;
    if(s.size()==1){
        cout<<"Impossible";
        return 0;
    } 
    for(int i=0;i+1<s.size();i++){
        if(s[i]!=s[i+1]){
            flag=0;
            break;
        } 
    }
    if(flag){
        cout<<"Impossible";
        return 0;
    }
    if(s.size()%2==1){
        cout<<2;
    } else{
        cout<<1; 
    }
    return 0;
}