周末总结4(基础常用知识)

wuchangjian2021-11-08 01:22:17编程学习

周末总结

  • 字符串操作
    • P5015 [NOIP2018 普及组] 标题统计
    • P1055 [NOIP2008 普及组] ISBN 号码
    • P1308 NOIP2011 普及组 统计单词数
    • P2010 [NOIP2016 普及组] 回文日期
    • P1012 [NOIP1998 提高组] 拼数
    • P5587 打字练习
  • 函数,递归及递推
    • P1028 [NOIP2001 普及组] 数的计算
    • P1036 [NOIP2002 普及组] 选数
    • P1464 Function
    • P5534 【XR-3】等差数列
    • P1192 台阶问题
    • P1025 [NOIP2001 提高组] 数的划分
    • P4994 终于结束的起点

这周做题也不多,没有一周我自己是满意的,没有那种知识的充实感,感觉是被任务推着走,计划好周末两天刷题加整理晚上写作业,但真的不如提前去做好。周日临时加了两篇思想汇报,一篇申情书,就很无语,希望接下来这周我再高效一点。下面我来整理一下这周做的一些基础题,不瞒大家说这些题整理完我还收获挺多的太菜啦

博客的题目看起来多,但都是一些容易理解的简单题,一些思路和实现相对比较重要些

字符串操作

P5015 [NOIP2018 普及组] 标题统计

题目
1.getline(cin,x)的使用

题意:计算除空格和换行符以外的字符数
输入:
234
输出:
3
输入:
Ca 45
输出:
4

#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
    getline(cin,s);
    int l=s.length();
    int ans=l;
    for(int i=0;i<l;i++)
    {
        if(s[i]==' ')
        {
            ans--;
        }
    }
    cout<<ans<<endl;
    return 0;
}

P1055 [NOIP2008 普及组] ISBN 号码

题目

1.注意整型和字符的转化
2.学习优化后的代码实现方式:将余数放在数组中,利用了下标和余数相等

计算规则:见题

输入:0-670-82162-4
输出:Right
输入:0-670-82162-0
输出:0-670-82162-4

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int j=1;
    int sum=0;
    int num=1;
    int ans=0;
    for(int i=0; i<=12; i++)
    {
        if(i==11)
        {
            ans=s[12]-'0';
            break;
        }
        if(s[i]!='-')
        {
            sum+=j*int(s[i]-'0');
            j++;
        }
    }
    sum=sum%11;
    if(sum==ans||(sum==10&&s[12]=='X')) cout<<"Right"<<endl;
    else
    {
        for(int i=0; i<=11; i++)
        {
            cout<<s[i];
        }
        if(sum==10) cout<<'X'<<endl;
        else   cout<<char('0'+sum)<<endl;
    }
    return 0;
}

优化:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    char a[14];
    char mod[12]="0123456789X";
    cin>>a;//输入字符串
    int i,j=1,sum=0;
    for(i=0; i<12; i++)
    {
        if(a[i]=='-') continue;
        sum+=(a[i]-'0')*j++;
    }
    if(mod[sum%11]==a[12]) cout<<"Right"<<endl;
    else
    {
        a[12]=mod[sum%11];
        cout<<a<<endl;
    }
  //  cout<<endl;
return 0;
}

P1308 NOIP2011 普及组 统计单词数

题目

C++ string 的使用
1.字符匹配:b.find(a)!=string::npos
2.转化大小写: b[i]=tolower(b[i]);

(详细使用见代码)

题意:
输入一个单词,和一行文章,输出出现该单词的个数和第一次出现的位置
没有该单词则输出 -1
分析:首先都将其转化为小写;查找有过没找到返回-1,如果找到了返回保留初始下标,并继续遍历计算总个数;(主要是函数的运用)
输入:
To
to be or not to be is a question
输出:
2 0

输入:
to
Did the Ottoman Empire lose its power at that time
输出:
-1

虽然这个代码还没过,40 scores
但我不打算晚上调它了(我就是个小拉吉)

#include <bits/stdc++.h>
using namespace std;
//知识点:
//字符匹配
//转化大小写
int main()
{
    string a,b;
    getline(cin,a);
    getline(cin,b);
    a=' '+a+' ';
    b=' '+b+' ';
    for(int i=0;i<b.length();i++)
    {
        a[i]=tolower(a[i]);
    }
    for(int i=0;i<b.length();i++)
    {
        b[i]=tolower(b[i]);
    }
    //转化成小写
    //寻找字符串a是否包含子串b
    //string::npos用来表示不存在的位置
    if(b.find(a)==string::npos)
    {
        cout<<-1<<endl;
    }//没有找到
    else
    {
        int chushi=b.find(a);//初始下标
        int n=b.find(a),sum=0;
        while(n!=string::npos)
        {
            ++sum;
            n=b.find(a,n+1);//从下一个位置开始查找
        }
        cout<<sum<<" "<<chushi<<endl;
    }
return 0;
}

P2010 [NOIP2016 普及组] 回文日期

题目

一个优化的题解肯定是思考了很久的,所以不必抱怨,还是再多练一点,积累一些思路
题意:
找两个日期间的回文串
分析:
直接简单粗暴遍历判断肯定超时,简直太狠啦,
该题解的思路:就是利用回文串前后串的对称,计算出十二个月对应的所有的回文串(因为月份和日期都已经确定所以回文串也将是唯一的),之后判断算出的回文串是否在该题目给定的两个年份之间的。

#include <iostream>

using namespace std;

int s[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
//0229  倒过来9220 是闰年
int main()
{
    int n,m,c,sum=0;
    int ans=0;
    cin>>n>>m;
    for(int i=0;i<=12;i++)//枚举月和日
    {
        for(int j=1;j<=s[i];j++)
        {
            c=(j%10)*1000+
            (j/10*100)+
            (i%10*10)+
            (i/10);//算出前四位
            sum=c*10000+i*100+j;//算出整个日期
            if(sum<n||sum>m) continue;
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

P1012 [NOIP1998 提高组] 拼数

题目
题意:
拼数,组成最大的数多多少少有点不会
分析:
一开始想到,拼数先比较最高位再比较较低位置,然而没有想到,其中一个截止了将比较它和另一数的最高位,看他们谁可以放在前面,举个例子理解这种情况32要优先321要靠前放,因为32321>32132,但我们一般常见的字符串比较会认为321>32的,所以将这种情况要考虑哟~

低级一点俗称详细一点的代码:

#include <iostream>
#define ll long long
using namespace std;
int t;
const int N=1e9;
bool cmp(int x,int y)
{
    return x>y;
}
//这个我在考虑存储数字的问题
//然而
string a[30];
//使用string存储更方便(可以直接比较大小)
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n;i++)//排序
    {
        for(int j=i+1;j<=n;j++)
        {
            if(a[j]+a[i]>a[i]+a[j])
            {
                swap(a[j],a[i]);
                /*
                举个例子 12,34
                1234<3412
                12和34 需要交换一下
                */
            }
        }
    }//排序结束
    //因为数据的个数少所以可以尝试着写双重循环,熟悉一下原理
    for(int i=0;i<=n;i++)
    {
        cout<<a[i];
    }
    return 0;
}

注意比较函数cmp()的定义,巧妙一些:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int t;
const int N=1e9;
bool cmp(string a,string b)
{
    return a+b>b+a;
}
//如果 return a>b
//会出现 321>32 的情况
string a[30];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++)
    {
        cout<<a[i];
    }
    return 0;
}

P5587 打字练习

题目

中文题目,题意也很好理解,就不再赘述

分析:
1.捕获n行文章,用getline(cin,s),并计数
2.不要忘记原文中还要考虑‘<’这个符号,就离谱
3.删除是的计数问题,考虑到‘<’这个符号在开头,就删除一个它本身,如果不在开头(开始的第一的位置),这种情况j-1>=0,就删除它本身和前一个元素,因为最后输入的要和原文比较嘛,所以有个退格"<"就将前一个元素删除。
4.精确度的处理,遇到这种要求时 《请你计算出他的 KPM(Keys per minutes,每分钟输入的字符个数),答案四舍五入保留整数部分。》

看下面:

    //精确度的处理
    double k=sum;
    k=k*60/t;
    sum=k;//sum是int类型
    if(k-sum>0.5) sum++;//进一
    cout<<sum<<endl;
    return 0;

完整dama:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e3+10;

int main()
{
    string s[N];
    string ss[N];

    int ii=0,jj=0;
    getline(cin,(s[ii]));
    while(s[ii]!="EOF")
    {
        ii++;
        getline(cin,(s[ii]));
    }
    getline(cin,(ss[jj]));
    while(ss[jj]!="EOF")
    {
        jj++;
        getline(cin,(ss[jj]));
    }
    int t;
    cin>>t;
    int sum=0;
    for(int i=0; i<ii; i++)
    {
        for(int j=0; j<s[i].length(); j++)
            if(s[i][j]=='<')
                if(j-1>=0)
                {
                    s[i].erase(j,1);
                    s[i].erase(j-1,1),j-=2;
                }
                else  s[i].erase(j,1),j--;
    }
    for(int i=0; i<ii; i++)
    {
        for(int j=0; j<ss[i].length(); j++)
            if(ss[i][j]=='<')
                if(j-1>=0)
                {
                    ss[i].erase(j,1);
                    ss[i].erase(j-1,1),j-=2;
                }
                else  ss[i].erase(j,1),j--;
    }
//    for(int i=0; i<ii; i++)
//    {
//        cout<<ss[i]<<endl;
//    }
    for(int i=0;i<min(ii,jj);i++)
    {
        for(int j=0;j<min(s[i].length(),ss[i].length());j++)
        {
            if(s[i][j]==ss[i][j])
                sum++;
        }
    }
    //精确度的处理,没有精度处理只有10分
    double k=sum;
    k=k*60/t;
    sum=k;
    if(k-sum>0.5) sum++;
    cout<<sum<<endl;
    return 0;
}

函数,递归及递推

P1028 [NOIP2001 普及组] 数的计算

题目
题意:
给一个数n,在该数前面加一个不超过最前面那个数字的一半的数,直到不能加任何数,问有多少个满足该题意的数字。
6的话,是6,16,26,126,36,136六种,输出6
分析:
写一写找规律,简单的说一下,6的种数f[6]是1的种数f[1]+2的种数f[2]+3的种数f[3]

#include <bits/stdc++.h>
using namespace std;
const int N=1000;

int f[N];;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i/2;j++)
        {
            f[i]=f[i]+f[j];
        }
        f[i]++;
    }
//    for(int i=1;i<=n;i++)
//    {
//        cout<<f[i]<<" ";
//    }
    cout<<f[n]<<endl;
    return 0;
}

P1036 [NOIP2002 普及组] 选数

題目

题意:
在n个数中选k个数相加和为素数的情况,输出有几种情况
分析:
重点是dfs()函数。可看代码详解,对于递归不熟可以纸上模拟一次
一次不行就两次

#include <bits/stdc++.h>
using namespace std;
bool prime(int n)
{
    for(int i=2;i*i<=n;i++)
        if(n%i==0)
            return false;
        return true;
}
int n,k;
long long ans;
int a[25];
//start可以保正是升序,因為排列中可能會存在重複,这样一来就去重啦
void dfs(int m,int sum,int start)//我们为了在n个数中找k个数字相加
{
    if(m==k)//k个数达到了要求,如果是素数的话就计数不是素数就return结束
    {
        if(prime(sum))
            ans++;
        return ;
    }
    for(int i=start;i<n;i++)
    {
        dfs(m+1,sum+a[i],i+1);//i+1是保证不重复之前的数
    }
    return ;
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    dfs(0,0,0);
    cout<<ans<<endl;
    return 0;
}

P1464 Function

题目

爆啦

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll w(ll a,ll b,ll c)
{
    if(a<=0||b<=0||c<=0) return 1;
    else if(a>20||b>20||c>20) return w(20,20,20);
    else if(a<b&&b<c) return w(a,b,c-1)+w(a,b-1,c-1)+w(a,b-1,c);
    else return w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
}
int main()
{
    ll a,b,c,ans;
    while(cin>>a>>b>>c)
    {
        if(a==-1&&b==-1&&c==-1) break;
        ans=w(a,b,c);
    cout<<"w("<<a<<","<<b<<","<<c<<")="<<ans<<endl;
    }
    return 0;
}

AC

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll h[40][40][40];
ll w(ll a,ll b,ll c)
{
    if(a<=20&&b<=20&&c<=20&&a>=0&&b>=0&&c>=0)if(h[a][b][c]) return h[a][b][c];
    if(a<=0||b<=0||c<=0) return 1;
    if(a>20||b>20||c>20) return w(20,20,20);
    if(a<b&&b<c) return h[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    return h[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
}
int main()
{
    ll a,b,c,ans;
    while(cin>>a>>b>>c)
    {
        if(a==-1&&b==-1&&c==-1) break;
    //printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,w(a,b,c));
    cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<w(a,b,c)<<endl;
    }
    return 0;
}

P5534 【XR-3】等差数列

题意
这个就不说了

P1192 台阶问题

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//有两种方法第一种是简单的找规律
//第二种Dp计算
const int N=1e5+10;
const int mod=100003;
int d[N];
int main()
{
    int n,k;
    cin>>n>>k;
    d[0]=1;
    d[1]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(i>=j)
            d[i]=(d[i-j]+d[i])%mod;
        }
    }
    //服了服了完全不明白了
    cout<<(d[n]+mod)%mod<<endl;
    return 0;
}

P1025 [NOIP2001 提高组] 数的划分

我喜欢这个题

#include <iostream>

using namespace std;

int dp[205][10];
int main()
{
    int n,k;
    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++)
        {
            //else if(i==j) dp[i][j]=1;
            if(i>=j) dp[i][j]=dp[i-1][j-1]+dp[i-j][j];
            else dp[i][j]=0;
        }
       // for(int i=1; i<=n; i++)
       //for(int j=1; j<=k; j++)
       //  cout<<dp[i][j]<<" ";
          cout<<dp[n][k]<<endl;
    return 0;
}
#include <iostream>

using namespace std;

//搜索无非也是个递归的过程,纯纯学习别人家的代码

int n,k;
int dfs(int n,int p,int ii)//分别代表着待分配的数,分的部分数和当下要选出的数
{
    if(p==1) return 1;//直到p==1,退出递归
    int sum=0;//仔细想想为什么一定在函数内初始化呢,因为这里是递归呀,有return,其实已经保留了
    for(int i=ii;i<=n/p;i++)//剪枝,因为枚举到n会有重复的情况
    {
        sum+=dfs(n-i,p-1,i);//这个很容易懂
    }
    return sum;
}
int main()
{
    cin>>n>>k;
    cout<<dfs(n,k,1)<<endl;
    return 0;
}

P4994 终于结束的起点

未完,11.9周一晚更新

相关文章

如何让类不能被继承

方法一:借助 final 关键字,用该关键字修饰的类不能被继...

“21天好习惯”第一期-5

john带上小狗Tommy去见女友Mary,他们同时出发相向而行。Tomm...

云计算提供商锁定的影响以及解决方案

问题 云计算提供厂商锁定是不能完全消除的,如果云计算提供商锁定将会产生很...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。