[数据结构与算法]小肥杨训练营——快速幂模板

P1897 电梯里的爱情

题目链接：https://www.luogu.com.cn/problem/P1897

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string>

using namespace std;

int a[100001];

/*
下一个人1s：+ns
每向上运行一层需要 6 秒钟：+h层*6
向下运行一层需要 4 秒钟：+h层*4
每开门一次需要 5 秒：+you层*5
*/

int main()
{
	int n,h,you=0,sum=0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a + n);  

	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		if (a[i]==a[i+1])
		{
			continue;
		}
		else
		{
			you++;
		}
	}

	sum = n + a[n - 1] * 10 + you * 5;
	cout << sum;
	return 0;
}

P1428 小鱼比可爱

题目链接：https://www.luogu.com.cn/problem/P1428

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string>

using namespace std;

int a[101], b[101];
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; j >= 0; j--)
		{
			if (a[j] < a[i])
				b[i]++;
		}
	}
		
	for (int i = 0; i < n-1; i++) 
		cout << b[i] << " ";
	cout << b[n-1];	
		
	return 0;
}

P2676 [USACO07DEC]Bookshelf B

题目链接：https://www.luogu.com.cn/problem/P2676

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string>

using namespace std;

int h[20000];
int main()
{
	int n,b,cnt=0;
	cin >> n>>b;
	for (int i = 0; i < n; i++)
	{
		cin >> h[i];
	}
	sort(h,h+n);
	
	int stmp = 0;
	for (int i = n-1; i > 0; i--)
	{
		stmp += h[i];
		cnt++;
		if (stmp>b)
		{
			break;
		}
	}
	cout << cnt;
	return 0;
}

P4414 [COCI2006-2007#2] ABC

题目链接：https://www.luogu.com.cn/problem/P4414

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string>

using namespace std;

int a[3];
char c[3];
int main()
{
	cin >> a[0] >> a[1] >> a[2];
	cin >> c[0] >> c[1] >> c[2];
	sort(a, a + 3);
	cout << a[c[0] - 'A'] << " " << a[c[1] - 'A'] << " " << a[c[2] - 'A'];
	return 0;
}

P2637 第一次，第二次，成交

题目链接：https://www.luogu.com.cn/problem/P2637

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string>

using namespace std;

int pr[1001];
int main()
{
	int m, n,price=0,max=0;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> pr[i];
	}
	sort(pr,pr+n);
	for (int i = n-1; i > 0; i--)
	{
		if ((n-i)*pr[i]>max)
		{
			max = (n - i)*pr[i];
			price = pr[i];
		}
	}
	cout << price << " " << max;

	return 0;
}

P1226 【模板】快速幂||取余运算

题目链接：https://www.luogu.com.cn/problem/P1226

快速幂函数模板

ll fast_power(ll a, ll b, ll c)
{
	ll ans = 1;
	a %= c;
	while (b)
	{
		// b 指数是奇数
		if (b & 1)
		{
			ans = (ans * a) % c;	// 指数加1
		}
		a = (a * a) % c;
		b >>= 1;
	}

	return ans;
}

快速幂函数模板原理

看这个视频自学，整理算法没劲，懒得再写了：https://www.bilibili.com/video/BV12r4y1w7tx

视频中代码：

// 降幂
ll fast_power(ll a,ll b, ll c)
{
	ll ans = 1;
	while (b)
	{
		// b 指数是奇数
		if (b%2==1)
		{
			ans = ans*a;	// 指数加1
			a = a * a;
			b / 2;
		}
		else	// b是偶数
		{
			a = a * a;;
			b / 2;
		}
	}

	return ans;
}

// 对每一步都取余
ll fast_power(ll a, ll b, ll c)
{
	ll ans = 1;

	while (b)
	{
		// b 指数是奇数
		if (b % 2 == 1)
		{
			ans = (ans * a)%c;	// 指数加1
		}
		a = (a * a)%c;
		b / 2;
	}

	return ans;
}

// 最终
ll fast_power(ll a, ll b, ll c)
{
	ll ans = 1;
	a %= c;
	while (b)
	{
		// b 指数是奇数
		if (b & 1)
		{
			ans = (ans * a) % c;	// 指数加1
		}
		a = (a * a) % c;
		b >>= 1;
	}

	return ans;
}