题目描述

题的目标很简单，就是求两个正整数A和B的和，其中A和B都在区间[1,1000]。稍微有点麻烦的是，输入并不保证是两个正整数。

输入说明

输入在一行给出A和B，其间以空格分开。问题是A和B不一定是满足要求的正整数，有时候可能是超出范围的数字、负数、带小数点的实数、甚至是一堆乱码。

注意：我们把输入中出现的第1个空格认为是A和B的分隔。题目保证至少存在一个空格，并且B不是一个空字符串。

输出说明

如果输入的确是两个正整数，则按格式A + B = 和输出。如果某个输入不合要求，则在相应位置输出?，显然此时和也是?。

输入样例1

123 456

输出样例1

123 + 456 = 579

输入样例2

22. 18

输出样例2

? + 18 = ?

输入样例3

-100 blabla bla...33

输出样例3

? + ? = ?

分析

这道题需要注意的是输入的整数大小需要介于[1,1000]之间，如果不满足则输出”?”，其次需要注意B中可能出现空格，比如样例123 3 4字符串A为”123”,B为”3 4”，所以为了能够存储B的全部内容，使用getline(cin,b)。
输出的时候按照每一项的判断进行。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n1,n2;
bool f1=true,f2=true,f3=true,f4=true;
int main()
{
    string a,b;
    cin>>a;
    getchar();  //抵消空格
    getline(cin,b); //b中可能包含空格，所以用getline进行输入
    for(int i=0;i<a.size();i++)
    {
        if(a[i]>='0' && a[i]<='9')
        {
            n1=10*n1+(a[i]-'0');
        }
        else{
            f1=false;   //含有非法字符，f1=false
            break;
        }
    }
    for(int i=0;i<b.size();i++)
    {
        if(b[i]>='0' && b[i]<='9')
        {
            n2=10*n2+(b[i]-'0');
        }
        else{
            f2=false;
            break;
        }
    }
    if(n1>1000 || n1<1) f3=false;
    if(n2>1000 || n2<1) f4=false;
    if(f1 && f3) cout<<n1;
    else cout<<"?";
    cout<<" + ";
    if(f2 && f4) cout<<n2;
    else cout<<"?";
    cout<<" = ";
    if(f1 && f2 && f3 && f4) cout<<n1+n2;
    else cout<<"?";
    return 0;
} 

题目描述

本题的要求很简单，就是求N个数字的和。麻烦的是，这些数字是以有理数分子/分母的形式给出的，你输出的和也必须是有理数的形式。

输入说明

输入第一行给出一个正整数N（≤100）。随后一行按格式a1/b1 a2/b2…给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外，负数的符号一定出现在分子前面。

输出说明

输出上述数字和的最简形式 —— 即将结果写成整数部分分数部分，其中分数部分写成分子/分母，要求分子小于分母，且它们没有公因子。如果结果的整数部分为0，则只输出分数部分。

输入样例1

5
2/5 4/15 1/30 -2/60 8/3

输出样例1

3 1/3

输入样例2

2
4/3 2/3

输出样例2

2

输入样例3

3
1/3 -1/6 1/8

输出样例3

7/24

分析

欧几里得gcd()求出两个分数的分母的最大公约数，然后更新分子的和。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
char c;
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    cin>>n;
    ll a,b,x,y;
    cin>>a>>c>>b;
    for(int i=1;i<n;i++)
    {
        cin>>x>>c>>y;
        int bb=b,yy=y;
        if(b<y)
        {
            int temp=b;
            bb=y;
            yy=temp;
        }
        ll mu=b*y/gcd(bb,yy);
        ll zi=a*(mu/b)+x*(mu/y);
        a=zi,b=mu;
    }
    ll k = gcd(a,b);
    a/=k,b/=k;
    ll q=a/b;
    ll r=a%b;
    if(r==0 && q==0) cout<<"0"<<endl;
    else if(r==0 && q!=0) cout<<q<<endl;
    else if(r!=0 && q!=0) cout<<q<<" "<<r<<"/"<<b<<endl;
    else if(r!=0 && q==0) cout<<r<<"/"<<b<<endl;
    return 0;
} 

一道分解质因数的题目，直接使用867题的模板即可。
https://www.acwing.com/problem/content/869/

C++ 代码

class Solution {
public:
    int primes[1010],cnt[1010],co,ans;
    bool prime(int x)
    {
        for(int i=2;i<=x/i;i++)
        {
            if(x%i==0) return false;
        }
        return true;
    }
    void getprimes(int x)
    {
        for(int i=2;i<=x/i;i++)
        {
            int s=0;
            while(x%i==0)
            {
                x/=i;
                s++;
            }
            ans+=i*s;
        }
        if(x>1)
        {
            ans+=x;
        }
    }
    int minSteps(int n) {
        if(n==1) return 0;
        if(prime(n)) return n;
        getprimes(n);
        return ans;
    }
};

数组排序后找下标即可

python 代码

class Solution(object):
    def smallerNumbersThanCurrent(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        nu=[]
        for item in nums:
            nu.append(item)
        nums.sort()
        ans=[]
        for i in range(len(nums)):
            idx=nums.index(nu[i])
            ans.append(idx)
        return ans

#include<bits/stdc++.h>
using namespace std;

const int N =1010;
char a[N],b[N];
int dp[N][N]; 
int main()
{   
    int n,m;
    scanf("%d%d",&n,&m);
    scanf("%s%s",a+1,b+1);

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            if(a[i]==b[j]) dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1);
        }
    }
    cout<<dp[n][m];
    return 0;
}

闫氏大法好！

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m,dp[N][N];
char a[N],b[N];
int main()
{
    cin>>n>>a+1>>m>>b+1;

    for(int i=0;i<=n;i++) dp[i][0]=i;
    for(int i=0;i<=m;i++) dp[0][i]=i;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
            if(a[i]==b[j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
            else dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
        }
    }

    cout<<dp[n][m];
    return 0;
}

y总方法

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N],dp[N],g[N],cnt,ans;
int main()
{
    int n=1;
    while(cin>>a[n]) n++;
    for(int i=1;i<n;i++)
    {
        dp[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]>=a[i]) dp[i]=max(dp[i],dp[j]+1);
        }
        ans=max(ans,dp[i]);
    }


    for(int i=1;i<n;i++)
    {
        int k=0;
        while(k<cnt && g[k]<a[i]) k++;
        g[k]=a[i];
        if(k>=cnt) cnt++;
    }
    cout<<ans<<endl;
    cout<<cnt<<endl;
    return 0;
}

lower_bound()返回值是一个迭代器,返回指向大于等于key的第一个值的位置
对象：有序数组或容器

lower_bound妙用

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N],dp[N],g[N],cnt,ans;
int main()
{
    int n=1;
    while(cin>>a[n]) n++;
    for(int i=1;i<n;i++)
    {
        dp[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]>=a[i]) dp[i]=max(dp[i],dp[j]+1);
        }
        ans=max(ans,dp[i]);

        int p = lower_bound(g, g+cnt, a[i]) - g;
        if(p == cnt) g[cnt ++] = a[i];  
        else g[p] = a[i];
    }
    cout<<ans<<endl;
    cout<<cnt<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N],dp[N],sum;
int main()
{
    int n; cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++)
    {
        dp[i]=a[i];
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])
            {
                dp[i]=max(dp[i],dp[j]+a[i]);
            }
        }
    }
    for(int i=1;i<=n;i++) sum=max(dp[i],sum);
    cout<<sum;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],q[N],len;
int main()
{
    int n; scanf("%d",&n);

    for(int i=0;i<n;i++) scanf("%d",&a[i]);

    q[0]=-2e9;
    for(int i=0;i<n;i++)
    {
        int l=0,r=len;
        while(l<r)
        {
            int mid = l+r+1 >> 1;
            if(q[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        len=max(r+1,len);
        q[r+1]=a[i];
    }
    cout<<len<<endl;
    return 0;
}

10月24日程序员日打卡成功！！！

经典01背包问题，背模板就完事！

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N =2e4+10;
int w;
int dp[N];
int main()
{
    int n,v; cin>>v>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w;
        for(int j=v;j>=w;j--)
        {
            dp[j]=max(dp[j],dp[j-w]+w); 
        }   
    }
    cout<<v-dp[v]; 
    return 0;
}