[C++知识库]22.01.15

本来七点吃完饭在找博客写总结

结果到八点看见消息发现周测已经开了，裂开

说实话考试的时候没看到最简单的B题……

目录

B素数判断

C动归

D快速幂

H优先队列

B素数判断

题意是 取一个数字 将除了最后一位翻转 加到该数字后面

注意加完后n会超出int? 用long long就行

#include<iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<string.h>
#include<cstring>
#include<cmath>
using namespace std;
//int n,k;


int main()
{
    long long n;
    cin>>n;
    long long t=n/10;
    while(t)
    {
        n=n*10+t%10;
        t/=10;
    }
    t=sqrt(n);
    int f=1;
    for(long long i=2;i<=t;i++)
    {
        if(n%i==0)
        {
            f=0;
            break;
        }
    }
    if(f)
        cout<<"prime"<<endl;
    else
        cout<<"noprime"<<endl;


	return 0;
}

C动归

这题一看就是动态规划

示例1

输入
7 5
10 3 4 2 2 9 8
输出
6

数据范围都在int 内

状态转移方程

minn=max(minn,j-i);

#include<iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<string.h>
#include<cstring>

#define MAX 0x3f3f3f3f

using namespace std;
long long sum[100010];
//和

int main()
{
    //priority_queue<int,vector<int>,greater<int>> a;//升序
    ios::sync_with_stdio(false);
    int n;
    int k;
    cin>>n>>k;
    sum[0]=0;
    int i,j;

    for( i=1;i<=n;i++)
    {
        int temp;
        cin>>temp;
        sum[i]=temp%k+sum[i-1];
    }
    int minn=0;
    for(i=0;i<n;i++)
    {
        for(j=i+minn;j<=n;j++)
        {
            if(sum[j]%k-sum[i]%k==0)
                minn=max(minn,j-i);
        }
    }
    cout<<minn;

    return 0;
}

D快速幂

没想到栽在快速幂这里了

当时不会写一直在死磕

现在还没写出来，还是超时（最后补上去）

快速幂模板先总结在这

int power(int a,long long b)
{
    long long sum=1;
    while(b)
    {
        if(b&1)
            sum=(sum*a)%mod;

        a=(a*a)%mod;
        b>>=1;
    }
    return sum;
}

H优先队列

?

看清题目就知道应该要用优先队列

升序排列，队头为最小

#include<iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<string.h>
#include<cstring>

#define MAX 0x3f3f3f3f

using namespace std;

stack<string>mystack;

//string a;
int main()
{
    priority_queue<int,vector<int>,greater<int>> a;//升序
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    unsigned long long sum=0;
    for(int i=0;i<n;i++)
    {
        int temp;
        cin>>temp;
        a.push(temp);
    }
    while(a.size()>=2)
    {
        //if(a.size()<=2)
            //break;
        int sum1=a.top();
        a.pop();
        int sum2=a.top();
        a.pop();
        sum+=sum1+sum2;
        a.push(sum1+sum2);
        
    }

    cout<<sum;
    return 0;
}

?