分类目录归档:字符串

洛谷 加分二叉树

题号:P1040
很有意义,想了不短时间,和一位群里的同学讨论了一下:代码如下:

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
int n;
struct re{
    int i;
    string s;
    re(){
       
    }
    re(int i,string s){
        this->i=i;
        this->s=s;
    }
    re operator = (const re r){
        this->i=r.i;
        this->s=r.s;
        return *this;
    }
}f[32][32];
int scores[35];
string construction(int num){
    string s="";
    while(num!=0){
        s.insert(0,1,'0'+num%10);
        num/=10;
    }
    s+=' ';
    return s;
}
re dfs(int l,int r){
    if(l==r)return re(scores[l],construction(l));
    if(l>r)return re(1,"");
    if(f[l][r].i!=0)return f[l][r];
    int mm=0;
    string s;
    for(int i=l;i<=r;i++){
        re re1=dfs(l,i-1);
        re re2=dfs(i+1,r);
        if(mm<re1.i*re2.i+scores[i]){
            mm=re1.i*re2.i+scores[i];
            s=construction(i)+re1.s+re2.s;
        }
    }
    return f[l][r]=re(mm,s);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>scores[i];
    re re1=dfs(1,n);
    cout<<re1.i<<endl;
    cout<<re1.s;
}

洛谷 【模板】KMP字符串匹配

题号:3375

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int _next[10000];
void buildNext(char * P){
    int m=strlen(P),j=0;
    int t=_next[0]=-1;
    while(j<m){
        if(t<0||P[j]==P[t]){
            _next[++j]=++t;
        }else
            t=_next[t];
    }
}
void KMP(char * P,char * T){
    int n=strlen(T),i=0;
    int m=strlen(P),j=0;
    while(i<n){
        if(j<0||T[i]==P[j]){
            i++;j++;
        }else
            j=_next[j];
        if(j==m){
            printf("%d\n",i-j+1);
            j=_next[j];
        }
    }
}
int main(){
    char P[10000],T[20000000];
    scanf("%s%s",T,P);
    buildNext(P);
    int lenP=strlen(P);
    KMP(P,T);
    for(int i=1;i<=lenP;i++){
        printf("%d ",_next[i]);
    }
}

KMP算法经典代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int _next[10000];
void buildNext(char * P){
    int m=strlen(P),j=0;
    int t=_next[0]=-1;
    while(j<m){
        if(t<0||P[j]==P[t]){
            _next[++j]=++t;
        }else
            t=_next[t];
    }
}
int KMP(char * P,char * T){
    int n=strlen(T),i=0;
    int m=strlen(P),j=0;
    while(i<n&&j<m){
        if(j<0||T[i]==P[j]){
            i++;j++;
        }else
            j=_next[j];
    }
    return i-j;
}

洛谷 拼数

题号:1012

这题也挺逗的,没有想到能这么做……
看了别人的题解……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
bool cmp(string & s1,string & s2){
    return s1+s2>s2+s1;
}
int main(){
    int n;
    cin>>n;
    string s[20];
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    sort(s,s+n,cmp);
    for(int i=0;i<n;i++){
        cout<<s[i];
    }
}