康复训练 洛谷题单 Part 1.3-1.4 字符串基础；函数，递归及递推

我觉得我还是尽量少水博客 这种水专题两三个并一块发。
最近再搬家，效率比较低哈哈，有时间就抽空做做题，这应该是前面基础部分最后一块了，后面就是基础算法了。

$Part1.3$ 字符串基础

P5015 [NOIP2018 普及组] 标题统计

传送门
这题在现场哈哈 不过没啥印象了 要是不加题头我都不知道我考过这道题

#include
using namespace std;
char str[100];
int l,ans;
int main(){
    gets(str);
    l=strlen(str);
    for(int i=0;i<l;i++){
        if(str[i]>='A'&&str[i]<='Z')ans++;
        else if(str[i]>='a'&&str[i]<='z')ans++;
        else if(str[i]>='0'&&str[i]<='9')ans++;
    }
    cout<<ans<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

P1055 [NOIP2008 普及组] ISBN 号码

传送门
擦 题真长 第一遍读题没看到余数为$10$是$X$

#include
using namespace std;
char chr[100];
int now,ans;
int main(){
    scanf("%s",chr);
    int l=strlen(chr);
    for(int i=0;i<l-1;i++){
        if(chr[i]>='0'&&chr[i]<='9')(ans+=(chr[i]-'0')*(++now))%=11;
    }
    if(ans==10){
        if(chr[l-1]=='X')puts("Right");
        else{
            chr[l-1]='X';
            puts(chr);
        }
    }
    else{
        if(ans==chr[l-1]-'0')puts("Right");
            else{
            chr[l-1]=ans+'0';
            puts(chr);
        }
    }
}
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

P1308 [NOIP2011 普及组] 统计单词数

传送门
$md$这题差点没做出来，丢大人 思路就是先给字符串前面加个空格 然后找空格就行了 其实应该复习一下$KMP$的 但是我忘了 留着后面一起复习吧

#include
using namespace std;
char str[20],s[1000100];
int l1,l2,num,sum;
int main(){
    gets(str);gets(s+1);s[0]=' ';
    l1=strlen(str),l2=strlen(s);
    for(int i=0;i<l1;i++)if(str[i]>='A'&&str[i]<='Z')str[i]=str[i]-'A'+'a';
    for(int i=0;i<l2;i++)if(s[i]>='A'&&s[i]<='Z')s[i]=s[i]-'A'+'a';
    for(int i=0;i<l2;i++){
        if(s[i]==' '){
            if(s[i+l1+1]==' '){
                int flag=0;
                for(int j=i+1;j<=i+l1;j++){
                    if(s[j]!=str[j-i-1]){
                        flag=1;break;
                    }
                }
                if(!flag){
                    sum++;
                    if(!num)num=i+1;
                    i+=l1;
                }
            }
        }
    }
    if(!num)puts("-1");
    else printf("%d %d\n",sum,num-1);
}
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

P2010 [NOIP2016 普及组] 回文日期

传送门
这我为啥要拿字符串做啊
话说 又一道考场原题 没印象呢

#include
using namespace std;
int a,b,ans,now,nowm;
int mon[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int res(int x){
    return x*10000+x%10*1000+x/10%10*100+x/100%10*10+x/1000;
}
bool check(int x){
    if(x%4!=0)return false;
    else if(x%100==0&&x%4!=0)return false;
    return true;
}
int main(){
    cin>>a>>b;
    for(int i=a/10000;i<=b/10000;i++){
        now=res(i),nowm=now/100%100;
        if(now<a||now>b)continue ;
        if(nowm>12||nowm<1)continue;
        if(check(i))mon[2]=29;
        if(now%100>0&&now%100<=mon[nowm])ans++;
        mon[2]=28;
    }
    cout<<ans<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

P1012 [NOIP1998 提高组] 拼数

传送门
$string$一步排序解决

#include
using namespace std;
string s[30];
int n;
bool cmp(string a, string b){
    return a+b>b+a;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i];
    sort(s+1,s+1+n,cmp);
    for(int i=1;i<=n;i++)cout<<s[i];
    cout<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

P5587 打字练习

传送门
$md,$范文还有退格键就离谱，做了好久

#include
using namespace std;
char s1[200010],s2[200010],chr;
int p1,p2,l1,l2,ans,T;
bool ept1(){return s1[p1]==10;}
void pop1(){p1--;}
void ins1(char chr){s1[++p1]=chr;}
bool ept2(){return s2[p2]==10;}
void pop2(){p2--;}
void ins2(char chr){s2[++p2]=chr;}
int main(){
    chr=getchar();
    while((chr<'a'||chr>'z')&&chr!='.')chr=getchar();
    s1[0]=s2[0]=10;
    while(1){
        if(chr=='E')break;
        if(chr=='<'){if(!ept1())pop1();}
        else ins1(chr);
        chr=getchar();
    }
    while((chr<'a'||chr>'z')&&chr!='.')chr=getchar();
    while(1){
        if(chr=='E')break;
        if(chr=='<'){if(!ept2())pop2();}
        else ins2(chr);
        chr=getchar();
    }
    int s=0,w=1;chr=getchar();
    while(chr<'0'||chr>'9')chr=getchar();
    while(chr>='0'&&chr<='9'){s=(s<<3)+(s<<1)+(chr&15);chr=getchar();}
    T=s*w;
    while(l1<=p1&&l2<=p2){
        if(s1[l1]==10&&s2[l2]==10){l1++,l2++;continue;}
        if(s1[l1]==10&&s2[l2]!=10){while(s2[l2]!=10)l2++;l1++,l2++;continue;}
        if(s2[l2]==10&&s1[l1]!=10){while(s1[l1]!=10)l1++;l1++,l2++;continue;}
        if(s1[l1]==s2[l2])ans++;
        l1++,l2++;
    }
    printf("%d\n",(int)((ans*60.0)/T+0.5));
}
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

$Part1.4$ 函数，递归及递推

P1028 [NOIP2001 普及组] 数的计算

传送门
小$dp$,我第一遍写居然用$dfs$全遍历了一遍 乐了奥

#include
using namespace std;
int n,ans,dp[1010];
int main(){
    cin>>n;
    dp[1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i>>1;j++)dp[i]+=dp[j];
        dp[i]+=1;
    }
    cout<<dp[n]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12

P1036 [NOIP2002 普及组] 选数

传送门
这回是$dfs$了

#include
using namespace std;
bool check(int x){
    if(x==1)return false;
    for(int i=2;i*i<=x;i++)if(x%i==0)return false;
    return true;
}
int n,k,ans,a[50];
void dfs(int depth, int now, int sum){
    if(depth>=n&&now==k){if(check(sum))ans++;return ;}
    if(depth>n)return ;
    dfs(depth+1,now,sum);
    dfs(depth+1,now+1,sum+a[depth]);
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    dfs(1,0,0);
    cout<<ans<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

P1464 Function

传送门
$tmd$臭水题 我把前两个条件看成并了 改了一堆 不用管什么$1LL$了 不写应该也能过
有个思路就是把$0-20$的存一遍 省着一直递归浪费时间

#include
#define ll long long
using namespace std;
ll sqr[30][30][30];
ll w(ll a, ll b, ll c){
    if(a<=0||b<=0||c<=0)return 1LL;
    else if(a>20||b>20||c>20)return w(20,20,20);
    else if(a>0&&b>0&&c>0){
        if(sqr[a][b][c])return sqr[a][b][c];
        else{
            if(a<b&&b<c)return sqr[a][b][c]=w(a,b,c-1LL)+w(a,b-1LL,c-1LL)-w(a,b-1LL,c);
            else return sqr[a][b][c]=w(a-1LL,b,c)+w(a-1LL,b-1LL,c)+w(a-1LL,b,c-1LL)-w(a-1LL,b-1LL,c-1LL);
        }
    }
    else{
        if(a<b&&b<c)return w(a,b,c-1LL)+w(a,b-1LL,c-1LL)-w(a,b-1LL,c);
        else return w(a-1LL,b,c)+w(a-1LL,b-1LL,c)+w(a-1LL,b,c-1LL)-w(a-1LL,b-1LL,c-1LL);
    }
}
ll x,y,z;
int main(){
    while(1){
        scanf("%lld%lld%lld",&x,&y,&z);
        if(x==-1LL&&y==-1LL&&z==-1LL)break;
        printf("w(%lld, %lld, %lld) = %lld\n",x,y,z,w(x,y,z));
    }
}
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

P5534 【XR-3】等差数列

传送门
这什么玩意

#include
using namespace std;
long long ans,a,b,d,n,an;
int main(){
    cin>>a>>b>>n;
    d=b-a;an=a+(n-1)*d;
    ans=(a+an)*n/2;
    cout<<ans<<endl;
}
1
2
3
4
5
6
7
8
9

P1192 台阶问题

传送门
小$dp$ 方程式思路很简单 考虑上的最后一步 假设最后一步走了$j,$那么最后一步之前走的方式就有$dp[n-j]$种情况 也就是最后一步走$j$步有$dp[n-j]$种方式 所以遍历最后一步 然后相加即可
方程式： d p [ i ] = { ∑ j = i − k i d p [ j ] i > k ∑ j = 0 i d p [ j ] i ≤ k dp[i]= {i∑j=i−kdp[j]i>ki∑j=0dp[j]i≤k

dp[i]=⎩ ⎨ ⎧​j=i−k∑i​dp[j]j=0∑i​dp[j]​i>ki≤k​
$($主要试试$markdown$打公式 熟悉熟悉 都忘没了

#include
using namespace std;
#define N int(1e5+10)
const int mod=100003;
int n,k,dp[N];
int main(){
    cin>>n>>k;
    dp[0]=dp[1]=1;
    for(int i=2;i<=n;i++)
        for(int j=i>k?i-k:0;j<i;j++)(dp[i]+=dp[j])%=mod;
    cout<<dp[n]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12

P1025 [NOIP2001 提高组] 数的划分

传送门
先写了个$dfs$ 居然直接过了
思路就是记录最小的划分、目前已经划分的个数、所有划分的和，然后往上枚举 我做完看了一眼题解 说不加$i\ast (k-depth)+num\le n$会超时，没注意 直接加上了 随手剪枝的好习惯hhh

#include
using namespace std;
int n,k,ans;
void dfs(int num, int depth, int minnum){
    if(depth>=k){
        if(depth==k&&num==n)ans++;
        return ;
    }
    for(int i=minnum;num+i*(k-depth)<=n;i++)dfs(num+i,depth+1,i);
}
int main(){
    cin>>n>>k;
    dfs(0,0,1);
    cout<<ans<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

还是写个$dp$练练手吧 刷题还是能多练就多练
设$dp[n][k]$为将整数$n$划分成$k$份的方案数
考虑数$i，$最简单的方法就是从$i-1$加个$1$直接变为$i，$因为$1$一定是最小的划分，不用考虑算重
但是这样就把划分的方案限定到一定划分出$1$的情况了
那么再考虑没有$1$的情况
只需要把已经划分的数每个都加$1,$那就一定没有$1$了
方程式： d p [ i ] [ j ] = { 0 , i < j 1 , i = j d p [ i − 1 ] [ j − 1 ] + d p [ i − j ] [ j ] , i > j dp[i][j]= {0,i<j1,i=jdp[i−1][j−1]+dp[i−j][j],i>j

dp[i][j]=⎩ ⎨ ⎧​01dp[i−1][j−1]+dp[i−j][j]​,i<j,i=j,i>j​

#include
using namespace std;
int n,k,dp[220][10];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)dp[i][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=2;j<=k;j++){
            if(i<j)break;
            if(i==j)dp[i][j]=1;
            else dp[i][j]=dp[i-1][j-1]+dp[i-j][j];
        }
    }
    cout<<dp[n][k]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

P4994 终于结束的起点

传送门
这 没想到这么简单啊 就直接循环就完事了？

#include
using namespace std;
int M,i=2,a=0,b=1,c=1,d;
int main(){
    cin>>M;
    while(1){
        a%=M,b%=M,d=(b+c)%M;
        a=b,b=c,c=d;
        i++;
        if(b==0&&c==1)break;
    }
    cout<<i-1<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

总结

做完了洛谷题单入门阶段练练手 中间因为一直出去玩 没空出时间好好做题 现在已经开学了还是多多找回之前的手感 准备一下看看有没有机会打打$acm$

最后这道题的题目背景真的好戳我 虽然一直跟别人开玩笑说自己没在役过 不算退役 但是自己心里还是很在乎的，把自己的热爱和时间奉献给了自己喜欢的$oi,$换来的只是教练的一句“你不适合学竞赛”，真的好伤人 希望学弟学妹不要被这一句话导致的失败耽误了学业
话说我是不是已经算是洛谷大龄用户了 有没有啥给大学生用的网站啊哈哈哈