1.不重最长子串

Description

给定一个字符串 ss，请你找出其中不含有重复字符的最长子串的长度。

Format

Input

一行，一个字符串 s，长度在 0∼50000 之间，由英文字母、数字和空格组成。

Output

输出一个整数，为不含有重复字符的最长子串的长度。

Samples

输入数据 1

abcabcbb

输出数据 1

3

Hint1

因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入数据 2

bbbbb

输出数据 2

1

Hint2

因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入数据 3

pwwkew

输出数据 3

3

Hint3

因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

Limitation

1s, 1024KiB for each test case.

解题思路：

双指针算法，枚举左边，分配右边，找到最长的

代码实现

#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
int main(){
    string n;
    getline(cin,n);
    int ans=0;
    unordered_map<char, int> a;
    for(int i=0,j=0;j<n.size();j++){
        a[n[j]]++;
        while(a[n[j]]>1){
            a[n[i++]]--;
        }
        ans=max(ans,j-i+1);
    }
    cout<<ans;
    return 0;
}

2. 小J的加密算法

Description

上大学了，小J学会了一种加密算法，这种算法可以根据一个行数 m，将一个字符串进行重新排列，变成无法读懂的密文。

例如：给定一个字符串 "PAYPALISHIRING"，行数 3，将其进行从上到下，从左到右的Z字形排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

Format

Input

一个由英文字母及英文标点符号组成的字符串 ss 及一个行数 m(1≤m≤1000)，ss 的长度在 1∼1000 之间。

Output

输出加密字符串

Samples

输入数据 1

PAYPALISHIRING 3

输出数据 1

PAHNAPLSIIGYIR

输入数据 2

PAYPALISHIRING 4

输出数据 2

PINALSIGYAHRPI

Hint2

P     I    N
A   L S  I G
Y A   H R
P     I

输入数据 3

A 1

输出数据 3

A

输入数据 4

hello,world! 3

输出数据 4

horel,ol!lwd

Limitation

1s, 1024KiB for each test case.

解题思路：

重点在于找到规律

代码实现：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string n;int m;
    cin>>n;
    n.insert(n.begin(),'0');
    cin>>m;
    if(m==1){
        for(int i=1;i<n.size();i++)
        cout<<n[i];
    }
    else {
        for(int i=1;i<=m;i++){
        for(int j=i;j<n.size();j+=2*m-2){
        if(i==1||i==m){    
            cout<<n[j];
        }
        else {
            cout<<n[j];
            if(j+2*m-2-(i-1)*2<n.size()){
                cout<<n[j+2*m-2-(i-1)*2];
            }
            
        }
    }    
}
    }

    
    return 0;
}

3. 数列的个数

Description

给出两个整数 n, mn,m。问有多少个长度为 nn 的序列 AA，满足以下条件：

• 1 ≤ A_i ≤ m(i = 1, 2, · · · , n)1≤Ai​≤m(i=1,2,⋅⋅⋅,n)

• \forall i\in [1, n-1]∀i∈[1,n−1], A_{i+1}Ai+1​ 是 A_iAi​ 的倍数。

由于答案可能很大，所以你只需要输出答案对 998244353998244353 取模的结果。

Format

Input

输入只有一行，两个整数 n, m(1\le n, m \le 2 \times 10^5)n,m(1≤n,m≤2×105)。

Output

输出只有一行，输出方案数。

Samples

输入数据 1

3 4

输出数据 1

13

输入数据 2

20 30

输出数据 2

71166

输入数据 3

200000 200000

输出数据 3

835917264

Limitation

1s, 1024KiB for each test case.

解题思路：

这一题我们要从后往前去看，可以看出有组合数的规律

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N = 998244353;
int dp[20]={1},n,m;
int solve(int k){
    int ans = 1;
    for(int i = 2;i*i<=k;i++){
        if(k%i) continue;
        int c=0;
        while(k%i==0) k/=i,c++;
        ans = ans *1LL*dp[c]%N;
    }
    if(k>1)ans = ans *1LL*dp[1]%N;
    return ans;
} 
int main(){
    int ans = 0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=19;j++)
            (dp[j]+=dp[j-1])%=N;
    for(int i=1;i<=m;i++)
        (ans+=solve(i))%=N;
    cout<<ans;
    return 0;
}

4. 匹配正则表达式

Description

给你一个字符串 ss 和一个字符规律 pp，请你来实现一个支持 . 和 * 的正则表达式匹配。

• . 匹配任意单个字符

• * 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 ss 的，而不是部分字符串。

Format

Input

多组测试数据 每组数据一行，两个字符串 ss(长度小于20) 和 pp(长度小于30)，ss 只包含小写字母，pp 包含小写字母以及 . 和 *。

Output

每组数据输出一行，如果 pp 能够匹配 ss，则输出 Yes，否则输出 No。

Samples

输入数据 1

aa a
aa aa
aa a.
aa b*aa
aa c*a.
aaaaab a*b

输出数据 1

No
Yes
Yes
Yes
Yes
Yes

Limitation

1s, 1024KiB for each test case.

 代码实现：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
string s,p;
LL dp[50][50];
bool check(int i,int j){
    if(i==0) return false;
    if(p[j-1]=='.') return true;
    return s[i-1]==p[j-1];
}
int main(){
    while(cin>>s>>p){
        int m=s.size();
        int n=p.size();
        memset(dp,0,sizeof dp);
        dp[0][0]=1;
        for(int i=0;i<=m;i++)
            for(int j=1;j<=n;j++)
                if(p[j-1]=='*'){
                    dp[i][j] |=dp[i][j-2];
                    if(check(i,j-1)){
                        dp[i][j] |=dp[i-1][j];
                    }
                }else if(check(i,j))
                    dp[i][j]|=dp[i-1][j-1];
    if(dp[m][n]) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    }
    return 0;
}