牛客算法入门课练习题单

华华教月月做数学

https://ac.nowcoder.com/acm/problem/23046 https://ac.nowcoder.com/acm/problem/24636

链接：https://ac.nowcoder.com/acm/problem/23046
题目描述
找到了心仪的小姐姐月月后，华华很高兴的和她聊着天。然而月月的作业很多，不能继续陪华华聊天了。华华为了尽快和月月继续聊天，就提出帮她做一部分作业。月月的其中一项作业是：给定正整数A、B、P，求ABmod PA^B\mod PABmodP的值。华华觉得这实在是毫无意义，所以决定写一个程序来做。但是华华并不会写程序，所以这个任务就交给你了。因为月月的作业很多，所以有T组询问。

输入描述:
第一行一个正整数T表示测试数据组数。
接下来T行，每行三个正整数A、B、P，含义如上文。

输出描述:
输出T行，每行一个非负整数表示答案。

示例
输入
2
2 5 10
57284938291657 827493857294857 384729583748273
输出
2
18924650048745

解析：很明显要用矩阵快速幂来求解，但是数据的范围达到了18次方了，只用矩阵快速幂会爆long long，而在做快速幂相乘时可以再对数据进行取模，比如ab可以写成a个b相乘，然后可以时1b

2b + 4b......在这个过程中可以取模免得溢出。

#include 
#include 
#include 
#include 
#include 
#include 
#define mod 1000000007
#define LL long long
using namespace std;
LL p;
LL mpow(LL res,LL ans)
{
LL t = 0;
while(ans){
if(ans & 1){
t = (t + res) % p;
}
res = (res + res) % p;
ans >>= 1;
}
return t;
}
LL mypow(LL A, LL B)
{
LL res = 1, ans = A;
while(B){
if(B & 1)
res = mpow(res,ans);
ans = mpow(ans,ans);
B >>= 1;
}
return res;
}
int main()
{
int T;
cin >> T;
while(T--){
LL A,B;
cin >> A >> B >> p;
LL ans = mypow(A,B);
cout << ans % p << endl;
}
return 0;
}

值周离散化+差分

https://ac.nowcoder.com/acm/problem/24636

#include <bits/stdc++.h>
#include <iostream>
const int Max = 1e6+5;
#define LL long long
const int inx = INT_MAX; 
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
//    srand(time(NULL));
//        m = rand() % 1000 + 1;

//交换元素 

typedef struct ss{
    int pos,num;
}ss;

ss s[2 * Max + 5];

bool cmp(ss a,ss b){
    return a.pos < b.pos;
}

int main(){
    int L,M,l,r,i;
    scanf("%d%d",&L,&M);
    for(i = 1; i <= M; i++){
        scanf("%d%d",&l,&r);
        s[2 * i - 1].pos = l;
        s[2 * i - 1].num = 1;
        s[2 * i].pos = r + 1;
        s[2 * i].num = -1;
    }
    sort(s + 1,s + 2*M + 1,cmp); 
    int ans = 0,temp = 0;
    for(i = 1; i <= M * 2; i++){
        temp += s[i].num;
        if(temp == 1 && s[i].num == 1){
            ans += s[i].pos - s[i - 1].pos;
        }
    }
    ans += L - s[2 * M].pos + 1;
    printf("%d",ans);
    return 0;
}

奇妙的拆分

https://ac.nowcoder.com/acm/problem/14709

因为这道题的因子不能够重复，所以选取的因子i*i<n才能够满足，所以可以直接枚举到根号n即可。

#include <bits/stdc++.h>
#include <iostream>
const int Max = 1e6+5;
#define LL long long
const int inx = INT_MAX; 
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
//    srand(time(NULL));
//        m = rand() % 1000 + 1;

int main()
{
    int T,n,i,ans = 0,temp;
    cin >> T;
    while(T--){
        cin >> n;
        temp = n;
        ans = 0;
        for(i = 1; i <= sqrt(n) + 2; i++){
            if(temp % i == 0 && temp / i > i){
                ans++;
                temp /= i;
            }
            else if(temp / i <= i){
                ans++;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

切长条：贪心区间选点

https://ac.nowcoder.com/acm/problem/25136

思路：该题相当于问你最少选几个点可以让这些点在区间内能找到，所以先按区间右端点从小到大排序，每次选区间右端点的值去与下一个区间的左端点值比较，这样可以保证这个区间覆盖到下一个区间，如果相同则按左端点从小到大排序。

#include <bits/stdc++.h>
#include <iostream>
const int Max = 1e6+5;
#define LL long long
const int inx = INT_MAX; 
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
//    srand(time(NULL));
//        m = rand() % 1000 + 1;

//交换元素 

typedef struct ss{
    int x,y;
}ss;

bool cmp(ss a,ss b)
{
    if(a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

int main()
{
    int N,a,L,i,ans = 0;
    cin >> N;
    ss s[32005];
    for(i = 1; i <= N; i++){
        cin >> s[i].x >> L;
        s[i].y = s[i].x + L;
    }    
    sort(s + 1,s + N + 1,cmp);
    int last = s[0].y;
    for(i = 1; i <= N; i++){
        if(s[i].x >= last){
            ans++;
            last = s[i].y;
        }
    }
    cout << ans;
    return 0;
}

合并果子：堆

https://ac.nowcoder.com/acm/problem/16663

思路：因为要求最少花费的力气，所以每次去合并所有堆中果子数量最少的堆。先把所有的堆合并成一个小根堆，然后每次合并的时候都是去这个小根堆的根，合并后再加入堆中即可得到答案。

#include <bits/stdc++.h>
#include <iostream>
const int Max = 1e6+5;
#define LL long long
const int inx = INT_MAX; 
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
//    srand(time(NULL));
//        m = rand() % 1000 + 1;

//定义i i(A) i+n i+n(B) i+n+n i+n+n(C) 
int t = 0;
int a[10005];
void Insert(int x)
{
    t++;
    int i,j;
    a[t] = x;
    i = t;
    j = i / 2;
    while(j > 0 && a[i] < a[j]){
        swap(a[i],a[j]);
        i = j;
        j = i / 2;
    }
}

int Pop(){
    int i,j,temp;
    temp = a[1];
    a[1] = a[t];
    t--;
    i = 1;
    j = i * 2;
    if(j + 1 <= t && a[j] > a[j + 1]) j++;
    while(j <= t && a[j] < a[i]){
        swap(a[i],a[j]);
        i = j;
        j = i * 2;
        if(j + 1 <= t && a[j] > a[j + 1]) j++;
    }
    return temp;
}

int main()
{
    int n,i,x,ans = 0;
    cin >> n;
    for(i = 1; i <= n; i++){
        cin >> x;
        Insert(x);
    }
    while(t >= 2){
        int a = Pop();
        int b = Pop();
        ans += a + b;
        Insert(a + b);
    }
    cout << ans;
    return 0;
}