T1 乘方

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

typedef long long LL; 

int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	
	LL res = 1;
	while (a > 1 && b -- )
	{
		res *= a;
		if (res > 1e9)
		{
			res = -1;
			break;
		}
	}
	
	printf("%lld\n", res);
	return 0;
} 

T2 奖学金

算法：

(排序,多关键字排序) $O(nlogn)$

多关键字排序即可。

时间复杂度：

这里使用快速排序，时间复杂度是 $O(nlogn)$。

C++ 代码：

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

const int N = 310;

int n;

struct Person
{
	int id, sum, a, b, c;
	// 重载小于号
	bool operator< (const Person &t) const
	{
		if (sum != t.sum) return sum > t.sum;
		if (a != t.a) return a > t.a;
		return id < t.id;
	}
}p[N];

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i ++ )
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		p[i] = {i + 1, a + b + c, a, b, c};
	}
	sort(p, p + n);
	
	for (int i = 0; i < 5; i ++ )
		printf("%d %d\n", p[i].id, p[i].sum);	
	
	return 0;
} 

T3 插入排序

sort(b + 1, b + n + 1, [&](int x, int y) { // 匿名函数 
	if (a[x] != a[y]) return a[x] < a[y];
    return x < y;
});

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

const int N = 8010;

int n, m;
int a[N], b[N], c[N];

bool cmp(int x, int y)
{
	if (a[x] != a[y]) return a[x] < a[y];
	return x < y;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++ )
	{
		scanf("%d", &a[i]);
		b[i] = i; 
	}
	
	sort(b + 1, b + n + 1, cmp);
	
	for (int i = 1; i <= n; i ++ )
		c[b[i]] = i;
	
	while(m -- )
	{
		int t, x, v;
		scanf("%d%d", &t, &x);
		if (t == 1)
		{
			scanf("%d", &v);
			a[x] = v;
			int k = c[x];
			
			while (k > 1 && (a[b[k - 1]] > a[b[k]] || a[b[k - 1]] == a[b[k]] && b[k - 1] > b[k]))
			{
				swap(b[k - 1], b[k]);
				swap(c[b[k - 1]], c[b[k]]);
				k -- ;
			}
			while (k < n && (a[b[k + 1]] < a[b[k]] || a[b[k + 1]] == a[b[k]] && b[k + 1] < b[k]))
			{
				swap(b[k + 1], b[k]);
				swap(c[b[k + 1]], c[b[k]]);
				k ++ ;
			}
		}
		else printf("%d\n", c[x]);
	}
	
	return 0;
} 

T4 火柴棒等式

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

const int cnt[] = {
    6, 2, 5, 5, 4, 5, 6, 3, 7, 6
};

int get(int x)
{
    if (!x) return cnt[0];
    int res = 0;
    while (x) res += cnt[x % 10], x /= 10;
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);

    int res = 0;
    for (int i = 0; i < 1000; i ++ )
        for (int j = 0; j < 1000; j ++ )
            if (get(i) + get(j) + get(i + j) + 4 == n)
                res ++ ;

    printf("%d\n", res);
    return 0;
}

T5 跳石头

算法：

二分，贪心 $O(NlogL)$

如果长度 $Len$ 可以满足，那么当长度小于 $Len$ 时也可以满足，所以我们可以二分出最大的 $Len$。

剩下的问题是如何判断给定 $Len$ 的情况下，能否最多拿走 $M$ 块石头，使得所有相邻两块石头之间的距离不小于 $Len$。

这一步可以贪心来做。从前往后扫描每个石头：

• 如果当前石头和上一块石头的距离小于 $Len$，则当前石头必须拿走，否则最小距离就会小于 $Len$。
• 如果当前石头和上一块石头的距离大于等于 $Len$，则必然存在一个最优解，使得当前石头可以被拿走。证明：如果存在一个最优解跟我们的贪心解留下的石头不同，那么找出第一个不同的石头，我们把最优解中的留下石头换成贪心解中留下的石头，会发现仍然会得到一组合法方案，通过这种方式，可以逐步将最优解调整成贪心解，且留下的石头数不变，所以贪心解就是一组最优解。

扫描结束后判断拿走的石头数量是否小于等于 $M$。

时间复杂度分析：

总共二分 $O(logL)$ 次，每次贪心的计算是 $O(N)$，因此总时间复杂度是 $O(NlogL)$。

C++ 代码：

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

const int N = 50010;

int L, n, m;
int w[N];

bool check(int mid)
{
	int res = 0;
	for (int i = 1, last = 0; i <= n; i ++ )
		if (w[i] - last < mid) res ++ ;
		else last = w[i];
	return res <= m;
}

int main()
{
	scanf("%d%d%d", &L, &n, &m);
	for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
	w[++ n] = L;	
	
	int l = 1, r = L;
	while (l < r)
	{
		int mid = l + r + 1 >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	
	printf("%d\n", r);
	return 0;
} 

T6 动物园

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

typedef unsigned long long ULL; // -2^64 ~ 2^64 - 1

const int N = 64;

int n, m, c, k;
bool has[N]; // 表示每一位有没有被要求过
bool food[N]; // 表示是否买了这一类饲料

int main()
{
	scanf("%d%d%d%d", &n, &m, &c, &k);
	
	ULL state = 0;
	for (int i = 0; i < n; i ++ )
	{
		ULL x;
		scanf("%llu", &x);
		state |= x;
	}
	for (int i = 0; i < m; i ++ )
	{
		int p, q;
		scanf("%d%d", &p, &q);
		has[p] = true;
		if (state >> p & 1) food[p] = true;
	}
	
	int cnt = 0;
	for (int i = 0; i < k; i ++ )
		if (food[i] || !has[i])
			cnt ++ ;
	if (cnt == 64 && !n) puts("18446744073709551616");
	else if (cnt == 64)
	{
		ULL t = -1; // 2^64 - 1
		printf("%llu\n", t - (n - 1));
	}
	else printf("%llu\n", (1ull << cnt) - n);
	
	return 0;
}